Howdy, Stranger!
It looks like you're new here. If you want to get involved, click one of these buttons!
This forum is in permanent archive mode. Our new active community can be found here.
Logic Puzzle 2 wrap-up
The Rules:
The main routine M has a 128 bit key A.
In an infinite loop:
Question:
How do you program the subroutines in such a way that the program will eventually stop with A==B? Effectively, how do you program the subroutines to "know" when they all have all been called by the main routine at least once?
How many loop iterations does your solution take, and can you prove that your solution is optimal (i.e. takes the least number of loop iterations)?
Remember:
The only changing variables are P_g, P_l### (and the loop counter, which you don't have access to).
To clarify:
There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
Solution:
pdf
- No visible posting of answers/hints/etc. for the first 24 hours after this is posted, i.e., whisper to self for later reveal.
- If you want bragging rights (since un-whispering will show up as an "edit"), copy paste the text of your whispered answer into a text file and post the md5 check sum.
- This puzzle has two solutions. After 24 hours I'll check to see if anyone has figured out the hard one. If yes, I'll stand in awe of the forum member in question (at least, in awe of his/her Googling skills). If no, I'll start dropping some hints.
- "Punctuation Fucking" (trans: Fin. "nit picking") is not the aim here. Nor is "thinking outside the box" (as commendable as that may be). If the puzzle is unclear whisper me, if you have "funny" solutions, wait 24 hours ;-).
The main routine M has a 128 bit key A.
In an infinite loop:
- The main routine will call at random a subroutine S_###, with ### a number between 000 and 127.
- The subroutine will be handed two arguments:
- the value of the bit in A, corresponding to the subroutines number, e.g. S_003 will get the value of the third bit in A.
- the loop counter.
- The subroutines can get() and set() the value of one global (all subroutines can see it) parameter P_g, with the length of 1 bit (0 or 1)
- The subroutines can get() and set() the value of one local (every subroutine has it's own) parameter P_l###, with infinite length
- The subroutines must exit with a 0 or 1.
- If the subroutine exist with a 0, the main routine continues the loop
Question:
How do you program the subroutines in such a way that the program will eventually stop with A==B? Effectively, how do you program the subroutines to "know" when they all have all been called by the main routine at least once?
How many loop iterations does your solution take, and can you prove that your solution is optimal (i.e. takes the least number of loop iterations)?
Remember:
The only changing variables are P_g, P_l### (and the loop counter, which you don't have access to).
To clarify:
- P_g and P_l### are static, i.e. they remain intact between different calls to subroutines. So, e.g., on loop iteration 403 S_032 sets P_l032 to a value (e.g. 001101100010101) before exiting and when S_032 is called the next time on, e.g., loop iteration 742, it can get the value of P_l032 (001101100010101) back.
- On the other hand, a subroutine on loop iteration 100 will get the value of P_g (0 or1) that the subroutine on iteration 99 set.
- The subroutines can only be called from the main routine, not recursively from within the subroutines (nice one Frank). If this were allowed the puzzle would have an easy solution, not just an "easy" solution ;-).
There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
Solution:
Comments
There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
Edit: Wait, was this an attempt to get me to call you a pilkunnussija?
There are 100 prisoners in solitary cells. There's a central living room with one light bulb; this bulb is initially off. No prisoner can see the light bulb from his or her own cell. Everyday, the warden picks a prisoner equally at random, and that prisoner visits the living room. While there, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting that all 100 prisoners have been to the living room by now. If this assertion is false, all 100 prisoners are shot. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world could always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity. The prisoners are allowed to get together one night in the courtyard, to discuss a plan. What plan should they agree on, so that eventually, someone will make a correct assertion?
edited: changed notation from angle brackets to square.
BTW, since I just remembered. Rym and Scott, your annunciation of "Karlsruhe" was decent enough
Small hint: You really don't need the loop counter at all for the "easy" solution.
Humongous hint: The total amount of memory needed for all the P_l###'s is 263 bits for the "easy" solution and about a few kilobits for the hard solution, the "infinite length" is a red herring.
I'm going to sleep now, have fun!
Edit: I previously miscalculated the amount of bits neccessary by the minimal solution.
if (P_g == 0) {
P_g = 1;
P_l###[0] = A[###];
P_l###[1] = 1;
if (S_000 && S_001 && ... && S_127)
return 1;
else {
P_g = 0;
return 0;
}
}
else {
if (P_l###[1] == 0)
return 0;
else
return 1;
}
}
Pros: Low memory use (each P_l### is only two bits big)
Cons: Computation is O(n^2)
EDIT: This is pretty much the same solution Timo posted below as the (cheating) solution, except this only uses 256 bits.
note 1:
I'll be modifying the notation for a bit more readability.
S[n] indicates subroutine number n.
Gbit is the global bit P_g
local[n].b indicates the bth bit of subroutine n's local store, starting from b = 0.
first off, let's clarify your definition of main.
main {
loopcounter = 0
Gbit = 0
do {
n = random int from (0..127)
rv = S[n](A.n, loopcounter)
loopcounter ++
} while ( rv == 0 )
// at this point, an S has returned a 1
for b = 0 to 127 {
B.n = local[n].0
} // This is the bit copy. The assumption here is that main can see the locals of all of the S.
}
My first thought is to kind of cheat using recursion.
S[n] (bit_of_A, loopcounter) {if local[n].1 == 0, {
set local[n].0 = bit_of_A
set local[n].1 = 1
call S[n+1 mod 128] ( next bit_of_A, loopcounter)
}
return 1
}
Each subroutine calls the next one, and so by induction, each sub gets called once (except the first, which gets called again, sees a 1 in its P's second bit, and jumps straight to the return, after which all the previous calls return.)
This gives a total of 129 subroutine calls, and completely bypasses the loop inside main.
problem: this only works if A is globally visible. if it's restricted to main, S[n] can't see A to pass it's n+1th bit to the next S.
-- hence: above idea does not work.
In the prisoner metaphor, this is allowing each prisoner to let the next prisoner into the room.
If A is only scoped to main, then each S[n] MUST be called from main, otherwise, they can not get the A.n bit as an argument, as no other function has A to pass to another function.
In this case, the only way to guarantee that main halts is to ensure that each S will return 1 after a finite number of calls, but this doesn't ensure that all S will be called by main.
-- second idea. --
This is going to abuse the purpose of the arguments to S[n].
Assumption is that the loop counter argument is at least 7 bits long.
The state of Gbit will have a well-defined meaning at the start of each S, namely:
0: this S was called by main.
1: this S was called by something else.
(meaning, before each call, we have to set Gbit.
S[n] ( Abit, lc) {
if n == 0 {
// we'll be using S[0] as a specialized tracker subroutine.
if Gbit == 0 {
local[0].0 = Abit
local[0].128 = 1
}
else { // called by another S
//here, we use lc as an informational channel, indicating which S called S[0].
//(this is S[0]'s local copy of lc, so we're not violating main's loopcounter.)
if lc in (0..127) {
// bits 0..127 will build up in local[0] a local copy of A, bits 128..255 will index which bits we've gotten.
if local[0].(lc+128) == 0 {
local[0].lc = Abit
local[0].(lc+128) = 1
}
}
}
if local[0].(128..255) are all 1 {
return 1
} else {
return 0
}
}
else { // n is in (1..127)
if Gbit == 0 {
local[n].0 = Abit
Gbit = 1
rv = S[0] ( Abit, n ) // send S[0] the bit we got, and where to put it.
Gbit = 0
return rv // S[0] will return 1 once all S have reported to it, and this passes the return from S[0] to main.
} // no one should call anything other than S[0] when Gbit is 1.
}
}
Time factor is constant for each S. S-calls from main will call S[n], who calls S[0]. The only loop is in S[0]'s all 1 check, and that's a constant time test of 128 bits.
Now, with main being random, there's no way to ensure that all S will be called, but it's a probability thing.
The first rand roll will always get a new n, with probability 128/128, after k different n have been rolled, the probability of rolling a new n is (128-k)/128.
This is a Bernoulli process, so the number of rolls before every new number will follow a geometric probability distribution.
This gives an expected number of rolls before a new n as 1/P(new n), or 128/(128-k).
Summing these expected numbers of rolls for an expected total calls from main gives 695.44 with a standard deviation of 161.64.
Worst case is that main perversely never calls a certain n, and thus never halts; best case is no misses, for 128 main calls, 255 total S calls.
I'm also wasting a good 128 bits of storage, it seems.
edit again: md5 sum dropped, had to fix an unfinished sentence, CBA to recalculate the md5.
Edit 3: Since the 24 hour embargo's over, revealing my attempt which kind of broke the conditions.
Edit: Only four more hours before I start dropping serious hints and any glory of having solved the puzzle diminished ;-).
Yes, I deliberately framed the problem so that it would not be easy to Google for it. The "100 prisoners and light bulb" puzzle is one of my favorite puzzles since it doesn't lend itself to solution by reduction and induction (i.e. start with 1 prisoner, then 2, then 3 and figure out the pattern) like the famous "blue eyes, brown eyes" puzzle. Sadly the puzzle has become very popular (and I liked it before it went mainstream!!) and thus solutions abound on the interwebs.
If you still want to figure it out for yourself, here is another hint: The "easy" solution is much, much easier than you'd think and will take around 15000 loop iterations (or 10000 days in the prisoner problem).
Note that I've simplified all of the 128-bit key stuff down to the idea that we only need to know that each subroutine has been called at least once.
A solution to the problem consists of one or more subclasses inheriting from Sub, which must define a __call__ method with a single argument (the value of the counter), and a list of these classes (i.e. as uninstantiated types) to use for the subroutines;
[CheatSub] * 128 is an example of this. Please note the following:
- The only access to the main routine allowed is via calls to self.main.setGlobal and self.main.getGlobal.
- The local variables are achieved using instance variables.
- Class variables are disallowed.
- The subroutines are not allowed any access to the other subroutines.
- The first iteration of the loop is number 1, not 0.
For anyone interested, I have an implementation of the "easy" solution Timo mentioned. I calculate the average number of iterations to be 16905.77 from 1000 runs.S[n] (Abit, Nloop) {
if Gbit == 0 { // if called from main
local[n].0 = Abit // remember the part of A given to me
local[n].1 = 1 // bit that says "I have been called at least once"
Gbit = 1
for m (0..127) { // call all subroutines
local[n].(2..8) += S[m] (0,0) // local[n].(2..8) is a 7 bit counter
}
if local[n].(2..8) == 0b1111111 { // if all routines report "yes"
return 1 // exit FTW!
}
clear local[n].(2..8) // otherwise, cleanup and
Gbit = 0
return 0 // back to work
}
// so I'm called by another S
if local[n].1 == 1 { // if I have already been called by M at least once
return 1 // say "yes"
}
return 0 // if not, say no
}
This (cheating) solution is optimal in that it will immediately terminate when all subroutines have been called at least once. Also note that you don't need the loop counter!
This solution uses 128 bits for storing A, 128 bits for the "I have been called" markers, and 7 bits for a counter which can be released after use, for a total of 263 bits. Interestingly, this is exactly one bit more than required by the real non-cheating solution (the "easy" one). This fact, and the way the above routine is constructed should serve as a big hint for people still figuring this out. EDIT: as has been pointed out above, the loop over subroutines can be replaced by a long logical statement thus saving the use of the counter and bringing the required bits down to 256. The real (easy) solution still needs 263 bits.
Finally, for those who have figured out / Googled / are otherwise familiar with the easy solution: How are you doing on finding the hard solution?
Posted By: Vhdblood: First, the easy solution, so you know I know and all, is to elect a leader. Every time anyone other than the leader goes in, they turn the light on if it is not on and they haven't turned it on before. The leader waits until he's turned it off 99 times and then asserts it.
This will on average take roughly 10000 days (or ~16000 loops in the computer program equivalent).
The hard solution cuts this down to around 3700 days, and the super hard solution (not so super hard once you figure out the hard one) can be shown to take ~2000 days. If you consider that it takes on average about 460 days for everyone to have been in the room that last one is not too bad.
I'll give a more accurate time analysis of the easy solution shortly, with and without my minor improvement. I'm currently working on the details of the hard solution myself.
I have no idea how to proceed on the hard solution, though. I'll have to hunker down and give it some serious thought.
Let us consider a single step of this process to be one where a previously uncalled person turns on the light, and then the leader is called and receives this signal. As Frank said, this is a Bernoulli process, so the expected number of trials for an event to occur is the inverse of the probability of it occurring in a single trial. If n is the number of prisoners, then n-1 such steps must occur. Additionally, if k people other than the leader have been called so far, then the probability of a new person being called is (n-k-1)/n, and so the expected number of trials before this occurs is n/(n-k-1). On the other hand, the chance of the leader being called is always 1/n, so we always expect n trials for the leader to be called.
Since all of these events must occur consecutively and cannot be concurrent, we can simply add up the expectations to get the total expected time. This is simply the sum from k = 0 to n-2 of [n/(n-k-1) + n], which can be simplified to n(n-1) + sum_1^{n-1}(n/(n-k)).
For n = 100, this equates to approximately 9000 + 518 = 9518; for n = 128, this equates to approximately 16256 + 694 = 16950.
As for the minor improvement I made, it introduces the following complication to the first step of the process:
1) After the first day, there is a (n-1)/n chance that a different person is called, who would then become the leader, and turn the light off. This would conclude the first step after 2 days.
2) However, there is a 1/n chance that the same person enters the room again. This person leaves the light on, and does not become the leader.
2a) After this, there is a further (n-1)/n chance that, as before, a different person is called (who turns the light off and becomes the leader), concluding the first step after 3 days. The overall chance of this is (n-1)/n^2
2b) Otherwise, with overall probability 1/n^2, the same person is called a third time in a row. They must then become the leader, which means that after 3 days we're in the same situation as for the basic easy solution.
Considering that the first step takes n + n/(n-1) days, the amount saved in comparison to the unimproved solution is:
E(first step w/o improvement) - E(first step with improvement)
= n + n/(n-1) - [(n-1)/n * 2 + (n-1)/n^2 * 3 + 1/n^2 * (3 + n + n/(n-1))]
For n = 100, the unimproved first step takes around 101 days, while the improved first step has an expectation of around 2 days, hence saving 99 days for an overall expectation of 9419 days.
For n = 128, the unimproved first step takes around 129 days, while the improved first step has an expectation of around 2 days, hence saving 127 days for an overall expectation of 16823 days.
]