## Friday, December 9, 2011

### A children can hop either 1, 2, or 3 steps in a stairway of N steps.

How many combinations do you have?

1. Isn't a recursive function? I am thinking the solution as a tree, the number of leaf nodes is our target. Mathematically,

F(N) = 1 if N = 1
= 2 if N = 2
= 4 if N = 3
= F(N-1) + F(N-2) + F(N-3) if N > 3

2. This blog is so much better than watching TV :)

So this is I think best to solve with a tree algorithm as Venkata suggested earlier. An initial naive solution might be to use a simple breadth first search like:

static Stack<long> nodes = new Stack<long>();
static long Combinations( int n )
{
long leafs = 0;
nodes.Push(n);
while (nodes.Count > 0)
{
var x = nodes.Pop();

// Leaf, just count
if (x <= 0) leafs++;
else
{
// Only push down options where the child can actually complete
// the stair jump on a complete jump (i.e. not taking last 1 step in a 3step jump)
if (x - 1 >= 0) nodes.Push(x - 1);
if (x - 2 >= 0) nodes.Push(x - 2);
if (x - 3 >= 0) nodes.Push(x - 3);
}
}
return leafs;
}

But it is soon obvious that for non-trivial N then this naive BFS is simply too slow.

However when looking at the ternary-tree it becomes obvious that it is simply a repeating pattern of the same subtrees. So enhancing this algorithm to be recursive and having a simple caching map for previously calculated subtrees drastically improves performance. Like so:

static Dictionary<int, BigInteger> map = new Dictionary<int, BigInteger>();
static BigInteger Combinations2(int n)
{
// Wooha, at a leaf
if (n <= 0) return 1;

BigInteger leafs = 0;
if (map.TryGetValue(n, out leafs))
return leafs;

if (n - 1 >= 0)
leafs += Combinations2(n - 1);
if (n - 2 >= 0)
leafs += Combinations2(n - 2);
if (n - 3 >= 0)
leafs += Combinations2(n - 3);

map[n] = leafs;
return leafs;
}

At least Combinations2 is a little bit more intelligent than before :)

3. Why such a complex code? We can see overlapped sub problems solving again and again and they are combined for end result. Here is simple smart code (linear in time and constant space),

int ChildHop(int N) {
int A[] = {1, 2, 4};
if( N <= 3 )
return A[N-1];

int x = 0, y = 1, next = 2;
int prev_next;
for(int i = 0; i < N-3; i++) {
prev_next = next;
next = (next+1)%3;
A[next] = A[prev_next] + A[x] + A[y];
x = y;
y = prev_next;
}

return A[next];
}

Use template with BigInteger typename to solve larger size stairs.

These days I am using Bing also along with Google. Surprise, when I search my name in Bing, I saw link of this page in results :)

@Antonio, I have two questions.