From: Jim Weigang Newsgroup: comp.lang.apl Date: Sun, 13 Feb 2000 17:27:55 -0500 Subject: Bridge Crossing Puzzler In the latest issue of Vector, Eugene McDonnell describes a puzzle that was posed on the J Forum. The earliest reference I could find to this puzzle was a posting by Thomas Okon on rec.games.trivia from January 1997. Thomas said the puzzle was asked at Microsoft job interviews. It goes something like this: Four men have to cross a bridge at night. The bridge is old and dilapidated and can hold at most two people at a time. There are no railings, and the men have only one flashlight. Any party who crosses, either one or two men, must carry the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, etc. Each man walks at a different speed. One takes 1 minute to cross, another 2 minutes, another 5, and the last 10 minutes. If two men cross together, they must walk at the slower man's pace. There are no tricks--the men all start on the same side, the flashlight cannot shine a long distance, no one can be carried, etc. As they say on Car Talk, the two questions are: 1) What's the fastest they can all get across? b) Why is the answer 17 minutes? Eugene presents two forms of a J program that finds the solution. The first is quite amusing. If ancient APLers ever actually played that game of dropping a cryptic one-liner on a colleague's desk and challenging him to figure out what it does, you can only imagine the reaction if some Jer traveled back in time and dropped this doozie on someone's desk. See for yourself at: http://www.vector.org.uk/v163/gene163.htm Unfortunately, the J solution is flawed. Eugene points out that it doesn't give the correct answer if the speeds are 1, 10, 11, and 12 minutes. Surely we APLers can do better! Anyone care to take a crack at this problem? Jim P.S. If you're reading this and you don't subscribe to Vector, you should! It's the best source of current information about APL available today. The price is a bargain (about $22/year to the U.S. via surface mail), and they'll auto-bill your credit card so the issues just keep rolling in. Subscribe today!  My Solution: First, the data structures. Get them right and the code will practically write itself. After fiddling around with more complicated forms, the simplest representations I could find were these:
The current state of the men is represented by a Boolean vector
having an element for each man. Zero indicates that the man is on
the starting side, one indicates that he's on the ending side. So
the vector:
0 1 0 1
indicates that the second and fourth men have crossed.
A series of crossings is represented by a Boolean "history matrix"
having a column for each man and a row for each crossing. One
indicates that the man crossed (either way), zero indicates that he
stayed put. For example:
1 0 0 1- men 1 and 4 cross0 0 0 1- the 4th man returns0 1 1 0- men 2 and 3 cross0 1 0 0- the 2nd man returns
Note that the rows are not cumulative--the ones in a row indicate only who moved in that single trip. The history matrix is nice because it's simple (non-nested), compact (Boolean), and because, given a matrix H and vector S of speeds (1 2 5 10), you can calculate the total time using a simple expression. (Can you figure out how?)
The programs below work by generating all possible sequences
for getting the men across the bridge. The BRIDGE routine then
computes the time for each sequence and picks the ones with the
fastest time.
The current state at any point in the search is represented by the
state vector and a history matrix of crossings made so far. Lines
[17-20] of CROSS compute B, all possible crossings of the
remaining men. Each row of B will become a history matrix row.
Not-equaling one of these rows with the current state vector S (an
"xor" operation in computer parlance) toggles the state of the men
marked by ones in the row of B.
One crucial element to solving the puzzle is realizing that the
flashlight doesn't have to be carried back by a member of the party
that just crossed--it can be returned by anyone who's on the far
side of the bridge. This is implemented in lines [3-4] of RETURN,
which use the current state, rather than the most recent trip,
to pick return candidates.
Here's the code:
| ||
| ||
Note: The APL programs on this page can be extracted
without you having to retype them. See "Downloading Code" for
instructions.
The puzzler problem is solved as follows:
 The first item of the result (17) is the fastest crossing time. The remaining items are the history matrices for the fastest crossings. There are two ways to get the men across in 17 minutes. First, the two fast guys (men 1 and 2) cross. One of them returns with the flashlight. (Either can return, leading to the two solutions.) Then the two slow guys (3 and 4) cross, and the remaining fast guy returns with the flashlight. Then the two fast guys cross again.*
Here are some other examples:
| ||
| ||
The exhaustive search used by this program is practical for small
cases (for example, the puzzler solution is found in 0.021 seconds
on my 300 MHz Pentium II with APL+Win 3.5), but the search space
increases very rapidly as you add more men to the problem. The
following table gives the number of possible crossing sequences for
various numbers of men and maximum people on the bridge.
Bridge Capacity
Number |
of Men | 2 3 4 5 6
--------+---------------------------------------
2 | 1 1 1 1 1
3 | 6 1 1 1 1
4 | 108 24 1 1 1
5 | 4,320 710 70 1 1
6 | 324,000 43,400 2,970 180 1
Clearly, you'd have to develop some heuristic if you wanted to solve larger
cases.
Avoiding Iteration The loops in CROSS and RETURN could be written non-iteratively using nested array operations, as follows: | ||
| ||
|
However, I don't really like the nested form. The meat of its
solution is mixed up with a bunch of extraneous control junk (eaches
and splits and encloses). Although the looping solution has control
junk, too, it's separated from the meat, which is stated in simple,
direct form within the loop. I find it laborious to figure out what
enclose-with-each or enclose-with-scalar-extension does,
structurally, in the nested solution. In contrast, I have no
problem understanding that the body of the loop is going to be
repeated for each row of B. Sometimes a non-looping solution is
easier to understand because it sits still and allows you to study
its progress through a few array transformations, whereas the
looping solution requires you to mentally execute the loop and
figure out how the steps carried out in one iteration will help
subsequent iterations to converge on a solution. But this is not
one of those cases.
The nested form, by the way, doesn't run significantly faster than
the looping form. (The speed difference when computing the puzzler
solution is only about 2%.)
Avoiding Recursion As absurd as the one-line J solution is, I have to admit a little jealousy at not having a one-line APL solution. Although CROSS and RETURN can each be written as a single line, their recursive nature makes it difficult to combine them into a single mega-line. So I hammered out the recursion, replacing it with two lists of search states that need to be examined. This resulted in the following program: | ||
| ||
With more work, this routine could presumably be reduced to a single
(hideous) APL expression, but by this point I'd sort of lost interest in doing
so.
JimW's Home Page | ||