Fuel Bunker Problem posted on Joel On Software

This looks like a school assignment. But it could be a legitimate question, so here's a solution. The solution appears to be O(N), but I haven't proven that yet, but empirical testing on synthetic data seems to bear that out.

Option Strict On
Option Explicit On

'''

''' Solution to problem posted on Joel on Software:
''' There are n petrol bunks arranged in circle.
''' Each bunk is separated from the rest by a certain distance.
''' You choose some mode of travel which needs 1litre of petrol to cover 1km distance.
''' You can't infinitely draw any amount of petrol from each bunk as each bunk
''' has some limited petrol only. But you know that the sum of litres of petrol
''' in all the bunks is equal to the distance to be covered.
''' ie let P1, P2, ... Pn be n bunks arranged circularly
'''

Module Module1

'''

''' Representation of a bunker. The next bunker
''' is at (m_position + 1) mod N
'''

Class Bunker
'''

''' Amount of fuel at this bunker
'''

'''
Public m_fuel As Integer
Public m_distance As Integer

Public Property fuel() As Integer
Get
Return m_fuel
End Get
Set(ByVal value As Integer)
m_fuel = value
End Set
End Property

Public Property distance() As Integer
Get
Return m_distance
End Get
Set(ByVal value As Integer)
m_distance = value
End Set
End Property
End Class

'Private Const MAX_N As Integer = 25
'Private Const MAX_DISTANCE As Integer = 100
Private Const MAX_SURPLUS As Integer = 100
Private Const DEBUG As Boolean = True
Private g_bunkers As List(Of Bunker) = Nothing
Private genRand As New Random()
Private g_operations As Integer = 0


Private Sub debugMessage(ByVal message As String)
If DEBUG Then
Console.WriteLine(message)
End If
End Sub
'''

''' Generate a random sequence of bunkers with
''' random distances and fuel in them in which
''' there is just enough fuel to get around the
''' circle. There is at least one bunker from which
''' a circuit is possible.
'''

''' the starting point
Private Function generateData(ByVal n As Integer, ByVal distance As Integer) As Integer
g_bunkers = New List(Of Bunker)
For i As Integer = 0 To n - 1
Dim bunker As New Bunker
' randomly assign distances to next bunker
bunker.distance = genRand.Next(0, distance)
g_bunkers.Add(bunker)
Next
' choose random starting point
Dim start As Integer = genRand.Next(0, n - 1)

' go (almost) around the circle ensuring that there is enough fuel to make it around
Dim surplus As Integer
For i As Integer = 0 To n - 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim bunker As Bunker = g_bunkers(bunkerNumber)

' choose random surplus
Dim currSurplus As Integer = genRand.Next(0, MAX_SURPLUS)

' fuel + previous surplus should add up to currSurplus, but cannot have negative fuel
Dim f As Integer = bunker.distance + currSurplus - surplus
f = Math.Max(0, f)
bunker.fuel = f
surplus = surplus + bunker.fuel - bunker.distance

' if last bunker then fudge the distance in case we have remaining fuel
If i = n - 1 And surplus > 0 Then
bunker.distance = bunker.distance + surplus
End If
Next
Return start
End Function

'''

''' Print out the route from start, printing out the distance
''' covered by the hop, fuel used, and current surplus.
'''

''' starting point of the route
Private Sub checkRoute(ByVal start As Integer, Optional ByVal quiet As Boolean = False)
Dim n As Integer = g_bunkers.Count()
Dim surplus As Integer = 0
For i As Integer = 0 To n - 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim b As Bunker = g_bunkers(bunkerNumber)
surplus = surplus + b.fuel - b.distance
If Not quiet Then
Console.Write(String.Format("Bunker[{0}]: fuel = {1}, distance = {2}, surplus = {3}.", _
bunkerNumber, b.fuel, b.distance, surplus))
If surplus < 0 Then
Console.WriteLine(" -- ran out of fuel")
Else
Console.WriteLine()
End If
End If
Next
If surplus >= 0 Then
Console.Write("Success:")
Else
Console.Write("Failure:")
End If
Console.WriteLine(String.Format(" start = {0}, surplus = {1}.", start, surplus))
End Sub

'''

