// file:    nim.C
// author:  Robert Keller
// purpose: nim-playing program originally developed in rex, transcribed to C++ 
// compile: g++ nim.C -L. -lpolya -lm

// User types a list of numbers representing nim piles.  Program responds with
// a revised set of piles.  The version of nim being played is that the
// player taking the last stone wins.

// This code is inadequately documented as it stands.
// Please see info/nim.doc and the solutions to a2 for more information.

#include "polya.H"

// prototypes
Polylist arbitrary_move(Polylist L);
int bad_input(Polylist L);
Polylist decrement_max(Polylist L, integer M);
Polylist make_nim_sum_zero(integer Sum, Polylist L);
integer max_list(Polylist L);
Polylist nim(Polylist L);
integer nim_sum(integer M, integer N);
integer nim_sum_list(Polylist L);


main()
{
Poly P;

while( cin >> P )
  {
  if( bad_input(P) )
    cout << "sorry, only lists of positive integers are allowed" << endl;
  else
    {
    Polylist L = P;
    cout << nim(L) << endl;
    }
  }
}


//
// return a new list of piles
//

Polylist nim(Polylist L)
{
integer Sum = nim_sum_list(L);
if( Sum == 0 )
  return arbitrary_move(L);
else
  return make_nim_sum_zero(Sum, L);
}


//
// the main strategy
//

Polylist make_nim_sum_zero(integer Sum, Polylist L)
{
integer pile = first(L);
Polylist piles = rest(L);
integer delta = nim_sum(Sum, pile);
if( delta <= pile )
  {
  if( delta == 0 )
    return piles;
  else
    return cons(delta, piles);
  }
else
  return cons(pile, make_nim_sum_zero(Sum, piles));
}


//
// compute the nim sum
//

integer nim_sum(integer M, integer N)
{
if( M == 0 )
  return N;
if( N == 0 )
  return M;
return (M+N)%2 + 2*nim_sum(M/2, N/2);
}


//
// compute the nim sum of a list
//

integer nim_sum_list(Polylist L)
{
if( isEmpty(L) )
  return 0;
else
  return nim_sum(first(L), nim_sum_list(rest(L)));
}


//
// make a move when you can't guarantee a win
//

Polylist arbitrary_move(Polylist L)
{
return decrement_max(L, max_list(L));
}


//
// decrement the largest pile
//

Polylist decrement_max(Polylist L, integer M)
{
integer F = first(L);
if( F == M )
  return F > 1 ? cons(M-1, rest(L)) : rest(L);
return cons(F, decrement_max(rest(L), M));
}


//
// find the max of a non-empty list
//

integer max_list(Polylist L)
{
integer result = first(L);
L = rest(L);
while( !isEmpty(L) )
  {
  if( integer(first(L)) > result )
    result = integer(first(L));
  L = rest(L);
  }
return result;
}


//
// test for bad input
//

int bad_input(Polylist L)
{
if( !isList(L) || isEmpty(L) )
  return 1;
while( !isEmpty(L) )
  {
  if( !isInteger(first(L)) || integer(first(L)) <= 0 )
    return 1;
  L = rest(L);
  }
return 0;
}