urgent response neaded

[kenith001]

My teacher at senior high has asked for us to hand in a project
Unfortunately, i have no idea, as to how to do it and if i don't i will fail the subject and remain in the same year. So i am in nead of urgent help.
The question is the following:

Benjamin and his friend Locke play the following game: At first they put N pebbles in a box.
• Each player in turn takes from one to K pebbles from the box.
• The player that the box is empty when it comes to his turn loses because he
can not play.
• Benjamin plays first.
Benjamin and Locke will play T rounds. Benjamin takes the game really
seriously and for every round he wants to know from the start if he can win. Help Benjamin to find out which player will win the game in each round if both players play optimally.

Sample inputs and their outputs, ar the following:
Sample input 1:
1
5 3
Sample output 1:

Benjamin

Sample input 2:
2
6 2
10 4

Sample output 2:
Locke
Locke
Urgent help is necessary guys, so that i can get out of this jam
I thank you in advance
Kenith

[JLBorges]

See: https://en.wikipedia.org/wiki/Nim#The_subtraction_game_S(1,_2,_._._.,_k)

[keskiverto]

i have no idea, as to how to do it and if i don't i will fail the subject and remain in the same year.

Would you say that it is fair to humanity at large to spoon-feed those, who fail to learn what they are supposed to learn?

This is not a homework site. Homework is all about you learning by doing. If you won't show any effort up front, then you indeed deserve an another year of schooling.

You must have received study material. (Re)read it, carefully.

You show sample input, but don't say what it contains. What do we know about N, K, T?

[jonnin]

Its probably not as hard as it looks.
first, this is a classic game, often used to rook idiots in bars (there are variations of it using various things like packs of sweetener or toothpicks or peanuts that are to be had at a bar). As a classic problem, the web probably has about 2 million coded solutions you could study.
On top of that, its not really a complicated problem (if you are sober, lol).

Treat it like any other problem. Break it down into pieces. Figure out what you need to solve it. Start thinking on it... do you need to represent each peanut in the box or do you just need an integer to count how many are in the box currently? What does the optimal play look like (you may have to play the game against yourself a few times to see how it works)? You probably need a loop, until the thing is empty. You need logic in the loop to do the optimal subtraction for each player each turn. You need to track who's turn it is currently (will a Boolean do here, or an even/odd on the loop variable? Or something else?). loop over the turns, apply the logic, and see who will win, then write that out. The only real challenge here, assuming you just need a couple of integers and a loop, is understanding the game itself well enough to write the logic that represents optimal play (if that wasn't provided in the problem statement).

[Grime]

In fact somebody made a post on THIS EXACT thing JUST one day before you
http://www.cplusplus.com/forum/beginner/247909/

coincidence? yes.

[ne555]

not the same problem
there was no decision there, but here you need to figure out the optimal play.

[Grime]

Ah yea my bad in that post we were taking out k^i but here it's just k.

Editing a quote taken from that thread:

But here's the generic approach to solving such problems. Mostly I'm right on this one but keep in mind that I'm a noob.

So you have a pile of N coins. Alice and Bob take coins from the pile. When Alice and Bob take coins from the pile, we are basically subtracting from the pile.

Suppose Alice just finished taking 4 coins from the pile leaving 2 coins, and Bob needs to take 4 coins. 2-4 would give -2 which is not possible, which I think you understood as well.

So how about something like this?

(pseudo code)

current turn = Alice's

for    (int i=0, Coins in Pile > 0, i++) {

if (Alice's turn)
   winner = Bob
   current turn = Bob
else
  winner = Alice
  current turn = Alice

Coins in Pile = Coins in Pile - k
}

Hopefully if there are any improvements, somebody else can mention it.

I'm sure you will understand most of the code.

By the way we're using a for-loop over a while loop because we can use "i" the iterating variable, we could have also used a while loop it's the same thing.

Okay mostly you probably could understand everything but you might get confused in one detail - why we're assigning the winner to be the person who played last turn. If you do then I think you should think about it yourself ;^), that's how you learn and that's how you build your logic!

edit:

there was no decision there, but here you need to figure out the optimal play.

Means? I didn't understand. We are just finding who wins right..? What decision?

edit: From reading keskiverto's reply, THE ABOVE IS WRONG PLEASE DO NOT RELY ON IT!
Thanks a lot keskiverto you're very observant!

[keskiverto]

Each player in turn takes from one to K pebbles from the box.

one to K

In the problem that you did link we know exactly how many to take on each turn.
It is pow(k, turn)

In here ... Lets compute N=5, K=3:

A)
Ben takes 1 on first turn, which leaves 4.
Locke must take at least 1, which leaves 3, and at most 3, which leaves 1.
Ben can take all remaining on the second turn and win.

B)
Ben takes 2 on first turn, which leaves 3.
Locke can take all remaining on the first turn and win.

C)
Ben takes 3 on first turn, which leaves 2.
Locke can take all remaining on the first turn and win.

In other words, Ben can take 1-3 on first turn, but only the "take 1" allows (and ensures) that he wins.

We know that Ben can take 1, 2, or 3 on the first turn. That is a decision. You have to compute the outcome of each choice in order to know which (if any) are optimal and lead to victory.

[Browni3141]

keskiverto wrote:

We know that Ben can take 1, 2, or 3 on the first turn. That is a decision. You have to compute the outcome of each choice in order to know which (if any) are optimal and lead to victory.

This is not true. It's a relatively simple math problem, not a programming one. The answer for any case can be computed with a one liner in constant time. It's not a difficult enough problem to warrant an actual game tree search, unless I'm being dumb and am missing something.

The losing positions are periodic, which is intuitive since the number of stones either player can remove has a fixed spread continuous over the whole numbers, and there is only one pile. Think about how you can use the modulus operator, OP.