1

I am solving the below problem using backtracking recursion. The first code "CoinGame1" is providing correct solution but the second code "CoinGame2" is providing a wrong solution. I guess, there is something bad happening since i am reversing the string earlier before calling recursively.

*Coin game: Alice and Bob are playing a game using a bunch of coins. The players pick several coins out of the bunch in turn. Each player can pick either 1 , 2 or 4 coins in each turn. Each time a player is allowed to pick coins, the player that gets the last coin is the winner. It is known that at last, when 1 , 2 or 4 coins are left, the player with first turn will definitely pick 1, 2 or 4 coins as required and win. For example, if there are 2 coins in end and Alice is the first player to pick, she will definitely pick 2 coins and win. Given the number of coins and the order of players (which means the first and the second players to pick the coins), write a program to print all the possibilities of winner of the game, 

F(1, {alice,bob})
alice
F(6, {alice,bob})
alice, bob, bob, alice, bob, bob
F(4, {alice,bob})
alice
F(3, {alice,bob})
bob, bob*

                         f(6,{A,B})                                     
                     /                \               \
            f(5,{B,A})                 f(4,{B,A})      f(2,{B,A})
          /     |      \                   B wins         B wins
f(4,{A,B})  f(3,{A,B})  f(1,{A,B}) 
A wins     /    |    \       A wins        
          /     |     \
f(2,{B,A})  f(1,{B,A}) f(-1,{B,A})
B wins         B wins

//SOLUTION1

public class CoinGame1
{
   public static void Count(int n, String[] s)   // n: no. of coins 
                                               //s:{"Alice","Bob"} (order) 
  {
       if(n>0)
       {
           if(n==1 || n==2 || n==4) System.out.println( s[0] );  // if 1/2/4 
                                 //coins left, the one with first chance wins
           else
           { 
               Count(n-1,new String[]{s[1],s[0]});
               Count(n-2,new String[]{s[1],s[0]});
               Count(n-4,new String[]{s[1],s[0]});  
           }
       }
  }

  public static void main(String[] args)
      {
          String[] order = new String[]{"A","B"};
          Count(6,order);
      }
}

java CoinGame1 A B B A B B

//SOLUTION2

public class CoinGame2
{
   public static void Count(int n, String[] s)          // n: no. of coins    
                                                 //s:{"Alice","Bob"} (order) 
  {
       if(n>0)
       {
           if(n==1 || n==2 || n==4) System.out.println( s[0] );  // if 1/2/4 
                                //coins left, the one with first chance wins
           else
           {
               String temp = s[0]; s[0] = s[1]; s[1] = temp;     // reverse s
               Count(n-1,s);
               Count(n-2,s);
               Count(n-4,s);  
           }
       }
  }

  public static void main(String[] args)
      {
          String[] order = new String[]{"A","B"};
          Count(6,order);
      }
}

java CoinGame2 A B B B B B

Gagandeep Singh
  • 19
  • 1
  • 9
  • 1
    In your second snippet, you're mutating the array, but this same array instance is used across all iterations. Put `System.out.println(Arrays.asList(s));` before each `Count(...)`. See https://stackoverflow.com/q/40480/1225328. – sp00m Jun 20 '18 at 12:32
  • @sp00m Thanks ....The second code is only giving 4th value incorrect..i am unable to understand by debugging. I tried to debug the second code and foundout that f(-1,{B,A}) is returning to f(5,{B,A}) (instead of f(5,{A,B}) ) which eventually calls f(1,{B,A})) (instead of f(1,{A,B}) ) returning B . Why is f(-1,{B,A}) not returning to f(5,{A,B})? – Gagandeep Singh Jun 20 '18 at 13:28

2 Answers2

0

It helps to simplify recursive problems sometimes. I re-wrote your problem, but I made it start with 5 coins and a choice of 1 or 2. This way, the first picker will always win. The only way you can lose is to pick twice in a row, and the results speak for themselves. Run this code and the conclusion is clear, as mentioned above, the same instance of s is being run through out the entire process.

    public static void Count(int n, String[] s)          // n: no. of coins
    //s:{"Alice","Bob"} (order)
    {
        if(n>0)
        {
            if(n==1 || n==2 ) System.out.println( s[0] );  // if 1/2/4
                //coins left, the one with first chance wins
            else
            {
                String temp = s[0]; s[0] = s[1]; s[1] = temp;     // reverse s
                Count(n-1,s);
                Count(n-2,s);

            }
        }
    }

    public static void main(String[] args)
    {
        String[] order = new String[]{"A","B"};
        Count(5,order);
    }
    // the result is B,B,B,A,A
MGT
  • 173
  • 12
  • In this case, the correct answer should be B, B, A, A, A . The code should return B, B, A, A, A. The same problem we are facing in this code also. same instance of Array 's' is running also in this case. – Gagandeep Singh Jun 20 '18 at 16:20
0

Changes in SOLUTION2 (this now gives correct result)

import java.util.*;
    public class CoinGame2
    {
       public static void Count(int n, String[] s)          // n: no. of coins    ,  s:{"Alice","Bob"} (order) 
      {
           if(n>0)
           {
               if(n==1 || n==2 || n==4) System.out.println( s[0] );  // if 1/2/4 coins left, the one with first chance wins
               else
               {
                  // String temp = s[0]; s[0] = s[1]; s[1] = temp;     // reverse s

                   String[] t = Arrays.copyOfRange(s,0,s.length);
                   String temp = t[0]; t[0] = t[1]; t[1] = temp; 

                   Count(n-1,t);

                   Count(n-2,t);

                   Count(n-4,t);  
               }
           }
      }

      public static void main(String[] args)
          {
              String[] order = new String[]{"A","B"};
              Count(6,order);
          }
    }
Gagandeep Singh
  • 19
  • 1
  • 9