I have no idea how to proceed on the hard solution, though. I'll have to hunker down and give it some serious thought.
If you want to learn programming at the same time, try to solve the hard version in Python. You'd be surprised how quickly you'll pick it up just by trying to solve a problem using it and referencing the documentation for each coding bit you don't understand.
I have no idea how to proceed on the hard solution, though. I'll have to hunker down and give it some serious thought.
If you want to learn programming at the same time, try to solve the hard version in Python. You'd be surprised how quickly you'll pick it up just by trying to solve a problem using it and referencing the documentation for each coding bit you don't understand.
Indeed. Trying to solve a problem is definitely the best way to learn a programming language, or indeed programming in general.
You may or may not wish to look at the Python I've posted up for the problem or for the easy solution (but note that my easy solution may be a bit too much of a giveaway for some of the important ideas for the hard solution). Note that I've used classes in order to provide modularity and accommodate the need for the subroutines/prisoners to have their own local memory.
So, regarding the optimization of the easy solution done by lackofcheese: You can choose the person to enter on the third day to be the leader. E.g., set it up so that if on the third day the light is on there have been two different people in the room and if the light is off the same person has been there twice (effectively this is the optimal solution of the n=3 case. After the third day you switch, of course, to the proper counting method).
In most cases (when day one and two see two different people) this will start the proper counting with two people already counted, whereas your solution always starts off having counted only one person.
So, before this thread disappears into the abyss that is pages three and up, I'll post a link to the white paper(pdf) discussing various ways of tackling the hard solution. I hope all of you had a fun time trying to find the solutions to this puzzle, it is one of my all time favorites, since at first it seems so completely impossible for a solution to exist. Indeed the only "symmetric" non trivial solution exists for three prisoners. The juxtaposition of the seeming impossibility and the relative simplicity of the easy solution gave me quite a laugh (I actually figured out the solution only after having received the "hint" that the solution was "totally easy dude!")
Most "100 blaa blaa..." puzzles are rather boring variations of a) reduce and induce or b) hash function/hamming distance construction. Not to say that those puzzles can't be amusing, my favorite variant a) puzzle is:
On an Island with no reflective surfaces whatsoever, lives a tribe of people who have either blue or brown eyes. Talking about eye color is tabu and finding out one's own eye color such a shame that ritualistic suicide by way of throwing yourself into the volcano at dawn of the next day is mandated.
An explorer visits the Island and manages to abide by the tabu while there, however on the day of his departure he casually says "one of you people has the most beautifull blue eyes I've ever seen.
What happend after the explorer leaves and when?
Which is quite fun. Bonus points for anyone who can point out the fallacy inherent in this puzzle, super bonus points for figuring out how to avoid said fallacy.
for the island one: I guess we have several assumptions not mentioned in the problem. 1) The tribe are not necessarily perfect logicians, and considering the result of knowing your eye color is death, it's quite reasonable for them to be in denial about it, even if they were highly intelligent individuals otherwise. 2)the explorer could be lying, and even if he himself never lies (perhaps having a weird taboo of his own?) there is no way for the tribesmen to know for sure.
I guess we have several assumptions not mentioned in the problem.
Yes, you are the reason I changed the "100 prisoners and a light bulb" problem to a computer program problem. Although I wonder whether you wouldn't have tried arguing for the influence of cosmic rays flipping bits in the computers memory.
Comments
You may or may not wish to look at the Python I've posted up for the problem or for the easy solution (but note that my easy solution may be a bit too much of a giveaway for some of the important ideas for the hard solution). Note that I've used classes in order to provide modularity and accommodate the need for the subroutines/prisoners to have their own local memory.
In most cases (when day one and two see two different people) this will start the proper counting with two people already counted, whereas your solution always starts off having counted only one person.
Most "100 blaa blaa..." puzzles are rather boring variations of a) reduce and induce or b) hash function/hamming distance construction. Not to say that those puzzles can't be amusing, my favorite variant a) puzzle is: Which is quite fun. Bonus points for anyone who can point out the fallacy inherent in this puzzle, super bonus points for figuring out how to avoid said fallacy.
Finally, for the more mathematically inclined:
a^1 + b^1 + c^1 + d^1 = 4a^2 + b^2 + c^2 + d^2 = 16
a^3 + b^3 + c^3 + d^3 = 64
a^4 + b^4 + c^4 + d^4 = 128
a^5 + b^5 + c^5 + d^5 = ???