Agnes, Becky, Cindy and Delia crossed a lake in a canoe that held only two persons.

1. The canoe held two persons on each of three forward trips across the lake and one person on each of two return trips.
2. Agnes was unable to paddle when someone else was in the canoe with her.
3. Becky was unable to paddle when anyone else but Cindy was in the canoe with her.
4. Each person paddled continuously for at least one trip.

Who paddled twice?

DECLARE SUB moveOver ()
DECLARE SUB moveBack ()
CLEAR , , 25000
DIM SHARED l$, r$, paddled(4), plthist$
CLS
l$ = "abcd": r$ = ""
DO
    moveOver
LOOP UNTIL permmove$ = h$

END

SUB moveBack
  FOR a = 1 TO LEN(r$)
    p1$ = MID$(r$, a, 1)
    good = 1
    pdl$ = p1$
    savel$ = l$: saver$ = r$
    r$ = LEFT$(r$, a - 1) + MID$(r$, a + 1)
    l$ = l$ + p1$
    pdr = INSTR("abcd", pdl$)
    plthist$ = plthist$ + pdl$ + " "
    paddled(pdr) = paddled(pdr) + 1

    moveOver

    plthist$ = LEFT$(plthist$, LEN(plthist$) - 2)
    l$ = savel$: r$ = saver$
    paddled(pdr) = paddled(pdr) - 1
  NEXT a

END SUB

SUB moveOver
  FOR a = 1 TO LEN(l$) - 1
  FOR b = a + 1 TO LEN(l$)
    p1$ = MID$(l$, a, 1)
    p2$ = MID$(l$, b, 1)
    FOR pdlr = 1 TO 2
      good = 1
      SELECT CASE pdlr
        CASE 1: pdl$ = p1$: npdl$ = p2$
        CASE 2: pdl$ = p2$: npdl$ = p1$
      END SELECT
      IF pdl$ = "a" THEN good = 0
      IF pdl$ = "b" AND npdl$ <> "c" THEN good = 0
      IF good THEN
        savel$ = l$: saver$ = r$
        l$ = LEFT$(l$, a - 1) + MID$(l$, a + 1)
        l$ = LEFT$(l$, b - 2) + MID$(l$, b)
        r$ = r$ + p1$ + p2$
        pdr = INSTR("abcd", pdl$)
        plthist$ = plthist$ + pdl$ + npdl$ + " "
        paddled(pdr) = paddled(pdr) + 1

        IF l$ = "" THEN
          FOR i = 1 TO 4
            IF paddled(i) = 0 THEN good = 0
          NEXT i
          IF good THEN
            PRINT plthist$; " |";
            FOR i = 1 TO 4
              IF paddled(i) > 1 THEN
                PRINT MID$("abcd", i, 1); paddled(i)
              END IF
            NEXT i
          END IF
        ELSE
          moveBack
        END IF

        plthist$ = LEFT$(plthist$, LEN(plthist$) - 3)
        l$ = savel$: r$ = saver$
        paddled(pdr) = paddled(pdr) - 1
      END IF
    NEXT pdlr
  NEXT b
  NEXT a
END SUB

finds

ca a da c bc | c 2
ca c bc a da | c 2
da a bc c ca | c 2
da a ca c bc | c 2
bc c da a ca | c 2
bc c ca a da | c 2

which in all cases indicates that Cindy paddled twice as shown by the last two columns, which indicate the identity of the double paddler.

In each row, the double letters indicate two people crossing to the opposite side; the one doing the paddling is listed first in the pair. The single letters (other than the last, which just indicates the double paddler) indicate who paddled the boat solo back to the original side.

Posted by Charlie on 2013-01-17 21:29:06