Advent of Code Day 22

For the second time in this year’s Advent of Code challenge, I feared I would not be able to get my two stars today. The first part of the puzzle was easy enough – parse the input with a regular expression active pattern, and then a nested for loop enabled me to find number of possible moves:

let (|Regex|_|) ptrn str = match Regex.Match(str, ptrn) with m when m.Success -> Some([ for g in m.Groups -> g.Value ] |> List.tail) | _ -> None

let parseLine line =
    match line with
    | Regex @"/dev/grid/node-x(\d+)-y(\d+)\s+(\d+)T\s+(\d+)T\s+(\d+)T\s+\d+\%" [x;y;s;u;a] -> Some ((int x,int y),int s,int u,int a)
    | _ -> None

let input = System.IO.File.ReadAllLines (__SOURCE_DIRECTORY__ + "\\input.txt")
 
let nodes = input |> Array.choose parseLine

seq {for (pos,s,u,a) in nodes do
        for (pos',s',u',a') in nodes do
            if pos <> pos' && u <> 0 && u < a' then
                yield 1} |> Seq.length |> printfn "part a: %d"

However, when I saw the second part of the puzzle, I realised that the brute force solution, whether tackled breadth or depth-first would take forever. We needed a much cleverer approach.

Basically the challenge involved us shifting data around a grid of computers. We could only move data from one computer to the next if there was enough space. But with a grid size of 30x33 nodes, the number of possibilities was overwhelming.

But there was a trick to solving part 2. And that was to notice something about the input data. In our grid, there were some nodes with so much data they could never be moved at all. So they were like walls in a maze. And there was just one empty node. All the other nodes had just enough data on them that they could only be copied to the empty node, but all had enough capacity to receive the data from any other node.

So this was essentially like a slide puzzle, where the empty node moves around the grid as we copy data onto it. We copy data until empty node is next to the one that has the target data. And then we shuffle the data up to the target node.

I wrote a very simple function to visualize the layout of my puzzle input. It visualizes the grid rotated, but that doesn’t matter for finding the shortest route:

let printPos (pos,s,u,a) =
    if u = 0 then "_" elif u > 100 then "#" else "."

nodes |> Array.chunkBySize 30 |>
    Array.map (Array.map printPos >> String.concat " ")
    |> (fun a -> System.IO.File.WriteAllLines(__SOURCE_DIRECTORY__ + "\\grid.txt", a))

Once I printed this out, it suddenly became obvious that the challenge was actually quite a simple one, hiding in the seemingly random problem input. My grid looks like this:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . _
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . # . .

The #’s mark ‘walls’ and the ‘_’ marks the empty node. And we just needed to move the data from the bottom left to top left.

Suddenly it becomes very obvious how to solve this. To get the empty node next to the bottom left we need to move it up 12 nodes, left 29 nodes and then down 28 nodes. Moving the target data up to the top left is a bit more complex as once we copy it up, the empty node is now the wrong side of the target data, so it takes four moves (right, up, up, left) to get it above the target data again. We have to repeat this five move sequence 35 times before needing one final copy to get the data to its target destination. So my answer could be calculated manually:

12+29+28+(31*5)+1 |> printfn "part b: %d"

Now in one sense, I was very pleased to get my answer, but this does feel a bit unsatisfactory. We’ve not written a general solution that could solve all possible inputs. I suppose we could write a solver that could solve “similar” inputs – where the optimal strategy was essentially the same. But a solver that found the shortest solution for all inputs would be very hard to create.

So today’s problem makes me think of the classic “YAGNI” principle: “You aren’t gonna need it”. So often as programmers we spend a long time writing complex code to meet imagined requirements that never materialize. But often just writing the minimal code that solves the actual problem we have today can save huge amounts of time. Yes, we may need to rewrite if harder inputs do come along in the future, but time now can be better spent on things we know we need.

The code is available on GitHub