1. range=1000, prevGuesses=(), numAfter=2 returns 750
Wouldn't 251 have the same chance of winning, for symmetry reasons?

EDIT: NM, I understand now.

2. >>Wouldn't 251 have the same chance of winning, for symmetry reasons?<<

Thats a good question that others might be curious about so I'll answer it anyways. The answer is no symmetry does not apply in this case. If you chose 251, player 2 would choose 750, then player 3 again having a choice between any number between 252 and 749 will choose the lowest one, being 252. Your winning chances in this scenario are much lower than the one in the example where you choose 750.

I've also made a small change in the easy problem allowing you to use c-strings instead of the string class if you want to in regards to a PM I received. I figured that a number of people who are just starting out C++ will be unfamiliar with strings and I'd prefer them not to have to worry about learning them just to send in code. Just be sure it is null terminated!

 Oops, guess I'm past the deadline for editing posts, I can't update the easy problem [/edit]

3. Originally Posted by PJYelton
She does however remember a curious fact. She remembers starting at a particular pearl and counting K times to the first gold pearl. She plucked it off, then continued counting K more times and again hit another gold pearl. She continued this pattern and every time she hit a gold pearl, never once a white pearl, until all the gold ones were removed.

...snip...

For example, say she tells you that there were 5 white pearls, 4 gold pearls, and K was 4. Then her original necklace would look like this where w stands for white and g stands for gold:

wwggwwwgg

Reasoning:

She remembers starting at a particular pearl and counting K times to the first gold pearl.

wwggwwwgg
Your example does not fit your given output. It cannot possibly be the first gold pearl with the input you've given. Not in that exact setting. You would have to shift your output.

"wwwggwwgg"

That would fit. Unless you don't really care what the starting point is, so long as some place in the string it matches up. If that's the case, then this is also a valid answer to your problem:

"ggwwggwww"

originalNecklace(9,13,11) returns ggggwgwgwwggwggwwwwggg
No it doesn't. It returns this:
wwwwwwwwwwgwwwwwwwwwwg

Here's why:

Start out blank:
wwwwwwwwwwwwwwwwwwwwww

Move out 11, and place one there:
wwwwwwwwwwgwwwwwwwwwww

Move out 11, and place one there:
wwwwwwwwwwgwwwwwwwwwwg

Move out 11, and... oops:
wwwwwwwwwwgwwwwwwwwwwg

There may be a way to get the output you want. I don't think your parameters will fit still though. If you're reconstructing, and starting from scratch, your wrap around will be different. However, your output still won't give you what you want, and you still won't encounter the "first gold pearl" like you have stated. That part of your example is incorrect, which leads to false assumptions in the rest of your logic.
[/edit]

Quzah.

4. I just sent PJyelton a PM saying the same thing.

5. Well let's try again, this time, only using the pearls available, and not starting with a blank full list.

I still don't believe you can get the required output. Here's my "in the edit-post box" try, which now has turned into a seperate post:

originalNecklace(9,13,11) returns ggggwgwgwwggwggwwwwggg
No, there isn't. Your last example is broken. Even if you started looping on reconstruction, you cannot get the output you want. Here's why:

1) There are only ever nine white pearls here in this example.
2) There are only ever thirteen gold ones. Let's build a necklace:

Nine white go on first:

wwwwwwwww

Now we're out of white, so we have to wrap around 2 places.

wwwwwwwww

Ok, now I'm on the eleventh white pearl. Do I insert before or after it?
Let's try after:

wwgwwwwwww
wwgwgwwwwww
wwgwggwwwwww
wwgwgggwwwwww
wwgwggggwwwwww
wwggwggggwwwwww
wwggwggggwwwwwgw
wwggwggggwgwwwwgw
wwggwgggggwgwwwwgw
wwggwgggggwgwwwwggw
wwggwggggggwgwwwwggw
wwgggwggggggwgwwwwggw
wwgggwggggggwggwwwwggw

Let's see if that output fits, shall we?

ggggwgwgwwggwggwwwwggg //origional
wwgggwggggggwggwwwwggw //mine, computed by hand

Nope. Doesn't work. Just compare the longest run of 'g', followed by the pattern after it. Now, I could be off here, after all, you try manually wrapping around in the context of this posting box, and getting it right.

But if I'm incorrect in my doing it by hand, that would be the solution. However, again, this doesn't really fit the origional described rules. For one, we still have the problem of the "first pearl encountered", which breaks the whole thing.

However, we have problems here too. Here they are:
1) Do we insert before or after the stopping space?
2) Does the new pearl you've just inserted constitute the "1" step, or is it not counted?

There's simply not enough information in this one case to solve the problem. We could guess, but that doesn't tell us for sure. For starters, she has absoultely no idea what the thing even looked like, so we don't, and can't, use "sample output" to test our fomulae, because there is none. So you can't rely on that.

So, excluding sample output, because that wouldn't be available, combine with not knowing if we insert before or after, and not knowing if we count the newly placed pearl, leaves this example unsolvable, or at best, incorrect.

