Edit: I saw the mail from Pulkit Agrawal very late, but he had explained the solution in a very elegant manner. Kudos to you too sir!
The key to the solution is keeping one prisoner as the counting man. One of the switches is a counting switch which is changed whenever a prisoner except the counting man finds it in off state, provided he has never toggled the switch before. In all other cases, he toggles the other switch which is dummy switch. On the other hand, the counting man simple switches off the counting switch (in case it is on) and increases his count which is initally zero, otherwise he also plays around with the dummy switch. So as soon as the count reaches 22, he knows that all have been once into the room. To account for the absence of knowledge of initial condition of the switch, he waits till count reaches 23.
As Aditya puts in, this is the algorithm for Stop and Wait protocol (he remembers to have read it in Computer Networks lectures :-O)
Ok, for this week, I don't have much. Have been excited over going home this weekend (that is once in 6 months :-) ). So I would put down a puzzle I remember from 1st year of my college.
A shopkeeper needs to weigh 125 packets of sugar. The packets are of weights 1kg,2 kg, 3kg, 4kg.... 125kg. Now, he seems to be in a hurry and wants to weigh it in minimum time possible. Of course the only operation consuming time is changing the weights on the balance. Hence, we plan to give him a strategy to weigh all the 125 packets with minimum changes of weights on the balance. Any suggestions for the strategy? He should also use the minimum number of weight-bars possible. Also, being a professional shopkeeper, he will weigh using the weight bars only,i.e. the already prepared packets cannot be used to weigh the packets prepared later.
Cheers,
Merry Christmas and a very Happy New year!
Vivek
nitkkr.vivek@gmail.com
No comments:
Post a Comment