'''
   20211024
   
   Robin Dawes
   
   The problem with the Nim function we defined previously was that in the
   process of solving a large problem it solved the same smaller problems over
   and over.  Recursion is much more efficient if we make sure we only solve
   each smaller problem once.
   
   In this version we use a dictionary to store the results of problems as we
   solve them.  Then when we encounter a problem for the second (or more) time
   we can just look up the result in the dictionary.  Since dictionary keys cannot
   be mutable, we convert each list to a tuple before using it as a key.
'''

solved_situations = { (0,0,0) : "L" }


def do_I_win_nim(situation):
      sit_tuple = tuple(situation)
      if sit_tuple in solved_situations:
         return solved_situations[sit_tuple]
      else:
         for heap in range(3):
            for i in range(1,situation[heap]+1):
               new_sit = situation[:]
               new_sit[heap] -= i
               if  do_I_win_nim( new_sit) == "L":
                  solved_situations[sit_tuple] = ("Win with", new_sit)
                  return ("Win with", new_sit)
         solved_situations[sit_tuple] = "L"
         return "L"
         
         
for p1 in range(1,3):
   for p2 in range(p1,4):
      for p3 in range(p2,5):
         print('[',p1,p2,p3,']',do_I_win_nim( [p1,p2,p3]))
     
# Now this problem is solved instantly - behold the power of saving the
# solutions to small problems!

s = [6, 8, 11]

print("\n", s, do_I_win_nim(s))