I mean, we already know that it can't be correct if we're leaving out a bunch of pearls. That means we have to know if we insert before or after, or what is counted or not. Furthermore, we cannot use sample output to give us this information, because in this scenario, there is no "sample output", because she again doesn't remember what it looks like.

Quzah.

6. Originally Posted by quzah
2) Does the new pearl you've just inserted constitute the "1" step, or is it not counted?
It should'nt be counted in my opinion.

Lets say we call the function with the following arguments :
Code:
`originalNecklace(1, 3, 1)`
If we count the pearl we've just inserted , it would look like this :

gwww

you simply insert a 'g' then insert another 'g' on top of it and same thing with the third one wich wouldn't make sense because the function call asked for 3 gold not 1.

man ... you gotta have lots of free time to make a colorful reply like that

7. Your example does not fit your given output. It cannot possibly be the first gold pearl with the input you've given. Not in that exact setting. You would have to shift your output.

"wwwggwwgg"

That would fit. Unless you don't really care what the starting point is, so long as some place in the string it matches up. If that's the case, then this is also a valid answer to your problem:

"ggwwggwww"
LOL, ok, you got me. Basically when I saw this problem it was very technical and since I didn't want to scare people off I decided to write a small little story to go along with it, thus the necklaces and the pearls. Unfortunately I missed the little mistake you pointed out.

To clarify, the FIRST pearl she runs into isn't necessarily the first one she plucks out of the necklace. She starts at the beginning and counts to k, plucks off a gold pearl, counts to k again, plucks off a gold pearl, continues to do this until there are no more gold pearls.

Unless you don't really care what the starting point is, so long as some place in the string it matches up. If that's the case, then this is also a valid answer to your problem:

"ggwwggwww"
Yes, starting place does matter, you must start from the beginning of the string. Sorry if I didn't clarify that.

This is the nuts and bolts of the problem: You have a string of pearls in a circle, you start at the beginning (in this case the beginning of the string) and count k times and take a gold pearl. You continue to do this numGold times until there are no more gold pearls. Now given k, numGold, and numWhite, what did the original necklace look like?

As for the second post, I can safely say that working backwards and inserting is not the best solution since not only do you have to tackle whether or not inserting before or after is correct, but you also have to figure out the correct spot to start from. You start from index 0 when you start taking away gold pearls, but you can end anywhere. You'd have to define precisely what the exact opposite of counting and taking out pearls is which would include inserting before or after, which direction to count, and whether or not to count the newly inserted pearl.

Lets use your method on something like (4,3,5). You would get "wgggwww" which clearly isn't correct since even if you could start anywhere, you still couldn't find a spot where you count to five, pluck a gold, count to five, pluck a gold, then count to five and pluck a gold. The correct answer is wggwgww.

There is a much simpler solution to this problem that involves no backtracking at all.

8. Originally Posted by PJYelton
Yes, starting place does matter, you must start from the beginning of the string. Sorry if I didn't clarify that.
I did start at the beginning of the string. However, again, you have no actual string. You must recreate one. If you use a "field of blanks", then the output I listed is a valid solution. It is exactly the same as yours, since this is in fact a circular necklace, except it's rotated slightly.

However, I suspect that your actual answer for that example is in fact wrong. Here's my spur of the moment attempt to prove it. We will work with the output, and do as you suggest:

originalNecklace(5,4,4) returns wwggwwwgg
First, we count ahead four places:

wwggwwwgg

Now we remove this pearl. This shortens the string by one. We're now here:

wwgwwwgg

wwgwwwg

Oops. Your program just broke. You cannot be "removing one pearl" from the string, and have the output you expect. It's impossible. She didn't have that output, because had she actually removed the pearls, the string would shorten itself, and on the third attempt, it breaks by stopping on a white pearl.

Also, aside from the broken example that I've shown, everything else is solvable with the exact same circular pattern, slightly shifted. (Check your PM.)

It doesn't matter that starting place, because as you've stated, it's a circle. Since it is circular, the output text would also be circular. So as long as the pearl pattern itself is correct, the necklace itself is correct. Besides, necklaces always slide around when worn anyway.

Originally Posted by PJYelton
This is the nuts and bolts of the problem: You have a string of pearls in a circle, you start at the beginning (in this case the beginning of the string) and count k times and take a gold pearl. You continue to do this numGold times until there are no more gold pearls. Now given k, numGold, and numWhite, what did the original necklace look like?
That's easy enough, again, check your PM.

Originally Posted by PJYelton
As for the second post, I can safely say that working backwards and inserting is not the best solution since not only do you have to tackle whether or not inserting before or after is correct, but you also have to figure out the correct spot to start from. You start from index 0 when you start taking away gold pearls, but you can end anywhere. You'd have to define precisely what the exact opposite of counting and taking out pearls is which would include inserting before or after, which direction to count, and whether or not to count the newly inserted pearl.
There is no "correct spot to start from". Just start from the beginning and build the string. However, you cannot with the information you provide, not for all of your cases. As stated, it is an impossibility to get the output you provide with her trying to assemble a new necklace by hand. You cannot get the output you state. Why? Well she only has nine white pearls. Therefore, you cannot plunk them all down and still move two "non existant white pearls" in play. They don't exist, therefore, the necklace couldn't have been made.

