Knight to E4

knight.py

'''
So, I started off by visualizing the network map

1 - 6 - 7
|   |   |
8   0   2
|   |   |
3 - 4 - 9

 5

Once the map was drawn, I realized there were only 4 possible types of positions
		 - corner (1,3,7,9)
		 - edge (2,8)
		 - edge-corner (4,6)
		 - center (0)
	Solving for any specific type and N number of hops would return the same answer.
	
	I also realized 5 was not connected and the result would always be 1 for it
	
	I decided to represent the starting position as a 1x4 matrix with a value of 1 if the starting position 
	was of that type and a value of 0 if not. I arbitrariliy decided to represent that as [corner, edge, edge-corner, center]
	
	So for a starting position of 1, it would be a corner and the array would be [[1,0,0,0]]

'''

import numpy as np

def get_start_type_array(starting_position):
	'''
	returns a 1x4 matrix of starting position type
	'''
	
	if starting_position in (1,3,7,9):
		# type is a corner
		return np.matrix([1,0,0,0])
	elif starting_position in (2,8):
		# type is a edge
		return np.matrix([0,1,0,0])
	elif starting_position in (6,4):
		# type is an edge corner
		return np.matrix([0,0,1,0])
	elif starting_position == 0:
		return np.matrix([0,0,0,1])
	
	# raise error if value isn't found


def count_sequences(starting_position, num_hops):
	# 5 has no neighbors so the unique set of numbers is always 1
	if starting_position == 5:
		return 1
	
	unqiue_next_position_types = np.matrix([[0,1,1,0],[2,0,0,0],[2,0,0,1],[0,0,2,0]])
	'''  
	this matrix is a 4x4 matrx to represent the number of unique next positions for each type given a starting position array.
  
  [0,1,1,0]
  [2,0,0,0]
  [2,0,0,1]
  [0,0,2,0]
  
	So for a corner position, the next possible unique positions are an edge corner or an edge, which is represented by row 1
	for an edge position, the next possible unique positions are 2 corners (row 2)
	for an edge-corner position, the next possible unique positions are 2 corners and 1 center (row 3)
	for a center position, the next possible unique positions are 2 edge-corners (row 4)
	
	So I figured, if I knew the number of positions of each type for each unique path as an array,
	I could figure out the number of positions of each type for one more hop
	by multiplying an array of the current number of unique positions of each type, by the 4x4 matrix.
	
	If that was true, to get the number of unique paths with a length of <=N,
	all I had to do was sum the number of unique positions for each hop. 

	With that, the Big O for this function would be O(N)
	'''
	
	total_unique_positions = 1
	
	possible_positions = get_start_type_array(starting_position)
	
	for i in range(num_hops):
		possible_positions = np.matmul(possible_positions, unqiue_next_position_types)
		total_unique_positions = total_unique_positions + np.sum(possible_positions)
	
	return total_unique_positions
			

def main():
	count = count_sequences(1,4)
	print(f'for a starting position of 1 and a num hops of 4, the number of unique paths should be 44, actual: {count}')
	
if __name__ == '__main__':
	main()
	
	
'''
On a side note: 
you mentioned memoization, so I'll mention there are 2 ways method could benefit from memoization that I didn't implement.

There are 2 major memoization improvements.

1. since we are doing the matrix multiplication any ways, the count of unique paths for each stage for each starting position should be stored.
	I would calculate the unique values for all unique starts at the same time by mulitplying the next locations matrix by an identity matrix and summing across rows
	It should result in a matrix of size 4 x Historical N where Historical N is the greatest N used since start up.

	this improvement would make Big O for N <= Historical N to O(1)

2. If we already have the memoization in part 1, It could be further improve it further
	With any solution up to and equal to N solved, performance could be improved by storing the current position states at N.
	By setting the possible_positions to memoized position and setting the begining position to the heighest historial N, the previous states wouldn't have to be calculated.

	This improvement would make Big O for N > Historical N to O(N-historical N)
  
 I am not sure what the overall Big O would be, but I figure you could run a few randomized experiments and fit a line to it. 

On another side note, here are the test I would want to cover:
 - starting position is invalid
 - number of hops is not an integer
 - for starting position of 5, unique paths is always 1
 - position doesn't matter as long as position type is the same
 - check a few random positions and num hops
 - check memoization for < Historical N
 - check memoization for > Historical N
'''

'''
Final notes:
It took me about an hour and a half to come up with the solution & vague idea of how to memoize. 
another half hour to figure out how to actually memoize, another 15 to figure out what test cases I would want 
and another 2 hours to actually type this up and get it working

I am not great at python yet, so I didn't write up the decorators or refactor to handle the memoization. 

so, 1 & 1/2 hours for a basic solution; 2 hours for a more complete solution. It isn't 45 minutes, but is that good for a beginner? 
I got stuck on what the actual problem was for awhile, but I am not sure whether an interviewer would generally help for that or not. 
'''