<p>从<a href="https://codereview.stackexchange.com/questions/71988/permutation-of-phone-numbers-starting-at-button-x-ending-at-button-y-and-z-num">codereview</a></p>
<pre><code>"""Solve the phone/chess paths problem from this question:
https://codereview.stackexchange.com/questions/71988
"""
# Move dictionary
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]}
# Cache implementation
def cache(func):
"""Standard cache decorator implementation."""
cache_dct = {}
def wrapper(*args):
if args not in cache_dct:
cache_dct[args] = func(*args)
return cache_dct[args]
return wrapper
# Recusive function
@cache
def rec(x, y, z):
"""Recursively count the number of path
to go from x to y in z moves.
"""
if not z:
return int(x == y)
return sum(rec(x, y, z-1) for x in MOVES[x])
# Paths function
def paths(x, y, z):
"""Count the number of paths to go from x to y
with z key strokes.
"""
if not z:
return 0
return rec(x, y, z-1)
# Main execution
if __name__ == "__main__":
example = "paths(1, 1, 99)"
print example + " = " + str(eval(example))
# Output: paths(1, 1, 99) = 30810672576979228350316940764381184
</code></pre>