0
$\begingroup$

I got thrown off by an interview question recently,

What structure do you use to find all the ways up a ladder with N steps in 1 or 2 steps moves?

It occured to me today that a graph expansion could be used but it's not optimal because when N = 30, it evalates almost 700,000 nodes on a single round of expansion.

Here's the output of solving for N = 5.

2 2 1 2 1 2 1 2 2 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 

My instinct is that maybe this problem can be solved with regular methods from Discrete Math that I'm just not remembering.

Is there a way to get the set of sequences containing (1, 2) where the sum of the elements is N?

If anyone is interested here's the code of the program I wrote.

  • 0
    Yes, i was asked to say how I'd find all the paths.2012-06-12

2 Answers 2

3

If $N=0$ there is one way: $\langle\rangle$. (No steps at all.) If $N=1$, there is one way, $\langle 1\rangle$. For $N>1$, take each way up a ladder of $N-2$ steps and append a $2$, and each way up a ladder of $N-1$ steps and append a $1$. Thus, for $N=2$ you get $\langle 2\rangle$ and $\langle 1,1\rangle$. The first few stages, with semicolons separating the paths derived from two steps back from those derived from one step back:

$\begin{align*} &N=0: \langle\rangle\\ &N=1: \langle 1\rangle\\ &N=2: \langle 2\rangle;\langle 1,1\rangle\\ &N=3: \langle 1,2\rangle;\langle 2,1\rangle,\langle 1,1,1\rangle\\ &N=4: \langle 2,2\rangle,\langle 1,1,2\rangle;\langle 1,2,1\rangle,\langle 2,1,1\rangle,\langle 1,1,1,1\rangle \end{align*}$

You never need to have more than two consecutive levels in storage at once, and it’s a straightforward generation with no trial and error. By the way, the number of paths for a given $N$ is $F_{N+1}$, the $(N+1)$-st Fibonacci number,

2

The number of such paths is the Fibonacci number $F_{n+1}$.

You can get the set $S_n$ of $n$-step paths recursively: append $1$ to each member of $S_{n-1}$, $2$ to each member of $S_{n-2}$, and take the union.

  • 0
    Heh. $B$eat me to the answer by 1 minute.2012-06-12