Backgrounder

I recently discovered that, a couple of years ago, a former coworker was wrestling with the following problem (and using the exercise to help him learn a new programming language).

Well, unfortunately this guy got “wrapped around the axle” and didn’t find a solution. He found a non-optimal member of the search space, and either thought it was optimal or didn’t know if it was optimal. (His team leader (not me) had to tell him that his approach was incorrect, and he didn’t have enough time to get back to it before moving off to do other things.)

Fast forward a couple of years later, when your author was spelunking code during a holiday weekend, where I happened upon the hapless code, but more importantly, the statement of the problem. I love puzzles, I have time, so … this is a no brainer: I have to try!

Solution

First, before we write one line of code, let’s think about this for a minute. The first thing we want to try to determine for problems like this is how big the search space is.

What’s the “search space”? That’s the set of all candidates for solutions to the problem, and the implication here is that we have a way to evaluate those candidates to show which ones are “better” than others, and to leverage that evaluation to find eventually the “best” of the candidates (which will be our solution(s)).

If the search space is large, we have to think of ways to “prune” it, to make it smaller. Usually this means that we think of a reason why it would not make sense to evaluate some candidate solutions (hopefully, a lot of them!). Any gains we make here will mean a more performant solver. Another way to say this is that we will end up NOT asking the computer to do a needless number of evaluations.

In our case here, our initial search space is all the different ways in which the people can get from one side of the bridge to the other, under the constraints of the problem statement.

If by “all the different ways” we mean the ways in which the number of bridge crossings and people making those crossings, differ, then, depending on how one counts those number of ways, the search space could be infinite!

But, the pruning for this problem (unlike problems in general) is actually trivial: it only takes a second or two to notice that, for each round trip (i.e. pair of bridge crossings, back and forth), we should always be accruing a person on the destination side (which means we will also be losing a person on the source side). If this condition does not prevail, then we have wasted movements, and such candidates would be a waste to generate and evaluate for “goodness”.

Hence, in a round trip, we should always be sending two people to the other (destination) side and returning one person (with the torch) to the original (source) side. Another way to say this is that any candidate for a solution should have

• two people crossing together to the other side
• one person returning
• two people crossing together to the other side
• one person returning
• two people crossing together to the other side

After this series of moves, all the people should be on the other side of the bridge.

It turns out that the search space described by the aforementioned contains only 108 candidates. This is how we could count them: there are

• 6 ways to send two people to the destination side (4 choose 2) TIMES
• 2 ways to send one person back (2 choose 1) TIMES
• 3 ways to send two people to the destination side (3 choose 2) TIMES
• 3 ways to send one back (3 choose 1) TIMES
• 1 way to send the final two people to the destination side (2 choose 2).

Finding a solution in such a small space is very “doable” with an exhaustive search, i.e., by evaluating every member of the search space. Sometimes, at work, we call this “caveman optimization.” And that is the method with which we are going to proceed.

The good news is that, as well as reduced runtime, we will have reduced “dev time” (development time), as the code to generate the solution is less than 30 lines of picolisp ² code.

A Useful Utility

First, we’ll need this utility that generates K-combinations out of the members of a list. Obviously, our most important usage will be the generation of all the different ways we can have 2-combinations (K = 2), in other words, all the different ways to choose a pair of people out of a group.

The following code was “stolen” from https://rosettacode.org/wiki/Combinations#PicoLisp. By the way, if you code in picolisp, you should know that there are many excellent examples of picolisp code on Rosetta Code.

