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 cross 0 0 0 1- the 4th man returns 0 1 1 0- men 2 and 3 cross 0 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 1Clearly, 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 |