Today a perfect brain teaser for a Friday night. Let’s find how many paths of a certain length a chess knight on a phone keypad has.

To find the solution I had to write down the adjacency list first. Instead of doing that mundane task manually, I wrote a small program.

from itertools import product
from collections import defaultdict

def isOK(x, y):
    return (0 <= x <= 2 and 0 <= y <= 2 or
            x == 1 and y == 3)

def generate_adjacency_dict():
    k = "123 456 789 x0x".split()
    jump = defaultdict(list)
    delta = list(product([2, -2], [1, -1])) + list(product([1, -1], [2, -2]))

    for y, row in enumerate(k):
        for x, ch in enumerate(row):
            if isOK(x, y):
                for d in delta:
                    if isOK(x + d[0], y + d[1]):
                        jump[ord(ch) - ord('0')].append(
                            ord(k[y + d[1]][x + d[0]]) - ord('0'))
    return jump

if __name__ == '__main__':
    print(generate_adjacency_dict())

The actual algorithm is based on the following observation: once we reach a phone key it is not important how we did that. We simply need to remember the total number of ways we had of reaching that key. So in each step one keeps the count of paths that end at a key. In the new iteration every reachable key will contain a sum of path counts of the keys that the knight jumped from.

from collections import defaultdict

def count_knight_paths(maxlevel):
    jump = {0: [6, 4], 1: [6, 8], 2: [9, 7],
            3: [4, 8], 4: [9, 3, 0], 6: [7, 1, 0],
            7: [6, 2], 8: [3, 1], 9: [4, 2]}
    c = { 1 : 1 }
    for level in range(maxlevel):
        cprim = defaultdict(int)
        for key in c:
            for jumped in jump[key]:
                cprim[jumped] += c[key]
        c = cprim
    return sum(c.values())

if __name__ == "__main__":
    for i in range(10):
        print(i + 1, count_knight_paths(i))
About these ads