(RECURSION PROBLEM)Very difficult C++ problem.. Picking coin game.., no idea.. need s

[student_x]

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 time a player is allowed to pick 1, 2 or 4
coins, and the player that gets the last coin is the winner. Assume that both players are
very smart and he/she will try his/her best to work out a strategy to win the game. For
example, if there are 2 coins and Alice is the rst player to pick, she will de nitely pick 2
coins and win. If there are 3 coins and Alice is still the rst player to pick, no matter she
picks 1 or 2 coins, Bob will get the last coin and win the game.
Given the number of coins and the order of players (which means the rst and the second
players to pick the coins), you are required to write a program pickcoin.cpp to calculate
the winner of the game, and calculate how many different strategies there are for he/she
to win the game. You should use recursion to solve the problem, and the parameters are
read from the command line. You can assume that there are no more than 30 coins.

Here are some sample runs of the program:
./pickcoin 1 alice bob
alice 1
./pickcoin 2 bob alice
bob 1
./pickcoin 3 alice bob
bob 2
./pickcoin 10 alice bob
alice 22
./pickcoin 25 alice bob
alice 3344
./pickcoin 30 alice bob
bob 18272

I really have no idea about how to write this.. I have thought about it for a few days but still have no ideas about the logic of this programme. Could someone give me some help?

Many thanks for your generosity!!!

[Sky Diploma]

SHOULD you decide the winner by looking at the number of possibilities of winning?

As in if bob has 300 strategies of winning and Alice has 299? Should we decide Bob as the winner?

[Salem]

But there is only "one" strategy, and that's to keep the other player with multiple of 3 to choose from. If the other player ends up looking at a total of 3, then you win.

Eg.
Total is 6 (for them)
They pick 4, you pick 2 and win
They pick 2, you pick 1, leaving 3 and you win next turn
They pick 1, you pick 2, leaving 3 and you win next turn

Your example answers suggest the number of permutations of wins possible, if both players just play dumb. That is, randomly picking 1,2,4 and seeing who wins.

My idea

void play ( int n, int me, int them ) {
  play( n-1, them, me );
  play( n-2, them, me );
  play( n-4, them, me );
}

n == 0 is a win for me
n < 0 is an invalid outcome

Though TBH, I think this rather gives the game away as it is.

[student_x]

Thank you Salem.

But to clarify one thing, the two players will not just pick randomly, they will choose to "win".

for example, we can make it clear in this way:
assume the order is alice, bob
for 1 coin, alice wins, 1 way
for 2 coin, alice wins, 1 way
for 3 coins, bob wins, 2 ways
for 4 coins, alice wins, 3 ways

for 5 coins, alice takes 2 first (other ways can not make her win) and make the situation the same as the initial situation: 3 coins and bob first, apparently there are 2 ways for alice to win.

for 6 coins, there are 3 initial actions alice can take, 1, 2 or 4. By taking 1, she reduces the situation to 5 coins, bob first, we have already analyzed that bob would win this situation with 2 ways. By taking 2, she reduces the situation to 4 coins, bob first, and we have shown bob would win with 3 ways. By taking 4, she reduces the situation to 2 coins, bob first, and bob wins with 1 way. So you can sum them up and come to the conclusion that bob wins with 6 ways.

[student_x]

Thinking about solem's direction. But this is a really difficult question, isn't it?

I really feel headache coding this.

[Sky Diploma]

Well if that is the case. Then the objective of the game will be to make the total number divisible by 3.
If in the first try the player can remove something ie : 1,2,4 coins and make the number divisible by 3 then he wins.

Consider

10

If i take in 1 coin, 9 remains. if the opponent takes 4. then i take 2 and win leave 3. Or else we loose.

If the number in the initial stages is divisible by 3 the player1 eventually will lose.

Just try all the other permutations and you will get it.

Secondly The total chances of winning can be calculated by random bruteforce i guess.

I am absolutely sorry . I dint see SALEMS POST.

[student_x]

Thanks.. but I still have no ideas about how to write the programme

and the code suggested by salem:

void play ( int n, int me, int them ) {
  play( n-1, them, me );
  play( n-2, them, me );
  play( n-4, them, me );
}

Isn't only the first play( n-1, them, me ); will be executed?

[student_x]

I have really no ideas.. I have been dealing with it for almost a week and still nothing can be done.

Sincerely hope someone could give me a helping hand #_#

[Salem]

> But this is a really difficult question, isn't it?
Would you feel bad if I told you I'd already solved it?

> Isn't only the first play( n-1, them, me ); will be executed?
I take it you've never studied the archetype recursive function for Towers of Hanoi?

play( n-1, them, me )
It keeps doing this until it runs into the end-stop, then it returns and does
play( n-2, them, me );
and so on.

Actually, it took a couple of attempts. My snippet is exactly half of the solution, and it produces stupidly large numbers for permutations.
What's missing is the strategy code for the winning plays.

[student_x]

