// Practicum proefstuderen 2014: recursie
// (expres) geen klassestructuren gebruikt om het 
// simpel te houden. Ook eenvoudige interface,
// dus geen uitvoerige tests of de invoer wel uit
// een getal bestaat, bijvoorbeeld

#include <iostream>
#include <stdlib.h>
#include <cstdlib>
#include <ctime>
using namespace std;

// *********************************************************************
// nim versie 1
// Gegeven een stapel met n lucifers; twee spelers mogen om de beurt 
// 1 of 2 lucifers van de stapel pakken
// Kan de beginnende speler altijd winnen? Is er een winnende strategie?


const int Max = 60;
// duurt al ongeveer een minuut om de berekenen of de stand winnend is of niet



void leesin (int & lucifers){
// leest het aantal lucifers in; 
// alleen waarden tussen 1 (>1) en Max (<= Max) zijn toegestaan

   lucifers = 0;
   while ( (lucifers <= 1) || (lucifers > Max) ) {
   // zolang nog geen goed aantal lucifers is ingelezen ... opnieuw vragen
      cout << "Geef het aantal lucifers, gevolgd door <enter> ... " << endl;
      cout << "Je moet een waarde >= 2 en <= " << Max << " invoeren!"<< endl;  
      cin >> lucifers;
      if ((lucifers < 1) || (lucifers > Max)) {
         cout << "Te veel of negatief aantal lucifers " << endl;
      }
      if (lucifers == 1) {
         cout << "Te weinig lucifers om dit spel leuk te spelen" << endl;
	  }
   } // while

} // leesin


void print (int lucifers){
// drukt lucifers lucifers af op het beeldscherm
// in groepjes van 10

   int teller;
   for (teller = 1; teller <= lucifers; teller++){
      cout << "o";
      if (teller%10 == 0)
         cout << " ";   
   }
   cout << endl;
   for (teller = 1; teller <= lucifers; teller++){
      cout << "|";
      // cout << "\u2551"; 
      // dit geeft mooiere lucifers, maar je moet daarvoor wel 
      // Character Encoding Unicode (UTF8) hebben
      if (teller%10 == 0)
         cout<< " ";
   }
   cout << endl<< endl;

} // print


int min(int x, int y) {
// berekent het minimum van x en y

   if (x < y)
      return x;
   else
      return y;

} // min


int winnend (int lucifers){
// geeft de winnende zet terug, dat wil zeggen het
// aantal lucifers (1 of 2) dat je kan pakken om te winnen.
// als de stand niet winnend is wordt de waarde 0 geretourneerd.
// lucifers is het aantal lucifers dat op dit moment op tafel ligt

   int i;
   int maximaal;
   if (lucifers == 0)
   // als er geen lucifers meer liggen heeft de tegenstander blijkbaar 
   // net de laatste gepakt. Hij heeft dan gewonnen, dus jij hebt verloren
      return 0;
   else {
   // alle mogelijke zetten aflopen; 
      maximaal = min(2,lucifers);
      // je mag er maximaal 2 wegnemen, maar je kunt er ook
      // niet meer wegnemen dan het aantal dat er al ligt

      for (i = 1; i<=maximaal; i++){
      // i lucifers weghalen
         if (winnend(lucifers - i) == 0){
         // als deze stand niet winnend (verliezend) is voor de tegenstander
	 // is die voor jou juist winnend!
            return i;
         }
      } 
      return 0;	 
      // helaas geen winnende zet gevonden
   } //else

} // winnend


