Coding Puzzle - Knight Sequences

Knight Sequences

Recently I have come across a coding exercise that is not difficult to solve, but somewhat stimulating to do so efficiently.

There are several solutions posted online to a slightly different rule set, but none solved the problem efficiently.    So I thought I would share several solutions, each a bit more efficient than the prior, all written in C++ 11 standard.

The Challenge

Find all key sequences for a given length that can be keyed into the keypad in the following manner:

• The initial key press can be any of the keys
• Each subsequent key press must be a “knight move” from the previous key press
• There is no wrapping allowed while preforming the knight move
• There can be at most 2 vowels in the sequence
• The solution will be used to solve sequence lengths of 10, 16 and 32 key sequences
• The program will write the total number of valid key sequences on a single line to standard out

Knight Moves...
 A knight move is made in one of the following ways:

• Move 2 steps horizontally and 1 step vertically
• Move 2 steps vertically and 1 step horizontally

Let's walk through a 4 key sequence beginning with 'A', the next valid sequence is either of: {H,L}, lets pick 'H'

From 'H' navigation to {A,E,K,O,1,3} is valid, lets pick '1'

From '1' the valid next sequence is one of the following: {F,H,N}, lets pick 'F'
By now the pattern is pretty clear, but lets do one more move just to make sure.

From 'F' the valid set might be {C,M,1} or {C,M}  it depends in the interpretation of knight moves.  Observe that the path from 'F' to '1' would require moving through a position without a key.  If a night move is strictly defined as 2 moves followed by 1 move then {C,M} is valid and {C,M,1} is invalid.    For this example the assumption is that the order of the move doesn't matter as long as the move is an 'L' and thus {C,M,1} is valid.  If you are asked to solve this puzzle, it's best to clarify what the assumption is.

Code Structure

In the illustrations above the rule set is established and a corner case was identified.  In the following code the rules are formalized into C++ code using C++ 11 initializers for the definitions.  

The type TKeyIdentity identifies each key on the keypad.   Observe that TKeyPath is a STL vector that contains the valid set moves from the current key.    Finally, observe that TKeyMap is a collection of TKeyPaths that represent all keys on the keypad.

Recursive Model - Top Down Approach

Before trying to write optimal code, it's a good practice to write a simple solution that is easy to debug and and understand.   This problem set is efficiently expressed in a recursive model where the state of a sequence is passed along each step of the way.   
Below is the code that provides a working model that provides the number of sequences for a key depth of 10, later we will explore methods to optimize it.

Top-Down Model Results:

What this top-down model proves is that there are 1,013,398 sequences possible for a depth of 10 keys and 18 sequences for a depth of 1 key. If we try to get a result with a depth of 32 keys, the algorithm will run far longer than you would expect with an algorithm complexity that is exponential. The reason it is so slow is that it is solving the same sub-problem over and over. We can do better than this if we are willing to use more space to memorize the solutions to the sub-problems. 

Dynamic Programming with Memoization - Top Down

Lets modify the code a bit to save the intermediate results (called memoization).
In function TraverseKeyPaths(), if we were to check to see if there was a solution for the given problem bound by three properties: pressedKey, pressesRemaining and vowelsAllowed then its possible to skip the recursion since it was already solved.  If no solution exists, then perform the recursive calculation and store the result in the memoize array before returning to the caller.  The space required is O(kp(v+1)) where k is the number of keys, p is sequence depth and v is the number of allowable vowels in a sequence. 
The code below contains the modifications that implement memoization, note that this approach can work with any recursion problem set that solves subproblems.   

Memoization results:

Now that the solution is only being calculated once, calculating the number of knight sequences to a depth of 36 happens very quickly.   In fact, the XCode profiler can't event trap a sample on it.    This is a very impressive speed improvement for not much memory, but in a memory constrained system the space required for memoizing may exceed the limits.   In the next section we will examine what a bottom-up solution looks like and how it can help with memory usage.

Dynamic Programming - Bottom Up Approach

Working from the bottom up, we solve the problem iteratively and only need enough memory to store state for the current and prior iteration.    The state contains the number of sequences for a given key at the specified vowel depth.    The current state is computed by traversing the adjacency table (keyPad) and summing up the prior state into the current state.  The space required is O(2k(v+1).  The performance performance is nearly identical to Memoization, but there may be ways to improve that as well.

Compile Time Computation - Partial Template Specialization

Up to this point all solutions discussed were solved at runtime.   Can we do better?   You bet - solve the problem at compile time.  Using C++ templates and partial template specialization, the solution is computed by the compiler (and rather quickly) and thus at runtime all we are doing is looking up the result for the given key sequence depth and printing it out.   Performance is O(1) and size is O(d) where d is the number of depths computed.  If the target depth is known at compile time the space would be O(1) as well.

Compile Time Computation - Meta Programming

The following example uses Meta Programming that is part of C++ 11 standard but has yet to show up on the Visual Studio 2013.   Xcode has its own issues as it doesn't perform recursion optimization so compile times can take forever.    The good news is GCC has this nailed and it compiles in a jiffy.    

Well that wraps this topic up - comments are welcome.