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

Home > Logic > Weights and Scales
River Cross Resolution (Posted on 2016-10-12) Difficulty: 3 of 5
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?

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information