There are 8 people that need to cross a river. The water is too deep and fast to walk or swim across, and the only transportation device available is a raft. The raft can only be operated by adults, cannot float across the river on its own, and can carry at most two people.

The 8 people are a juvenile delinquent, her jailer, and a dysfunctional family of six: mother, father, two sons, and two daughters. To be clear, the only adults are the jailer, the mother, and the father.

Unfortunately some people fight with each other:

The juvenile delinquent will fight with anybody if her jailer is not present.

The father fights with either daughter if the mother is not present to mediate.

The mother fights with either son if the father is not present to mediate.

How can these 8 people cross the river without any fights? How many trips on the raft did it take?

For a fun way to test out your theories, click here and then click on the blue circle.

(In reply to re: Finally--a computer solution--bug by Charlie)

The fixed program produces:

9 Jj                       DFJMSdjs
8 Js J       Jj            DFMSds
7 FS Jj      Jjs           DFMSd
6 FM F       FSs           DJMdj
5 Jj M       FMSs          DJdj
4 FM F       FJSjs         DMd
3 Md M       FJMSjs        Dd
2 DJ jJ      FJMSdjs       D
1 Jj J       DFJMSds       j

Where, again, the sequence is from bottom to top, so follow the numbers in that direction.  Each row represents a round trip except for row 9 at the top, so this is indeed 2*8+1=17 rides across the river. F and M are the father and mother; J is the jailer and j is the j.d.; S and D are the elder son and daughter and s and d are the younger son and daughter.

The columns are the sequence number, the travelers for the outgoing trip and then the trip back, and the resulting sets of people still on the first side and then the second side.

