game of sticks

Back to General discussions forum

Goodwin Lu     2020-06-17 00:18:15

I'm stuck on the programming logic. I thought it through but I just can't figure out how to figure out the correct winner.

The crux on my program relies on

bool determinewinner(int m){ 

if (m == 1){

    return false;

    }
 if (m == 2){

    return true;

}

// You can get rid to make the problem n-1, n-2
// see if we can reduce the problem to one where opponent cannot win

return !determinewinner(m-2)|| !determinewinner(m-1);
}

and then counts how many "losts" and "wins" you have in the matches. The final logic gate in psuedocode is:

if ((count%2 == 1 && wincount ==0) || (wincount%2 + count %2==0&&wincount>0)){

    print "0 ";

}

else
{

print "1 ";

}

My logic is: Losses offset each other, therefore if there are no wins and odd amount of losses then you lose. Wins offset each other so if you have even amount of wins then you also lose. (Ex. consider 3, which you win, 3 3 you lose, but 3 3 1 you can create a game where the opponent is bound to lose (by taking the 1 match)

does this seem correct or not?

sontran     2020-06-17 01:26:59

I haven't solved this, but I suspect it has something to do with Sprague–Grundy.

Please login and solve 5 problems to be able to post at forum