All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 River Cross Resolution (Posted on 2016-10-12)
Six friends, Alex, Ben, Cal, Dan, Elmer and Frank need to cross a river in a small canoe. The canoe can only carry a maximum of 130 kg.

Al weighs 120 kg, Ben weighs 110 kg, Cal weighs 90 kg, Dan weighs 80 kg, Elmer weighs 50 kg, Frank weighs 40 kg and they have 20kg of supplies.

How do they get across in a minimum number of steps?

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 computer solution Comment 1 of 1
The program that solved Bridge Cross Baffle (hmmm... there's a trial going on now about Gov. Christie's involvement), was modified to allow the needed single-passenger crossings going to the opposite side, and counting crossings instead of minutes, while keeping the weight at or below the maximum allowed.

The first 10 ways (f for forward, b for back):

`f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:CF b:C      f:DE b:F      f:CF 13f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:CF b:F      f:DE b:C      f:CF 13  f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:CF b:F      f:DE b:D      f:DF 13f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:CF b:F      f:DE b:E      f:EF* 13f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:CF b:F      f:DF b:D      f:DE 13f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:CF b:F      f:DF b:F      f:EF* 13f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:CF b:F      f:EF* b:E     f:DE 13f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:CF b:F      f:EF* b:F     f:DF 13f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:DE b:D      f:CF b:E      f:DE 13f:CF b:C     f:A b:F      f:CF b:C      f:B* b:F      f:DE b:D      f:CF b:F      f:DF 13`

29888 done

Indicates that these 10 solutions, with 13 crossings each, which is the minimum, are the first ten of 29,888 variations that will work -- quite a lot more than the eight optimal solutions for the Bridge problem. (Trying for 12 or fewer crossings produced no solutions.)

Taking the second one to expand manually:

`forward   back           remaining    crossed over  CF        C             ABCDE                 F  A         F              BCDEF           A  CF        C              BCDE            A    F  B         F               CDEF           AB  CF        F                DEF           ABC  DE        C               C  F           AB DE  CF                                       ABCDEF`

The supplies can go over with B on his solo crossing.

Some of the other methods shown above include a crossing with E and F; their total of 90 pounds would allow for a greater margin of error if they carried the supplies instead of B alone.

The program did not consider getting the supplies across, but marked any trip with an * if it had enough spare capacity for them, and all the solutions had at least one trip with such a capacity, particularly as B must make the crossing alone (no person is light enough to go with him), and has just enough spare capacity to bring the supplies.

Some sampling of other solutions (every 500th scenario):