DECLARE FUNCTION btcompat# (s$)
DECLARE SUB getRec (s$, row#, col#)
DECLARE SUB putRec (s$, row#, col#)
DECLARE FUNCTION compat# (s$)
DECLARE FUNCTION number# (s$)
DEFDBL A-Z
CLS
DIM SHARED template$
template$ = "DFJMSdjs"  ' Dgtr1,Father,Jailer,Mother,Son1,Dgtr2,JD,Son2
DIM side1$(256), side2$(256)

OPEN "dyscros2.bin" FOR BINARY AS #2
' at 4 bytes per cell, a 256x256 matrix takes up 262,144 bytes
' first and second  = boat rider(s)'s letter(s)
' third and fourth  = return boat rider(s)'s letter(s)

s4$ = "    "
FOR i = 0 TO 255
 FOR j = 0 TO 255
  PUT #2, , s4$
 NEXT
NEXT

FOR n = 0 TO 255
  s1$ = template$: s2$ = ""
  i = n: p = 8
  DO
    r = i MOD 2: i = i \ 2
    IF r = 0 THEN
      MID$(s1$, p, 1) = " "
      s2$ = MID$(template$, p, 1) + s2$
    END IF
    p = p - 1
  LOOP UNTIL p = 0
  DO
   ix = INSTR(s1$, " ")
   IF ix THEN s1$ = LEFT$(s1$, ix - 1) + MID$(s1$, ix + 1)
  LOOP UNTIL ix = 0
  side1$(n) = s1$: side2$(n) = s2$
 ' PRINT n; TAB(15); s1$; TAB(30); s2$
 ' IF n MOD 40 = 0 THEN DO: LOOP UNTIL INKEY$ > ""
NEXT

'build transition matrix
FOR start = 0 TO 255
  s1$ = side1$(start): s2$ = side2$(start)
  IF compat(s1$) AND compat(s2$) THEN
   FOR i = 1 TO LEN(s1$)
    bt$ = MID$(s1$, i, 1) + " "
    newS2$ = RTRIM$(s2$ + bt$)
    newS1$ = LEFT$(s1$, i - 1) + MID$(s1$, i + 1)
    IF btcompat(bt$) AND compat(newS2$) AND compat(newS1$) THEN
      newNum = number(newS1$)
      getRec chk$, start, newNum
      IF chk$ < "A" THEN
        putRec bt$, start, newNum
      END IF
      ' figure return trip
      FOR k = 1 TO LEN(newS2$)
       bt2$ = MID$(newS2$, k, 1) + " "
       newerS1$ = RTRIM$(newS1$ + bt2$)
       newerS2$ = LEFT$(newS2$, k - 1) + MID$(newS2$, k + 1)
       IF compat(newerS1$) AND compat(newerS2$) AND btcompat(bt2$) THEN
        newerNum = number(newerS1$)
        getRec chk$, start, newerNum
        IF MID$(chk$, 3, 2) < "A" THEN
          putRec bt$ + bt2$, start, newerNum
        END IF
       END IF
       FOR l = k + 1 TO LEN(newS2$)
         MID$(bt2$, 2, 1) = MID$(newS2$, l, 1)
         newerS1$ = RTRIM$(newS1$ + bt2$)
         ix = INSTR(newerS2$, RIGHT$(bt2$, 1))
         newestS2$ = LEFT$(newerS2$, ix - 1) + MID$(newerS2$, ix + 1)
         IF compat(newerS1$) AND compat(newestS2$) AND btcompat(bt2$) THEN
           newerNum = number(newerS1$)
           getRec chk$, start, newerNum
           IF MID$(chk$, 3, 2) < "A" THEN
             putRec bt$ + bt2$, start, newerNum
           END IF
         END IF
       NEXT l
      NEXT k
    END IF
    FOR j = i + 1 TO LEN(s1$)
      MID$(bt$, 2, 1) = MID$(s1$, j, 1)
      newS2$ = RTRIM$(s2$ + bt$)
      ix = INSTR(newS1$, RIGHT$(bt$, 1))
      newerS1$ = LEFT$(newS1$, ix - 1) + MID$(newS1$, ix + 1)
      IF compat(newerS1$) AND compat(newS2$) AND btcompat(bt$) THEN
        newerNum = number(newerS1$)
        getRec chk$, start, newerNum
        IF MID$(chk$, 1, 2) < "A" THEN
          putRec bt$, start, newerNum
        END IF
    
        ' figure return trip
        FOR k = 1 TO LEN(newS2$)
         bt2$ = MID$(newS2$, k, 1) + " "
         newestS1$ = RTRIM$(newerS1$ + bt2$)
         newerS2$ = LEFT$(newS2$, k - 1) + MID$(newS2$, k + 1)
         IF compat(newestS1$) AND compat(newerS2$) AND btcompat(bt2$) THEN
          newerNum = number(newestS1$)
          getRec chk$, start, newerNum
          IF MID$(chk$, 3, 2) < "A" THEN
            putRec bt$ + bt2$, start, newerNum
          END IF
         END IF
         FOR l = k + 1 TO LEN(newS2$)
           MID$(bt2$, 2, 1) = MID$(newS2$, l, 1)
           newestS1$ = RTRIM$(newerS1$ + bt2$)
           ix = INSTR(newerS2$, RIGHT$(bt2$, 1))
           newestS2$ = LEFT$(newerS2$, ix - 1) + MID$(newerS2$, ix + 1)
           IF compat(newerS1$) AND compat(newestS2$) AND btcompat(bt2$) THEN
             newestNum = number(newestS1$)
             getRec chk$, start, newestNum
             IF MID$(chk$, 3, 2) < "A" THEN
               putRec bt$ + bt2$, start, newestNum
             END IF
           END IF
         NEXT l
        NEXT k
      END IF
    NEXT
   NEXT i
   FOR i = 1 TO LEN(s$) - 1
     FOR j = i + 1 TO LEN(s$)
     NEXT
   NEXT
  END IF
NEXT

REM

DIM h$(30, 256)

genr = 1
FOR i = 0 TO 255
 getRec s$, 255, i
 IF LTRIM$(s$) > "" THEN
  h$(1, i) = CHR$(255) + s$
  PRINT i; s$; side2$(i)
 END IF
NEXT

DO
 genr = genr + 1
 flag = 0
 FOR dest = 0 TO 255
  ps$ = h$(genr - 1, dest)
  IF LTRIM$(MID$(ps$, 2, 1)) = "" OR LTRIM$(MID$(ps$, 4, 1)) = "" AND dest <> 0 THEN
    FOR src = 0 TO 255
     getRec s$, src, dest
     IF LTRIM$(s$) > "" AND dest = 0 OR LTRIM$(MID$(s$, 3)) > "" THEN
      backw = 1
      DO
        ps$ = h$(genr - backw, src)
        IF LTRIM$(MID$(ps$, 4, 1)) = "" THEN EXIT DO
        IF LTRIM$(MID$(ps$, 4, 1)) <> "-" THEN EXIT DO
        backw = backw + 1
      LOOP
      IF LTRIM$(MID$(ps$, 4, 1)) > "" THEN
        h$(genr, dest) = CHR$(src) + s$
        PRINT genr; src; side1$(src); ","; side2$(src); ";"; dest; side1$(dest); ","; side2$(dest); ";"; s$
        flag = 1
        EXIT FOR
      END IF
     END IF
    NEXT
  ELSE
    h$(genr, dest) = CHR$(dest) + "----"
  END IF
 NEXT
LOOP UNTIL flag = 0 OR genr > 12
PRINT genr

prv = 0
FOR i = genr TO 1 STEP -1
 PRINT i; MID$(h$(i, prv), 2, 2); " "; MID$(h$(i, prv), 4, 2), side1$(prv), side2$(prv)
 prv = ASC(h$(i, prv))
NEXT

CLOSE
END

FUNCTION btcompat (s$)
  c = 1
  IF LEN(RTRIM$(s$)) > 1 THEN
    IF INSTR(s$, "j") > 0 AND INSTR(s$, "J") = 0 THEN c = 0
    IF INSTR(s$, "F") > 0 AND INSTR(LCASE$(s$), "d") > 0 AND INSTR(s$, "M") = 0 THEN c = 0
    IF INSTR(s$, "M") > 0 AND INSTR(LCASE$(s$), "s") > 0 AND INSTR(s$, "F") = 0 THEN c = 0
  END IF
  IF INSTR(s$, "F") = 0 AND INSTR(s$, "M") = 0 AND INSTR(s$, "J") = 0 THEN c = 0
  btcompat = c

END FUNCTION

FUNCTION compat (s$)
  c = 1
  IF LEN(RTRIM$(s$)) > 1 THEN
    IF INSTR(s$, "j") > 0 AND INSTR(s$, "J") = 0 THEN c = 0
    IF INSTR(s$, "F") > 0 AND INSTR(LCASE$(s$), "d") > 0 AND INSTR(s$, "M") = 0 THEN c = 0
    IF INSTR(s$, "M") > 0 AND INSTR(LCASE$(s$), "s") > 0 AND INSTR(s$, "F") = 0 THEN c = 0
  END IF

  compat = c
END FUNCTION

SUB getRec (s$, row, col)
 p = row * 256 * 4 + col * 4 + 1
 s$ = SPACE$(4)
 GET #2, p, s$
END SUB

FUNCTION number (s$)
 pow = 1
 FOR p = 8 TO 1 STEP -1
  IF INSTR(s$, MID$(template$, p, 1)) THEN n = n + pow
  pow = pow * 2
 NEXT
 number = n
END FUNCTION

SUB putRec (s$, row, col)
 p = row * 1024 + col * 4 + 1 ' 1024=256*4
 s1$ = LEFT$(s$ + SPACE$(4), 4)
 PUT #2, p, s1$
END SUB

 

Posted by Charlie on 2005-09-28 13:54:43