'''
   20211004
   
   Robin Dawes
   
   The Game of Nim is similar to token-taking games that have been played
   for centuries in many different parts of the world.  
   
   The rules of Nim are simple:  the game starts with a number of heaps or rows
   of small objects (typically pebbles, matches, pennies, poker chips, etc.)  In this
   description we will assume that the objects are gummy bears, and that there
   are three heaps.
   
   Two players take turns removing one or more bears from any one of the heaps.  
   The player who takes the last bear wins the game.  (A popular variant flips 
   this around: the player who takes the last bear loses.)
   
   Nim is an example of what we call a perfect information game.  There is no
   randomness, and there are no unknowns.  (This type of game includes classic
   board games such as chess, checkers, go, owari, shogi, nine men's morris and
   many others.)  When a perfect information game must end and cannot end in a 
   tie, there must be a strategy for either the first or the second player that 
   always leads to a win.
   
   In a game such as chess or checkers, the initial situation is fixed and therefore 
   only one player can have the winning strategy.  But in Nim the initial situation 
   is defined by the number of bears in each heap ... and some initial situations are
   Wins for Player 1 and some are Wins for Player 2.
   
   Anyone wishing to make a career as a professional Nim player needs to be able
   to know, for any initial situation, whether they should be Player 1 or Player 2.
   
   Some situations are obvious wins for Player 1:  If two of the heaps have 0 bears 
   and the other heap has at least one bear, then Player 1 can win by taking all
   the bears in that heap.
   
   Some situations are wins for Player 2.  If one heap has 0 bears and the other
   two heaps have an equal number of bears, no matter how many bears Player 1
   takes, Player 2 will be able to take the same number from the other heap.  Thus
   Player 1 cannot have the last move, so Player 2 must be the eventual winner.
   
   But given an initial situation such as one heap with 2 bears, one with 3 bears and one 
   with 4 bears, it is not so obvious who has the winning strategy.  This is where
   recursion can help us: it is easy to write a recursive function that determines
   who has the winning strategy for any initial situation.
   
   The principle is this: All situations can be labelled "W" or "L".  We label a situation
   "W" if it is a winning situation for whoever makes the next move, and "L" if it is
   a winning situation for the player who is not making the next move.  The rule for
   labelling a situation is simple:  we label a situation "W" if ANY of the situations 
   that can be reached from it in one move are labelled "L", and we label a
   situation "L" if ALL of the situations that can be reached from it in one move
   are labelled "W".
   
   So we can start with any situation and determine its label by first determining
   the labels for all of its successors, which we do by first determining the labels on
   all of their successors, and so on.  Recursion is a natural way to do this!
   
   
'''


def do_I_win_nim(situation):
      ''' returns "L" if this is an "L" situation
          returns "Win with " and the winning move if there is one
      '''
      if situation == [0,0,0]:
         return "L"
      else:
         for heap in range(3):
            for i in range(1,situation[heap]+1): 
               new_sit = situation[:]
               new_sit[heap] -= i                           # remove i bears from this heap
               if  do_I_win_nim(new_sit) == "L":   # If this creates a losing situation
                                                                      # for the other player, the current
                                                                      # situation is a Win for me.
                  return ("Win with", new_sit)
         return "L"                                             # if none of the new situations is
                                                                      # a losing situation, they must all
                                                                      # be winners for the other player,
                                                                      # so the current situation is a Lose
                                                                      # for me.
                                                               
         
# Show the result for a few initial situations

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]))


# Do not uncomment the next two lines of code unless you enjoy watching your 
# computer sitting there silently for many minutes.

# s = [6, 8, 11]

#print(s, do_I_win_nim(s))    

# To see how to deal efficiently with large Nim problems, see the next version!