Wouldn't 251 have the same chance of winning, for symmetry reasons?range=1000, prevGuesses=(), numAfter=2 returns 750
EDIT: NM, I understand now.
Wouldn't 251 have the same chance of winning, for symmetry reasons?range=1000, prevGuesses=(), numAfter=2 returns 750
EDIT: NM, I understand now.
Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
>>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!
[edit] Oops, guess I'm past the deadline for editing posts, I can't update the easy problem [/edit]
Your example invalidates itself.Originally Posted by PJYelton
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.She remembers starting at a particular pearl and counting K times to the first gold pearl.
wwggwwwgg
"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"
No it doesn't. It returns this:originalNecklace(9,13,11) returns ggggwgwgwwggwggwwwwggg
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
[edit]
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.
Last edited by quzah; 03-04-2005 at 10:02 AM.
Hope is the first step on the road to disappointment.
I just sent PJyelton a PM saying the same thing.
My Tutorials :
- Bad programming practices in : C
- C\C++ Tips
(constrcutive criticism is very welcome)
- Brain Cell
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:
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:originalNecklace(9,13,11) returns ggggwgwgwwggwggwwwwggg
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.
Hope is the first step on the road to disappointment.
It should'nt be counted in my opinion.
Lets say we call the function with the following arguments :
If we count the pearl we've just inserted , it would look like this :Code:originalNecklace(1, 3, 1)
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
My Tutorials :
- Bad programming practices in : C
- C\C++ Tips
(constrcutive criticism is very welcome)
- Brain Cell
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.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"
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.
Yes, starting place does matter, you must start from the beginning of the string. Sorry if I didn't clarify that.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"
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.
Last edited by PJYelton; 03-04-2005 at 12:16 PM. Reason: added quote tags
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:
First, we count ahead four places:originalNecklace(5,4,4) returns wwggwwwgg
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.
That's easy enough, again, check your PM.
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.
No, my method gives me:
"wgwwgwg"
Which clearly is correct. [edit]...wrong...wft...lol...[/edit]
Your answer is clearly wrong. Here's why:
Which clearly is wrong. Now look at my output, which is correct.Code:wggwgww 12345 wggwgww 345 12 wggwgww 5 1234
[edit](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.
Last edited by quzah; 03-04-2005 at 12:54 PM.
Hope is the first step on the road to disappointment.
It's perfectly fine to have food in your mouth. It's called eating.
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
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:
I've resent you a PM with the "real" working version.Code:gwgwgww
Quzah.
Hope is the first step on the road to disappointment.
I'll admit a certain amount of ignorance. I read the whole thread, but some of the details seem over my head.That's what I got too. It works, depending on how you count. Remove the red, start the next pass through at the blue.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:wgwwgwg 12345 wgwwwg 45 123 wwwwg 12345That leads to removing a white. Using a step-forward method:Code:gwgwgww 12345 gwgwww 45 123This also leads to removing a white.Code:gwgwgww 12345 gwgwww 345 12 gwwww 45123
edit: If you want a step-forward solution, you can use "wggwgww" as PJYelton suggested.Code:wggwgww 12345 wggwww 345 12 wgwww 45123
Last edited by pianorain; 03-04-2005 at 01:22 PM.
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
Actually, it works.Code:wwggwwwgg 1234 wwgwwwgg 1234 wwgwwwg 234 1 wwwwwg 1234
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
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.
Last edited by Lithorien; 03-04-2005 at 01:42 PM. Reason: I gave away the algorithm.
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.
If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein
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.
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.First, we count ahead four places:
wwggwwwgg
Now we remove this pearl. This shortens the string by one. We're now here:
wwgwwwgg
wwgwwwg
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:
Notice how you have to skip the third gold pearl the second time through the string?Code:12345 wggwgww 345 12 wggwgww 45 1 23 wggwgww
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.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.
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.
Last edited by PJYelton; 03-04-2005 at 02:05 PM.
