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?
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 13
f: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 13
f: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* 13
f: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 13
f: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* 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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* 13
f: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 13
f: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 13
f: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* 13
f: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* 13
f: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 13
f: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 13
f: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* 13
f: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* 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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* 13
f: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 13
f: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* 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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* 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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* 13
f: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* 13
f: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 13
f: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* 13
f: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* 13
f: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* 13
f: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 13
f: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 13
f: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 13
f: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* 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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 13
f: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
Private Sub Form_Load()
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
goAhead = 0
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 + " "
goAhead = 1
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 + " "
goAhead = 1
solitaire = 0
End If
End If
If goAhead Then
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 |
computer solution
