Optimizing an algorithm

Question

Problem:

On a given standard dial pad, what is the # of unique numbers that can be generated from jumping N times with the constraint that when you jump, you must move like the knight chess piece. You also cannot land on any invalid values like the X's but you may pass through them.

Dialer:

Very similar to this

Generate 10-digit number using a phone keypad

What I have so far but is crazy 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'm guessing the easiest way to optimize would to have some kind of memoization but I can't figure out how to use one given the problem constraints.

Paul Hankin · Answer 1 · 2016-04-09T00:56:32.947

Let K(k, n) be the number of unique numbers of length n, starting with key k. Then, K(k, n+1) = sum(K(i, n)) where i ranges over the keys that it's possible to jump to from key k.

This can be calculated efficiently using dynamic programming; here's one way that takes O(n) time and O(1) space:

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)

Faster: it's possible to compute the answer in log(n) time and O(1) space. Let M be the 10 by 10 matrix with M[i,j] = 1 if it's possible to jump from i to j, and 0 otherwise. Then sum(M^n * ones(10, 1)) is the answer. The matrix power can be computed using exponentiation by squaring in log(n) time. Here's some code using 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)

score 1 · Answer 2 · answered Apr 09 '16 at 00:54

You can use the lru_cache, it will memoize calls:

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

Optimizing an algorithm

2 Answers2