Working through a puzzle-question.
Mar. 25th, 2023 02:01 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
brooksmosesBecause I find solving this sort of thing fun, and I find watching other people talk their way through puzzles" to be fascinating.
Behind a cut, in case you don't.
The question is from https://vlb.typepad.com/commentary/2003/10/puzzle_cult.html, and is roughly an interview question asked in 2003, around the time that asking puzzle questions in interviews was becoming a fad. (That link has a lot more commentary on the general trend, and references How Would You Move Mount Fuji? Microsoft's Cult of the Puzzle as a book that has a lot more historical commentary.)
Quoting from there:
The obvious structure for the solution is two people cross, one comes back, repeat this two more times. It doesn't seem like having two people come back will ever move us "forward" in solving the problem, since there aren't rules about who can cross together or stay behind that we need to workaround, so doing something different from that is probably not where the trick is. Let's start by assuming that is correct, and come back if we need to.
One thing that stands out is the time it takes for one person to come back with the lantern. That's wasted time, so let's try making that as short as possible: A crosses with B, comes back, crosses with C, comes back, and crosses with D. The time is 2+1+5+1+10 minutes, which is 19 minutes -- just a minute too slow.
Given the nature of puzzles like this, that is not a surprise. The fact that it is exactly one minute too slow is almost certainly intentional, and suggests that there is indeed a trick that we are expected to find.
I don't see any obvious tricks immediately, but it's not that large a set of possibilities, so let's start by exploring the set exhaustively.
It looks like the problem is time-reversible; if we switch the sides of the bridge and run everything in reverse, obviously the people successfully get to the other side in the same amount of time. That halves the possible set of options, and means that if we have a solution that starts with a given pair of people, we also have a solution that ends with that pair of people. That may be a useful insight later.
Meanwhile, it means we can arbitrarily start with "who goes first" rather than "who goes last" without worrying about which question gets us to the answer faster.
Let's start by thinking about D. Suppose they go first. If they go with C, then C has to come back with the lantern; that's 15 minutes taken and C can't get back across in the remaining 3 minutes. If they go with B and B comes back, then that's 12 minutes taken; C's crossing takes 5 more minutes whenever it happens, and we still need two more crossings to get the third person, so that's over time as well. And if A goes with D, then we have A, B, and C on the wrong side with 7 minutes to spare, and we can go through that smaller problem the same way.
We certainly could go through things this way, and then consider C going first, and so on. That will cover all the options, and should find a solution.
However, I was able to jump ahead a bit here. The "A, B, and C in 7 minutes" problem looks a lot like the overall problem, and if the best solution to the overall problem is having D go first, then this will probably have a best solution of having C go first, and that gets us back to the 19-minute non-solution that we tried originally, which didn't work. So probably we can just discard this in the "to look at later if other things don't work" pile.
What is becoming clear from trying these possibilities is that C and D crossing separately is a problem; that takes 15 minutes, and getting everyone else across in the remaining 3 minutes doesn't seem possible. So, suppose that they cross at the same time. We can't have them go first, because then C will have to cross back with the lantern, and that takes too long. We can't have them go last, because of the symmetry I mentioned. So they have to go in the middle.
If they go in the middle, that means A and B cross first. Someone needs to cross back with the lantern; A doing that is fastest. Then C and D cross, leaving A behind. Again, someone needs to cross back with the lantern, and if it's not C or D, it has to be B. Then A and B can cross one more time. That's 2 minutes for A and B, 1 minute for A to come back, 10 minutes for C and D, 2 minutes for B to come back, and 2 minutes for A and B again, making a total of 17 minutes.
This is a very satisfying answer; 17 minutes is clearly less than 18 minutes rather than being equal, avoiding an ambiguity, and it seems very likely that the puzzle constructor would have chosen numbers so that things work out this way with the ideal solution -- in particular, for this sort of thing, the difference between the "obvious" answer and the "nonobvious best" answer tends to depend on the difference between the highest and lowest input numbers, so a reasonable puzzle constructor would probably choose the smallest input difference that produced a satisfactory output difference.
The symmetrically-opposite answer has B coming back first, and then A coming back, which is also satisfying; it means that the somewhat-arbitrary choice of who comes back first indeed didn't matter and either would have been equivalent.
Anyway, the question didn't ask us to prove a best answer, just to find one that worked, so this answer suffices.
...
It might be interesting to look at the choice of times, and see what's going on with those. I notice that D's time as the sum of the lower three times plus 2, and C's time is the sum of the lower two times plus 2. Maybe the "plus 2"'s being the same is meaningful, and maybe the fact that it equals the difference between the obvious solution and the best solution is meaningful, or maybe this is coincidence.
At first glance, this seems coincidental; D's time is the limiting time in one crossing in either case, so changing it so long as we maintain ordering doesn't affect the totals or their difference. Also, so long as we maintain the ordering, there's not going to be a possibility for it to be the limiting time in fewer than one crossing, and it seems very unlikely that having it be the limiting time in more crossings will ever be useful, so unless there's some psychological trap I'm missing, 10 really is pretty arbitrary and it could have just as easily been as low as 5.
It's with the other numbers that things become interesting. The obvious solution has B and C the limiting times in "forward" crossings once each, and A coming back twice. The best solution has B the limiting factor in two "forward" crossings, A coming back once, and B coming back once. In equation form (and including the time for D), T1 = 2A + B + C + D, and T2 = A + 3B + D. The difference is T1-T2 = A - 2B + C, which we can rearrange to say that B is the average of A and C, minus half the desired difference in the two solutions. If we want a minimal set with different integer values, we'd want A=1 and B=2, which for a difference of two gives C=5, so those numbers seem determined by being the smallest different integers.
On the other hand, the ordering can be the same even if numbers are equal (it just becomes arbitrary), so having them be equal doesn't change the possible solutions. Thus, we could ask the same problem with A=B=1 and C=D=3. There, the obvious answer takes 9 minutes, and the best answer takes 7 minutes.
Another observation here is that T1-T2 is not necessarily positive. For example, if A=1, B=2, C=3, and D=4, either way takes 11 minutes. More generally, if B is higher than the average of A and C, then the "obvious" way is faster; it's only when it's lower that sending C and D together in the middle works better.
...
For a followup, why are manhole covers round? I thought of three new answers today, to go with all the other ones I've heard. I'll put those in a comment.
Behind a cut, in case you don't.
The question is from https://vlb.typepad.com/commentary/2003/10/puzzle_cult.html, and is roughly an interview question asked in 2003, around the time that asking puzzle questions in interviews was becoming a fad. (That link has a lot more commentary on the general trend, and references How Would You Move Mount Fuji? Microsoft's Cult of the Puzzle as a book that has a lot more historical commentary.)
Quoting from there:
4 people are "escaping from zombies" (or whatever). It is night. They have 1 lantern between them. They reach a gorge, spanned by a log bridge. There are crocodiles in the gorge (or at any rate, it's very deep). They need to cross the gorge before the zombies arrive (cross completely, then destroy the bridge).This is somewhat like the "wolf, sheep, and cabbage across the river" problem; the solution is a sequence of back-and-forth crossings, and probably there is some trick to it.
As with all such puzzles, there are various artificial constraints:
* The people have 18 minutes before the zombies arrive.
* They must cross the gorge in _less than_ 18 minutes.
* Only two people can be on the bridge at the same time or it will not hold them.
* They need the lantern to cross; they can't cross in the dark.
* It's a long bridge and an old-fashioned lantern. You can barely see your feet; you can't see very far ahead or behind on the bridge.
* It's OK to be left alone in the dark on one side or the other.
* It gets more complicated (of course)
* Person A takes 1 minute to cross
* Person B takes 2 minutes to cross
* Person C takes 5 minutes to cross
* Person D takes 10 minutes to cross
(How they know this ahead of time is not provided by the puzzle gods).
Your job is to get everyone across the bridge, never more than two on the bridge at a time, always a lantern on the bridge, in under 18 minutes so they outwit the zombies.
The obvious structure for the solution is two people cross, one comes back, repeat this two more times. It doesn't seem like having two people come back will ever move us "forward" in solving the problem, since there aren't rules about who can cross together or stay behind that we need to workaround, so doing something different from that is probably not where the trick is. Let's start by assuming that is correct, and come back if we need to.
One thing that stands out is the time it takes for one person to come back with the lantern. That's wasted time, so let's try making that as short as possible: A crosses with B, comes back, crosses with C, comes back, and crosses with D. The time is 2+1+5+1+10 minutes, which is 19 minutes -- just a minute too slow.
Given the nature of puzzles like this, that is not a surprise. The fact that it is exactly one minute too slow is almost certainly intentional, and suggests that there is indeed a trick that we are expected to find.
I don't see any obvious tricks immediately, but it's not that large a set of possibilities, so let's start by exploring the set exhaustively.
It looks like the problem is time-reversible; if we switch the sides of the bridge and run everything in reverse, obviously the people successfully get to the other side in the same amount of time. That halves the possible set of options, and means that if we have a solution that starts with a given pair of people, we also have a solution that ends with that pair of people. That may be a useful insight later.
Meanwhile, it means we can arbitrarily start with "who goes first" rather than "who goes last" without worrying about which question gets us to the answer faster.
Let's start by thinking about D. Suppose they go first. If they go with C, then C has to come back with the lantern; that's 15 minutes taken and C can't get back across in the remaining 3 minutes. If they go with B and B comes back, then that's 12 minutes taken; C's crossing takes 5 more minutes whenever it happens, and we still need two more crossings to get the third person, so that's over time as well. And if A goes with D, then we have A, B, and C on the wrong side with 7 minutes to spare, and we can go through that smaller problem the same way.
We certainly could go through things this way, and then consider C going first, and so on. That will cover all the options, and should find a solution.
However, I was able to jump ahead a bit here. The "A, B, and C in 7 minutes" problem looks a lot like the overall problem, and if the best solution to the overall problem is having D go first, then this will probably have a best solution of having C go first, and that gets us back to the 19-minute non-solution that we tried originally, which didn't work. So probably we can just discard this in the "to look at later if other things don't work" pile.
What is becoming clear from trying these possibilities is that C and D crossing separately is a problem; that takes 15 minutes, and getting everyone else across in the remaining 3 minutes doesn't seem possible. So, suppose that they cross at the same time. We can't have them go first, because then C will have to cross back with the lantern, and that takes too long. We can't have them go last, because of the symmetry I mentioned. So they have to go in the middle.
If they go in the middle, that means A and B cross first. Someone needs to cross back with the lantern; A doing that is fastest. Then C and D cross, leaving A behind. Again, someone needs to cross back with the lantern, and if it's not C or D, it has to be B. Then A and B can cross one more time. That's 2 minutes for A and B, 1 minute for A to come back, 10 minutes for C and D, 2 minutes for B to come back, and 2 minutes for A and B again, making a total of 17 minutes.
This is a very satisfying answer; 17 minutes is clearly less than 18 minutes rather than being equal, avoiding an ambiguity, and it seems very likely that the puzzle constructor would have chosen numbers so that things work out this way with the ideal solution -- in particular, for this sort of thing, the difference between the "obvious" answer and the "nonobvious best" answer tends to depend on the difference between the highest and lowest input numbers, so a reasonable puzzle constructor would probably choose the smallest input difference that produced a satisfactory output difference.
The symmetrically-opposite answer has B coming back first, and then A coming back, which is also satisfying; it means that the somewhat-arbitrary choice of who comes back first indeed didn't matter and either would have been equivalent.
Anyway, the question didn't ask us to prove a best answer, just to find one that worked, so this answer suffices.
...
It might be interesting to look at the choice of times, and see what's going on with those. I notice that D's time as the sum of the lower three times plus 2, and C's time is the sum of the lower two times plus 2. Maybe the "plus 2"'s being the same is meaningful, and maybe the fact that it equals the difference between the obvious solution and the best solution is meaningful, or maybe this is coincidence.
At first glance, this seems coincidental; D's time is the limiting time in one crossing in either case, so changing it so long as we maintain ordering doesn't affect the totals or their difference. Also, so long as we maintain the ordering, there's not going to be a possibility for it to be the limiting time in fewer than one crossing, and it seems very unlikely that having it be the limiting time in more crossings will ever be useful, so unless there's some psychological trap I'm missing, 10 really is pretty arbitrary and it could have just as easily been as low as 5.
It's with the other numbers that things become interesting. The obvious solution has B and C the limiting times in "forward" crossings once each, and A coming back twice. The best solution has B the limiting factor in two "forward" crossings, A coming back once, and B coming back once. In equation form (and including the time for D), T1 = 2A + B + C + D, and T2 = A + 3B + D. The difference is T1-T2 = A - 2B + C, which we can rearrange to say that B is the average of A and C, minus half the desired difference in the two solutions. If we want a minimal set with different integer values, we'd want A=1 and B=2, which for a difference of two gives C=5, so those numbers seem determined by being the smallest different integers.
On the other hand, the ordering can be the same even if numbers are equal (it just becomes arbitrary), so having them be equal doesn't change the possible solutions. Thus, we could ask the same problem with A=B=1 and C=D=3. There, the obvious answer takes 9 minutes, and the best answer takes 7 minutes.
Another observation here is that T1-T2 is not necessarily positive. For example, if A=1, B=2, C=3, and D=4, either way takes 11 minutes. More generally, if B is higher than the average of A and C, then the "obvious" way is faster; it's only when it's lower that sending C and D together in the middle works better.
...
For a followup, why are manhole covers round? I thought of three new answers today, to go with all the other ones I've heard. I'll put those in a comment.