`f:CF b:C       f:A b:F       f:EF* b:E       f:B* b:F       f:DF b:F       f:EF* b:F       f:CF 13f:CF b:C       f:B* b:F       f:DF b:D       f:DE b:F       f:A b:E       f:EF* b:F       f:CF 13f:CF b:C       f:DE b:E       f:A b:D       f:DE b:F       f:B* b:D       f:CF b:F       f:DF 13f:CF b:C       f:DE b:F       f:B* b:E       f:CF b:D       f:A b:F       f:EF* b:F       f:DF 13f:CF b:F       f:A b:C       f:CF b:F       f:EF* b:C       f:B* b:F       f:CF b:E       f:DE 13f:CF b:F       f:B* b:C       f:CF b:F       f:A b:C       f:CF b:F       f:DE b:E       f:EF* 13f:CF b:F       f:B* b:C       f:EF* b:F       f:A b:E       f:EF* b:F       f:DF b:F       f:CF 13f:CF b:F       f:DE b:C       f:CF b:D       f:B* b:F       f:A b:E       f:EF* b:F       f:DF 13f:CF b:F       f:DE b:D       f:B* b:E       f:A b:C       f:CF b:F       f:DE b:E       f:EF* 13f:CF b:F       f:DE b:E       f:A b:C       f:CF b:F       f:EF* b:F       f:B* b:E       f:EF* 13f:CF b:F       f:DE b:E       f:EF* b:D       f:B* b:E       f:DE b:F       f:A b:C       f:CF 13f:CF b:F       f:DF b:D       f:A b:F       f:B* b:C       f:CF b:F       f:EF* b:F       f:DF 13f:CF b:F       f:DF b:D       f:DE b:E       f:B* b:D       f:A b:F       f:DF b:F       f:EF* 13f:CF b:F       f:DF b:F       f:B* b:D       f:DE b:E       f:A b:D       f:DE b:E       f:EF* 13f:CF b:F       f:EF* b:C       f:A b:F       f:DF b:F       f:B* b:E       f:CF b:D       f:DE 13f:CF b:F       f:EF* b:E       f:B* b:F       f:EF* b:E       f:DE b:F       f:A b:C       f:CF 13f:CF b:F       f:EF* b:F       f:A b:E       f:DF b:F       f:B* b:D       f:EF* b:F       f:DF 13f:CF b:F       f:EF* b:F       f:DF b:F       f:A b:D       f:DF b:E       f:B* b:D       f:DE 13f:DE b:D       f:A b:E       f:DF b:F       f:CF b:D       f:B* b:F       f:DE b:C       f:CF 13f:DE b:D       f:B* b:E       f:DE b:E       f:CF b:F       f:A b:D       f:DE b:C       f:CF 13f:DE b:D       f:CF b:C       f:B* b:F       f:CF b:E       f:DE b:F       f:A b:E       f:EF* 13f:DE b:D       f:CF b:E       f:DE b:D       f:A b:F       f:DF b:D       f:B* b:E       f:DE 13f:DE b:D       f:CF b:F       f:B* b:C       f:CF b:F       f:A b:E       f:DF b:F       f:EF* 13f:DE b:D       f:DF b:D       f:A b:E       f:DE b:D       f:B* b:F       f:CF b:E       f:DE 13f:DE b:D       f:DF b:F       f:A b:D       f:B* b:E       f:EF* b:F       f:CF b:E       f:DE 13f:DE b:D       f:DF b:F       f:CF b:E       f:B* b:F       f:EF* b:E       f:A b:D       f:DE 13f:DE b:E       f:A b:D       f:DF b:D       f:DE b:F       f:CF b:E       f:B* b:D       f:DE 13f:DE b:E       f:B* b:D       f:DE b:E       f:A b:D       f:DE b:E       f:EF* b:F       f:CF 13f:DE b:E       f:CF b:C       f:B* b:F       f:A b:D       f:DE b:D       f:CF b:F       f:DF 13f:DE b:E       f:CF b:D       f:DE b:C       f:B* b:F       f:CF b:F       f:A b:E       f:EF* 13f:DE b:E       f:CF b:F       f:B* b:C       f:A b:D       f:DF b:F       f:EF* b:F       f:CF 13f:DE b:E       f:CF b:F       f:EF* b:F       f:B* b:E       f:A b:D       f:EF* b:F       f:DF 13f:DE b:E       f:EF* b:E       f:B* b:F       f:EF* b:F       f:A b:D       f:CF b:F       f:DF 13f:DE b:E       f:EF* b:F       f:CF b:E       f:B* b:C       f:A b:F       f:CF b:D       f:DE 13f:DF b:D       f:A b:F       f:DF b:D       f:B* b:F       f:CF b:F       f:EF* b:F       f:DF 13f:DF b:D       f:B* b:F       f:DE b:D       f:DF b:D       f:A b:F       f:DF b:F       f:CF 13f:DF b:D       f:DE b:D       f:B* b:E       f:A b:F       f:EF* b:F       f:DF b:F       f:CF 13f:DF b:D       f:DE b:F       f:A b:E       f:EF* b:D       f:B* b:F       f:CF b:E       f:DE 13f:DF b:F       f:A b:D       f:CF b:C       f:B* b:F       f:EF* b:F       f:CF b:E       f:DE 13f:DF b:F       f:A b:D       f:EF* b:E       f:DE b:F       f:CF b:D       f:B* b:E       f:DE 13f:DF b:F       f:B* b:D       f:DF b:F       f:A b:D       f:DE b:E       f:CF b:D       f:DE 13f:DF b:F       f:CF b:D       f:A b:F       f:B* b:C       f:CF b:F       f:EF* b:F       f:DF 13f:DF b:F       f:CF b:D       f:DE b:E       f:B* b:D       f:A b:F       f:DF b:F       f:EF* 13f:DF b:F       f:CF b:F       f:B* b:D       f:DE b:E       f:A b:D       f:DE b:E       f:EF* 13f:DF b:F       f:EF* b:D       f:A b:F       f:DF b:F       f:B* b:E       f:CF b:D       f:DE 13f:DF b:F       f:EF* b:F       f:A b:E       f:CF b:D       f:B* b:F       f:DE b:E       f:EF* 13f:DF b:F       f:EF* b:F       f:CF b:F       f:B* b:E       f:A b:D       f:DE b:E       f:EF* 13f:EF* b:E       f:A b:F       f:EF* b:E       f:B* b:F       f:CF b:F       f:DF b:F       f:EF* 13f:EF* b:E       f:B* b:F       f:DF b:D       f:DE b:D       f:A b:F       f:CF b:E       f:DE 13f:EF* b:E       f:DE b:E       f:A b:D       f:B* b:F       f:EF* b:F       f:CF b:E       f:DE 13f:EF* b:E       f:DE b:F       f:B* b:E       f:A b:D       f:EF* b:F       f:DF b:F       f:CF 13f:EF* b:F       f:A b:E       f:CF b:F       f:DF b:F       f:B* b:D       f:DF b:F       f:EF* 13f:EF* b:F       f:B* b:E       f:CF b:C       f:DE b:F       f:A b:E       f:EF* b:F       f:CF 13f:EF* b:F       f:B* b:E       f:EF* b:F       f:A b:E       f:DE b:D       f:CF b:F       f:DF 13f:EF* b:F       f:CF b:E       f:A b:F       f:EF* b:F       f:B* b:C       f:CF b:F       f:DF 13f:EF* b:F       f:CF b:E       f:DE b:F       f:B* b:E       f:EF* b:E       f:A b:D       f:DE 13f:EF* b:F       f:CF b:F       f:DF b:C       f:B* b:F       f:A b:E       f:EF* b:F       f:CF 13f:EF* b:F       f:DF b:D       f:B* b:F       f:DF b:F       f:A b:D       f:CF b:F       f:DF 13f:EF* b:F       f:DF b:F       f:B* b:D       f:DF b:F       f:A b:E       f:CF b:D       f:DE 13`