void nim1spelen ( ){
// gebruiker begint en speelt het spel tegen de computer;
// de computer doet steeds een random (willekeurige) zet.
// de gebruiker krijgt telkens een hint wat de beste zet is

   int lucifers;
   int goedezet;
   // waarde wordt 0 als er geen winnende zet is, anders geeft
   // goedezet het aantal lucifers aan dat je moet pakken om te winnen
   int zoveel;
   
   leesin(lucifers);
   cout << endl;
   print(lucifers);

   while (lucifers > 0) {

      goedezet = winnend(lucifers);
      // winnende zet wordt berekend
      cout << " Jij bent aan de beurt." << endl;
      cout << " Er zijn nog " << lucifers << " lucifers. " << endl;
      if (goedezet == 0) 
          cout << " Geen winnende zet " << endl;
      else {
	  // hint aan de gebruiker
          cout << " Om te winnen moet je er " << goedezet << " wegpakken.";
          cout << endl << endl;
      }
      zoveel = 0; 
      while ((zoveel < 1) || (zoveel > 2 ) || (zoveel > lucifers)) {
	 // zet van de gebruiker inlezen
         cout << " Hoeveel wil je er wegnemen?" << endl;
         cin >> zoveel;
         if ((zoveel < 1) || (zoveel > 2 ) || (zoveel > lucifers))
	    cout << " Nog een keer............ " << endl;
      }
      lucifers = lucifers - zoveel;
      // de gebruiker heeft een zet gedaan
      
      if (lucifers == 0)
        cout << " Je hebt gewonnen ! " << endl;
      else {
      // randomzet van de computer;
         zoveel = rand( )%2 + 1;
	     if (zoveel > lucifers) 
	     // om te voorkomen dat computer er 2 neemt als er maar 1 ligt
	        zoveel = lucifers;
	     cout << " De computer is nu aan de beurt en neemt er " << zoveel;
             cout << endl << endl;
	     lucifers = lucifers - zoveel;
	     // de computer heeft een zet gedaan
	 
	     if (lucifers == 0)
	        cout << " Je hebt verloren " << endl; 
	     else
	        print(lucifers);
	  } // else: randomzet

   } //while

}  // nim1spelen


// *******************************************************************
// nim versie 2
// Gegeven een stapel met n lucifers; twee spelers mogen om de beurt 
// een zeker maximaal aantal lucifers van de stapel pakken. In de eerste
// zet mag maximaal n - 1 weggenomen worden; in elke andere zet mag 
// degene die aan de beurt is maximaal 2 keer het aantal lucifers dat de 
// tegenstander in de vorige beurt heeft weggepakt wegnemen
// Kan de beginnende speler altijd winnen? Is er een winnende strategie?


int winst (int lucifers, int maxwegnemen){
// geeft de winnende zet terug, dat wil zeggen het aantal
// lucifers dat je kan pakken om te winnen.
// als de stand niet winnend is wordt de waarde 0 geretourneerd.
// lucifers is het aantal lucifers dat op dit moment op tafel ligt
// maxwegnemen is het aantal lucifers dat de speler die aan de
// beurt is maximaal mag pakken

   int i;
   int maximaal;
   
   if (lucifers == 0)
   // als er geen lucifers meer liggen heeft de tegenstander blijkbaar 
   // net de laatste gepakt. Hij heeft dan gewonnen, dus jij hebt verloren
      return 0;
      
   else {
   // alle mogelijke zetten aflopen 
      maximaal = min(maxwegnemen, lucifers);
      // je mag er maximaal maxwegnemen wegpakken, maar je kunt er ook
      // niet meer wegnemen dan het aantal dat er al ligt

      for (i = 1; i<=maximaal; i++){
         if (winst(lucifers - i, 2*i) == 0){
         // i lucifers weghalen
            return i;
         }
      } 
      return 0;	 
      // geen winnende zet gevonden
   } 
} // winnend