(de comb (K Lst)
  (cond ((=0 K) '(NIL))
        ((not Lst))
        (T
         (conc
          (mapcar '((Y) (cons (car Lst) Y))
                  (comb (dec K) (cdr Lst)) )
          (comb K (cdr Lst)) ) ) ) )

Here is an example usage.

: (comb 2 '(A B C D))
-> ((A B) (A C) (A D) (B C) (B D) (C D))

That’s 8 LOC (lines of code) so far. comb is actually more general than what we need, but that’s OK.

Cost Input

The association list Costs contains the costs — the time in minutes needed to cross the bridge alone — that is associated to each person. This is our main input and was given in the problem statement. A person is represented by a symbol (either A, B, C or D).

(de Costs (A . 1) (B . 2) (C . 5) (D . 8))

LOC is now at 9.

Crossing the bridge

We have to have a way to model the effects of people crossing the bridge. In this instance of the problem, there will be either one or two people crossing the bridge at one time.

The following function cross will move the Crossers (a list of people/persons) from one side of the bridge Src (a list) to the other side Dst (a list), by computing a list of the “new Src” and “new Dst”.

(de cross (Crossers Src Dst)
  (list (diff Src Crossers) (append Crossers Dst)))

Total LOC is now 11.

Crossing Example

(cross '(B C) '(A B C) '(D)) evaluates to ((A) (B C D)) which means that when A, B, and C are on one side of the bridge (i.e., in Src) and D is on the other (i.e., in Dst), after B and C cross the bridge, they leave A behind and join D on the other side, i.e. the other side now “contains” B, C and D.

Search

Now, we have everything in place to write our search routine. Before that, some definitions are now in order.

move

A move is a crossing of the bridge (in either direction) and is represented by a list of one or two people, e.g., (A B) which means that A and B cross the bridge together; (A) means A crosses alone.

path

A path is a series (i.e., a list) of moves that gets all the people from one side of the bridge to the other in a minimum number of crossings, if they can only cross one or two at a time, and with each crossing they must carry the (one) torch.

For instance, the path ((B C) (B) (B A) (A) (A D)) means that

• B and C cross over together,
• B crosses back alone,
• then B and A cross over together,
• A crosses back alone,
• and finally, A and D cross over together

(and now everyone is together on the other side of the bridge).

Path Finder

Now, with the aforementioned code, we are able to write a routine to determine all the paths in our search space.

The “meat” of the search algorithm is in the following function find-all-paths*. It finds all paths that begin with a move of K people (K = 1 or 2) from one side of the bridge Src to the other Dst.

The idea is that this function will be called recursively. At the top of the call stack (i.e., the first time find-all-paths* is called), K will be 2 (i.e., 2 people will start crossing the bridge), all the people will be at/in Src and no one will be at/in Dst. Moves will contain all the possible pairs of people (who will make the first crossing) drawn from the four. For each of those moves (Move), we compute the change in state at each of the sides — that’s NewSrc and NewDst — by calling cross. Then, we set up the recursive sub-problem: say, Move is (A B); we now find all the (sub-)paths that follow the move (A B). We do this by recursive call, changing K to 1 (i.e., one person will be returning), and effectively swapping the source and destination sides — notice in the call that NewDst precedes NewSrc — as now the next crossing will occur in the opposite direction.

We continue along in this fashion until, after a crossing, NewSrc is empty – this means that there are no more moves to make. This is the base case of our recursion, and at this point, we offer up a list containing the empty list (i.e., (list NIL)) to satisfy the cons of the current Move (which is also the last move of the path that this process is building).

(de find-all-paths* (K Src Dst)
  (let Moves (comb K Src)
    (mapcan '((Move)
              (let ((NewSrc NewDst) (cross Move Src Dst))
                (mapcar '((Path) (cons Move Path))
                        (if NewSrc
                            (find-all-paths* (if (= 2 K) 1 2) NewDst NewSrc)
                            (list NIL)))))
            Moves)))

Total LOC is now 20.

Path Finder Wrapper

This is the wrapper that accepts only the list of people that start on one side of the bridge at the beginning of the problem. It sets up the first (top level) call to find-all-paths* that kicks things off. Notice that this call

• directs two people to cross,
• all the people are on the Src side, and
• there is nobody on the Dst side.

(de find-all-paths (People)
  (find-all-paths* 2 People NIL))

Total LOC is now at 22.

Examples

Here are a couple of examples to see what it looks like from the caller side.

If there are only two people that need to cross, there is only one path in the search space.

: (find-all-paths '(A B))
-> (((A B)))

If there are only three people that need to cross, there are 6 paths in the search space. (Each path has length 3, i.e., there are three bridge crossings for each path.)

: (find-all-paths '(A B C))
 -> (((A B) (A) (A C)) ((A B) (B) (B C)) ((A C) (A) (A B))
     ((A C) (C) (C B)) ((B C) (B) (B A)) ((B C) (C) (C A)))

Finding all the paths is the same as generating the search space. We know that our search space has size 108. Let’s quickly check that.

: (length (find-all-paths '(A B C D)))
-> 108

Path Evaluation

Finally, we need a function to compute the total cost of having everyone get to the other side of the bridge, for each way to do that (i.e., for each path). This will be the “scoring”, or evaluation, function for each path.

Given a path Path, we compute its total cost by the summing up the cost of each “step” (or move) in the path.

(Recall from the problem statement that if a move/step is (X Y) — i.e., persons X and Y cross together — then the cost of that move is the greater of the costs of persons X and Y, when each cross alone. (“When two people cross the bridge together, they must move at the slower person’s pace.”))

(de cost (Path)
  (sum '((Move) (maxi '((Person) (get Costs Person)) Move) @@) Path))

Example:

: (cost '((B C) (B) (B A) (A) (A D)))
-> 18

Total LOC has now reached 24.

Application

Now, we can set up our call that computes the answer to the problem. If we were building an executable program, this would be part of the body of our “main()” function; however, since we are in the REPL, I like to call it “the punchline”.

Our punchline here produces all the optimal paths and their (common) cost.

: (list (mini '((L) (cost (car L)))
              (by cost group (find-all-paths '(A B C D))) )
        @@)
-> ((((A B) (A) (C D) (B) (B A)) ((A B) (B) (C D) (A) (A B))) 15)

Ah! We found two solutions!

And our final count for LOC is 27.

Answering the question

Recall the question from the problem statement.

The question is, can they all get across the bridge in 15 minutes or less?

The answer is: yes; it can be accomplished in 15 minutes, if

• A and B go over together (2 minutes)
• A / B comes back (1 / 2 minute(s))
• C and D go over together (8 minutes)
• B / A comes back (2 / 1 minute(s))
• A and B go over together (2 minutes).