//nim5OK.c  ---  NIM GAME, by tsaiwn@csie.nctu.edu.tw
//prototype by tsaiwn@csie.nctu.edu.tw
//******
// ..這版本 就把 nim3.c  加上 computer 可贏就贏的策略
//  C++ 本來就認識 bool, false, true; C則可用 typedef enum...bool;
/**********
  請仔細研讀前一版 num2.c 中的說明 與 Lab-11 的說明 
 *******************************************************///////////   
/// 若要用  Turbo C++ 的分割劃面可以參考:
///    ftp://ftp.csie.nctu.edu.tw/pub/CSIE/course/cs2/textwin.cpp
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <errno.h>

#ifndef __cplusplus
  //typedef int bool;    // 與 #define bool int  同效果, 但要加分號;
 typedef enum {false=0, true } bool;   // 更好 :-) 跟 C++ 同樣!
  // C++/Java 已經認識 false, true; 但 bool 在 Java 是 boolean
#endif

#define MAX_PILE 7
#define MAX_STONE 31
#define MIN_STONE 5

/// =================> use Global variables 比較方便但要小心處理!
int nPile;  /* number of Pile */
int nStone[MAX_PILE + 1];   // 第 0 堆不要用, 用 1 到 7  !!
         // 注意不用第 0 堆是因這樣跟人的習慣比較像 :-)
int pTake, nTake;   // take from which pile, how many stones
bool quit;  // indicate that user want to Stop playing

bool lastToWin;  // 1 == 拿到最後一個贏,  0 == 拿到最後一個贏輸 
bool userFirst;   // user want to Go first
bool gameBegin;  // used in printStatus( )
char msgWin[ ][33] = { "拿到最後一顆輸Lose!", "拿到最後一顆贏Win!" };

bool gameOver( );   // indicate somebody took the last stone
void userTurn(void),  computerTurn(void);
void prepareGame(void);  // 把game 用到的整體(global;共用)變數準備好.
void playGame(void);
void printStatus(void);  // 印出各堆石頭狀況.
void hello(void) {
    printf("NIM 是從many多石頭堆中輪流拿, \r\n");
    // 有些compiler下不能寫 "許" ? compile時會出問題! 故寫 many 多 :-)
    printf(" ..NIM 每次只能從一堆拿, 至少拿一個, 至多把該堆拿光,\r\n");
    printf(" .. 可規定拿到最後一顆贏, 或拿到最後一顆輸!\r\n\n");
}

bool askYN( ){
    bool ans;   // 1 == true == Yes, 0 == false == No
    static char buf[333];
    fgets(buf, sizeof(buf), stdin);
    if(buf[0] == 'N' || buf[0] =='n') return false;
    if(buf[0] == 0 ) return false;   //  '\0'  ==  0
    return true;   // We like the user to play :-) So default is YES
}
void clrERR( ) {
   errno = 0; // clear  errno in <errno.h>
}//clrErr

int main( ) {
   bool playAgain;  // Local variable is enough
   hello( );
   srand( time(0) &0xfffff );  // true random, see "man 3 time"
   playAgain = true;  // force to play :-)
   while(playAgain) {
      prepareGame( );
      playGame( );
      printf("Want to play again (Y, N)? ");
      playAgain = askYN( );
   }
   printf("\r\nThank you for your play!\nCome to play again!\n");
   return 0;
} // main

///////////////////////////////////////////////////////////
void prepareGame(void) {
    int i;
    lastToWin = userFirst =  (38==38);  // true
    if(rand( ) % 100 >= 50) lastToWin = false;  // 50%, 就是 %2 == 1
    nPile = 3 + rand( ) % (MAX_PILE-3+1);  // 3..7 
    for(i=1; i <= nPile; ++i) {  /// 注意由第一堆算起
       nStone[i] = MIN_STONE + rand( ) % (MAX_STONE -MIN_STONE +1);
    }
} // prepareGame

void printStatus( ){
    int i;
    printf("There are 共有 %d pile堆石頭:\r\n", nPile);
    printf("   P_%d: %d", 1, nStone[1]);  // Note that 沒第 0 堆
    for(i=2; i <= nPile; ++i) {  // then pile-2, pile-3, ...
       printf(",  P_%d: %d", i, nStone[i]);
    }
    printf("\r\n");
    if(gameBegin) {   // 只有剛開始才印這句
       printf("!!! 注意 %s! %s!!\r\n",  
               msgWin[lastToWin], msgWin[lastToWin]);
       gameBegin = false; //So that won't print again
    }
} // printStatus

