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 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     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.


I find it curiously illuminating that Microsoft used this puzzle in job interviews. The solution is somewhat counter-intuitive; finding it manually requires a mind that's open to exploring all possibilities. And the solution has philosophical/political implications for the workplace: The journey is completed in surprising time without leaving anyone behind. The slow guys walk together so they don't hold back the fast guys, and the fast guys make more trips because they can.



JimW's Home Page