``````""" The hard part of this challenge was figuring out how to make it in the time limit, much like the old XOR challenge. This one though was on another optimization technique, memoization(I see what you did there Google, challenges using the skills you ask for interviews on your website). Hashing the entire list would have been too long, even as a tuple, so instead we had to be clever and use another trick: building an history of all the moves that happened. This allows us, given a pair of row and column a and b, to avoid having to do extreme amount of recursive computation to get a result, as long as an history of the last (past grid row + current move) moves is saved. The rest of the problem is fairly easy: we recursively try out all possible combinations for this grid and save the number of correct ones we could get. """ def answer(state, a=0, b=0, past=0, solutions=0, history=0): if(past==0): past=[[True] * (len(state)+1) for i in range(len(state)+1)] solutions = {} history = [] if(b==len(state)+1): return True res=0 index=((a,b), tuple(history[-(len(state)+2):])) if index in solutions: return solutions[index] for cell in [True, False]: # either all True(c and 1 cell) or all False (!c and !1 cell) if (not a or not b) or len(set([((past[a][b-1] + past[a-1][b] + past[a-1][b-1] + cell)==1), state[a-1][b-1]]))==1: history.append(cell) past[a][b] = cell res+=answer(state, a=(a+1)%(len(state)+1), b=b+(a+1)//(len(state)+1), past=past, solutions=solutions, history=history) history.pop() solutions[index]=res return res``````