bool gameOver( ) {  // Note that Pile# is 1..nPile
   int i, totalStone=0;
   for(i=1; i <= nPile; ++i) totalStone += nStone[i];
   return (totalStone <= 0);  // no more stone == gameOver
}

void userTurn( ) {
    bool goodData;   // Note that "quit" is a Global variable
    static char buf[88];
 //again:
    while( true ) {  // not got good data yet
       quit = false;  // assume continue to play !
       printf("Take from which Pile? ");
       fgets(buf, sizeof(buf), stdin);
       pTake = (int)atol(buf);
       // 防呆處理: 要確保輸入資料正確, 不可讓 user 亂輸入..
       // ... 若該堆 0 個也不要讓他拿喔!
       if(feof(stdin)) { clrERR( ); pTake = -1;  } // 讀到 CTRL_Z
       if(pTake < 0) {
            // 輸入負數看要如何處理, 可當作錯, 也可表示不玩了 :-) 
            quit = true;  // want to quit from the game
            break;
       }
       if(pTake ==0 ) {
           printf(" Sorry, there is no pile#0\r\n");
           continue;  // goto again;
       }
       if(pTake > nPile ) {
           printf(" ? Which pile? "); // print 沒那麼多堆喔 !
           continue;   // goes back to while( )  (again:)
       }
      //again22:
       while( true )  {  // Loop forever
          printf(" from Pile# %d, take how many stones (1..%d)? ",
              pTake, nStone[pTake]);
          fgets(buf, sizeof(buf), stdin);
          nTake = (int)atol(buf);
          // 防呆處理: 要確保輸入資料正確, 不可拿超過
          ///*** how ? 
          if(feof(stdin)){clrERR( ); nTake = -1;} // 輸入 CTRL_Z
          if(nTake < 0) { 
             // 如何允許他後悔改從別堆 Pile 拿 ?
             goodData = false; // set FLAG for outside while Loop
             break;  // leave this while Loop
          } // if
          if(nTake == 0 || nTake > nStone[pTake]) {
              printf(" 耍白痴?? 不要亂打啦!\r\n");
              continue;  // goto again22;
          }
          goodData = true;   // data is good :-)
          break;  //
       } // while
       if( !goodData ) continue; // goto again;
       break;  // OK, 取得 pTake 堆 與  nTake
    } // while !dataOK
    if(quit) {
        fprintf(stderr, " You chicken!!! \r\n");
        return;  // user 不玩了 
    }
    nStone[pTake] -= nTake;
    printStatus( );
} // userTurn

void playGame(void) {
   int userWin;  // Local variable is enough
   gameBegin = true;// 每次game開始, 要印出拿最後一個會贏還是會輸
   quit = false;   // indicate continue to play
   printStatus( );  // 印出目前各堆石頭, 若第一次印要印上列說的
   printf("\r\n ..Want to go first (Y, N)? ");
   userFirst =  askYN( );
   userWin = false;
   // Game starts ..
   if(userFirst) userTurn( );
   if(gameOver( ) && lastToWin) userWin = true;
   while(!quit && !gameOver( )){ // take turn till no more stone
      computerTurn( );
      if(gameOver( )) {
         if(lastToWin) userWin = false; else userWin = true;
         break;
      }
      userTurn( );
      if(gameOver( )) {
         userWin = false;
         if(lastToWin) userWin = true;  // user took the last
         break;
      }
   } // while
   if(userWin) {
      printf(" Congratulations -- You Win!\r\n");
   }else{
      printf(" SOOORRRY Sorry! -- Ha Ha Ha! -- I Won!\r\n");
   }
} // playGame
/************
-- 
 Proof techniques #1: Proof by Induction.
 Q: 試用歸納法證明:飯永遠吃不飽.
    1. 吃一粒米顯然不會飽
    2. 假設吃了 n 粒米沒有飽
       再吃一粒米顯然也不會飽, 就是說吃 n+1 粒米也不會飽
      由此可推得米飯永遠吃不飽 !
   QED.   (QED translates from the Latin as "So what?")
((((((((((((((((((((((((((()))))))))))))))))))))))))))))
********************************************************/