DefDbl A-Z
Dim crlf\$, leftMemb(6), rightMemb(6), totTime, minTime, h\$, solCt

Form1.Visible = True
leftMemb(0) = 6
leftMemb(1) = 120
leftMemb(2) = 110
leftMemb(3) = 90
leftMemb(4) = 80
leftMemb(5) = 50
leftMemb(6) = 40

rightMemb(0) = 0

minTime = 13

Open "river cross resolution.txt" For Output As #2

Text1.Text = ""
crlf = Chr\$(13) + Chr\$(10)

xfer

Close 2
Text1.Text = Text1.Text & crlf & solCt & " done"

End Sub

Sub xfer()
For i = 1 To 6
If leftMemb(i) > 0 Then
onBoard = leftMemb(i)
rightMemb(i) = leftMemb(i)
leftMemb(i) = 0
For j = 0 To 6
DoEvents
If j = 0 Then
leftMemb(0) = leftMemb(0) - 1
rightMemb(0) = rightMemb(0) + 1
hh1\$ = h
h = h + "f:" + Mid("ABCDEF", i, 1)
If onBoard <= 110 Then h = h + "*"
h = h + " "
solitaire = i
ElseIf j > i Then
If leftMemb(j) > 0 And onBoard + leftMemb(j) <= 130 Then
rightMemb(j) = leftMemb(j)
leftMemb(j) = 0
leftMemb(0) = leftMemb(0) - 2
rightMemb(0) = rightMemb(0) + 2
hh1\$ = h
h = h + "f:" + Mid("ABCDEF", i, 1) + Mid("ABCDEF", j, 1)
If onBoard + rightMemb(j) <= 110 Then h = h + "*"
h = h + " "
solitaire = 0
End If
End If
totTime = totTime + 1
If rightMemb(0) = 6 Then
If totTime <= minTime Then
minTime = totTime
solCt = solCt + 1
If solCt <= 10 Then
Text1.Text = Text1.Text & h & minTime & crlf
End If
Print #2, h, minTime
End If
Else
For k = 1 To 6
DoEvents
If rightMemb(k) > 0 And k <> solitaire Then
leftMemb(k) = rightMemb(k)
rightMemb(k) = 0
leftMemb(0) = leftMemb(0) + 1
rightMemb(0) = rightMemb(0) - 1
totTime = totTime + 1
hh2\$ = h
h = h + "b:" + Mid("ABCDEF", k, 1) + " "

If totTime < minTime Then
DoEvents
xfer
End If

h = hh2
leftMemb(0) = leftMemb(0) - 1
rightMemb(0) = rightMemb(0) + 1
rightMemb(k) = leftMemb(k)
leftMemb(k) = 0
totTime = totTime - 1
End If

Next k

End If

h = hh1

totTime = totTime - 1
If solitaire Then
leftMemb(0) = leftMemb(0) + 1
rightMemb(0) = rightMemb(0) - 1
Else
leftMemb(0) = leftMemb(0) + 2
rightMemb(0) = rightMemb(0) - 2
leftMemb(j) = rightMemb(j)
rightMemb(j) = 0
End If
End If
Next j
leftMemb(i) = rightMemb(i)
rightMemb(i) = 0
End If
Next i
End Sub

 Posted by Charlie on 2016-10-12 12:21:50

 Search: Search body:
Forums (4)