Riddler (Find Your Favorite Song) 2019-12-06

1_probability.py

def get_chance_of_better_than_next_on_next_roll(num):
    # this is a sliding scale
    return (42 - num - 1) / 100

def get_prob(num):
    if num == 41:
        return 0
    prob = get_chance_of_better_than_next_on_next_roll(num)
    return prob + ((1 - prob) * get_prob(num +1))

if __name__ == '__main__':
    for x in range(41):
        print(f'The prob of beating Nexting is: {round(get_prob(x), 4)} for starting value of {x}')

2_probability_output.txt

The prob of beating Nexting is: 1.0 for starting value of 0
The prob of beating Nexting is: 0.9999 for starting value of 1
The prob of beating Nexting is: 0.9999 for starting value of 2
The prob of beating Nexting is: 0.9998 for starting value of 3
The prob of beating Nexting is: 0.9997 for starting value of 4
The prob of beating Nexting is: 0.9995 for starting value of 5
The prob of beating Nexting is: 0.9993 for starting value of 6
The prob of beating Nexting is: 0.9989 for starting value of 7
The prob of beating Nexting is: 0.9983 for starting value of 8
The prob of beating Nexting is: 0.9974 for starting value of 9
The prob of beating Nexting is: 0.9962 for starting value of 10
The prob of beating Nexting is: 0.9945 for starting value of 11
The prob of beating Nexting is: 0.9922 for starting value of 12
The prob of beating Nexting is: 0.989 for starting value of 13
The prob of beating Nexting is: 0.9848 for starting value of 14
The prob of beating Nexting is: 0.9791 for starting value of 15
The prob of beating Nexting is: 0.9718 for starting value of 16
The prob of beating Nexting is: 0.9624 for starting value of 17
The prob of beating Nexting is: 0.9505 for starting value of 18
The prob of beating Nexting is: 0.9357 for starting value of 19
The prob of beating Nexting is: 0.9176 for starting value of 20
The prob of beating Nexting is: 0.8957 for starting value of 21
The prob of beating Nexting is: 0.8696 for starting value of 22
The prob of beating Nexting is: 0.839 for starting value of 23
The prob of beating Nexting is: 0.8037 for starting value of 24
The prob of beating Nexting is: 0.7635 for starting value of 25
The prob of beating Nexting is: 0.7184 for starting value of 26
The prob of beating Nexting is: 0.6687 for starting value of 27
The prob of beating Nexting is: 0.6148 for starting value of 28
The prob of beating Nexting is: 0.5572 for starting value of 29
The prob of beating Nexting is: 0.4968 for starting value of 30
The prob of beating Nexting is: 0.4347 for starting value of 31
The prob of beating Nexting is: 0.3718 for starting value of 32
The prob of beating Nexting is: 0.3097 for starting value of 33
The prob of beating Nexting is: 0.2497 for starting value of 34
The prob of beating Nexting is: 0.1932 for starting value of 35
The prob of beating Nexting is: 0.1417 for starting value of 36
The prob of beating Nexting is: 0.0965 for starting value of 37
The prob of beating Nexting is: 0.0589 for starting value of 38
The prob of beating Nexting is: 0.0298 for starting value of 39
The prob of beating Nexting is: 0.01 for starting value of 40

3_Explanation.md

Let's make a few observations:

1. You should never be clicking next and then clicking random. If you are going to click random, you need to do it before you click next.
2. This implies that the general strategy should be to click random until you get "close enough" to click next until you get to 42.

Let's investigate how close is close enough where you can start clicking next.

By using probability.py, we use a recursive function to accurately describe the probability that you will fare better by clicking Random, instead of clicking next every time. This formula was reasoned out by the following intuition (loosely based on my memory of an inductive proof):

• If your starting number is 42, you obviously are finished, and never should click random
• If your starting number is 41, you obviously should click next, and never click random. Clicking random will, at best match the number of moves it takes to click next and get to 42
• If your starting number is 40, then you can start to think about clicking random.
  • It's possible that you click random and get 42. This is the only scenario in which you will get to 42 more efficiently than by clicking next twice.
  • We know that, by the binomial distribution where p = 0.01, k = 1, n = 1, that this probability is 1%.
  • That's not very likely to happen, so it's in our long term, average, best interest to click next twice, rather than risk it.
• If your starting number is 39, then you again can think about clicking random.
  • Using the same logic, there are 2 outcomes of clicking random (41, 42) that will guarantee that you use less moves than clicking next
  • If you random into 40, then you will use the same number of moves, so you should have just clicked next.
  • We can model the probability that clicking random is better by adding this probability of your next roll guaranteeing a better result (2%) to the probability of not rolling a better result (98%) multiplied by the probability of getting a better result when you would have been at 40 (1%)
  • this results in a probability of performing better than next being 2.98%.
  • Hey that's a better chance! But still not good enough to warrant clicking random.
• By continuing this pattern, we can calc the probability for every number between 0 and 42.
  • This is shown above (probability_output.txt).

The main point of the above file is to find the "tolerance" on which it stops becoming worth it to click "Random". By reading the probabilities, we can see that it is better on average to click random until you roll a 30, at which point it becomes slightly better to click next until you get to 42.

4_songs.py

import random

def perform_game(track, tolerance):
    # print(f'Starting game on track: {track}.')
    winning_track = 42
    lower_bound = winning_track - tolerance
    # print(lower_bound)
    moves = 0

    while track != winning_track:
        if track >= lower_bound and track < winning_track:
            # Press Next
            track += 1
            if track == 101:
                # Account for going over 100
                track = 1
        else:
            # Press random
            track = random.randint(1,101)
        moves += 1
    # print(f'Finished game that took: {moves} moves.')
    return moves

if __name__ == '__main__':
    current_track = 30
    target = 42
    distance = target - current_track
   
    for tolerance in range(12,16):
        moves = []
        size = 1000001
        for _ in range(size):
            moves.append(perform_game(random.randint(1,101), tolerance))

        sum = 0
        for x in moves:
            sum += x
        print(f'The final average is: {sum / (size - 1)} moves for lower bound: {42 - tolerance}')

5_songs_output.txt

The final average is: 12.758916 moves for lower bound: 30
The final average is: 12.716598 moves for lower bound: 29
The final average is: 12.732438 moves for lower bound: 28
The final average is: 12.80545 moves for lower bound: 27

6_Explanation_Songs.md

According to our Monte Carlo simulation, the average number of moves required to get to track 42 is 12.717 moves using the ideal strategy of clicking random until you are within 29-42.

What's interesting in the above Monte Carlo simulation is that I don't exactly get the same results as I expected.

According to our original calculation of when it becomes better, on average, to click next, you should start clicking next when you are between 30-42. According to our Simulation, you have a lower expected number of moves if you set the lower bound to be 29 instead of 30.

Perhaps this can be explained by the true lower bound should be between 29 and 30, however we are dealing with discrete track numbers, rather than continuous. It's possible the random variance introduced in the simulation causes this fine line to be misinterpreted.

Could there be any other explanation? Perhaps I'm mis-counting somewhere in the code...

Here's the link to the Riddler problem I'm trying to work out: https://fivethirtyeight.com/features/how-fast-can-you-skip-to-your-favorite-song/