/*
 * Nim.java
 * Created on 19-Nov-2003 by J.M. Rosengard
 *  
 * Copyright (C)2003 Syronex
 * http://w2.syronex.com/jmr/
 */

/**
 * OVERVIEW: example Nim game. user picking last token loses.
 * 
 * @author jmrose
 * package: 
 * class: Nim
 */

import java.io.*;

class Nim {   
  static BufferedReader inBuf = new BufferedReader(new InputStreamReader(System.in));

  // initialise game and control game sequence	
  static void play() {
    int nHeaps = readInt("Nim Game Example\nNumber of heaps\t(2..n)\n> ");
    String[] players = { "USER", "MACHINE" };
    int[] game = new int[nHeaps];
    for (int i = 0; i < nHeaps; i++) game[i] = (int) (Math.random() * 10) + 1;
    int lap = 0;
    int sum = -1;
    int cur = 0;
    while (sum != 0) {
      printGame(game);
      cur = lap % 2;
      System.out.println("\n" + players[cur] + " plays. ");
      if (cur == 0) userPlays(game); else machinePlays(game);
	  sum = 0;
	  for (int i = 0; i < nHeaps; i++) sum += game[i];      
      lap++;
    }
    System.out.println(players[cur] + " wins.");
  }

  // enter user moves
  static void userPlays(int[] game) {
    int heap = readInt("Which heap? ");
    int tokens = readInt("Number of tokens to remove? ");
    game[heap - 1] -= tokens;
  }

  // play machine strategy
  static void machinePlays(int[] game) {
  	int len = game.length;
	int xor = 0;
	for (int i = 0; i < len; i++) xor ^= game[i];
	int heap = 0;
	if (xor == 0) { // min move to make game last longer and push user to mistake
	  while(game[heap = (int)(Math.random() * len)] == 0);
	  game[heap]--;	
	} 
	else {  // find move leaving xor == 0
	  int[] anddedGame = new int[len];	
	  for(int i=0; i<len; i++) anddedGame[i] = game[i] & xor;
	  heap = maxIdx(anddedGame);	
	  game[heap] -= (game[heap] - (xor ^ game[heap]));	  		
	}
  }

  // helpers
  static int readInt(String prompt) {
    System.out.print(prompt);
    int val=0;
    try {
      val = Integer.parseInt(inBuf.readLine());
    } catch (Exception e) {
      System.err.println("Input error -- giving up.");
      System.exit(1);
    }
    return val;
  }
  
  // REQUIRE: ar.length > 1	
  static int maxIdx(int[] ar) {
  	int idx = 0;
  	int max = ar[0];
	for(int i=1; i<ar.length; i++) if(max < ar[i]) {
	  max = ar[i];
	  idx = i;
	} 
	return idx;
  }

  static void printGame(int[] game) {
  	System.out.print("Game state: ");
  	for(int i=0; i<game.length; i++) System.out.print("\t" + game[i]);
  }
  
  public static void main(String[] args) {
	play();
  }
}