void nim2spelen ( ){

   int lucifers;
   int maxwegnemen;
   int goedezet;
   // waarde wordt 0 als er geen winnende zet is
   int zoveel;
   
   leesin(lucifers);
   maxwegnemen = lucifers - 1;
   // dit mag je in de eerste beurt maximaal wegpakken
   cout << endl;
   print(lucifers);
       
   while (lucifers > 0) {
      
      goedezet = winst(lucifers, maxwegnemen);
      // winnende zet wordt berekend
      cout << " Jij bent aan de beurt." << endl;
      cout << " Er zijn nog " << lucifers << " lucifers,";
      cout << " waarvan je er maximaal " << maxwegnemen << " mag wegpakken, ";
      cout << endl;
      if (goedezet == 0) 
          cout << " Geen winnende zet " << endl;
      else { 
	  // hint aan de gebruiker
          cout << " Om te winnen kun je er " << goedezet << " wegpakken";
          cout << endl << endl;
      }
      zoveel = 0; 
      while ((zoveel < 1) || (zoveel > maxwegnemen ) || (zoveel > lucifers)) {
	 // zet van de gebruiker inlezen
         cout << " Hoeveel wil je er wegnemen?" << endl;
         cin >> zoveel;
         if ((zoveel < 1) || (zoveel > maxwegnemen ) || (zoveel > lucifers))
	        cout << " Nog een keer............ " << endl;
      }
      lucifers = lucifers - zoveel;
      // de gebruiker heeft een zet gedaan
      maxwegnemen = 2*zoveel;
      // dit mag de computer zometeen maximaal wegnemen
	  
      if (lucifers == 0)
         cout << " Je hebt gewonnen ! " << endl;
      else {
      // randomzet van de computer;
         zoveel = rand( )%maxwegnemen + 1;
	 if (zoveel > lucifers)
	 // om te voorkomen dat de computer er meer neemt dan er liggen
	    zoveel = lucifers;
	    cout << " De computer neemt er " << zoveel << endl << endl;
	    lucifers = lucifers - zoveel;
	    // de computer heeft een zet gedaan
	    maxwegnemen = 2*zoveel;
	    // dit mag de gebruiker zometeen maximaal wegpakken
	 
	    if (lucifers == 0)
	       cout << " Je hebt verloren " << endl; 
    	    else
	       print(lucifers);
      } // else: randomzet 
   } // while lucifers > 0
}  // nim2spelen





//************************************************************************
// Hoofdprogramma

int main (){

// nim1 of nim2 
// **************************************************************
  
  char keuze = '6';
  int zet;
  int aantal; // aantal lucifers
  srand ((unsigned)time(0));
  // randomgenerator aanzetten voor random zetten tegen computer

  while (!(keuze == '5')) {

     cout << " Maak je keuze <enter> " << endl; 
     cout << "1: als je nim versie 1 wilt spelen" << endl;
     cout << "2: als je alleen wilt weten of nim versie 1 winnend is"<< endl;
     cout << "3: als je nim versie 2 (Fibonacci nim) wilt spelen" << endl;
     cout << "4: als je alleen wilt weten of nim versie 2 winnend is" << endl;
     cout << "5: als je wilt stoppen" << endl;
     cin >> keuze;
  
  
     switch (keuze) {
        case '1': nim1spelen ( ); break;
        case '2': leesin(aantal);
	          zet = winnend(aantal);
	          cout << "Nim versie 1 met " << aantal << " lucifers is "; 
	          if (zet == 0) 
                     cout << " NIET WINNEND " << endl;
                  else { 
                     cout << "WINNEND!" << " Winnende zet: "<< zet;
                     cout << " lucifer wegpakken" << endl;
                  }
	          break;
        case '3': nim2spelen ( ); break;
        case '4': leesin(aantal);
	          zet = winst(aantal, aantal-1);
	          cout << "Nim versie 2 met "<< aantal << " lucifers is "; 
	          if (zet == 0) 
                     cout << " NIET WINNEND " << endl;
                  else { 
                     cout << " WINNEND!" << " Winnende zet: "<< zet;
                     cout << " lucifer wegpakken" << endl;
                  }
                  break;
	case '5': exit(1);
        default:  cout << "Niet toegestane keuze "<< endl;
	       
     }
  }	
    
  return 0;
}