The only way to fix that, is to grab all the pearls randomly, and from a bag, start laying them out until you're at the 11th position, and then start counting for K. You can't however. Again, since you have no output to work from (remember, you don't actually know what the necklace looks like), you have no idea of knowing when you've got them all shuffled around in the right order. Like so:

ggwwwgwwwwg....

There. We randomly throw out pearls until we hit K, and now we place one gold one. We contunue to randomly throw out pearls until we hit K2. What happens if we've used up all of our whites, or golds, before we hit K2? Or K3? Well then you have to go steal one from some place else, and subsitute it with something.

So you now must create an index of ones you can't steal from. Then you repeat moving through N times and hope your output lines up with something you can't check against.

Originally Posted by PJYelton
Lets use your method on something like (4,3,5). You would get "wgggwww" which clearly isn't correct since even if you could start anywhere, you still couldn't find a spot where you count to five, pluck a gold, count to five, pluck a gold, then count to five and pluck a gold. The correct answer is wggwgww.

There is a much simpler solution to this problem that involves no backtracking at all.
No, my method gives me:

"wgwwgwg"

Which clearly is correct. ...wrong...wft...lol...[/edit]
Originally Posted by PJYelton

Code:
```wggwgww
12345

wggwgww
345  12

wggwgww
5  1234```
Which clearly is wrong. Now look at my output, which is correct.
(Well it should have been. I've been tweaking this so much trying to get the third one fixed, I'll have to go over it again. Anyway, for this one, my output is wrong apparently. (Anyone have a shoehorn? I seem to have a food in my mouth. It looks like we're both wrong.))[/edit]

Quzah.

9. Originally Posted by quzah
I seem to have a food in my mouth.
It's perfectly fine to have food in your mouth. It's called eating.

10. Hah. Ok, I found out why that was wrong. I had been changing the starting value of a counter to try and get it shifted correctly. Here's the "real" correct output:
Code:
`gwgwgww`
I've resent you a PM with the "real" working version.

Quzah.

Originally Posted by quzah
No, my method gives me:

"wgwwgwg"

Which clearly is correct.
That's what I got too. It works, depending on how you count. Remove the red, start the next pass through at the blue.
Code:
```wgwwgwg
12345

wgwwwg
45 123

wwwwg
12345```
As you can see, this works if you fall back to the previous pearl after removal. I fail to see how "gwgwgww" can work using any counting method. Using a fall-back counting:
Code:
```gwgwgww
12345

gwgwww
45 123```
That leads to removing a white. Using a step-forward method:
Code:
```gwgwgww
12345

gwgwww
345 12

gwwww
45123```
This also leads to removing a white.

edit: If you want a step-forward solution, you can use "wggwgww" as PJYelton suggested.
Code:
```wggwgww
12345

wggwww
345 12

wgwww
45123```

12. Originally Posted by quzah
originalNecklace(5,4,4) returns wwggwwwgg
First, we count ahead four places:
wwggwwwgg
Now we remove this pearl. This shortens the string by one. We're now here:
wwgwwwgg
wwgwwwg
Actually, it works.
Code:
```wwggwwwgg
1234

wwgwwwgg
1234

wwgwwwg
234   1

wwwwwg
1234```

13. PJY is correct in his reasoning in the inital problem. When the contest is over, if he doesn't, I'll release my source so ya'll can see why.

14. Heh, it took me a while to figure out the algorithm, even though I developed the solutions for both originalNecklace(5,4,4) and originalNecklace(4,3,5). I wasn't exactly sure how I was doing it; it just worked when I was finished with it.

15. LOL, this is turning into the most complicated "easy" problem of all time

Quzah, I admit that I'm a little confused with where you stand at this point since you've corrected yourself a couple of times, so if I say something you already know just bear with me. Also, I'm at work and can't test your code until tonight sometime.

First, we count ahead four places:

wwggwwwgg

Now we remove this pearl. This shortens the string by one. We're now here:

wwgwwwgg

wwgwwwg
You have a mistake here (which might be the counting error you mentioned). You counted 5 as the distance between your first and second gold pearl, thus you took out the wrong one.

Like pianorain's example, you have to remember that when you find your gold pearl, you must remove it. Your examples keep the gold pearl there thus it gets counted again. However, pianorain starts the count again from the previous pearl when you are instead supposed to start from the next pearl. Lets go to my example of (4,3,5). With my answer of wggwgww:
Code:
```12345
wggwgww
345  12
wggwgww
45 1 23
wggwgww```
Notice how you have to skip the third gold pearl the second time through the string?

It doesn't matter that starting place, because as you've stated, it's a circle. Since it is circular, the output text would also be circular. So as long as the pearl pattern itself is correct, the necklace itself is correct. Besides, necklaces always slide around when worn anyway.
LOL true, I'd prefer if you assume she counted from the beginning of the C++ string that is returned from the function when plucking the pearls so that everyone has the same answer.

Quzah, I admit to being rather confused with your example of why the (9,13,11) is broken. If you follow my above example with the answer ggggwgwgwwggwggwwwwggg it works, counting to 11, taking away the gold pearl from the string, rinse repeat 13 times.