/* Game Description-    'A game is played between two players and there are N piles    of stones such that each pile has certain number of stones.    On his/her turn a player selects a pile and can take any    non-zero number of stones upto 3 (i.e- 123)    The player who cannot move is considered to lose the game    (i.e. one who take the last stone is the winner).    Can you find which player wins the game if both players play    optimally (they don't make any mistake)? '    A Dynamic Programming approach to calculate Grundy Number    and Mex and find the Winner using Sprague - Grundy Theorem. */   #include       using     namespace     std  ;   /* piles[] -> Array having the initial count of stones/coins    in each piles before the game has started.    n -> Number of piles    Grundy[] -> Array having the Grundy Number corresponding to    the initial position of each piles in the game    The piles[] and Grundy[] are having 0-based indexing*/   #define PLAYER1 1   #define PLAYER2 2   // A Function to calculate Mex of all the values in that set   int     calculateMex  (  unordered_set   <  int  >     Set  )   {      int     Mex     =     0  ;      while     (  Set  .  find  (  Mex  )     !=     Set  .  end  ())      Mex  ++  ;      return     (  Mex  );   }   // A function to Compute Grundy Number of 'n'   int     calculateGrundy  (  int     n       int     Grundy  [])   {      Grundy  [  0  ]     =     0  ;      Grundy  [  1  ]     =     1  ;      Grundy  [  2  ]     =     2  ;      Grundy  [  3  ]     =     3  ;      if     (  Grundy  [  n  ]     !=     -1  )      return     (  Grundy  [  n  ]);      unordered_set   <  int  >     Set  ;     // A Hash Table      for     (  int     i  =  1  ;     i   <=  3  ;     i  ++  )      Set  .  insert     (  calculateGrundy     (  n  -  i       Grundy  ));      // Store the result      Grundy  [  n  ]     =     calculateMex     (  Set  );      return     (  Grundy  [  n  ]);   }   // A function to declare the winner of the game   void     declareWinner  (  int     whoseTurn       int     piles  []      int     Grundy  []     int     n  )   {      int     xorValue     =     Grundy  [  piles  [  0  ]];      for     (  int     i  =  1  ;     i   <=  n  -1  ;     i  ++  )      xorValue     =     xorValue     ^     Grundy  [  piles  [  i  ]];      if     (  xorValue     !=     0  )      {      if     (  whoseTurn     ==     PLAYER1  )      printf  (  'Player 1 will win  n  '  );      else      printf  (  'Player 2 will win  n  '  );      }      else      {      if     (  whoseTurn     ==     PLAYER1  )      printf  (  'Player 2 will win  n  '  );      else      printf  (  'Player 1 will win  n  '  );      }      return  ;   }   // Driver program to test above functions   int     main  ()   {      // Test Case 1      int     piles  []     =     {  3       4       5  };      int     n     =     sizeof  (  piles  )  /  sizeof  (  piles  [  0  ]);      // Find the maximum element      int     maximum     =     *  max_element  (  piles       piles     +     n  );      // An array to cache the sub-problems so that      // re-computation of same sub-problems is avoided      int     Grundy  [  maximum     +     1  ];      memset  (  Grundy       -1       sizeof     (  Grundy  ));      // Calculate Grundy Value of piles[i] and store it      for     (  int     i  =  0  ;     i   <=  n  -1  ;     i  ++  )      calculateGrundy  (  piles  [  i  ]     Grundy  );      declareWinner  (  PLAYER1       piles       Grundy       n  );      /* Test Case 2    int piles[] = {3 8 2};    int n = sizeof(piles)/sizeof(piles[0]);    int maximum = *max_element (piles piles + n);    // An array to cache the sub-problems so that    // re-computation of same sub-problems is avoided    int Grundy [maximum + 1];    memset(Grundy -1 sizeof (Grundy));    // Calculate Grundy Value of piles[i] and store it    for (int i=0; i <=n-1; i++)    calculateGrundy(piles[i] Grundy);    declareWinner(PLAYER2 piles Grundy n); */      return     (  0  );   }   

   import     java.util.*  ;   /* Game Description-   'A game is played between two players and there are N piles   of stones such that each pile has certain number of stones.   On his/her turn a player selects a pile and can take any   non-zero number of stones upto 3 (i.e- 123)   The player who cannot move is considered to lose the game   (i.e. one who take the last stone is the winner).   Can you find which player wins the game if both players play   optimally (they don't make any mistake)? '   A Dynamic Programming approach to calculate Grundy Number   and Mex and find the Winner using Sprague - Grundy Theorem. */   class   GFG     {       /* piles[] -> Array having the initial count of stones/coins    in each piles before the game has started.   n -> Number of piles   Grundy[] -> Array having the Grundy Number corresponding to    the initial position of each piles in the game   The piles[] and Grundy[] are having 0-based indexing*/   static     int     PLAYER1     =     1  ;   static     int     PLAYER2     =     2  ;   // A Function to calculate Mex of all the values in that set   static     int     calculateMex  (  HashSet   <  Integer  >     Set  )   {      int     Mex     =     0  ;      while     (  Set  .  contains  (  Mex  ))      Mex  ++  ;      return     (  Mex  );   }   // A function to Compute Grundy Number of 'n'   static     int     calculateGrundy  (  int     n       int     Grundy  []  )   {      Grundy  [  0  ]     =     0  ;      Grundy  [  1  ]     =     1  ;      Grundy  [  2  ]     =     2  ;      Grundy  [  3  ]     =     3  ;      if     (  Grundy  [  n  ]     !=     -  1  )      return     (  Grundy  [  n  ]  );      // A Hash Table      HashSet   <  Integer  >     Set     =     new     HashSet   <  Integer  >  ();         for     (  int     i     =     1  ;     i      <=     3  ;     i  ++  )      Set  .  add  (  calculateGrundy     (  n     -     i       Grundy  ));      // Store the result      Grundy  [  n  ]     =     calculateMex     (  Set  );      return     (  Grundy  [  n  ]  );   }   // A function to declare the winner of the game   static     void     declareWinner  (  int     whoseTurn       int     piles  []        int     Grundy  []       int     n  )   {      int     xorValue     =     Grundy  [  piles  [  0  ]]  ;      for     (  int     i     =     1  ;     i      <=     n     -     1  ;     i  ++  )      xorValue     =     xorValue     ^     Grundy  [  piles  [  i  ]]  ;      if     (  xorValue     !=     0  )      {      if     (  whoseTurn     ==     PLAYER1  )      System  .  out  .  printf  (  'Player 1 will winn'  );      else      System  .  out  .  printf  (  'Player 2 will winn'  );      }      else      {      if     (  whoseTurn     ==     PLAYER1  )      System  .  out  .  printf  (  'Player 2 will winn'  );      else      System  .  out  .  printf  (  'Player 1 will winn'  );      }      return  ;   }   // Driver code   public     static     void     main  (  String  []     args  )      {          // Test Case 1      int     piles  []     =     {  3       4       5  };      int     n     =     piles  .  length  ;      // Find the maximum element      int     maximum     =     Arrays  .  stream  (  piles  ).  max  ().  getAsInt  ();      // An array to cache the sub-problems so that      // re-computation of same sub-problems is avoided      int     Grundy  []     =     new     int  [  maximum     +     1  ]  ;      Arrays  .  fill  (  Grundy       -  1  );      // Calculate Grundy Value of piles[i] and store it      for     (  int     i     =     0  ;     i      <=     n     -     1  ;     i  ++  )      calculateGrundy  (  piles  [  i  ]       Grundy  );      declareWinner  (  PLAYER1       piles       Grundy       n  );      /* Test Case 2    int piles[] = {3 8 2};    int n = sizeof(piles)/sizeof(piles[0]);    int maximum = *max_element (piles piles + n);    // An array to cache the sub-problems so that    // re-computation of same sub-problems is avoided    int Grundy [maximum + 1];    memset(Grundy -1 sizeof (Grundy));    // Calculate Grundy Value of piles[i] and store it    for (int i=0; i <=n-1; i++)    calculateGrundy(piles[i] Grundy);    declareWinner(PLAYER2 piles Grundy n); */      }   }      // This code is contributed by PrinciRaj1992   

   ''' Game Description-     'A game is played between two players and there are N piles     of stones such that each pile has certain number of stones.     On his/her turn a player selects a pile and can take any     non-zero number of stones upto 3 (i.e- 123)     The player who cannot move is considered to lose the game     (i.e. one who take the last stone is the winner).     Can you find which player wins the game if both players play     optimally (they don't make any mistake)? '         A Dynamic Programming approach to calculate Grundy Number     and Mex and find the Winner using Sprague - Grundy Theorem.        piles[] -> Array having the initial count of stones/coins     in each piles before the game has started.     n -> Number of piles         Grundy[] -> Array having the Grundy Number corresponding to     the initial position of each piles in the game         The piles[] and Grundy[] are having 0-based indexing'''   PLAYER1   =   1   PLAYER2   =   2   # A Function to calculate Mex of all   # the values in that set    def   calculateMex  (  Set  ):   Mex   =   0  ;   while   (  Mex   in   Set  ):   Mex   +=   1   return   (  Mex  )   # A function to Compute Grundy Number of 'n'    def   calculateGrundy  (  n     Grundy  ):   Grundy  [  0  ]   =   0   Grundy  [  1  ]   =   1   Grundy  [  2  ]   =   2   Grundy  [  3  ]   =   3   if   (  Grundy  [  n  ]   !=   -  1  ):   return   (  Grundy  [  n  ])   # A Hash Table    Set   =   set  ()   for   i   in   range  (  1     4  ):   Set  .  add  (  calculateGrundy  (  n   -   i     Grundy  ))   # Store the result    Grundy  [  n  ]   =   calculateMex  (  Set  )   return   (  Grundy  [  n  ])   # A function to declare the winner of the game    def   declareWinner  (  whoseTurn     piles     Grundy     n  ):   xorValue   =   Grundy  [  piles  [  0  ]];   for   i   in   range  (  1     n  ):   xorValue   =   (  xorValue   ^   Grundy  [  piles  [  i  ]])   if   (  xorValue   !=   0  ):   if   (  whoseTurn   ==   PLAYER1  ):   print  (  'Player 1 will win  n  '  );   else  :   print  (  'Player 2 will win  n  '  );   else  :   if   (  whoseTurn   ==   PLAYER1  ):   print  (  'Player 2 will win  n  '  );   else  :   print  (  'Player 1 will win  n  '  );   # Driver code   if   __name__  ==  '__main__'  :   # Test Case 1    piles   =   [   3     4     5   ]   n   =   len  (  piles  )   # Find the maximum element    maximum   =   max  (  piles  )   # An array to cache the sub-problems so that    # re-computation of same sub-problems is avoided    Grundy   =   [  -  1   for   i   in   range  (  maximum   +   1  )];   # Calculate Grundy Value of piles[i] and store it    for   i   in   range  (  n  ):   calculateGrundy  (  piles  [  i  ]   Grundy  );   declareWinner  (  PLAYER1     piles     Grundy     n  );          ''' Test Case 2     int piles[] = {3 8 2};     int n = sizeof(piles)/sizeof(piles[0]);             int maximum = *max_element (piles piles + n);         // An array to cache the sub-problems so that     // re-computation of same sub-problems is avoided     int Grundy [maximum + 1];     memset(Grundy -1 sizeof (Grundy));         // Calculate Grundy Value of piles[i] and store it     for (int i=0; i <=n-1; i++)     calculateGrundy(piles[i] Grundy);         declareWinner(PLAYER2 piles Grundy n); '''   # This code is contributed by rutvik_56   

   using     System  ;   using     System.Linq  ;   using     System.Collections.Generic  ;   /* Game Description-   'A game is played between two players and there are N piles   of stones such that each pile has certain number of stones.   On his/her turn a player selects a pile and can take any   non-zero number of stones upto 3 (i.e- 123)   The player who cannot move is considered to lose the game   (i.e. one who take the last stone is the winner).   Can you find which player wins the game if both players play   optimally (they don't make any mistake)? '   A Dynamic Programming approach to calculate Grundy Number   and Mex and find the Winner using Sprague - Grundy Theorem. */   class     GFG      {       /* piles[] -> Array having the initial count of stones/coins    in each piles before the game has started.   n -> Number of piles   Grundy[] -> Array having the Grundy Number corresponding to    the initial position of each piles in the game   The piles[] and Grundy[] are having 0-based indexing*/   static     int     PLAYER1     =     1  ;   //static int PLAYER2 = 2;   // A Function to calculate Mex of all the values in that set   static     int     calculateMex  (  HashSet   <  int  >     Set  )   {      int     Mex     =     0  ;      while     (  Set  .  Contains  (  Mex  ))      Mex  ++  ;      return     (  Mex  );   }   // A function to Compute Grundy Number of 'n'   static     int     calculateGrundy  (  int     n       int     []  Grundy  )   {      Grundy  [  0  ]     =     0  ;      Grundy  [  1  ]     =     1  ;      Grundy  [  2  ]     =     2  ;      Grundy  [  3  ]     =     3  ;      if     (  Grundy  [  n  ]     !=     -  1  )      return     (  Grundy  [  n  ]);      // A Hash Table      HashSet   <  int  >     Set     =     new     HashSet   <  int  >  ();         for     (  int     i     =     1  ;     i      <=     3  ;     i  ++  )      Set  .  Add  (  calculateGrundy     (  n     -     i       Grundy  ));      // Store the result      Grundy  [  n  ]     =     calculateMex     (  Set  );      return     (  Grundy  [  n  ]);   }   // A function to declare the winner of the game   static     void     declareWinner  (  int     whoseTurn       int     []  piles        int     []  Grundy       int     n  )   {      int     xorValue     =     Grundy  [  piles  [  0  ]];      for     (  int     i     =     1  ;     i      <=     n     -     1  ;     i  ++  )      xorValue     =     xorValue     ^     Grundy  [  piles  [  i  ]];      if     (  xorValue     !=     0  )      {      if     (  whoseTurn     ==     PLAYER1  )      Console  .  Write  (  'Player 1 will winn'  );      else      Console  .  Write  (  'Player 2 will winn'  );      }      else      {      if     (  whoseTurn     ==     PLAYER1  )      Console  .  Write  (  'Player 2 will winn'  );      else      Console  .  Write  (  'Player 1 will winn'  );      }      return  ;   }   // Driver code   static     void     Main  ()      {          // Test Case 1      int     []  piles     =     {  3       4       5  };      int     n     =     piles  .  Length  ;      // Find the maximum element      int     maximum     =     piles  .  Max  ();      // An array to cache the sub-problems so that      // re-computation of same sub-problems is avoided      int     []  Grundy     =     new     int  [  maximum     +     1  ];      Array  .  Fill  (  Grundy       -  1  );      // Calculate Grundy Value of piles[i] and store it      for     (  int     i     =     0  ;     i      <=     n     -     1  ;     i  ++  )      calculateGrundy  (  piles  [  i  ]     Grundy  );      declareWinner  (  PLAYER1       piles       Grundy       n  );          /* Test Case 2    int piles[] = {3 8 2};    int n = sizeof(piles)/sizeof(piles[0]);    int maximum = *max_element (piles piles + n);    // An array to cache the sub-problems so that    // re-computation of same sub-problems is avoided    int Grundy [maximum + 1];    memset(Grundy -1 sizeof (Grundy));    // Calculate Grundy Value of piles[i] and store it    for (int i=0; i <=n-1; i++)    calculateGrundy(piles[i] Grundy);    declareWinner(PLAYER2 piles Grundy n); */      }   }      // This code is contributed by mits   

    <  script  >   /* Game Description-   'A game is played between two players and there are N piles   of stones such that each pile has certain number of stones.   On his/her turn a player selects a pile and can take any   non-zero number of stones upto 3 (i.e- 123)   The player who cannot move is considered to lose the game   (i.e. one who take the last stone is the winner).   Can you find which player wins the game if both players play   optimally (they don't make any mistake)? '       A Dynamic Programming approach to calculate Grundy Number   and Mex and find the Winner using Sprague - Grundy Theorem. */   /* piles[] -> Array having the initial count of stones/coins    in each piles before the game has started.   n -> Number of piles       Grundy[] -> Array having the Grundy Number corresponding to    the initial position of each piles in the game       The piles[] and Grundy[] are having 0-based indexing*/   let     PLAYER1     =     1  ;   let     PLAYER2     =     2  ;   // A Function to calculate Mex of all the values in that set   function     calculateMex  (  Set  )   {      let     Mex     =     0  ;          while     (  Set  .  has  (  Mex  ))      Mex  ++  ;          return     (  Mex  );   }   // A function to Compute Grundy Number of 'n'   function     calculateGrundy  (  n    Grundy  )   {      Grundy  [  0  ]     =     0  ;      Grundy  [  1  ]     =     1  ;      Grundy  [  2  ]     =     2  ;      Grundy  [  3  ]     =     3  ;          if     (  Grundy  [  n  ]     !=     -  1  )      return     (  Grundy  [  n  ]);          // A Hash Table      let     Set     =     new     Set  ();          for     (  let     i     =     1  ;     i      <=     3  ;     i  ++  )      Set  .  add  (  calculateGrundy     (  n     -     i       Grundy  ));          // Store the result      Grundy  [  n  ]     =     calculateMex     (  Set  );          return     (  Grundy  [  n  ]);   }   // A function to declare the winner of the game   function     declareWinner  (  whoseTurn    piles    Grundy    n  )   {      let     xorValue     =     Grundy  [  piles  [  0  ]];          for     (  let     i     =     1  ;     i      <=     n     -     1  ;     i  ++  )      xorValue     =     xorValue     ^     Grundy  [  piles  [  i  ]];          if     (  xorValue     !=     0  )      {      if     (  whoseTurn     ==     PLAYER1  )      document  .  write  (  'Player 1 will win  
'  );      else      document  .  write  (  'Player 2 will win  
'  );      }      else      {      if     (  whoseTurn     ==     PLAYER1  )      document  .  write  (  'Player 2 will win  
'  );      else      document  .  write  (  'Player 1 will win  
'  );      }          return  ;   }   // Driver code   // Test Case 1      let     piles     =     [  3       4       5  ];      let     n     =     piles  .  length  ;              // Find the maximum element      let     maximum     =     Math  .  max  (...  piles  )          // An array to cache the sub-problems so that      // re-computation of same sub-problems is avoided      let     Grundy     =     new     Array  (  maximum     +     1  );      for  (  let     i  =  0  ;  i   <  maximum  +  1  ;  i  ++  )      Grundy  [  i  ]  =  0  ;          // Calculate Grundy Value of piles[i] and store it      for     (  let     i     =     0  ;     i      <=     n     -     1  ;     i  ++  )      calculateGrundy  (  piles  [  i  ]     Grundy  );          declareWinner  (  PLAYER1       piles       Grundy       n  );          /* Test Case 2    int piles[] = {3 8 2};    int n = sizeof(piles)/sizeof(piles[0]);            int maximum = *max_element (piles piles + n);        // An array to cache the sub-problems so that    // re-computation of same sub-problems is avoided    int Grundy [maximum + 1];    memset(Grundy -1 sizeof (Grundy));        // Calculate Grundy Value of piles[i] and store it    for (int i=0; i <=n-1; i++)    calculateGrundy(piles[i] Grundy);        declareWinner(PLAYER2 piles Grundy n); */   // This code is contributed by avanitrachhadiya2155    <  /script>