# Doc/Articles/Play163

**At Play With J**
... Table of Contents ... Previous Chapter ... Next Chapter

# 22. We’ll Cross That Bridge When We Come To It

. *By* Eugene McDonnell. *First published in* Vector, 16, 3, *(January 2000), 126-130*.

Björn Helgason, from Iceland, submitted this problem to the Internet J Forum:

Four people, A, B, C, and D, come to a bridge at night, with only a flashlight to guide them. The time each one takes to cross the bridge is: A in 1 minute, B in 2 minutes, C in 5 minutes, and D in 10 minutes. The bridge will only support two of them at a time, and the time to cross is, of course, that of the slower walker. The flashlight must be carried on any crossing. They want to get across the bridge as quickly as possible. Since they have a palmtop computer with J installed, they write a program that tells them what the minimum time is, and in what order they should go forth and back over the bridge. Your problem is to write an equivalent program. To help you get started, the program found that the minimum time is seventeen minutes.

The first response to Björn’s problem said that there was no need for a program to be written, because it could be solved in one’s head; and complained, furthermore, that seventeen minutes was impossible; it was demonstrable that the minimum time was nineteen minutes: the fastest one, A, going across first with B and the flashlight, leaving B on the other side, coming back with the flashlight to go across with C, then coming back with the flashlight again to go across with D: two plus one plus five plus one plus ten, making nineteen, and that the order was unimportant so long as A was the constant companion. It couldn’t be done more quickly, since the fastest man was always the one to go back. However, Helgason kept insisting that seventeen was the minimum, and offered to send a private message to the complainer giving such a solution.

After a fair amount of back and forth between Helgason and the disbeliever, the issue was resolved when Kirk Iverson finally submitted a solution from Toronto which gave the seventeen-minute solution for the problem. He admitted that he wasn’t sure whether the program would give the minimum answer for all possible combinations of number of people per crossing and times for each to cross, but it would handle many cases. [Yes, Kirk is related to Ken; he’s a nephew.] The disbeliever was converted, of course, and made a handsome apology. See whether you can arrive at a solution, either to this specific problem, or to the more general one solved by Kirk. When you’re satisfied that you either can solve the problem, or have thrown up your hands in frustration, or else are just too lazy to give it any more thought, you can go on to read Kirk Iverson’s solution. From here on, it is his text, slightly amended, with additional comments by me shown in square brackets.

First, the “compiled” code, in case anyone wants to run this without seeing what it does:

