My solutions for google foobar
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

42 lines

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