/* Library(s) used by the Program */
import java.util.Scanner;

class Game21Matches {
	// Global scanner to read the input
	public static Scanner input = new Scanner(System.in);

	public static int PlayTurn(int f)

	{ /* Function that handles a Player turn and returns his choice */
		/* Is a valid Play (0 = No) */
		int ok = 0;

		/* Player Play */


		int j = 1;

		do {
			/* Asks how many Matches the Player wants to take ? */
			System.out.print("How many Matches will you take (1 to 4) : ");

			/* Gets the number of Matches that the Player wants to take */
			j = input.nextInt();
			input.nextLine();

			/* Verifies if the value is valid */
			if(j < 1)
				System.out.println("\nNumber too Low!\n");
			else if(j > 4)
				System.out.println("\nNumber too High!\n");
			else if((f < 4) && (j > f)) 
				System.out.println("\nThere aren't that many matches left!\n");
			else
				ok = 1;
		} while(ok == 0);

		/* Returns the number of Matches that the Player takes */
		return j;
	}

	public static int CompTurn(int f, char e, int d)
	{ /* Function that handles a Computer turn and returns his choice */
		/* Saves the number of matches that the Comp. will take */
		int r = 1;

		/* If its the Comp. turn, he uses the following algorithm */
		if (e == 'n')
		{
			/* If all the matches are left, the Computer takes 4 matches */
			if (f != 21)
			{
				if (f > 11)
					r = 5-d + ((f-1) % 5);
				else
					r = 5-d;
			}
			else
				r = 4;
		}
	
		/* Ensures that the Computer never takes more than 4 matches */


		if (r > 4)
		   r = 4;

		/* If it is not the First Player, use the following algorithm */
		if (e == 'y')
			r = 5-d;

		/* If there are only 5 matches or less, the Computer makes the smart choice */
		if ((f <= 5) && (f>1))
			r = f-1;

		/* Return the number of matches that the Comp. takes */
		return r;
	}

	public static void Game(int Type)
	{ /* Game Loop, ends when there are no matches left */
		/* Says whose turn it is (Player number) */
		int v = 1;

		/* Number of matches taken */
		int d = 0;

		/* Says how many matches are left */
		int f = 21;

		/* Says if Game is versus Player or Computer */
		char e = ' ';

		/* On games versus Computer, ask who starts */


		if(Type == 1)
		{
			do {
				/* Ask and get the choice of the Player */
				System.out.print("\nDo you want to be the First Player (y or n) : ");
				String temp;
				try {
					temp = input.nextLine();
					e = temp.charAt(0);
				} catch(Exception x) {
					e = ' ';
				}

				/* Warn the Player if the choice is invalid */
				if ((e != 'y') && (e != 'n'))
					System.out.println("\nInvalid Choice !");
			} while ((e != 'y') && (e != 'n'));
		}

		/* Main Game Loop */
		while(f > 1)
		{
			/* Show matches left */
			System.out.println("\nMatches : "+f);

			/* Say whose turn it is */
			System.out.println("Player Turn : "+v);

			/* Who should play, according to Game type */
			if(Type != 1)
			{ /* Human versus Human */
				/* Run the PlayTurn function and get the Player choice  */
				d = PlayTurn(f);
			}
			else
			{ /* Hum. versus Comp. */
				/* See who should play */
				if (!(((e == 'n') && (v == 1)) || ((e == 'y') && (v != 1))))
				{ /* Its the Hum. turn */
					/* Run the PlayTurn function and get the Play. choice */
					d = PlayTurn(f);
				}
				else
				{ /* Comp. turn */
					/* Run the CompTurn function and get his play */
					d = CompTurn(f,e,d);

					/* Shows the question and the Comp. choice */
					System.out.println("How many matches do you want to take (1 to 4) : "+d);
				}
			}

			/* Take matches from the total */
			f -= d;

			/* If no one won, Go to next turn */


			if(f > 1)
			{
				v++;
				if (v > 2)
					v = 1;
			}
		}

		/* Show who Won */
		System.out.println("\nThe Winner is Player "+v+"!\n");
	}

	public static void main(String[] args)
	{ /* Main Loop,the Menu is a Loop that only stops when the User asks to Exit */
		/* Player Option */
		int op = 0;

		/* Beginning of the Main Loop */
		do {
			/* Presentation of the Game and its Rules */


			System.out.println("Game of the 21 Matches");
			System.out.println("\nRules:");
			System.out.println("\tThere are 21 Matches.");
			System.out.println("\tEach Player can take 1 to 4 Matches in his turn.");
			System.out.println("\tThe Player that takes the last Match loses.");

			/* Initial Menu */


			System.out.println("\n1) Play, Human versus Computer");
			System.out.println("2) Play, Human versus Human");
			System.out.println("0) Exit\n");

			/* Get and Interpret the Choice */
			System.out.print("Choice: ");
			op = input.nextInt();
			input.nextLine();

			switch(op)
			{
			case 2:
				/* Run the Game */
				Game(op);
				break;
			case 1:
				/* Run the Game */
				Game(op);
				break;
			case 0:
				/* Exit the Game */
				break;
			default:
				/* Tell the User that he made an Invalid Choice */
				System.out.println("\nInvalid Number !");
			}
		} while(op != 0);
	}
}