NB. ---- copy into ijs window and execute -------------------- ".(noun define)-.LF bridge=:(<./@(>@(2&{))({.@],(1&{@],&.><@[),(2&{@]-.&.><@[),3&} .@],<@[)])^:(*@#@(>@(1&{)))@(((((>@{.@[-.]);>@{:@[)}.@(([-.[-. ])/))@(>@(0&{)(([<.#@]){.])"1(,:|.)@(/:~)@(>@(1&{)))([>@{~(>@( 2&{)@]<&(<./)>@{:@[)+.#@(>@{:@[)=#@(>@(1&{))@])])({.@],(1&{@]- .&.><@[),(2&{@],&.><@[),3&}.@],<@[)])^:(*@#@(>@(1&{)))^:_&.(({ .;}.;''"_) :.((+/@:(>./@>);])@(3&}.)))@, ) NB. ----------------------------------------------------------

[I speculate that Kirk first wrote a series of verbs to accomplish the objective, then obtained this unreadable mess by applying the fix adverb (`f.`) to the main verb. Doing this replaced all the subordinate verbs by their definitions, yielding the aforesaid mess. He probably then obtained the character string corresponding to the fixed function, using the `5!:5` form of the foreign conjunction, and displayed this in a field 62 characters wide, giving the six lines shown above, and copied them. The line following the first `NB.` line contains three items that are defined in a script loaded when a J session starts: the variable *noun* has the value `0`; the adverb *define* has the value ` : 0` (explicit definition script form) and the variable *LF* is the linefeed character, defined as `0{a.` . The `(noun define)` in the first line after the comment line (beginning with `NB.`) permits entry of multiple lines of text. Kirk pasted in the six lines, then typed a right parenthesis on the next line, and hit enter, thus causing entry to terminate, and the `(noun define)` was replaced by the six lines shown. The `-.LF` removed the linefeeds from this text, and the `".` executed the line, causing a verb named `bridge` to be defined.

I copied the `bridge` verb, and pasted it into a J session, and it worked as advertised.
The left argument to `bridge` is the maximum number of people who can walk on the bridge at the same time; the right argument is a list of the length of time each person needs to cross.
The result is a boxed list of total elapsed time, followed by all moves:

2 bridge 1 2 4 +-+---+-+---+ |7|1 2|1|4 1| +-+---+-+---+

The result signifies 7 minutes total time; 1 and 2 cross; 1 returns; 4 and 1 cross. [This is your last chance to try figuring out how to solve our problem, because the solution Kirk obtained is now going to be shown.]

NB. ----------------------------------------------------------------------- NB. Crossing the bridge. NB. Rules NB. Move all people from one side of bridge to other. NB. Each person has an individual time it takes to cross. NB. At most MAXLOAD number of people on bridge. NB. Torch must always be with a group on the bridge. NB. Speed of a group is the speed of the slowest member. NB. Strategy NB. Overall strategy is to pick a good group to go over, and NB. then have the fastest person to return with the torch. Wash, NB. rinse, repeat. I call the guy to return the torch the "runner". NB. NB. We attempt to move the slowest people together as a group, NB. rather than split them up to slow down all groups. We move NB. the slowest ones over whenever there is a suitable runner NB. to return, i.e., none of this slow group will have to return. NB. NB. If there is no good runner, we select the fastest to go over NB. and act as runners. We only include enough runners which are NB. necessary to bring in the rest of the people. NB. Notes NB. Iteration is done by repeatedly applying a function to NB. the full set of data until it results in everyone moved. NB. Data is maxload;unmoved;moved;move0;move1;move2;... NB. Verbs to access pieces from the data maxload=: >@(0&{) NB. maximum number of people on the bridge unmoved=: >@(1&{) NB. people not yet moved moved=: >@(2&{) NB. people already moved moves=: 3&}. NB. record of all moves more=: *@#@unmoved NB. are there more to move? NB. move/unmove move people across bridge NB. x. is list of people to move; y. is data move=: {.@] ,(1&{@] less each <@[),(2&{@] , each <@[), 3&}.@] , <@[ unmove=: {.@] ,(1&{@] , each <@[),(2&{@] less each <@[), 3&}.@] , <@[ NB. Strict <less> Similar to -. but removes from x only the number NB. of matching items found in y. All items in y are expected to be NB. found in x, and the items in the result are in the same order as NB. they appear in x. Universe is ~.x, and is catenated in front of NB. y, therefore count (#/.~) of each returns the counts of the NB. respective items. The difference (incremented to compensate for NB. the catenation of the universe onto y) is used to copy items from NB. the universe. less=: universe #~ [ >:@-&count universe , ] universe=: ~.@[ count=: #/.~ NB. Pick the group to go across. Runners are the fast group to NB. shuttle the rest over; waddlers are the slower group put together NB. to capitalize on the slowest of the bunch. groups=: sort@unmoved (runners ; waddlers) ] runners=: [ maxtake~ required <. maxload@] required=: 1 >:@>. #@[ <:@>.@% <:@maxload@] waddlers=: maxload@] maxtake |.@[ pickslow=: nogoodrunner +. lastgroup NB. 0-runners; 1-waddlers nogoodrunner=: moved@] <:&fastest slower lastgroup=: #@slower = #@unmoved@] NB. fastest/slowest in a group fastest=: <./ slowest=: >./ slower=: >@{:@[ maxtake=: ([ <. #@]) {. ] NB. take, but don't overtake pick=: groups (pickslow >@{ [) ] NB. forward - pick group to go and move them NB. return - pick fastest runner and move back, if more to move forward=: pick move ] return=: (fastest@moved unmove ])^:more NB. iterate repeats the forward/return action until there are no more. iterate=: return@forward^:more^:_ NB. assemble the argument into the data structure; inverse NB. computes total trip time from moves, and returns that along NB. with the moves. assemble=: ({. ; }. ; ''"_) :. ((+/@:(slowest@>) ; ])@moves) NB. maxload play speeds bridge=: (iterate&.assemble)@, NB. -----------------------------------------------------------------------

[And now for our problem:]

2 bridge 1 2 5 10 +--+---+-+----+-+---+ |17|1 2|1|10 5|2|2 1| +--+---+-+----+-+---+

The total time is 2+1+10+2+2, or 17, as was required. An alternative would have 2 return the first time, and 1 the second time, and this also is minimum.
Kirk’s J implementation consists of two dozen or so verbs, all in tacit form, so this is a functional programming solution. The iterate verb continues until there is no more to be done, using power to the limit, denoted by infinity (`^:_`).

As this article goes to press, it is recognized that Kirk’s solution is not guaranteed to give the minimum result for all cases; for example, it fails for 1 10 11 12; but it was the first solution that gave the minimum result for the given case 1 2 5 10.

This article has ** not** been updated to reflect the current version of J because the code works as-is.

In verb `required`, I nevertheless replaced `1:` by `1` to propose a NVV fork rather than a VVV fork, as suggested in the Editing Guidelines. gk