riddler_hoops.md

Answer and explanation for https://fivethirtyeight.com/features/how-many-hoops-will-kids-jump-through-to-play-rock-paper-scissors/

Rock-Paper-Scissors

There are 9 permutations of 2 players playing rock-paper-scissors. 3 of those permutations lead to ties: Rock-Rock, Paper-Paper, Scissors-Scissors.

1 game + (1/3)(another game)
= 1 game + (1/3)(1 game + (1/3)(another game)) . . .
= Σ (1/3)n
= 3/2 games

If each round of rock-paper-scissors takes 1 second, this means the average complete game of rock-paper-scissors should take 1.5 seconds.

Hoop jumping

2 Hoops

Let's start with a small game of 2 hoops. With 2 hoops, each player makes 1 jump, then plays a game of rock-paper-scissors. I'll use the following notation for this:

H(hoops ahead of you) = jumps + rock-paper-scissors-games

So

H2 = 1 + R

Once one player wins, they will always have 1 hoop ahead of them, so this can be notated like:

H2 = 1 + R + H1

With 1 hoop ahead of them, the two players make 1 jump into the same hoop. Half the time the same player wins (thus winning the game), and the other half of the time the other player wins, leaving 1 more hoop ahead of them:

H1 = 1 + R + (1/2)(0 [the game is over]) + (1/2)H1
   = 1 + R + (1/2)H1
   = Σ (1/2)n(1 + R)
   = 2 (1 + R)
   = 2 + 2R

Thus

H2 = 1 + R + H1
   = 1 + R + 2 + 2R
   = 3 + 3R
   = 3 + 3 * 1.5
   = 7.5 seconds

8 Hoops

The same logic can be applied to more hoops. The initial equations for 8 hoops looks like:

H1 = 1 + R + (1/2)H7
H2 = 1 + R + (1/2)H1 + (1/2)H7
H3 = 2 + R + (1/2)H1 + (1/2)H6
H4 = 2 + R + (1/2)H2 + (1/2)H6
H5 = 3 + R + (1/2)H2 + (1/2)H5
H6 = 3 + R + (1/2)H3 + (1/2)H5
H7 = 4 + R + (1/2)H3 + (1/2)H4
H8 = 4 + R + H4

This can eventually be reduced to

H8 = 36 + 15R
   = 58.5 seconds

More Hoops

If you calculate this out for 1 - 8 hoops a pattern starts to emerge:

1 hoop  =  1 +  1R
2 hoops =  3 +  3R
3 hoops =  6 +  5R
4 hoops = 10 +  7R
5 hoops = 15 +  9R
6 hoops = 21 + 11R
7 hoops = 28 + 13R
8 hoops = 36 + 15R

I calculated 1, 2, 3, 4, and 8 hoops by hand, then double-checked my math by running a simulaton (python code included in the gist).

This turns into the following formula:

seconds for n hoops = (Σ n) + (2n - 1)R
                    = (n * (n + 1))/2 + (2n - 1)(3/2)
                    = (n2 + 7n - 3)/2

Solving for 1800 seconds (30 minutes) gives us ~56.63. Round that up to 57 to get an average game that lasts more than 30 minutes.

riddler_hoops.py

#!/usr/bin/env python

import random
import time

random.seed(time.time())

def rock_paper_scissors():
    """Play a round of rock-paper-scissors."""
    # 0 = rock; 1 = paper; 2 = scissors
    # -1 = a wins; 1 = b wins; 0 = tie
    a = random.randint(0, 2)
    b = random.randint(0, 2)
    if a == b:
        return 0
    elif a == 0:
        return 1 if b == 1 else -1
    elif a == 1:
        return 1 if b == 2 else -1
    elif a == 2:
        return 1 if b == 0 else -1

def rock_paper_scissors_forever(limit=None):
    """Play rock-paper-scissors until there is a winner.

    Returns (result, games_played)
    """
    games = 0
    result = 0
    while result is 0 and (limit is None or games < limit):
        games += 1
        result = rock_paper_scissors()
    return (result, games)

def game_step(board_length, squares_ahead):
    """Process a step in the game.

    `board_length`   length of the board
    `squares_ahead`  number of squares ahead of the current player

    Returns (squares_ahead, steps_taken, rock_paper_scissors_count)
    """
    # integer division for ceil(squares_ahead / 2)
    to_move = (squares_ahead + 1) / 2
    (result, game_count) = rock_paper_scissors_forever()
    if result == 1:
        # Keep going in this direction
        return squares_ahead - to_move, to_move, game_count
    else:
        # Turn around
        return board_length - to_move, to_move, game_count

def simulate_game(board_length):
    """Simulate a single game.

    Returns (total_seconds, steps_taken, rounds_played)
    """
    squares_ahead = board_length
    total_seconds = 0
    total_steps = 0
    rounds_played = 0
    while squares_ahead > 0:
        squares_ahead, steps, games = game_step(board_length, squares_ahead)
        rounds_played += 1
        total_steps += steps
        total_seconds += steps + games
    return (total_seconds, total_steps, rounds_played)

if __name__ == '__main__':
    simulation_count = 1000000
    for game_size in range(1, 9):
        totals = reduce(lambda x, y: (x[0] + y[0], x[1] + y[1], x[2] + y[2]),
                        (simulate_game(game_size) for n in range(simulation_count)))
        print 'game_size: %d' % (game_size,),
        print 'averages ', [float(x) / simulation_count for x in totals]