Skip to content

Instantly share code, notes, and snippets.

@akshayjshah
Last active August 29, 2015 14:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save akshayjshah/11165882 to your computer and use it in GitHub Desktop.
Save akshayjshah/11165882 to your computer and use it in GitHub Desktop.
Knights Code
import functools
moves = {
0: [4, 6],
1: [6, 8],
2: [7, 9],
3: [4, 8],
4: [0, 3, 9],
5: [],
6: [0, 1, 7],
7: [2, 6],
8: [1, 3],
9: [2, 4],
}
def memoize(func):
"""NB, this memoize implementation isn't thread-safe and won't memoize
functions with named parameters.
"""
memo = {}
@functools.wraps(func)
def wrapper(*args):
if args not in memo:
memo[args] = func(*args)
return memo[args]
return wrapper
@memoize
def count_codes(remaining_length, ending_digit):
if remaining_length == 1:
return 1
return sum(count_codes(remaining_length - 1, d) for d in moves[ending_digit])
if __name__ == '__main__':
target_length = 12
print sum(count_codes(target_length, end) for end in moves)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment