Earlier today, I saw a cute little puzzle on Reddit . The puzzle is pretty simple, we have a 3x3 grid where each square is either pink or turquoise. We are also given a target grid with a different configuration of colors. Finally, we can use 3 horizontal brushes(A, B, and C) that is pink, or 3 vertical brushes(D, E, and F) that is turquoise. The goal is to find the minimum number of brush strokes required to paint the target grid.

It took me a couple of minutes to come up with the solution, I’m leaving the answer below in a spoiler box. If you want to try it yourself, please do so before reading the answer.

The next thought I had was, how hard would it be to write a program that solves this problem for any given grid? . I thought it would be a fun little exercise to write a program that solves this problem. Although I don’t think my solution is perfect(my intuition is that there are cases where it takes the wrong step which is possible to detect in the future and revert, but I didn’t implement it), I’m happy with the simplicity of the result.

The first question that requires answering when solving such a question is, what does the solution space look like? If the solution space is very small, we can just enumerate all of them(hint: it’s not that large). For a 3x3 grid, we only have 6 brushes, and using a brush twice does not provide any additional benefit. This is an important insight into pushing the solution space down, so let’s think about why that is for a second.

The reason why, is that there is only one way to paint a square. If we want to paint a square pink, we have to use the horizontal brush on that level, if we want to paint a square turquoise, we have to use the vertical brush on that level. Let’s say that we have a sequence of brush strokes x_1, x_2, x_3... . The question we need to ask is, why do we even care about the order of strokes to begin with? The reason is that column and row strokes don’t commute . Applying r_i where r_i is the row stroke for the i’th row, and c_i where c_i is the column stroke for the i’th column, is not the same as applying c_i and then r_i . r_i c_j means that cell[i, j] is painted turqoise , and c_j r_i means that cell[i, j] is painted pink . This gives us two piece of information:

1. Order of strokes matter.
2. By changing the order of two strokes, we can change the color of a cell in the way we want.

As we can change the color of a cell by changing the order of strokes, running c_i ... r_j ... c_i is the same as running r_j ... c_i . That is it is sufficient to use each stroke once. Although working, this solution did not really satisfy my curiosity, it was just too inelegant.

The next step we can take is to invert our thinking process for the previous solution. Previously, we decided that we can always change the order of two strokes when we want to change the color of something. Thinking backwards, this also means that we can just place the strokes in the order we want to paint the cells. If we want to paint cell i, j pink, now we know that our solution must be in the form ... c_i ... r_j ... . For this solution, we will first calculate the difference of the current grid and the target grid, then we will find a set of moves required to paint the grid in the way we want. We will order the strokes with respect to the painting order, and apply the first stroke in the list. After the application, we recompute the difference, and continue this process until the paintings are the same.

This solution scales much better, as it’s local. We use a greedy approach to solve the problem, so we don’t have to generate the whole permutation space of strokes. The solution is also very simple to implement, the solver logic relies on the two functions provided in Typescript below. The order managed the order of strokes to solve commutation issues, and the solve function applies the strokes in the order provided by the order function.

1
const order = (d1: Directive, d2: Directive, c: Canvas): number => {
2
    if (d1.orient === d2.orient) {
3
        return 0;
4
    }
5

6
    let dr = d1.orient === "row" ? d1 : d2;
7
    let dc = d1.orient === "column" ? d1 : d2;
8

9
    let t = c[dr.index][dc.index];
10

11
    if (d1.orient === "row" && t === "pink") {
12
        return -1;
13
    } else if (d1.orient === "column" && t === "blue") {
14
        return -1;
15
    } else {
16
        return 1;
17
    }
18
}
19

20
const solve = (c1: Canvas, c2: Canvas): Directive[] => {
21
    let path : Directive[] = [];
22

23
    while (different(c1, c2)) {
24
        let d = diff(c1, c2);
25
        let dirs = getDirectives(d);
26
        let sortedDirs = dirs.sort((d1, d2) => order(d1, d2, c2));
27
        let dir = sortedDirs.pop() as Directive;
28
        c1 = applyDirective(c1, dir);
29
        path.push(dir);
30
    }
31

32
    return path;
33
}