Fog Creek Software
Discussion Board




solution: hard river crossing (improved)

solution: hard river crossing

a disfunctional family has to cross the river. on one side of the river are a mom and 2 daughters, dad and 2 sons, the maid and the dog. there is a boat only big enough to hold 2 people (counting the dog as 1 person). only the adults are capable of operating the boat. everyone has to get to the other side, without anything bad happening.

difficulties: if the dog is left with anyone and the maid isn't there to control him, he'll bite. the dad can't be left with any of the daughters when the mom isn't there. likewise, the mom can't be trusted alone with either of the sons when the dad isn't there.

remember! only an adult can operate the boat, AND the boat can't drive itself.

Original solution given requires 19 one-way trips  whereas the modified one requires 17:

Modified Solution:

We start with a mother (m), two daughters (d1, d2), a father (f), two sons (s1, s2), a housemaid (h), and a dog (c - canine) on the west (W) shore, and they all want to get to the east (E) shore.


W = {m, d1, d2, f, s1, s2, h, c} // everyone on the west shore
E = {} // no one on the east shore

let's move everyone, over...

housemaid and canine go east, and the housemaid comes back:

W = {m, d1, d2, f, s1, s2, h}
E = {c}

housemaid (h) and father (f) go east, father comes back:

W = {m, d1, d2, f, s1, s2}
E = {h, c}

father and s1 go east, father comes back:

W = {m, d1, d2, f, s2}
E = {s1, h, c}

father and s2 go east, father comes back:

W = {m, d1, d2, f}
E = {s2, s1, h , c}

mother and father go east, mother comes back:

W = {m, d1, d2}
E = {f, s2, s1, h, c}

mother and d1 go east, housemaid and c come back:

W = {d2, h, c}
E = {m, d1, f, s1, s2}

h and d2 go east, h comes back

W = {h, c}
E = {m, d1, d2, f, s1, s2}

h and c go east

W = {}
E = {m, d1, d2, f, s1, s2, h, c}

Deepti
Tuesday, February 10, 2004

Second step, you violate one of the rules:
housemaid (h) and father (f) go east, father comes back:

W = {m, d1, d2, f, s1, s2}
E = {h, c}


if h and f go east.. it leaves m with the sons.  can't do this w/o father there.

Michael Pryor
Fog Creek Software
Tuesday, February 10, 2004

"can't leave m with sons"

ok, then, but at least grant that the original phrasing was ambiguous:
"the mom can't be trusted ALONE with EITHER of the sons when the dad isn't there"

It wouldn't be unreasonable to say that this constraint is satisfied when
(a) the other son is present, or (stronger)
(b) a daughter is present.

ano nymous
Friday, February 13, 2004

I would assume that the OP's solution meets the OP's (intended) statement.
However, "the mom can't be trusted alone with either of the sons when the dad isn't there" is ambiguity incarnate.  "alone" already implies the dad isn't there, so adding that clause confuses things.  In addition, the "likewise" indicates that this statement should mirror the one about the mother, which doesn't have the "when the x isn't there" clause.

Brian
Friday, February 13, 2004

*  Recent Topics

*  Fog Creek Home