# nimGame.py
# Game of Nim


import random


def makeMove(piles):
  nSum = nimSum(piles)
  n = len(piles)

  if (nSum != 0):
    for i in range(n):
      if ((piles[i] ^ nSum) < piles[i]):  # if legal
        pileIdx = i
        nChips = piles[i]-(piles[i] ^ nSum)
        piles[i] = (piles[i] ^ nSum)
        break
  else:
    # randomly choose a non-empty pile and remove some chips
    non_zero_indices = []
    for i in range(n):
      if piles[i] > 0:
        non_zero_indices.append(i)
    pileIdx = random.choice(non_zero_indices)
    nChips = random.randint(1, piles[pileIdx])
    piles[pileIdx] -= nChips

  return pileIdx, nChips


def nimSum(piles):
  nSum = piles[0]
  for i in range(1, len(piles)):
    nSum = nSum ^ piles[i]
  return nSum



def isGameOver(piles):
  for p in piles:
    if p != 0:
      return False
  return True



piles = [3, 4, 5]

if nimSum(piles) != 0:
  print("Prediction: COMPUTER will win")
else:
  print("Prediction: HUMAN will win")

isComputer = True
print("\nGAME STARTS")
while not isGameOver(piles):
  print("Piles:", piles)
  pileIdx, nChips = makeMove(piles)
  name = "COMPUTER" if isComputer else "HUMAN"
  print(name, "removes", nChips, "chips from pile", pileIdx)
  isComputer = not isComputer

print("Piles:", piles)
if isComputer:
  print("\nCOMPUTER lost")
else:
  print("\nHUMAN lost")