Algorithm optimization

Question

Problem:

On a given standard dial pad, which is # unique numbers that can be generated when jumping N times with a restriction that, when you jump, should move like a knight’s chess piece. You also cannot land on any invalid values, such as X, but you can go through them.

Dialer:

1 2 3

4 5 6

7 8 9

X 0 X

Very similar to that

Generate a 10-digit number using the telephone keypad

What I still have, but insanely slow (Python 2.7)

jumpMap = {
  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],
  0: [4, 6]
}
def findUnique(start, jumps):

  if jumps == 1:
    # Base case 1 jump
    return len(jumpMap[start])
  if start == 5:
      return 0
  sum = 0
  for value in (jumpMap[start]):
    sum = sum + findUnique(value, jumps-1)

  return sum

I assume that the easiest optimization method will have some memory, but I cannot figure out how to use one of the given limitations of the problem.

Answer 1

K (k, n) - n, k. K (k, n + 1) = sum (K (i, n)), , k.

; , O (n) O (1) :

jumpMap = [map(int, x) for x in '46,68,79,48,039,,017,26,13,24'.split(',')]

def jumps(n):
    K = [1] * 10
    for _ in xrange(n):
        K = [sum(K[j] for j in jumpMap[i]) for i in xrange(10)]
    return sum(K)

for i in xrange(10):
    print i, jumps(i)

: log (n) O (1) . M - 10 10 M [i, j] = 1, j 0 . (M ^ n * (10, 1)) . log (n) . numpy:

jumpMap = [map(int, x) for x in '46,68,79,48,039,,017,26,13,24'.split(',')]
M = numpy.matrix([[1 if j in jumpMap[i] else 0 for j in xrange(10)] for i in xrange(10)])

def jumps_mat(n):
    return sum(M ** n * numpy.ones((10, 1)))[0,0]

for i in xrange(10):
    print i, jumps_mat(i)

Answer 2

lru_cache, :

from functools import lru_cache

jumpMap = {
  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],
  0: [4, 6]
}

@lru_cache(maxsize=1000)
def findUnique(start, jumps):

    if jumps == 1:
        return len(jumpMap[start])
    if start == 5:
        return 0
    sum = 0
    for value in (jumpMap[start]):
        sum = sum + findUnique(value, jumps-1)

    return sum