TL, DR
Google Foobar is a hidden coding challenge by Google, and Prepare the Bunnies’ Escape is the challenge I solved using Python in order to move forward in level 3.
This post is part of a series on Google Foobar, with all the challenges I encountered. The full series is available here.
Getting ready to run
The fifth task I got for Foobar was to plan for the escape of my fellow bunnies. I had to calculate the shortest path for them to reach the escape pods, with the chance to remove one obstacle. The full description of the challenge is the following:
Prepare the Bunnies' Escape
===========================You're awfully close to destroying the LAMBCHOP doomsday device and freeing Commander Lambda's bunny workers, but once they're free of the work duties the bunnies are going to need to escape Lambda's space station via the escape pods as quickly as possible. Unfortunately, the halls of the space station are a maze of corridors and dead ends that will be a deathtrap for the escaping bunnies. Fortunately, Commander Lambda has put you in charge of a remodeling project that will give you the opportunity to make things a little easier for the bunnies. Unfortunately (again), you can't just remove all obstacles between the bunnies and the escape pods - at most you can remove one wall per escape pod path, both to maintain structural integrity of the station and to avoid arousing Commander Lambda's suspicions.You have maps of parts of the space station, each starting at a work area exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the station is at the top left (0,0) and the door into an escape pod is at the bottom right (w-1,h-1).
Write a function solution(map) that generates the length of the shortest path from the station door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans. The path length is the total number of nodes you pass through, counting both the entrance and exit nodes. The starting and ending positions are always passable (0). The map will always be solvable, though you may or may not need to remove a wall. The height and width of the map can be from 2 to 20. Moves can only be made in cardinal directions; no diagonal moves are allowed.
Tests
The challenge also list a couple of test cases you will need to pass. However, it also indicates that there will be additional hidden tests that you need to pass. But you may not know what those test are about. Nice, uh?
Test cases
==========
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here.-- Python cases --
Input:
solution.solution([[0, 1, 1, 0], [0, 0, 0, 1], [1, 1, 0, 0], [1, 1, 1, 0]])
Output:
7
Input:
solution.solution([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]])
Output:11
Constraints
You also need to keep in mid a few constraints. They are divided between Java and Python ones.
Python
======
Your code will run inside a Python 2.7.13 sandbox. All tests will be run by calling the solution() function.Standard libraries are supported except for bz2, crypt, fcntl, mmap, pwd, pyexpat, select, signal, termios, thread, time, unicodedata, zipimport, zlib.Input/output operations are not allowed.Your solution must be under 32000 characters in length including new lines and and other non-printing characters.
There are two important caveats to consider:
- Even if in the Python section there is no mention, execution time is limited. They say so in the Java section, but somehow they do not repeat it in the Python one.
- There are additional blacklisted libraries. For instance, I got a “BLACKLISTED CODE” exception when I tried to import the
syslibrary
Putting a solution together
Spoiler alert: you can find a complete working solution below. However I think that just copy-pasting a solution will not do you any good. But maybe looking at the flow and understanding the thinking behind the code may put you in the right direction to solve the challenge and learn something in the doing!
Coming to our challenge, the task is basically to find the shortest pattern connecting the entrance to the exit, with the opportunity to remove one wall to make the path shorter.
You should note that removing one wall may not necessarily make your path shorter…it really depend by the map. Anyway, the problems falls into the graph optimization area.
Classy graph theory
One of the most used algorithms for finding the shortest path in a graph is the one by Dijkstra. It dates back to 1959, and it still works like a wonder!
You are free to code yourself the algorithm…but for me, I hate to reinvent the wheel more than necessary. And maybe I’m too old for that too. A quick Google search brought me to this fantastic Udacity page, with a full implementation of Dijkstra’s algorithm in Python.
The main takeaway from there was the Graph class, reported below. Items of this class are than used as argument for a dijkstra_algorithm method that return the shortest path between a start node and all others.
class Graph(object):
def __init__(self, nodes, init_graph):
self.nodes = nodes
self.graph = self.construct_graph(nodes, init_graph)
def construct_graph(self, nodes, init_graph):
graph = {}
for node in nodes:
graph[node] = {}
graph.update(init_graph)
for node, edges in graph.items():
for adjacent_node, value in edges.items():
if graph[adjacent_node].get(node, False) == False:
graph[adjacent_node][node] = value
return graph
def get_nodes(self):
return self.nodes
def get_outgoing_edges(self, node):
connections = []
for out_node in self.nodes:
if self.graph[node].get(out_node, False) != False:
connections.append(out_node)
return connections
def value(self, node1, node2):
return self.graph[node1][node2]
def dijkstra_algorithm(graph, start_node):
unvisited_nodes = list(graph.get_nodes())
shortest_path = {}
previous_nodes = {}
max_value = float("inf")
for node in unvisited_nodes:
shortest_path[node] = max_value
shortest_path[start_node] = 0
while unvisited_nodes:
current_min_node = None
for node in unvisited_nodes:
if current_min_node == None:
current_min_node = node
elif shortest_path[node] < shortest_path[current_min_node]:
current_min_node = node
neighbors = graph.get_outgoing_edges(current_min_node)
for neighbor in neighbors:
tentative_value = shortest_path[current_min_node] + graph.value(current_min_node, neighbor)
if tentative_value < shortest_path[neighbor]:
shortest_path[neighbor] = tentative_value
previous_nodes[neighbor] = current_min_node
unvisited_nodes.remove(current_min_node)
return shortest_pathNow all we are left to do is to transform the map we are receiving into a graph and calculate the shortest pattern with one wall removed.
From map to graph
Let’s consider the map transformation. Since we will need to remove all walls (one at a time) in order to calculate the shortest path from entry to exit, we need to make a choice. We either recreate the graph every time we remove a wall, reconsidering all connections, or we take a shortcut. And we love shortcuts that decrease our execution time.
We know from the description that the map will be limited in extent (maximum 20×20 blocks). This provides us with maximum 400 steps in the map (the actual maximum number of steps from entry to exit needs to be less…but let’s work with rough numbers to keep it simple).
Therefore, if we set walls as nodes with a very high distance weight (let’s say, 1000) we would strongly discourage our Dijkstra algorithm from passing throughout them. And this would be just good enough for our purposes.
Then all we need to do is to iteratively reduce the weights on the wall – one at a time, and calculate the new shortest pattern. We can actually even skip the base case, because the path with a wall removed cannot be longer than the path with all the walls in place.
We need to transform the map given by the challenge into a graph with the format requested by our Graph class. Each node needs to connect with the one on its right (except the rightmost column) and the one below (except the last row). Weight for the connection is the highest value between 1 (for free nodes) and 1001 (for walls). Since connections are bi-directional, that’s all we need to do.
Getting to the point
The function below build the graph and runs minimum distance calculation removing one wall for each iteration. I think the commented code is better than any description.
import itertools
import copy
def solution(map):
# Get the size of the map
# it can be non-squared
h = len(map)
w = len(map[0])
# Give a name to columns and rows
cols = [str(x) for x in range(w)]
rows = [chr(x) for x in range(97, (97+h))]
# Give a name to each node
nodes = [c+r for (c,r) in itertools.product(rows, cols)]
# Set the cells at 1, and walls at 1001
weights = [(item*1000)+1 for sublist in map for item in sublist]
# Initialize a list for results
results = []
for i, weight in enumerate(weights):
# only run for the walls,
# changing the value of the
# specific wall to 1 to remove it
if weight > 1000:
new_weights = copy.deepcopy(weights)
# Removing the wall
new_weights[i] = weights[i] - 1000
# Creating the graph
init_graph = {}
for node in nodes:
init_graph[node] = {}
for i, node in enumerate(nodes):
# If node i is not the last one
if i < len(nodes) -1:
# and it's not on the rightmost column
if (i+1) % w != 0:
# Connect with next node (right)
init_graph[node][nodes[i+1]] = max(new_weights[i], new_weights[i+1])
# If node i is not on the last row
if i < len(nodes) - w:
# connect with node below
init_graph[node][nodes[i+w]] = max(new_weights[i], new_weights[i+w])
graph = Graph(nodes, init_graph)
# Find the shortest path for the specific graph
shortest_path = dijkstra_algorithm(graph=graph, start_node="a0")
# Exit is always the last node
result = shortest_path.get(nodes[-1]) +1 # add 1 because Dijkstra do not count the starting node as a step
# Save the result in our list
results.append(result)
return min(results) # Return the shortest pathAs a note, in the first iteration of my solution I was getting an error for test 4 and 5 because I set only one value for height and width assuming the map was always squared. Apparently that’s not the case, and by treating separately the two dimensions I managed to pass all tests.
Once you are ready, you can check your work by typing:
verify solution.pyIf you completed your work correctly, a happy green message like this one will greet you:
You can then submit the solution as indicated. And that’s it for Google Foobar Challenge level 3 – Prepare the Bunnies’ Escape!
I will write about each individual challenge in a dedicated post. You will find the post series via the link at the end of this post, stay tuned for updates!
Related links
- Google Foobar link (it is by invitation only)
- My series of posts on Google Foobar link
- Dijkstra’s algorithm on Wikipedia page
- Python implementation of Dijkstra’s algorithm on Udacity page
Do you like our content? Check more of our posts in our blog!
