Algorithm to count the number of Android patterns

count_android_patterns.py

#!/usr/bin/env python

# The Android dots are labelled as
# 0 1 2
# 3 4 5
# 6 7 8

# The following is a handcoded table where table[i][j] is the number crossed by path i -> j.
table = [
    [None, None, 1, None, None, None, 3, None, 4],
    [None, None, None, None, None, None, None, 4, None],
    [1, None, None, None, None, None, 4, None, 5],
    [None, None, None, None, None, 4, None, None, None],
    [None, None, None, None, None, None, None, None, None],
    [None, None, None, 4, None, None, None, None, None],
    [3, None, 4, None, None, None, None, None, 7],
    [None, 4, None, None, None, None, None, None, None],
    [4, None, 5, None, None, None, 7, None, None]
]

def generateAndroidPattern(prefix):
    if not prefix: # Special cases for empty prefix
        for i in xrange(9):
            for n in generateAndroidPattern((i,)):
                yield n
    else:
        if len(prefix) >= 4:
            yield prefix
        for i in xrange(9):
            if i in prefix: # Android patterns must have distinct dots
                continue
            crossNumber = table[prefix[-1]][i] # The number crossed by the proposed path
            if crossNumber is None or crossNumber in prefix:
                for n in generateAndroidPattern(prefix + (i, )):
                    yield n

print(sum(1 for n in generateAndroidPattern(tuple())))