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?
Pubblicato da a
Reazioni: 

2 commenti:

  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

    Any comments?

    ReplyDelete

  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;

    // We need to calculate it if not found
    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 :)

    ReplyDelete

Subscribe to: Post Comments (Atom)