Google foobar, part v: breaking the n-th wall
written on February 25, 2023
This post is the fifth installment of the foobar challenge series. You can read the first one to learn more about foobar and see what sort of intro problems the challenge presents if you don't want any real spoilers.
WARNING: Obviously, MAJOR spoilers ahead, for the problems themselves and possible solutions or hints. Even if you're attempting one of these and feel completely stuck, give it another go before reading the rest. Keep reading only if you don't mind getting spoiled!
Problem statement
This one was a lot of fun! The problem statement is the following:
Given a map, where a \(0\) signifies a walkway and a \(1\) signifies a wall, compute the length of the shortest possible path from the top left corner to the bottom right corner. No diagonal movement is authorized, and at most one wall can be broken (and turned into a walkway). The length of the path is the number of walkways that it contains, counting both the top left corner and the bottom right corner.
The minimum for the width and height is 2, and the maximum is 20 (but the map can be non-square).
Maybe that's kind of hard to visualize, so here's an easy example:
[
[0, 1, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 1],
[0, 0, 0, 0],
]
I'll use #s for walls and .s for walkways to make it a bit more easy on the eyes:
. # # #
. # . #
. # # #
. . . .
So here the length of the shortest path is 7 (imagine that @ is a character walking around in the map):
@ # # # . # # # . # # # . # # # . # # # . # # # . # # #
. # . # -> @ # . # -> . # . # -> . # . # -> . # . # -> . # . # -> . # . #
. # # # . # # # @ # # # . # # # . # # # . # # # . # # #
. . . . . . . . . . . . @ . . . . @ . . . . @ . . . . @
There isn't really a wall we can break here that will make the path any shorter; the only wall that we can break that can make any difference is the one at \((2, 1)\) (the origin \((0, 0)\) is in the top left, the first number is the row and the second is the column, both 0-indexed), but it also produces a path of length 7.
Here is another interesting example:
. . . .
# # # .
. . . .
. # # #
. # # #
. . . .
Here, again, there is a path from the top left to the bottom right, but it's of length 15; look at what happens when we break the wall at \((1, 0)\) however:
. . . .
# # # .
. . . .
. # # #
. # # #
. . . .
Suddenly, we have a path going down the left side that's dramatically shorter: 9 walkways! It is important to remember that we are looking for the shortest path, not just any path from the top left to the bottom right.
@@@@@@@@@@
@@@@@@@@@@
SECOND WARNING: If you want to solve this yourself, STOP HERE! Anything past this point is a spoiler of some part of figuring out the solution, or of the solution itself. You've been warned!
@@@@@@@@@@
@@@@@@@@@@
First ideas
When I saw this, my mind immediately went to Dijkstra's algorithm. I knew that obviously that wouldn't outright solve the problem—you have to incorporate the wall-breaking mechanic somehow—but at least it's a good place to start, for the low-hanging fruit, y'know.
Before we do that, we need some way to convert the map as it's given by the challenge input to a Dijkstra-compatible form. Basically, we need to go from this:
[
[0, 1],
[1, 0],
]
To this:
[
[0, None, None, None],
[1, 0, None, 1 ],
[1, None, 0, 1 ],
[None, None, None, 0 ],
]
The second one is a table that describes the cost of going from a specific point in
the map to another specific point. For example, the first row addresses the costs of moving
from the origin (top left, \((0, 0)\)) to any other point. The first element of the first row
is \(0\), because obviously moving from the origin to the origin costs
nothing. This is why the entire diagonal is \(0\)s: for any point in the map, moving
from the point to itself costs \(0\). The second element in the first row is None, because moving from the origin to the right is impossible,
as there's a wall (a \(1\)). You can use many different things to signify this (e.g. float("inf")), but I chose None here. Similarly, the rest of the points on the first row
are inaccessible: going down is impossible because there's a wall, and going diagonally is also
impossible because it's forbidden by the rules.
Of course, Dijkstra's algorithm can support different weights, but here moving from any walkway
to any other walkway always has the same cost, as you can't jump
over anything or
anything of the sort. So for example, as going down by one from the point \((0, 1)\) is
allowed, the fourth element of the second row of the cost table is \(1\).
That might seem weird to you; how is it allowed to go anywhere from \((0, 1)\), it's a wall! Well, that's the entire point of the wall-breaking mechanic: we can break it and allow passage through it.
All that being said, here is a function to transform the inputs of the challenge into cost tables:
solution.py
def dijkstrify(foobar_map):
res = []
height = len(foobar_map)
width = len(foobar_map[0])
for i in range(height * width):
res.append([])
index_y = i // width
index_x = i - index_y * width
for j in range(height * width):
# Unreachable by default.
value = None
# Diagonal.
if i == j:
value = 0
# Moving left.
if j == i - 1 and i % width != 0:
value = 1 if foobar_map[index_y][index_x - 1] == 0 else None
# Moving right.
if j == i + 1 and (i + 1) % width != 0:
value = 1 if foobar_map[index_y][index_x + 1] == 0 else None
# Moving up.
if j == i - width and i - width >= 0:
value = 1 if foobar_map[index_y - 1][index_x] == 0 else None
# Moving down.
if j == i + width and i + width <= width * height - 1:
value = 1 if foobar_map[index_y + 1][index_x] == 0 else None
res[i].append(value)
return res
The collection of if statements in the lines 16-33 take
care of all the special
conditions we mentioned before: they verify if the movement is
legal (i.e., if the move can even be attempted, regardless of if there's a wall or not
in the way), and then either assign a cost of 1 if the
movement is valid (i.e., if there is no wall in the way) or None if it's not (a wall makes the point unreachable). Of
course, we have to check for boundaries (hence the whole (i + 1) % width != 0 business) because there's no way to go left
from the first column, right from the last column, up from the top row and down from the bottom
row.
Now that we have that, let's implement Dijkstra's algorithm:
solution.py
def simple_dijkstra(graph, source):
unvisited_nodes = list(range(len(graph)))
dist = [float("inf")] * len(graph)
dist[source] = 0
while unvisited_nodes:
u = unvisited_nodes[0]
for node in unvisited_nodes:
if dist[node] < dist[u]:
u = node
unvisited_nodes.remove(u)
for i in range(len(graph[u])):
if graph[u][i] is None:
continue
alt = dist[u] + graph[u][i]
if alt < dist[i]:
dist[i] = alt
return dist
It might sound silly, but this algorithm always looks cool to me, especially when implemented
in a language with very minimal syntax like Python: it's super simple and clean yet super
powerful. This is of course the discount version (hence the simple_ prefix), because we don't care about what the paths
actually are; we only care about their length. Otherwise, it's a pretty
standard
implementation of the algorithm. The numbers of the nodes
(i.e., the
points) are given in raster order: the first one is the origin (\((0, 0)\)), the second one is
the one to its right and so on, and when we reach the end of the first row we circle back to
the first element of the second row. The last point to be numbered is of course the exit (the
bottom right corner).
If you're curious about why we even need the source
argument (don't we always start at (0, 0) anyway?),
well, you'll see.
Let's put everything together:
solution.py
def solution(map):
graph = dijkstrify(map)
dists = simple_dijkstra(graph, 0)
return dists[-1] + 1
We take the last distance because we've ran Dijkstra's algorithm on the origin and we want to
get the distance from the origin to the last point (i.e., the exit). We need the + 1 part to stay in accordance with the rules, because the
algorithm doesn't include the origin in the path length.
Let's test it out:
$ shell
$ python2 Python 2.7.18 (default, Jul 1 2022, 10:30:50) [GCC 11.2.0] on linux2 Type "help", "copyright", "credits" or "license" for more information.>>> import solution >>> solution.solution( ... [ ... [0, 1, 1, 1], ... [0, 1, 0, 1], ... [0, 1, 1, 1], ... [0, 0, 0, 0], ... ] ... ) 7
But of course, the wall-breaking mechanic isn't handled:
>>> Python 2 REPL
>>> solution.solution(
... [
... [0, 1],
... [1, 0],
... ]
... )
inf
So that's what we'll take care of next.
Bit flips(?)
Well, this is not much of an idea, but it's what I tried while waiting for a better idea to come to mind: we can try to randomly break the walls one by one and see if that makes any difference.
solution.py
def solution(map):
graph = dijkstrify(map)
dists = simple_dijkstra(graph, 0)
res = [dists[-1] + 1]
ones = [
(i, j)
for i, line in enumerate(map)
for j, value in enumerate(line)
if value == 1
]
while ones:
scratch_map = list(map)
wall_to_break = ones.pop()
scratch_map[wall_to_break[0]][wall_to_break[1]] = 0
graph = dijkstrify(scratch_map)
dists = simple_dijkstra(graph, 0)
res.append(dists[-1] + 1)
return sorted(res)[0]
We make a scratch map
to avoid having to repair any walls we break next time we try
breaking a different wall. Let's see if it works:
>>> Python 2 REPL
>>> solution.solution(
... [
... [0, 1],
... [1, 0],
... ]
... )
3
Nice, it figured out a way out this time! How about a map with a shortcut?
>>> Python 2 REPL
>>> 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],
... ]
... )
11
This means that it did indeed find the optimal path; if you don't break any walls and take the
existing solution
, then you end up with a huge path (21). But if you break the wall at
\((1, 0)\) then the optimal path appears.
Okay, let's stress this dumb little algorithm out: I'm gonna give it the biggest possible graph and make it such that the last wall it can break is actually the one it has to break:
[
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0],
] # Shortest path length: 39
If you look carefully, the wall that needs to break is at \((19, 18)\), which (not at all) coincidentally is the last one to appear in the map (the exit is at \((19, 19)\)). So how does the algorithm deal with that?
$ shell
$ time python2 solution.py
39
python2 solution.py 11,35s user 0,00s system 99% cpu 11,352 total
Ouch! The result is correct but that's just way too slow. It's time to think of a real solution.
Solution
Remember that thing I mentioned earlier about looking at the distance from a wall point
?
Well, it actually isn't that bad of an idea: what if we simply looked at the sum of the
distances between a wall point, the entry point, and the exit point? If the sum of the two is
not infinite, then we have a valid path that can be created by breaking the wall of the wall
point. Let's try it out:
solution.py
def solution(map):
graph = dijkstrify(map)
dists = simple_dijkstra(graph, 0)
res = [dists[-1] + 1]
# Try to find the 1 that needs to be flipped.
for i in range(1, len(graph)):
dists = simple_dijkstra(graph, i)
if dists[0] != float("inf") and dists[-1] != float("inf"):
res.append(dists[0] + dists[-1] + 1)
return sorted(res)[0]
Definitely looks cleaner, but what about performance?
$ shell
$ time python2 solution.py # Using the big 20x20 map again.
39
python2 solution.py 3,22s user 0,01s system 99% cpu 3,252 total
That's much better than before, but still way too slow; at this point, I think that anything above sub-second times for the biggest inputs is probably going to be rejected on foobar.
Obviously the problem here is that we're running Dijkstra's algorithm for way too many wall
points; the check for infinite distance happens after the call, by which point we've
already paid the performance cost. So, what we need is a way to know if it's worth it to run
the algorithm before we call simple_dijkstra()
on the wall point.
If you think about it, there's a simple criterion: there is no point in running simple_dijkstra() on any wall point that's surrounded by
walls on all sides, because there's just no way that it can be part of a valid path, as we can
only break one wall! That means that the only thing we have to check is the presence of
any walkway that's accessible from the point. This thankfully translates to something
very simple in code: the presence of a path with cost 1
in the cost table (or graph in the code).
solution.py
def solution(map):
graph = dijkstrify(map)
dists = simple_dijkstra(graph, 0)
res = [dists[-1] + 1]
# Try to find the 1 that needs to be flipped.
for i in range(1, len(graph)):
if 1 in graph[i]:
dists = simple_dijkstra(graph, i)
if dists[0] != float("inf") and dists[-1] != float("inf"):
res.append(dists[0] + dists[-1] + 1)
return sorted(res)[0]
Let's test it out:
$ shell
$ time python2 solution.py # Using the big 20x20 map again.
39
python2 solution.py 0,65s user 0,00s system 99% cpu 0,657 total
And there we go!