fully recursive binary decomposition solution to Google's Knight Dialer

FullyRecursiveSolution.py

import numpy as np
import math
from functools import lru_cache

@lru_cache(maxsize=None) # for memoization
def getMatrix(turns):
    """
    returns a matrix represents the number of unique paths starting in one position and ending in another in N turns
    """

    # our transition matrix
    matrix = np.matrix([
        [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
        [0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
        [0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
        [1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0, 0, 0, 0]], dtype=object)


    # exit condition
    if turns==1:
        return matrix

    else:
        turnsBaseTwo = math.log(turns, 2)

        # condition: turns is a power of 2 
        if turnsBaseTwo.is_integer():
            tempMatrix = getMatrix(turns/2)
            tempMatrixTwo = tempMatrix

        # condition: turns is not a power of 2  
        else:
            tempTurns = 2**math.floor(turnsBaseTwo)
            tempTurnsTwo = turns - tempTurns

            tempMatrix = getMatrix(tempTurns)
            tempMatrixTwo = getMatrix(tempTurnsTwo)

        return tempMatrix*tempMatrixTwo


def getPossibilities(startingPosition, turns):

    # edge case 0 turns is just 1 number
    if turns==0:
        return 1
    
    # get our new matrix N turns ahead
    newMatrix = getMatrix(turns)
    
    # sum the relevant row
    return np.sum(newMatrix[startingPosition])