// NIM Game 電腦必贏的密技 ---
//#######################
   // #define MAX_PILE 7
   // int nPile = 3 + rand( )%(MAX_PILE -3 + 1);  // 3..7
   // int nStone[MAX_PILE + 1];    // 第 0 堆不用, 所以要多一堆
   // assume that the global variable nPile is the #of pile in this game.
   // assume that  nStone[1] .. nStone[nPile]  are 各堆石頭數
   // 注意第0堆不用, 浪費一個元素沒關係! 這會方便許多, why ?
//////
int findPile(int sumXOR); // function to find the available pile
int atMostOne(int p, int n);  // to check if we reach to the critical step
    // this function is ONLY useful for the one takes last object to lose
    // i.e., check to 看看若從第 p 堆拿走 n 個後是否造成各堆最多一個?
void computerTurn( ) {     // 把 array 多留一個元素, 第0個不要用
   int pp, nn, remain, i;   //  注意不是 0..n-1,  我們用 1..n 堆!
   int sum = 0;
   for(i=1; i <= nPile; ++i)  sum ^= nStone[i];    // 不用第 0 堆!
   if(sum == 0) {
        nn = 1; // 因 XOR 起來是0, 表示必輸的, 隨便拿一個等對方拿錯
          // ..從任一有石頭的堆(pp) 拿走一個 (nn = 1);
         // ..  (用 while 找 pp,  很簡單, 留給 同學們 想 :-)
        // ..或從最多石頭那堆拿一個更好!
   } else {   // 會贏, 但是要找出如何拿..
      pp = findPile(sum);  // find which pile that we can win in normal NIM   
           //  找出該拿哪一堆才會贏, 先用拿最後一個會贏的策略
      remain = nStone[pp] ^ sum;  // 要拿成剩下 remain 這麼多 
      nn = nStone[pp] - remain;    // 算出該拿 nn 這麼多才會使 sum 是 0
      //special process for last object to lose, 若拿最後是輸, 要特別處理
      if( ( ! lastToWin) && atMostOne(pp, nn) ) {    
          if(remain==1) ++nn; //還有, 拿光它,把剩下的那個也拿走;例 1,1,1,6
          if(remain==0) --nn; //放回一個!Why?例 1,1,5 會誤判要拿成 1, 1, 0
      } // if lastToWin== false 表示拿到最後的是輸
   }//if 
   nStone[pp] -= nn;  // 從 pp 堆拿走 nn 個, 阿就該堆減去 nn 啦 
   fprintf(stdout, "..I just took %d stone(s) from pile#%d\n",nn, pp);
   printStatus( );  // tell user 目前各堆的狀況..
}
int findPile(int sum) {  // 找 #of objects 與 sum 做 xor 後會變少的堆
   int i=1;
   for(i=1; i<=nPile; ++i)    // 從第 1 堆找到第  nPile 堆
       if( (sum ^ nStone[i] ) < nStone[i]) return i; // XOR 後變小表示可
   // impossible to here --- 因不可能找不到任何一堆! wikipedia.org 有證明
   fprintf(stderr, " ? 有問題喔! impossible to here!\n");
   return -1; // 故意回傳 -1
} // findPile
int atMostOne(int p, int n) {   // 看看從第 p 堆拿走 n 個會不會每堆最多一個
       // 若從第 p 堆若拿走 n 個後, 沒有一堆超過一個石頭, 則傳回 1 表示 yes
   int i, ans = 1;  // assume yes;  也可像我之前範例使用 true/false
   nStone[p] -= n ;   // 注意是 減等於 (-=) ,  先假裝第 p 堆拿走 n 個
   for(i=1; i<=nPile; ++i)  // check all piles (heaps) 1..nPile
        if(nStone[i] > 1) ans = 0;  // at least one pile has stones > 1  
   nStone[p] += n ;  // 把 n 個放回第 p 堆! 因我們只是檢查 
   return ans;    // 若要用 tru/false, 函數開始須  bool ans = true;
} // atMostOne in each pile (heap)
///////////////////////////////////////////////