My daughter was given the following puzzle as extra credit:
Four men want to cross a bridge. The bridge is of a width
such that a maximum of 2 people may cross at a time.
One man takes 10 minutes to cross, another takes 5 minutes to
cross, another takes 2 minutes to cross, and the last takes 1
minute to cross.
Here is the catch. If two people cross the bridge
together, they must walk at the pace of the slower one. Also, it is
night. Each trip requires a flashlight. There is only one
flashlight. The men are not allowed to toss the light over the
river.
How fast can you get all 4 men over the bridge?
Note: try to figure it out for yourself before looking at the comments.
The fastest I’ve come up with in a couple of minutes looking at it is 19 minutes.
10 & 1 go across together (10 minutes),
1 goes back across (+1 = 11)
1 & 5 go across (+5 = 16)
1 goes back across (+1 = 17)
1 & 2 go across (+2 = 19)
The fastest time is 17 minutes. You must combine 5 and 10. However during an interview for Altera I was given this question and I answered it successfully. The next question I was given was the following: Given a set of times a1, a2, a3 ... an, come up with an algorithm for figuring out the optimum way to cross the bridge. I couldn’t answer the question but it involve creating some graph of the times and doing something with it. I failed the interview of course
10 minutes.
going single file.
the slowest one leads, carrying the flashlight.
These are people right? They can walk single file right?
it is a narrow bridge, but a real bridge right?
There appears to be no constraint other than that implied by the wierdly worded instructions: The bridge is of a width
such that a maximum of 2 people may cross at a time.
if you interpret this to mean only that the width of the bridge prevents members of the group from walking more than two abreast, then the solution above appears to hold for all cases.
10 minutes, the slowest traveler is the limiting constraint.
If you interpret this to mean that only two members of the group can cross the bridge on a single trip, then you haven’t really seen enough bridges.
This is what people get when they try to be too fancy making up the word problem. It would work much better if it were a boat that only fit two people crossing a river. No single-file tricks, no need for convoluted flashlight restrictions...
(Note: I wish I could take credit for recognizing that. But I hate word problems, and spent 10 seconds coming up with Wade’s 19 minutes solution. My wife pointed out bud’s solution, then told me that the problem would work better with a boat...)
Yup, I second the 10 minute in a single file solution.
It is clearly the fastest solution to this puzzle - the way it is worded - and because it’s a word-puzzle the wording is crucial to its solution. ;-)
The supposed issue with more than two people on the bridge is weight: eg it breaks with more than two people on it. Otherwise single file is obviously fastest... and the problem becomes rather boring.
Re: assman, I agree that the more interesting problem is writing an algorithm capable of solving this problem.
This would most likely make an excellent introduction to continuations lab.
Here’s how I would solve the general problem: Suppose a1, a2, a3 ... an is sorted from smallest to largest. The two smallest numbers (i.e., the two fastest walkers), a1 and a2, are used to transport the flashlight back to the originating side. The largest numbers are paired up and cross together, e.g., an and an-1 cross together, an-2 and an-3 cross together, etc. This way you minimize the amount of time used getting the flashlight back to the original side and you absorb the time of slow walker an-1 into an’s time. Iterate Patrick Ritchie’s above solution, with a tweak if there are an odd number of people, and you’ve got the general solution.
Oh well, if you want to read it as a word play, then the minimum time becomes two minutes: have 1 and 2 carry 5 and 10 on their shoulders, and there you go.
intertwingly.net: Sam Ruby: Bridge Crossing Puzzle (2006 March 3)
(includes a comment by me) 'Four men want to cross a bridge. The bridge is of a width such that a maximum of 2 people may cross at a time. One man takes 10 minutes to cross, another takes 5 minutes to cross, another takes 2 minutes to cross, and the...
We own two vehicles - one family car and one two-seater. My wife wanted to get the family car detailed. She dropped ivy off at school, then the car at the car wash. I picked her up in the two-seater. We will have to retrieve ivy from school before...
Patrick Ritchie’s answer is the and correct answer to this puzzle. The wording to this particular puzzle on this page may not have been the best ever, but the “put them on their shoulders” and “walk in single file line” answers are just cop outs.
The problem with the proposed algorithm above is that it assumes one has “solved” the problem, i.e. it presumes that it is obvious that the slowest dudes must cross together. Here is a “brute-force” algorithm that tries all unique combinations and works out the answer for any number of dudes (and/or dudettes) crossing whatever (bridge/river/The Rubicon), with any token (torch or boat or a copy of a Dark Sith Lord’s DNA)
(In VB.Net)
Imports System.Console
Module Module1
Sub Main()
Dim p As New BridgePuzzle
p.Solve()
ReadKey()
End Sub
End Module
Public Class BridgePuzzle
public minTime As Integer = Integer.MaxValue
Private minSequence() As Integer
Public Sub Solve()
' List of dudes on "this" side having to cross
Dim ThisSide() As Integer = {1, 2, 5, 10}
' Dudes on "that" side
Dim ThatSide() As Integer = {}
' Array with total time in first element, and crossing sequence in rest of array
Dim Sequence() As Integer = {}
'Solve (recursion starts, start by moving dudes to "that" side)
MoveToThatSide(ThisSide, ThatSide, Sequence)
' Show Optimal Answer
WriteLine("")
Write("Optimal Answer: ")
OutputSequence(Me.minSequence)
End Sub
Private Sub MoveToThatSide(ByRef ThisSide() As Integer, ByRef ThatSide() As Integer, ByRef Sequence() As Integer)
For i As Integer = 0 To ThisSide.Length - 1
For j As Integer = i + 1 To ThisSide.Length - 1 ' Process Unique Combo's Only
' create new array minus dudes leaving for "that" side and..
Dim newThisSide((ThisSide.Length - 1) - 2) As Integer
Dim m As Integer = 0
For n As Integer = 0 To ThisSide.Length - 1
If n <> i And n <> j Then
newThisSide(m) = ThisSide(n) : m += 1
End If
Next
' ...put dudes on "that" side
Dim newThatSide((ThatSide.Length - 1) + 2) As Integer
For p As Integer = 0 To ThatSide.Length - 1
newThatSide(p) = ThatSide(p)
Next
newThatSide((ThatSide.Length - 1) + 1) = ThisSide(i)
newThatSide((ThatSide.Length - 1) + 2) = ThisSide(j)
' Add two dudes crossing to crossing sequence
Dim newSequence((Sequence.Length - 1) + 2) As Integer
For t As Integer = 0 To Sequence.Length - 1
newSequence(t) = Sequence(t)
Next
newSequence((Sequence.Length - 1) + 1) = ThisSide(i)
newSequence((Sequence.Length - 1) + 2) = ThisSide(j)
If newThisSide.Length > 0 Then ' More dudes to collect?
MoveToThisSide(newThisSide, newThatSide, newSequence) ' cross-recurse
Else ' Everyone is now on "that" side - output answers, end recursion
OutputSequence(newSequence)
End If
Next
Next
End Sub
Private Sub MoveToThisSide(ByRef ThisSide() As Integer, ByRef ThatSide() As Integer, ByRef Sequence() As Integer)
For i As Integer = 0 To ThatSide.Length - 1
' create new "that" side array minus dude leaving for "this" side and...
Dim newThatSide((ThatSide.Length - 1) - 1) As Integer
Dim m As Integer = 0
For n As Integer = 0 To ThatSide.Length - 1
If n <> i Then
newThatSide(m) = ThatSide(n) : m += 1
End If
Next
' create new "this" side array and put dude on "this" side
Dim newThisSide((ThisSide.Length - 1) + 1) As Integer
For p As Integer = 0 To ThisSide.Length - 1
newThisSide(p) = ThisSide(p)
Next
newThisSide((ThisSide.Length - 1) + 1) = ThatSide(i)
' Add dude crossing to crossing sequence
Dim newSequence((Sequence.Length - 1) + 1) As Integer
For t As Integer = 0 To Sequence.Length - 1
newSequence(t) = Sequence(t)
Next
newSequence((Sequence.Length - 1) + 1) = ThatSide(i)
MoveToThatSide(newThisSide, newThatSide, newSequence) 'cross-recurse
Next
End Sub
Private Sub OutputSequence(ByRef Sequence() As Integer)
Dim time As Integer = 0
' every third value is a dude heading back to "this" side
For x As Integer = 0 To Sequence.Length - 1
If (x + 1) Mod 3 = 0 Then
time = time + Sequence(x) + Math.Max(Sequence(x - 1), Sequence(x - 2))
Write(" <" & Sequence(x) & " ")
Else
Write(" >" & Sequence(x) & " ")
End If
Next
' last two moving to "that" side...
time = time + Math.Max(Sequence((Sequence.Length - 1) - 1), Sequence((Sequence.Length - 1) - 2))
' output total time
Write(" = " & time & vbCrLf)
' Check and record minimum time
If time < Me.minTime Then
Me.minTime = time
Me.minSequence = Sequence
End If
End Sub
End Class
...and here is an optimized version of the algorithm. Except for cosmetic changes (like using Lists instead of arrays), the algorithm stops exploring sequences as soon as the exceed the current minimum sequence. Also fixed a bug in the Output routine that sneaked in before.
Imports System.Console
Module Module1
Sub Main()
Dim p As New BridgePuzzle
p.Solve()
ReadKey()
End Sub
End Module
Public Class BridgePuzzle
' storage for best time and sequence
Private minTime As Integer = Integer.MaxValue
Private minSequence As New List(Of Integer)
' Possible combinations
Private sequences As Integer = 0
' Initialize and run
Public Sub Solve()
Dim ThisSide As New List(Of Integer) ' List of dudes on "this" side having to cross
Dim ThatSide As New List(Of Integer) ' Dudes on "that" side
Dim Sequence As New List(Of Integer) ' Crossing sequence in rest of array
Dim SequenceTotal As Integer = 0
' Initialise dudes on "this" side
With ThisSide : .Add(1) : .Add(2) : .Add(5) : .Add(10) : End With
'Solve (recursion starts, start by moving dudes to "that" side)
MoveToThatSide(ThisSide, ThatSide, Sequence, SequenceTotal)
' Show Solutions
WriteLine("Best Time : ")
OutputSequence(minSequence)
WriteLine("# of sequences: ")
Write(sequences)
End Sub
Private Sub MoveToThatSide(ByRef ThisSide As List(Of Integer), ByRef ThatSide As List(Of Integer), ByRef Sequence As List(Of Integer), ByRef SequenceTotal As Integer)
' For each unique combo of two dudes on "this" side - eg. (1,2) = (2,1)
For i As Integer = 0 To ThisSide.Count - 1
For j As Integer = i + 1 To ThisSide.Count - 1
' Move two dudes from "this" side...
Dim newThisSide As New List(Of Integer)
For n As Integer = 0 To ThisSide.Count - 1
If n <> i And n <> j Then newThisSide.Add(ThisSide.Item(n))
Next
'...to "that" side...
Dim newThatSide As New List(Of Integer)
For p As Integer = 0 To ThatSide.Count - 1
newThatSide.Add(ThatSide.Item(p))
Next
newThatSide.Add(ThisSide.Item(i))
newThatSide.Add(ThisSide.Item(j))
'..and track this sequence of moves
Dim newSequence As New List(Of Integer)
For t As Integer = 0 To Sequence.Count - 1
newSequence.Add(Sequence.Item(t))
Next
newSequence.Add(ThisSide.Item(i))
newSequence.Add(ThisSide.Item(j))
' Copy Sequence total time and update
Dim newSequenceTotal As Integer = SequenceTotal
newSequenceTotal += Math.Max(ThisSide.Item(i), ThisSide.Item(j))
If newSequenceTotal >= Me.minTime Then
' This sequence is worse than the best time
ElseIf newThisSide.Count > 0 Then ' More dudes to collect?
MoveToThisSide(newThisSide, newThatSide, newSequence, newSequenceTotal) ' cross-recurse
Else
' Everyone is now on "that" side - output sequence
OutputSequence(newSequence)
sequences += 1
End If
Next
Next
End Sub
Private Sub MoveToThisSide(ByRef ThisSide As List(Of Integer), ByRef ThatSide As List(Of Integer), ByRef Sequence As List(Of Integer), ByRef SequenceTotal As Integer)
' Try each dude on "that" side coming back in turn
For i As Integer = 0 To ThatSide.Count - 1
' Move the one dude from "that' side...
Dim newThatSide As New List(Of Integer)
For n As Integer = 0 To ThatSide.Count - 1
If n <> i Then newThatSide.Add(ThatSide.Item(n))
Next
' ...to this side and...
Dim newThisSide As New List(Of Integer)
For p As Integer = 0 To ThisSide.Count - 1
newThisSide.Add(ThisSide.Item(p))
Next
newThisSide.Add(ThatSide.Item(i))
' ...and track the move...
Dim newSequence As New List(Of Integer)
For t As Integer = 0 To Sequence.Count - 1
newSequence.Add(Sequence.Item(t))
Next
newSequence.Add(ThatSide.Item(i))
' Copy Sequence total time and update
Dim newSequenceTotal As Integer = SequenceTotal
newSequenceTotal += ThatSide.Item(i)
'..take the next dude across to "this" side
If newSequenceTotal >= Me.minTime Then
' This sequence is worse than the best time
Else
MoveToThatSide(newThisSide, newThatSide, newSequence, newSequenceTotal) 'cross-recurse
End If
Next
End Sub
Private Sub OutputSequence(ByRef Sequence As List(Of Integer))
Dim time As Integer = 0
For x As Integer = 0 To Sequence.Count - 1
' every third value is a dude heading back to "this" side
If (x + 1) Mod 3 = 0 Then
' add the slower of the previous two, and the dude who headed back
time = time + Sequence.Item(x) + Math.Max(Sequence.Item(x - 1), Sequence.Item(x - 2))
Write(" <" & Sequence.Item(x) & vbTab)
Else
' one of two dudes heading "that" side
Write(" >" & Sequence.Item(x) & vbTab)
End If
Next
' add slower of last two dudes who moved to "that" side and...
time = time + Math.Max(Sequence.Item((Sequence.Count - 1)), Sequence.Item((Sequence.Count - 1) - 1))
' ...output the total time taken
Write(" = " & time & vbCrLf)
' Check and record if this is the minimum (fastest) time
If time < Me.minTime Then
Me.minTime = time
Me.minSequence = Sequence
End If
End Sub
End Class
Here’s the thing about word problems. The application of real-world lateral thinking about things like boats or bridges can either make for entertaining creative solutions or it can miss the point entirely. The best way to handle that is to state directly “ignore the illustrative details and treat this as an abstract problem of time and numbers.” Then I don’t waste your time telling you that I could rebuilt the parts of your two-man boat into 4 emergency flotation devices, etc.
I got the boat version of this problem and with a little creative thinking got it down to round thriteen and a half minutes :D
Tie a rope to the boat (since if its possible to row across in 1 minute its not a very wide river :D)
Sent the ten minutes and 5 minute guys together. That will take ten minutes.
Pull the boat back (if you’re strong enough to row across in 1 minute surely you can pull it back faster but lets be pessimistic and give it a minute and a half )
Row across with the people rowing two minutes and one minute... (add two minutes)
LOL. Yes I know this is not the answer sought but I kind of enjoy the idea of creative thinking :D