''' Find the next index at or after position in Bunkers with a deficit,
''' modulo number of bunkers. If there is none, returns 0.
'''

''' position at which to start search
''' next bunker with a deficit
Private Function findNextDeficit(ByVal position As Integer) As Integer
debugMessage("findNextDeficit: position = " & position)
Dim n As Integer = g_bunkers.Count
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim j = (i + position) Mod n
If g_bunkers.Item(j).distance > g_bunkers.Item(j).fuel Then
debugMessage("findNextDeficit: returning " & j)
Return j
End If
Next
debugMessage("findNextDeficit: failure - returning 0")
Return 0
End Function

'''

''' Find the next index at or after position in Bunkers with a surplus,
''' modulo number of bunkers. If there is none, throws an exception
''' since there should be at least one.
'''

''' position at which to start search
''' next bunker with a deficit
Private Function findNextSurplus(ByVal position As Integer) As Integer
debugMessage("findNextSurplus: position = " & position)
Dim n As Integer = g_bunkers.Count
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim j = (i + position) Mod n
If g_bunkers.Item(j).distance < g_bunkers.Item(j).fuel Then
debugMessage("findNextSurplus: returning " & j)
Return j
End If
Next
Throw New Exception("findNextSurplus - no surplus found")
End Function

'''

''' Try and see if a loop around the bunkers can be constructed from
''' start. If succeeds, return -1, otherwise return position at
''' which it failed.
'''

'''
''' -1 for success, position of failure otherwise
Private Function tryLoop(ByVal start As Integer) As Integer
debugMessage("tryLoop: start = " & start)
Dim n As Integer = g_bunkers.Count()
Dim surplus As Integer = 0
For i As Integer = 0 To n - 1
g_operations = g_operations + 1
Dim bunkerNumber As Integer = (i + start) Mod n
Dim b As Bunker = g_bunkers(bunkerNumber)
surplus = surplus + b.fuel - b.distance
If surplus < 0 Then
' failed
debugMessage("tryLoop: failed - returning " & bunkerNumber)
Return bunkerNumber
End If
Next
' success
debugMessage("tryLoop: suceeded - returning -1")
Return -1
End Function
'''

''' Find a route. Calculate the surplus for each individual hop.
''' The only possible starting points have to be at the beginning of a sequence
''' of positive surpluses.
'''

''' the start position
'''
Private Function findRoute() As Integer
Dim n As Integer = g_bunkers.Count
Dim done As Boolean = False
Dim position As Integer = 0
While True
' find the next deficit
Dim i As Integer = findNextDeficit(position)
' find the next surplus starting point after the deficit
Dim j As Integer = findNextSurplus(i)
position = j
' try and see if a circuit can be completed from position.
' if it can, return position. if not, set position to
' the place where it failed and try again
i = tryLoop(position)
If i = -1 Then
Return position
Else
position = i
End If
End While
' should be able to find a route
Throw New Exception("findRoute - couldn't find route")
End Function

'''

''' Do a single test iteration.
'''

'''
Public Sub test()
Dim start As Integer = generateData(1000, 10000)
g_operations = 0
Try
Dim foundStart = findRoute()
checkRoute(foundStart)
Catch ex As Exception
' failure
Console.WriteLine(ex.Message())
End Try
Console.WriteLine("Number of operations = " & g_operations)
End Sub

Sub Main()
test()
Console.ReadLine()

End Sub

End Module

Google Profile: http://www.google.com/profiles/larrywatanabe
Stack overflow profile: http://stackoverflow.com/users/118860/larry-watanabe
Blog: http://larrywatanabe.blogspot.com
Master's thesis: http://portal.acm.org/citation.cfm?id=125337
Publications: http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/w/Watanabe:Larry.html
MacShapa: http://portal.acm.org/citation.cfm?id=211243