Another week, another riddler. This one was fun, even if a bit lackluster. Austin Chen’s problem reads:
You have a playlist with exactly 100 tracks (i.e., songs), numbered 1 to 100. To go to another track, there are two buttons you can press: (1) “Next,” which will take you to the next track in the list or back to song 1 if you are currently on track 100, and (2) “Random,” which will take you to a track chosen uniformly from among the 100 tracks. Pressing “Random” can restart the track you’re already listening to — this will happen 1 percent of the time you press the “Random” button.
For example, if you started on track 73, and you pressed the buttons in the sequence “Random, Next, Random, Random, Next, Next, Random, Next,” you might get the following sequence of track numbers: 73, 30, 31, 67, 12, 13, 14, 89, 90. You always know the number of the track you’re currently listening to.
Your goal is to get to your favorite song (on track 42, of course) with as few button presses as possible. What should your general strategy be? Assuming you start on a random track, what is the average number of button presses you would need to make to reach your favorite song?
This type of problem is fun because you can make a model of it and test it against your brute force case pretty easily. My model was to find a threshold at which you press random — but once your “random” function gets you below the threshold press “next” until you get to the selected song. This model ended up being correct.
Here is how I represented the model with the threshold at 0 (we press random until we hit the exact song we want):
This shows it would take 99 button presses on average. And here it is with a threshold of 1 (if we are one or less away we’ll press next to get to the song):
This shows it would take 49.5 button presses on average. Finally, here is the equation for a generalized threshold, R:
This is minimized when R = 13 for an expected 12.643 button presses.
Fun fact: You can use the equation above to find for different sized playlists by replacing the 100 with your playlist size. For a 10,000 song playlist? It takes a surprisingly low 139.92 presses