Our first solution to the Knight Dialer

KnightSolution1.py

import numpy as np

def getMatrix(matrix, turns):
    newMatrix = np.identity(matrix.shape[0])
    for i in range(turns):
            newMatrix = newMatrix*matrix
    return newMatrix
  
def getPossibilities(startingPosition, turns):
    
    # our transition matrix
    transitionMatrix = 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)
    # we use the datatype of object because the numbers we will be getting will be huge
    # 500 turns out will be somewhere between 2^500 and 3^500
    
    # get our new matrix N turns ahead
    newMatrix = getMatrix(transitionMatrix, turns)
    
    # sum the relevant row
    return np.sum(newMatrix[startingPosition])

def main():
    startingPosition = 0
    turns = 8
    possibilities = getPossibilities(startingPosition, turns)
    print(f'Starting at {startingPosition} in {turns}, Knight can dial {possibilities} numbers')

if(__name__=='__main__'):
    main()