Google foobar, part v: breaking the n-th wall

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 as follows:

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 0s: 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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

40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

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

63
64
65
66

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:

$ 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:

>>> 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

63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

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:

>>> solution.solution(
...     [
...         [0, 1],
...         [1, 0],
...     ]
... )
3

Nice, it figured out a way out this time! How about a map with a shortcut?

>>> 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?

$ 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

63
64
65
66
67
68
69
70
71
72
73
74

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?

$ 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

63
64
65
66
67
68
69
70
71
72
73
74
75

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:

$ 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!