Sorry Salem, I know I am really stupid in programming >o< I really know..

void play ( int n, int me, int them ) {
play( n-1, them, me );
play( n-2, them, me );
play( n-4, them, me );
}

But is this function completed? Because nothing is returned and how can I determine who is the winner? Should I add something like this? (the base case)

if (n % 3 == 0)
return them;
if (n == 1 || n == 2 || n == 4)
return me;

[Salem]

Read my first post again.

n == 0 means "me" is the winner.

Notice this?
void play ( int n, int me, int them ) {
play( n-1, them, me );
This is how it alternates between taking turns.

play( n-1, them, me );
play( n-2, them, me );
play( n-4, them, me );
This is what the losing player has to do - that is, they're stuck with n % 3 == 0
Try every possible move to see what works (if anything).

The winning player does something else, read your notes.

[student_x]

Read my first post again.

n == 0 means "me" is the winner.

Notice this?
void play ( int n, int me, int them ) {
play( n-1, them, me );
This is how it alternates between taking turns.

play( n-1, them, me );
play( n-2, them, me );
play( n-4, them, me );
This is what the losing player has to do - that is, they're stuck with n % 3 == 0
Try every possible move to see what works (if anything).

The winning player does something else, read your notes.

I run the programme like this and what comes out is segmentation fault and the programme runs the play( n-1, them, me ); until n is negative infinity.

#include <iostream>
#include <cstdlib>

using namespace std;

void play(int n, int me, int them){

  play(n-1, them, me);
  play(n-2, them, me);
  play(n-4, them, me);
}


int main(int argc, char * argv[]){
  int n = atoi(argv[1]);  
  play(n, 0, 1);

  return 0;
}

I am still very confused.. could you write the return and checking result for the function?

[Salem]

You're not reading.

void play(int n, int me, int them){
  if ( n == 0 ) {
    // me is the winner
    counter[me]++;
  } else if ( n < 0 ) {
    // took too many, just ignore it as we're trying every combo
  } else {
    play(n-1, them, me);
    play(n-2, them, me);
    play(n-4, them, me);
  }
}

EVERY recursive function needs a base case which stops it looping forever.

That's it, I can't really help you any more without blurting out the answer.

[student_x]

You're not reading.

void play(int n, int me, int them){
  if ( n == 0 ) {
    // me is the winner
    counter[me]++;
  } else if ( n < 0 ) {
    // took too many, just ignore it as we're trying every combo
  } else {
    play(n-1, them, me);
    play(n-2, them, me);
    play(n-4, them, me);
  }
}

EVERY recursive function needs a base case which stops it looping forever.

That's it, I can't really help you any more without blurting out the answer.

Is it the completed function? I spend 3 hours working on this but still fail...
You use "void" as the return type in the function. Should I return the value of "me" or return the int count?

[Sky Diploma]

Well counter in the above function might have been declared globally. So in after the total function has worked out all the permutations.

Counter[me] // will have all the times 'ME' has won
and Counter[them] will have the times "them" has won the game.
(Dont forget to initialise (Counter[me] and Counter[them] ) to zero.

I guess you should post in the total code which you are currently working on.

But i STILL HAVE A Doubt for Salem..

The Code

void play(int n, int me, int them){
if ( n == 0 ) {
    // me is the winner
    counter[me]++;
}

Doesnt the above imply that them is the winner. Because He was the last person to take in the coins and the me has nothing left to take. So because them has taken the last coin. Me has nothing left with him.

I think the function should be

void play(int n, int me, int them){
if ( n == 0 ) {
    // them is the winner
    counter[them]++;
}

[Salem]

> Doesnt the above imply that them is the winner. Because He was
> the last person to take in the coins and the me has nothing left to
> take. So because them has taken the last coin. Me has nothing left
> with him.
You could very well be right, well spotted.
My program produced the right answer for one of them, and I gave up even thinking about it any further; the challenge was all but over.

[student_x]

#include <iostream>
#include <cstdlib>

using namespace std;

int way;

int play(int n, int me, int them){
  if (n == 1 || n == 2 || n == 4){
    way++;
    return me;
  } 
  
  if (n > 1 && n != 4 && n != 2)
    play(n-1, them, me);
  if (n > 2 && n != 4)
    play(n-2, them, me);
  if (n > 4)
    play(n-4, them, me);

  
}


int main(int argc, char * argv[]){
  int result;
  int n = atoi(argv[1]);  
  result = play(n, 0, 1);
  if (result == 0)
    cout << argv[2] << " ";
  else if (result == 1)
    cout << argv[3] << " ";
  cout << way;
  return 0;
}

Here is my code. But the way is not correct.

If I don't add the condition before play, Salem's programme will never end.

Could you correct it for me?

[Salem]

If n % 3 is 1, then you can either take 1, or take 4, and still be in a winning position.

[$Tweety$]

Please could u provide the entire code for the above program?
u see i hav tried but failed 2 understand it...

[G._1]

Anybody has the code? using backtracking recursion