jsmp: The Riddler

In this document I solve riddles rom 538’s The Riddler, using programming, mainly in Julia. Updated continuously.

imports


using Random
using Statistics
using Memoize
using Base.Iterators
using Combinatorics
using Distributions

repeat(f::Function, n::Integer) = [f() for _ in 1:n]

nsims = 10^6
simprob(f) = sum(repeat(f, nsims)) / nsims

function ifirst(cond, itr)
    for elem in itr
        cond(elem) && return elem
    end
end

Random.seed!(0);

1. Knight on an infinite chessboard

From the Riddler book

Problem

Suppose that a knight makes a “random walk” on an infinite chessboard. Specifically, every turn the knight follows standard chess rules and moves to one of its eight accessible squares, each with probability 1/8.

What is the probability that after the twentieth move the knight is back on its starting square?

Simulation solution

The knight moves two tiles in any direction, and one tile in a direction perpendicular to that.


move() = shuffle(1:2) .* rand([-1, 1], 2)
is_back_to_start() = sum(repeat(move, 20)) == [0,0]


simprob(is_back_to_start)


0.006213

Exact solution

We recursively go through all moves the night can do, and count all the ones that return to the starting spot after 20 moves.


@memoize function knight_returns(moves_left, i, j)
    moves_left == 0 && return i == j == 0
    n_return = 0
    for(x,y) in product([(1,2),(2,1)], product([-1,1], [-1, 1]))
        n_return += knight_returns(moves_left - 1, i + x[1]*y[1], j + x[2]*y[2])
    end
    n_return
end


knight_returns(20,0,0) // 8^20


111846980495107//18014398509481984

2. How large is Santa’s playlist?

Dec 21 2018

Problem

In Santa’s workshop, elves make toys during a shift each day. On the overhead radio, Christmas music plays, with a program randomly selecting songs from a large playlist.

During any given shift, the elves hear 100 songs. A cranky elf named Cranky has taken to throwing snowballs at everyone if he hears the same song twice. This has happened during about half of the shifts. One day, a mathematically inclined elf named Mathy tires of Cranky’s sodden outbursts. So Mathy decides to use what he knows to figure out how large Santa’s playlist actually is.

Solution

The risk of having a repeat song is the same as 1 minus the probability of no repeat songs. To get no repeat songs, the second played song needs to not be a repeat of the first (chance = 1/n), and the third song needs to not be a repeat of any of the two first ones (chance = 2/n), etc. So we find the first n so that this risk is just below 0.5.

(Note: this is the Birthday problem)


risk_of_repeated_song(n) = 1 - prod((n - i) / n for i in 1:99)


ifirst(n -> risk_of_repeated_song(n) < 0.5, countfrom(101))

3. Numbers divisible by 100

Feb. 8, 2019

Problem

The song “Seasons of Love” from the musical “Rent” states that a year has 525,600 minutes. And, indeed, 365×24×60 = 525,600.

This, naturally, raises an abstract mathematical question: Given any three random integers — X, Y and Z — what are the chances that their product is divisible by 100?

Solution


count(a * b * c % 100 == 0 for a in 0:99, b in 0:99, c in 0:99) / 99^3


0.1281048419095557

4. Collecting cigarette cards

Mar 1, 2019

Problem

In the video game “Red Dead Redemption 2,” there is a side quest where the main character is supposed to collect 12 sets of cigarette cards, each consisting of 12 unique cards.

Some cards can be found lying around in the open world, but the easiest way to collect the cards is to buy cigarettes at the store and collect the single random card included in each pack. Suppose Arthur is too lazy to look for cards in the open world and tries to complete the set only by buying packs at the store.

At $5 a pack, how much money do we expect Arthur to spend to complete all 12 sets?

Simulation solution


function get_price()
    cards, dollars = Set(), 0
    while length(cards) < 144
        push!(cards, rand(1:144))
        dollars += 5
    end
    dollars
end


mean(repeat(get_price, nsims))


3995.29166

Exact solution

This is the Coupon collector’s problem. If you are only lacking one card out of 144, it will take an average of 144 packs to get it; if you are lacking two cards, it will take an average of 144 / 2 packs, and so on. So we sum all these averages.


sum(144 // n for n in 1:144) * 5

5. Ticket to Ride

Mar 29, 2019

Problem

You are playing your first ever game of “Ticket to Ride,” a board game in which players compete to lay down railroad while getting so competitive they risk ruining their marriages. At the start of the game, you are randomly dealt a set of three Destination Tickets out of a deck of 30 different tickets. Each reveals the two terminals you must connect with a railroad to receive points. During the game, you eventually pick up another set of three Destination Tickets, so you have now seen six of the 30 tickets in the game.

Later, because you enjoyed it so much, you and your friends play a second game. The ticket cards are all returned and reshuffled. Again, you are dealt a set of three tickets to begin play. Which is more likely: that you had seen at least one of these three tickets before, or that they were all new to you?

Simulation solution


seen_one_before = []
tickets = 1:30

for i in 1:nsims
    first_tickets = Set(sample(tickets, 6, replace=false))
    second_tickets = Set(sample(tickets, 3, replace=false))
    push!(seen_one_before, length(intersect(first_tickets, second_tickets)) == 0)
end


sum(seen_one_before) / nsims


0.498872

Exact solution

6 out of 30 tickets have been picked before. The first one therefore has a 24/30 chance to not have been picked. The second pick is from the pile without the first pick, and thus has a 23/29 chance of not having been picked in the first round. 22/28 for the last pick.


24//30 * 23//29 * 22//28


506//1015

6. Gift cards

5 Apr, 2019

Problem

Lucky you! You’ve won two gift cards, each loaded with 50 free drinks from your favorite coffee shop, Riddler Caffei-Nation. The cards look identical, and because you’re not one for record-keeping, you randomly pick one of the cards to pay with each time you get a drink. One day, the clerk tells you that he can’t accept the card you presented to him because it doesn’t have any drink credits left on it.

What is the probability that the other card still has free drinks on it? How many free drinks can you expect are still available?

Simulation solution


drinks_left = []
for i in 1:nsims
    cards = [50, 50]
    while minimum(cards) >= 0
        cards[rand([1, 2])] -= 1
    end
    push!(drinks_left, maximum(cards))
end

Probability other card has drinks:


1 - sum(drinks_left .== 0) / nsims


0.920383

Number of free drinks you can expect are available:


sum(drinks_left) / nsims


7.034115

Exact solution

Using dynamic programming.


ntickets = 50
dim = ntickets + 2
a = fill(0.0, dim, dim)
a[2, 2] = 1

for diag in 5:2*dim, i in 2:dim, j in 2:dim
    if i + j == diag
        a[i, j] = a[i-1, j] / 2 + a[j-1, i] / 2
    end
end

Probability other card has drinks:


1 - a[dim, dim]


0.9204107626128212

Number of free drinks you can expect are available:


sum(a[i, dim] * (dim - i) for i in 2:dim-1)


7.038512976105056

The Riddler

Table of Contents

1. Knight on an infinite chessboard

Problem

Simulation solution

Exact solution

2. How large is Santa’s playlist?

Problem

Solution

3. Numbers divisible by 100

Problem

Solution

4. Collecting cigarette cards

Problem

Simulation solution

Exact solution

5. Ticket to Ride

Problem

Simulation solution

Exact solution

6. Gift cards

Problem

Simulation solution

Exact solution