Simulation of an Oxford (Undergrad) Interview Question

[This article was first published on Decisions and R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

plot of chunk unnamed-chunk-1

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)

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')

To leave a comment for the author, please follow the link and comment on their blog: Decisions and R. offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)