I requested my first Foobar problem at level 4 difficulty. Google did not disappoint:
Running with Bunnies
====================
You and the bunny workers need to get out of this collapsing death trap of a space station -- and fast! Unfortunately, some of the bunnies have been weakened by their long work shifts and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.
The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave -- you can move to and from the bulkhead to pick up additional bunnies if time permits.
In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.
Write a function of the form solution(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest worker IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by worker ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.
For instance, in the case of
[
[0, 2, 2, 2, -1], # 0 = Start
[9, 0, 2, 2, -1], # 1 = Bunny 0
[9, 3, 0, 2, -1], # 2 = Bunny 1
[9, 3, 2, 0, -1], # 3 = Bunny 2
[9, 3, 2, 2, 0], # 4 = Bulkhead
]
and a time limit of 1, the five inner array rows designate the starting point, bunny 0, bunny 1, bunny 2, and the bulkhead door exit respectively. You could take the path:
Start End Delta Time Status
- 0 - 1 Bulkhead initially open
0 4 -1 2
4 2 2 0
2 4 -1 1
4 3 2 -1 Bulkhead closes
3 4 -1 0 Bulkhead reopens; you and the bunnies exit
With this solution, you would pick up bunnies 1 and 2. This is the best combination for this space station hallway, so the solution is [1, 2].
Languages
=========
To provide a Java solution, edit Solution.java
To provide a Python solution, edit solution.py
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.
-- Java cases --
Input:
Solution.solution({{0, 1, 1, 1, 1}, {1, 0, 1, 1, 1}, {1, 1, 0, 1, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 0}}, 3)
Output:
[0, 1]
Input:
Solution.solution({{0, 2, 2, 2, -1}, {9, 0, 2, 2, -1}, {9, 3, 0, 2, -1}, {9, 3, 2, 0, -1}, {9, 3, 2, 2, 0}}, 1)
Output:
[1, 2]
-- Python cases --
Input:
solution.solution([[0, 2, 2, 2, -1], [9, 0, 2, 2, -1], [9, 3, 0, 2, -1], [9, 3, 2, 0, -1], [9, 3, 2, 2, 0]], 1)
Output:
[1, 2]
Input:
solution.solution([[0, 1, 1, 1, 1], [1, 0, 1, 1, 1], [1, 1, 0, 1, 1], [1, 1, 1, 0, 1], [1, 1, 1, 1, 0]], 3)
Output:
[0, 1]
Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.
I had to read the question multiple times to even understand what it was asking. This one was definitely more difficult than the prior ones! Once I understood, I created a diagram of their example data:
There was no doubt that I was dealing with a graph theory problem. But I’ve needed to traverse a graph only a handful of times in the past years. This problem was well out of my comfort zone. The only thing that came to mind was Dijkstra’s algorithm, but even that was only a vague memory from University times. I started reviewing Dijkstra’s since that was all I had, but quickly came to the conclusion that it wouldn’t be useful due to the negative cycles in the graph.
I played around with the problem for a few hours, but I was getting nowhere. Having nothing better to try, I went off to research graph algorithms in the hope that I’d come across something that would inspire an idea. I struck gold when I found William Fiset on YouTube. He goes into great detail explaining many, many graph theory algorithms. At the time of writing this he also works at Google. Maybe he had something to do with this very question? I spent a full day bingeing his videos. Two algorithms caught my attention. One was Bellman Ford, and the other was Floyd Warshall.
It was mentioned that Floyd Warshall works best on an adjacency matrix, which this problem is conveniently already using. It also gives all shortest paths, which will be required because we will need to attempt a rescue of every single bunny. It wouldn’t work well if there were a large number of nodes ( it is O(#nodes ^ 3) ), but the question tells us there will never be more than 5 bunnies thus we know there will never be more than 7 nodes. So Floyd Warshall seemed ideal!
I updated the graph of the sample data with the edges converted to the shortest path outputs:
Then visualized a solution using that data from the graph:
My idea was to determine how long it would take to reach the first bunny. Then check how long it takes to get to the exit from that bunny. If we can’t reach the exit that path isn’t valid. If we can reach it, then see how long it takes to get from the first bunny to the second bunny. If we can’t reach the second bunny that path also isn’t valid. If we can reach it, however, then see if we can reach the exit too. If we can then we know we can save both bunnies. Traverse the entire graph in this way while keeping track of the maximum set of bunnies we’ve saved along the way.
Test cases were failing upon first implementation, but it turned out to be a misunderstanding with how I was passing objects. My more recent work had been in C type languages, and Python’s “Pass by Object Reference” behaviour wasn’t what I had been expecting. But as soon as I got that sorted out the tests passed:
# Author: Derek Moran, Level 4, Bunny Planet Rescue Service
# With big thanks and kudos to Google software engineer William Fiset; his video series on graph algorithms was invaluable for this solution
# Date: 08-DEC-2022
def solution(times,times_limit):
# Your code here
return getMaxBunniesWeCanRescueWithinTimeLimit( times, times_limit )
# When given an adjacencyMatrix:
# - such that each column will indicate the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order
# - the order of the rows follows the same pattern (start, each bunny, bulkhead)
# - we can escape only through the bulkhead, and only when there is 0 or more time units remaining
# - times must be integers, note they can be positive OR negative ( bulkhead opens again if a negative route puts it back to 0 )
# - Infinite can also be used if a particular route is not possible
# - there can be at most 5 bunny rows
#
# And given a timeLimit that is a non-negative integer that is at most 999 time units
#
# Then this will return a list containing the maximum number of bunnies that can be visited prior to escaping, sorted by lowest bunny workerId
# The bunny workerIds start at 0 ( i.e. are their row index - 1 )
# If multiple sets of the same size are possible, the result will favour the one starting with lowest workerIds
def getMaxBunniesWeCanRescueWithinTimeLimit( adjacencyMatrix, timeLimit ):
validateInputs( adjacencyMatrix, timeLimit )
bulkheadIndex = len(adjacencyMatrix) - 1
numBunnies = bulkheadIndex - 1
# We can tell how many bunnies we have from the original matrix, so let's bail early if we have the chance!
if numBunnies == 0: return []
# We don't need the original matrix any more, so will just convert it in place to avoid additional memory complexity
convertAdjacencyMatrixToAllPairsShortestPaths( adjacencyMatrix )
startIndex = 0
# If we can't reach the bulkhead from the start then no point going further
if adjacencyMatrix[startIndex][bulkheadIndex] > timeLimit: return []
rangeOfBunnyIndexes = range( startIndex + 1, bulkheadIndex )
# Using dictionary entry allBunniesSaved[1] as a workaround to get similar functionality to a nonlocal bool
# ( Python 2.7.13 does not support assignment to a bool with a nonlocal closure )
allBunniesSaved = {}
def getMaxBunniesWeCanRescueWithinTimeLimit( currentNode, timeTakenSoFar, bunniesVisitedSoFar, bunniesSavedSoFar ):
if 1 in allBunniesSaved: return bunniesSavedSoFar
elif len(bunniesSavedSoFar) == numBunnies:
allBunniesSaved[1] = True
return bunniesSavedSoFar
maxBunniesSavedTotal = list(bunniesSavedSoFar)
for nextBunnyIndex in rangeOfBunnyIndexes:
if nextBunnyIndex in bunniesVisitedSoFar: continue
nextBunniesVisitedSoFar = bunniesVisitedSoFar.copy()
nextBunniesVisitedSoFar.add(nextBunnyIndex)
timeToReachNextBunny = adjacencyMatrix[currentNode][nextBunnyIndex]
timeToEscapeWithNextBunny = adjacencyMatrix[nextBunnyIndex][bulkheadIndex]
if timeTakenSoFar + timeToReachNextBunny + timeToEscapeWithNextBunny > timeLimit: continue
nextBunniesSaved = list(bunniesSavedSoFar)
nextBunniesSaved.append(nextBunnyIndex-1)
maxBunniesIfWeSaveNextBunny = getMaxBunniesWeCanRescueWithinTimeLimit(
currentNode = nextBunnyIndex,
timeTakenSoFar = timeTakenSoFar + timeToReachNextBunny,
bunniesVisitedSoFar = nextBunniesVisitedSoFar,
bunniesSavedSoFar = nextBunniesSaved
)
# Note that since we are trying bunnies with lowest id first, we will get the set we want even if others with the same size exist
if len(maxBunniesIfWeSaveNextBunny) > len(maxBunniesSavedTotal): maxBunniesSavedTotal = maxBunniesIfWeSaveNextBunny
return maxBunniesSavedTotal
maxBunniesWeCanRescueWithinTimeLimit = getMaxBunniesWeCanRescueWithinTimeLimit(
currentNode = startIndex,
timeTakenSoFar = 0,
bunniesVisitedSoFar = set(),
bunniesSavedSoFar = []
)
maxBunniesWeCanRescueWithinTimeLimit.sort()
return maxBunniesWeCanRescueWithinTimeLimit
Infinite = float('inf')
NegativeInfinite = float('-inf')
# Transforms the given adjacencyMatrix into one that gives all-pairs-shortest-paths
# Use Infinite to represent an edge that cannot be crossed
# NegativeInfinite will be used to represent edges caught in a negative cycle
#
# This is a version of the Floyd-Warshall algorithm - one explained in fantastic detail in a video series by Google software engineer William Fiset
def convertAdjacencyMatrixToAllPairsShortestPaths( adjacencyMatrix ):
# Let intermediateNode be a potential node in the shortest path from sourceNode to destinationNode
# If the path through intermediateNode turns out to be shorter, then update to that shorter path
# Do this times the number of nodes to ensure any path size reductions propagate through
# At this point we'll do a second pass. If a path through intermediateNode turns out to still be shorter, then we must have a negative cycle
# If we do have a negative cycle, then update that path to NegativeInfinite to represent this case
# Do this times the number of nodes to ensure any negative cycles propagate through
rangeOfNodes = range( len(adjacencyMatrix) )
for reductionPass in [1, 2]:
for intermediateNodeIndex in rangeOfNodes:
for row in rangeOfNodes:
for col in rangeOfNodes:
pathLengthViaIntermediateNode = adjacencyMatrix[row][intermediateNodeIndex] + adjacencyMatrix[intermediateNodeIndex][col]
if pathLengthViaIntermediateNode < adjacencyMatrix[row][col]:
adjacencyMatrix[row][col] = pathLengthViaIntermediateNode if reductionPass == 1 else NegativeInfinite
def validateInputs( adjacencyMatrix, timeLimit ):
if not type(timeLimit) is int or timeLimit < 0 or timeLimit > 999:
raise Exception( "timeLimit must be a non-negative integer that is at most 999" )
adjacencyMatrixExceptionMessage = "The adjacencyMatrix must be a square matrix of integers ( or Infinite if an edge is disconnected ); "\
"the size must be at least 2 ( ie there must be at least a starting point and the bulkhead ) and no more than 7 ( ie 0-5 optional bunnies )"
numMatrixRows = len(adjacencyMatrix)
if numMatrixRows < 2 or numMatrixRows > 7:
raise Exception( adjacencyMatrixExceptionMessage )
for row in range(numMatrixRows):
col = adjacencyMatrix[row]
colLength = len(col)
if colLength != numMatrixRows: raise Exception( adjacencyMatrixExceptionMessage )
for col in range(colLength):
colValue = adjacencyMatrix[row][col]
if not type(colValue) is int and not ( type(colValue) is float and colValue in [Infinite, NegativeInfinite] ):
raise Exception( adjacencyMatrixExceptionMessage )
Leave a Reply