Simulation of an Oxford (Undergrad) Interview Question

A friend of mine, who's an economics teacher in London, is responsible for preparing some of his students for interviews at Oxford and Cambridge. He told me that, at these schools, students have to go through a nerve-wracking experience where faculty pepper them with quiz questions meant to assess the ability to think quickly under pressure.

It turns out that these schools publish example questions, which are much more fun to think about in your own home, without an accomplished faculty waiting in silence.

I've found the list of practice questions in Computer Science interesting – these questions don't require computer-assistance to solve, but they offer a nice chance to practice programming skills nonetheless.

As an example, here's the 'lilypad problem':

Eleven lily pads are numbered from 0 to 10. A frog starts on pad 0 and wants to get to pad 10. At each jump, the frog can move forward by one or two pads, so there are many ways it can get to pad 10. For example, it can make 10 jumps of one pad, 1111111111, or five jumps of two pads, 22222, or go 221212 or 221122, and so on. We'll call each of these ways different, even if the frog takes the same jumps in a different order. How many different ways are there of getting from 0 to 10?

While this question really should be answered using permutation, I thought it'd be fun to try writing a short script to use simulation to solve.

My approach was to first write a function (solution.gen) which generates a random route. Next, I draw from this function (a large number of times, using draw.func), and examine the number of unique solutions.

To test the approach, I plot the number of unique solutions for 200 trials ranging from 50 to 10000 draws.

Result: It looks like this process uncovers 89 distinct routes. With a few hiccups, it looks like about 1000 draws recover these, and more than 2000 draws recover them reliably.

While simulation isn't always the best approach, it's a nice tool to have if the analytic solution is too opaque (or in this case, just tiresome) to figure out.

Here's the code:

solution.gen = function() {
    draw = rbinom(10, 1, 0.5) + 1
    sub = which(cumsum(draw) <= 9)
    draw = draw[sub]
    if (sum(draw) == 9) {
        draw = c(draw, 1)
    } else {
        draw = c(draw, 2)
    }
    return(draw)
}

draw.func = function(x) {
    length(unique(replicate(x, solution.gen())))
}

draws = seq(from = 50, to = 10000, by = 50)
unique.routes = sapply(draws, draw.func)

df = data.frame(draws, unique.routes)

# (not run) code to create plot: library(ggplot2) p = ggplot(df, aes(x =
# draws, y = unique.routes)) + geom_point() + geom_line() p + labs(title =
# 'Unique Lilypad Routes')