How I Work: Tackling Advent of Code, Day 21

For the past three years, the amazing Eric Wastl has been running the Advent of Code - programming puzzles in the format of an advent calendar, a new puzzle every day for the month of December. They’re mindbending but great fun!

I wondered if people might be curious how I attack these kinds of puzzles - and by the reaction I got on Twitter, I guess the answer is yes! So here goes - this is day 21, the most recent puzzle I’ve completed in the 2017 edition.

About Advent of Code

Each day of Advent of Code is a puzzle in two parts, to be solved any way you see fit. There’s no set programming language to use, or even a requirement to use code at all - people have solved puzzles using everything from Excel to Haskell to C to Elm to pen and paper. I’ve always tried using Elixir, even though Ruby would be my strongest programming language these days. This blog post will have its code snippets in Elixir.

The second part of each puzzle is only revealed after you solve the first part, which can be interesting. Part 2 will typically build on the code written for part 1 - it may add an extra constraint, a change in algorithm, or a longer run (eg. repeat a process 5,000,000 times instead of 50). I’ve only had to come up with a completely different solution for part 2 on one day of the 2017 puzzle set so far. (And here’s hoping that luck holds…)

The link for the puzzle covered in this post is here:

http://adventofcode.com/2017/day/21

If it’s not one you’ve tackled yourself, I definitely recommend going and having a read of it, otherwise this blog post won’t make much sense. Think about how you might solve it - try it out, even! When you’re familiar with what’s going on, come back and keep reading and see how I did it.

Step 1: Write a test for the overall problem

Helpfully, each problem typically comes with a fully-worked-through example, which I use to write to write tests in a TDD fashion. I wrote the following test based on the puzzle example:

defmodule Advent.Day21Test do
  use ExUnit.Case
  alias Advent.Day21


  test "part1/2" do
    assert Day21.part1("../.# => ##./#../...\n.#./..#/### => #..#/..../..../#..#", 2) == 12
  end
end

I’m not incredibly imaginative with my top-level naming scheme - a module named for each day’s puzzle, and part1 and part2 functions.

The list of transformation rules is the puzzle input, so I’ll pass that in to the function I’ll write. The number of iterations of the main process changes too - the example has two, but the real puzzle asks about pixels after five iterations.

Naturally, this test fails, and will continue to fail until I’m pretty satisfied that I’ve solved the puzzle.

Step 2: Decide on internal representation of puzzle input and state

I need to represent the puzzle input, the transformation rules, somehow. Some will be transforming a 2x2 grid into a 3x3 grid, some a 3x3 grid into a 4x4 grid.

I also need to store the current grid of pixels somehow.

I also need to store things in a way that makes flipping and rotating easy. I’ll either need to flip and rotate sections of the grid, or the input for each transformation rule.

Two ways of storing the data pop into my head:

  • Storing each “on” pixel (the #‘s) as a x,y co-ordinate tuple in a list. In this representation, the starting grid would look like: [{1, 0}, {2, 1}, {0, 2}, {1, 2}, {2, 2}] (if the top-left corner is {0, 0}).

It doesn’t have any extra information (I don’t really care about the pixels that are off) but its not really easy to visualise. As the grid gets bigger it will also need to be split up so the transformation rules can be applied - say a 9x9 grid will need to be split into 3x3 pieces. I can see it getting messy like this - find the co-ordinates between {0, 0} and {2, 2} for one piece, then {3, 0} to {5, 2} for the next, etc.

(Full disclosure - I worked with this representation for a while, parsing the transformation rules into the same format. Ultimately I decided it felt like I was making things too hard.)

  • Storing the grid as a list of strings, one string for each row of the grid. In this representation, the starting grid would look like [".#.", "..#", "###"].

It will be a lot easier to parse the puzzle input and the transformation rules into this state. It’s easier to visualise - at any point it will look a lot like the examples given.

It won’t be too tricky to rotate a section of the grid - I can find the size (the length of the strings inside), and rotating it right will be kind of transposing the characters in the lists. The first row after rotating the starting grid to the right should be "#.." - the first character of each of the rows.

Flipping the grid is even easier - reversing each of the strings in the list for a flip around the vertical axis, and reversing the order of the rows for flipping around the horizontal axis.

On that note, I decide to store each transformation rule in a Rule struct - each has an input and an output, taken directly from the puzzle input, but I also decide to precompute the rotated and flipped forms of each input. It’s an added cost up front, but if the grid ends up growing large, I won’t need to keep flipping and rotating the same pieces over and over again. (There’s only so many combinations you can have for a 2x2 or 3x3 grid, after all.)

# Input rule
"../.# => ##./#../..."


# Output rule
%Rule{
  input: ["..", ".#"],
  # Flipping is already covered by rotating. Original input should always take priority over
  # rotated and flipped versions (ie. only need to see if a rotated version matches if no rules
  # match based on their original input), so these stored separately.
  alternates: [["..", "#."], ["#.", ".."], [".#", ".."]],
  output: ["##.", "#..", "..."],
}

Step 3: Write test to make sure puzzle input is parsed correctly

This is basically just codifying the idea from above. There are two transformation rules in the example - this should be parsed into a list of two Rule structs.

describe "parse_input/1" do
  test "generates correct result for example provided" do
    parsed_input = Day21.parse_input("../.# => ##./#../...\n.#./..#/### => #..#/..../..../#..#")
    assert parsed_input == [%Rule{
      input: ["..", ".#"],
      alternates: [["..", "#."], [".#", ".."], ["#.", ".."]],
      output: ["##.", "#..", "..."]
     },
     %Rule{
      input: [".#.", "..#", "###"],
      alternates: [[".#.", "#..", "###"], ["###", "..#", ".#."], ["#..", "#.#", "##."],
                   ["###", "#..", ".#."], [".##", "#.#", "..#"]],
      output: ["#..#", "....", "....", "#..#"]
     }]
  end
end

Of course, it fails because I haven’t written the parse_input/2 function yet.

Step 4: Write code to make previous test pass

The complex part of this is the calculation of the alternates (the rotated and flipped version of each input). I don’t claim to be an Elixir master, but eventually I muddled my way to the following code for calculating alternates, given a Rule that already has its input and output set correctly:

def calculate_alternates(%Rule{}=rule) do
  %{ rule | alternates: [flip_horizontal(rule.input), flip_vertical(rule.input)] ++
    rotate_right(rule.input, 3) |> Enum.uniq }
end


defp flip_horizontal(input), do: Enum.map(input, &(String.reverse(&1)))
defp flip_vertical(input),   do: Enum.reverse(input)


defp rotate_right(_, 0), do: []
defp rotate_right(input, counter) do
  size = String.length(hd(input))
  new_input = Enum.map(1..size, &(new_row(input, &1-1)))
  [new_input | rotate_right(new_input, counter-1)]
end

The alternates are the result of flipping the input around both the horizontal and vertical, as well as rotating it three times (for 90, 180 and 270 degree rotations). It might not be pretty (especially the rotate_right/2 method), but the test for parsing input now passes. Sweet.

Step 5: Break down the algorithm into smaller pieces

Now that the input has been dealt with, I can look at the “real” work - how to run the iterations, transforming the grid based on the rules.

The main algorithm will need to be a loop, where the result of running one iteration is the input to the next.

In each iteration, I’ll need to:

  • Break down the current grid into either 2x2 or 3x3 smaller grids
  • Find the matching rule to transform each of the smaller grids. I need to compare the main inputs first - the rotated/flipped alternates only need to be compared if none of the main inputs match
  • Replace each of the smaller grids with the output from the matching transformation rule
  • Reassemble the new, larger grid.

After the prescribed number of iterations have been run, then I need to count the “on” pixels - the number of ”#” characters in the final grid.

In Ruby-ish pseudocode, that might look like this:

pixel_grid = starting_grid
rules = parse_input
iteration_count.times do
  pieces = disassemble(pixel_grid)
  replacement_pieces = pieces.map { |piece| find_replacement_piece(piece, rules) }
  pixel_grid = reassemble(replacement_pieces)
end
count_on_pixels(pixel_grid)

Step 6: Write tests for each part of the pseudocode

I’ve chosen to focus on the disassemble/reassemble parts first, as I think they’ll be the trickiest.

describe "disassemble/1" do
  test "can disassemble a grid into 2x2 chunks" do
    chunks = Day21.disassemble(["...#", "###.", "#.#.", ".###"])
    assert chunks == [["..", "##"], [".#", "#."], ["#.", ".#"], ["#.", "##"]]
  end


  test "can disassemble a grid into 3x3 chunks" do
    chunks = Day21.disassemble([".........", "#########", ".#.#..##.",
      "##.##.##.", "#########", ".........",
      ".........", ".#.#..##.", "##.##.##."])
    assert chunks == [
      ["...", "###", ".#."], ["...", "###", "#.."], ["...", "###", "##."],
      ["##.", "###", "..."], ["##.", "###", "..."], ["##.", "###", "..."],
      ["...", ".#.", "##."], ["...", "#..", "##."], ["...", "##.", "##."]
    ]
  end


  test "prefers 2x2 grids over 3x3 grids" do
    # A 6x6 grid could disassemble to either.
    chunks = Day21.disassemble(["......", "......", "......", "......", "......", "......"])
    assert hd(chunks) |> List.first |> String.length == 2
  end
end

I’ve had to just make up an example for the 3x3 splitting - the provided example doesn’t come with one. The reassemble specs are identical to the first two disassemble specs, except with the input and output reversed.

Step 7: Implement disassemble/reassemble

How exactly do you disassemble a grid?

           #.  .#
#..#       ..  ..
....  -->
....       ..  ..
#..#       #.  .#

I can:

  • Find the size I need to divide the grid into (2 or 3, based on the divisibility of the first row. 2, 4, 6, 8, etc. will split into size 2 grids. 3, 9, etc. will be size 3.)
  • Split each row into groups of that size. (I Googled how to do that nicely in Elixir.) Now I have lists of lists of strings.
["#..#",      [["#.", ".#"],
 "....",  -->  ["..", ".."],
 "....",       ["..", ".."],
 "#..#"]       ["#.", ".#"]]
  • Split the rows into groups of that size.
[["#.", ".#"],
 ["..", ".."],  -->  [[["#.", ".#"], ["..", ".."]],
 ["..", ".."],        [["..", ".."], ["#.", ".#"]]]
 ["#.", ".#"]]
  • Transpose the elements in each row group. (I Googled that too. Thank you, Stack Overflow.)
[[["#.", ".#"], ["..", ".."]],  -->  [[["#.", ".."], [".#", ".."]],
 [["..", ".."], ["#.", ".#"]]]        [["..", "#."], [".#", ".."]]]

And now each sub-sub-list is a section of the grid. Fantastic.

In code, that looks like this:

def disassemble(grid) do
  chunk_size = if rem(String.length(hd(grid)), 2) == 0, do: 2, else: 3


  grid
  # https://stackoverflow.com/a/43062529/560215
  |> Enum.map(&(for <<x::binary-size(chunk_size) <- &1>>, do: x))
  |> Enum.chunk_every(chunk_size)
  |> Enum.flat_map(&transpose/1)
end


# https://stackoverflow.com/a/42887944/560215
defp transpose(rows) do
  rows
  |> List.zip
  |> Enum.map(&Tuple.to_list/1)
end

With that, the disassemble specs pass.

Reassembling is roughly the inverse procedure of disassembling - chunk, transpose, then join the rows together. The only problem is calculating the size of the target grid, so I know how many grids to chunk together. Inverting the logic, if the smaller grids are 2x2 then I need to chunk together 2 of them to create a row, so that the larger grid is 4x4. String.length(hd(hd(grid))) works for deciding the chunk size here, and the reassemble tests pass.

def reassemble(grid) do
  chunk_size = String.length(hd(hd(grid)))


  grid
  |> Enum.chunk_every(chunk_size)
  |> Enum.flat_map(&transpose/1)
  |> Enum.map(&Enum.join/1)
end

Step 8: Write test and implement transformation step

The transform step is really the critical part of the algorithm. I have each smaller grid from the disassembly, now I need to find the matching rule, where the grid matches either the rule input or one of the rule alternates. The format of the grid/rule data doesn’t really matter here, as it’s just equality checking, so I wrote the following specs:

describe "transform_chunks/2" do
  test "applies a primary transform" do
    rules = [%Rule{input: 1, output: 2}, %Rule{input: 3, output: 4}]
    assert Day21.transform_chunks([3], rules) == [4]
  end


  test "applies a secondary transform when no primary transform matches" do
    rules = [%Rule{input: 1, alternates: [5, 6], output: 2}, %Rule{input: 3, alternates: [7, 8], output: 4}]
    assert Day21.transform_chunks([7], rules) == [4]
  end


  test "gives priority to primary transforms" do
    rules = [%Rule{input: 1, alternates: [6, 7], output: 2}, %Rule{input: 3, alternates: [1, 5], output: 4}]
    assert Day21.transform_chunks([1], rules) == [2]
  end
end

After using the chunk method in disassembly/reassembly, I started referring to the smaller sub-grids as “chunks”. I even toyed with the idea of having a Chunk struct to represent each chunk - but ultimately decided not as there’s no logic that needs to be associated with a chunk. What methods would I have added to the Chunk module? I couldn’t think of any, it would just be a plain data store, so I stuck to having a list of strings instead.

In the specs I’m representing each chunk with just a number, to make them easier to read and follow. A list of chunks goes in, and a list of chunks comes out, and each chunk gets replaced based on the matching rule.

This was perhaps the easiest part of the code so far. I coded up the following functions:

def transform_chunks(grid, rules) do
  Enum.map(grid, &(transform_chunk(&1, rules)))
end


defp transform_chunk(chunk, rules) do
  chunk
  |> Rule.matching(rules)
  |> Map.get(:output)
end

And added some logic to the Rule module to find a rule matching the provided input:

def matching(chunk, rules) do
  primary_match(chunk, rules) || alternate_match(chunk, rules)
end


defp primary_match(chunk, rules) do
  Enum.find(rules, fn rule -> rule.input == chunk end)
end


defp alternate_match(chunk, rules) do
  Enum.find(rules, fn rule -> Enum.member?(rule.alternates, chunk) end)
end

They could probably be shortened, but I think it’s pretty clear what they do and I’m pretty happy with them.

Step 9: Tie it all together and count the on pixels

All the pieces of the pseudocode algorithm are there, now I can tie them together and write the main loop.

@starting_grid [".#.", "..#", "###"]


def part1(rules, iterations) do
  do_part1(@starting_grid, parse_input(rules), 0, iterations)
  |> count_on_pixels
end


defp do_part1(grid, _, iteration, iteration), do: grid
defp do_part1(grid, rules, iteration, max_iterations) do
  grid
  |> disassemble
  |> transform_chunks(rules)
  |> reassemble
  |> do_part1(rules, iteration+1, max_iterations)
end

I’ve found that this is a common pattern in Advent of Code puzzles - a process needs to be run X times, and then a calculation done at the end. Sometimes it seems like it would be simpler to take shortcuts - for example, if I didn’t need the full grid from one iteration as input to the next, calculating it would be a bit of a waste of time. But then if part 2 actually does need the grid, that could be a serious amount of rework to add it in. So I always tend to take the naive approach just to be safe.

I haven’t yet defined the count_on_pixels/1 function, but it seems like it would be easy. I didn’t write any specs for it - and in hindsight I should have, because the code ended up being messy. It felt like I was so close to the end though - and if worse comes to worse, I could just count the ”#” characters manually, right?

def count_on_pixels(grid) do
  grid
  |> Enum.reduce(0, fn line, acc ->
    acc + (line
    |> String.codepoints
    |> Enum.count(&(&1 == "#")))
  end)
end

I did rush this code, I’ll admit. It splits each line into a list of one-character strings using the String.codepoints/1 function - I’ve used that function a lot in these puzzles - and then counts the ”#” characters of each line in a reduce function. It only gets called once, it will do!

And now, after all this work, it seems like all the tests (including the original test I wrote in step 1) should pass. Do they? They do! Excellent!

Step 10: Run the code with the real puzzle input.

I fire up iex to run the real function, feeling pretty confident that it will spit out a number that I can then copy-paste to the website to complete part 1.

iex(1)> data(21) |> Advent.Day21.part1(5)
** (BadMapError) expected a map, got: nil
    (elixir) lib/map.ex:423: Map.get(nil, :output, nil)
    (elixir) lib/enum.ex:1294: Enum."-map/2-lists^map/1-0-"/2
    (advent) lib/advent/day_21.ex:69: Advent.Day21.do_part1/4
    (advent) lib/advent/day_21.ex:61: Advent.Day21.part1/2

(Side note: Advent.data/1 is a helper method I’ve written to load up puzzle input. It just builds up a path to a file, in this case “lib/advent/data/day_21”, in which I previously saved the puzzle input, and then reads the file into a string.)

So… that’s not a number like I expected. What did I do wrong?????

I called Map.get(rule, :output) after finding a matching transformation rule, to get the output it should be transformed to. So for some input, my code didn’t find a matching transformation rule at all. What? Why?

I add a bunch of debugging IO.inspect statements into my pipelines, to see how far my code gets before it dies. To my surprise, it dies on the very first transformation step - when the chunk is the starting grid.

Did I copy the starting grid into my code right? I double check, I did.

What rule do I expect to match, given the starting input?

I manually make a list of possible options for the starting grid - I rotate it three times, I flip it horizontally, I flip it vertically. I have five chunks, one of which needs to match an input in the puzzle input file. I open the file and search for each of the strings - none are there. So I’ve really missed something in my reading of the puzzle.

I go back and re-read the puzzle very carefully, focussing on the part about the missing rules and needing to rotate or flip the input.

The artist explains that sometimes, one must rotate or flip the input pattern to find a match.

Yep, all good.

When searching for a rule to use, rotate and flip the pattern as necessary.

… wait a second. Rotate AND flip? So I need to flip and then rotate the input, when building up the list of alternates?

I manually draw out what that means for the starting grid:

# Input     Rotations


.#.         #..  ###  .##
..#         #.#  #..  #.#
###         ##.  .#.  ..#


# Flip around vertical axis and rotate


.#.         ##.  ###  ..#
#..         #.#  ..#  #.#
###         #..  .#.  .##


# Flip around horizontal axis and rotate


###         ..#  .#.  ##.
..#         #.#  #..  #.#
.#.         .##  ###  #..

One of the new rotations has to match a rule in the puzzle input, right? It does!

Okay, so my test for parsing input needs to be expanded, to reflect the proper list of alternates.

test "generates correct result for example provided" do
  parsed_input = Day21.parse_input("../.# => ##./#../...\n.#./..#/### => #..#/..../..../#..#")
  assert parsed_input == [%Rule{
    input: ["..", ".#"],
    alternates: [["#.", ".."], [".#", ".."], ["..", "#."]],
    output: ["##.", "#..", "..."]
   },
   %Rule{
    input: [".#.", "..#", "###"],
    alternates: [["###", "#..", ".#."], ["###", "..#", ".#."], ["##.", "#.#", "#.."],
                 ["#..", "#.#", "##."], [".##", "#.#", "..#"], [".#.", "#..", "###"],
                 ["..#","#.#", ".##"]],
    output: ["#..#", "....", "....", "#..#"]
   }]
end

There are two more elements in the list of alternates now, and I sorted them for good measure. The test fails, so now…

Step 11: Make failing parse_input/1 spec pass

Though my spec is for parse_input/1, the failing code is the part that generates the list of alternate inputs when building the Rule struct. That’s probably a failing of my test methodology - I should have written more granular tests for the parsing process - but this code is small enough for me to easily locate the source of the problem.

At the moment I calculate alternates like this:

def calculate_alternates(%Rule{}=rule) do
  %{ rule | alternates: [flip_horizontal(rule.input), flip_vertical(rule.input)] ++
    rotate_right(rule.input, 3) |> Enum.uniq }
end

This needs to be updated so I rotate both the flipped inputs and the original input. After a bit of rewriting and refactoring, I end up with the following:

def calculate_alternates(%Rule{}=rule) do
  vertical = flip_vertical(rule.input)
  horizontal = flip_horizontal(rule.input)
  size = String.length(hd(rule.input))


  %{ rule | alternates: (
    [vertical] ++ rotations(vertical, size, 3) ++
    [horizontal] ++ rotations(horizontal, size, 3) ++
    rotations(rule.input, size, 3)
    |> Enum.uniq
    |> Enum.sort
    |> Enum.reject(&(&1 == rule.input))
  )}
end


defp flip_horizontal(input), do: Enum.map(input, &(String.reverse(&1)))
defp flip_vertical(input),   do: Enum.reverse(input)


defp rotations(_, _, 0), do: []
defp rotations(input, size, counter) do
  new_input = Enum.map(1..size, &(new_row(input, &1-1)))
  [new_input | rotations(new_input, size, counter-1)]
end

I could have probably tried to reuse the transpose function I grabbed from the interwebs, but this is okay for my purposes. The parse_input/1 spec now passes, so I should be good to go with running the puzzle input, right?

Step 12: Run against real input again…

iex(1)> data(21) |> Advent.Day21.part1(5)
145

Awesome! It didn’t error, it gave me a result. This should be the number of “on” pixels in the final grid after 5 iterations. So I go to the puzzle page, submit the answer…

That’s not the right answer; your answer is too low.

Well, bollocks.

I go back to the very first test I wrote, for the overall problem. I print out the grid after each iteration:

["#..#", "....", "....", "#..#"]
["##.##.##.", "#..#..#..", ".........", "##.", "#..", "..."]

… That’s not right. The first one is okay, it disassembled, transformed, and reassembled the grid correctly. The second one is all wrong - a grid doesn’t have three rows 9 pixels wide, and three rows 3 pixels wide. What’s gone wrong?

I add a lot more IO.inspect statements throughout the whole loop process, to see where it goes wrong.

defp do_part1(grid, rules, iteration, max_iterations) do
  IO.inspect "--------"
  grid
  |> IO.inspect
  |> disassemble
  |> IO.inspect
  |> transform_chunks(rules)
  |> IO.inspect
  |> reassemble
  |> IO.inspect
  |> do_part1(rules, iteration+1, max_iterations)
end


"--------"
[".#.", "..#", "###"]
[[".#.", "..#", "###"]]
[["#..#", "....", "....", "#..#"]]
["#..#", "....", "....", "#..#"]
"--------"
["#..#", "....", "....", "#..#"]
[["#.", ".."], [".#", ".."], ["..", "#."], ["..", ".#"]]
[
  ["##.", "#..", "..."],
  ["##.", "#..", "..."],
  ["##.", "#..", "..."],
  ["##.", "#..", "..."]
]
["##.##.##.", "#..#..#..", ".........", "##.", "#..", "..."]

Everything looks right up until the very last line of the output. On the second iteration, the grid was split and transformed correctly - but reassembled all wrong. So there’s a bug in my reassemble/1 function. Dangit.

I write a new test, with the exact grid from that output, and what it should reassemble to, based on the example in the problem.

1) test reassemble/1 example in problem (Advent.Day21Test)
   test/day_21_test.exs:72
   Assertion with == failed
   code:  assert grid == ["##.##.", "#..#..", "......", "##.##.", "#..#..", "......"]
   left:  ["##.##.##.", "#..#..#..", ".........", "##.", "#..", "..."]
   right: ["##.##.", "#..#..", "......", "##.##.", "#..#..", "......"]

The chunk_size calculation in the reassemble function is wrong - the strings in the chunks are length 3, so it’s trying to group 3 chunks for each row to create rows of length 9 when reassembling. There are 4 chunks that should be put together into a 2x2 grid - 4 is divisible by 2, so the chunk size should be 2, not 3. Got it.

def reassemble(grid) do
  chunk_size = if rem(length(grid), 2) == 0, do: 2, else: 3


  grid
  |> Enum.chunk_every(chunk_size)
  |> Enum.flat_map(&transpose/1)
  |> Enum.map(&Enum.join/1)
end

That looks a lot more like the chunk size calculation in the disassemble function, too. When I re-run the failing spec, it now passes, so it’s reassembling correctly. Great!

Step 13: Run against real input for a third time…

iex(1)> data(21) |> Advent.Day21.part1(5)
186

A different larger number! I cross my fingers and enter it onto the puzzle page…

That’s the right answer! You are one gold star closer to debugging the printer.

😎

Step 14: Pray that part 2 will build on part 1 code

For this puzzle, it turns out that part 2 is really straightforward.

How many pixels stay on after 18 iterations?

I run the code again, with a different iteration number:

iex(2)> data(21) |> Advent.Day21.part1(18)
3006440

It takes six or seven seconds or so to run, but it comes back with a plausible number. I enter it onto the puzzle page:

That’s not the right answer; your answer is too low.

Not again!

Time for some more IO.inspect debugging. I suspect the reassemble/1 function again, but I’ll wait and see. I inspect the reassembled grid on each loop…

"-------"
[".##.", "####", ".#.#", ".#.."]
"-------"
["######", ".#..#.", "#.##.#", "#.#..#", "##.##.", "...##."]
"-------"
["####.####", ".#.##..#.", "#.#...#.#", "#.#####.#", "##..#.##.", "...#.#...",
 "#.##.##.#", "##.##.##.", "........."]
"-------"
["######.#####", "#.##.#..#.##", "#####...####", ".####.#..###", "##.#######.#",
 ".#..#.##.#..", "#...#####...", "#.#..####.#.", "##.###.###.#", ".#...#...#..",
 "#...#...#...", "#.#.#.#.#.#."]
"-------"
["###.#.", ".#..#.", "#.####", "###..#", ".#.##.", "#.###.", "###.#.", ".#..#.",
 "#.####", "###.#.", ".#..#.", "#.####", "#.#..#", "##.##.", "...##.", "###.#.",
 ".#..#.", "#.####", "###..#", ".#.##.", "#.###.", "###.#.", ".#..#.", "#.####",
 "###..#", ".#.##.", "#.###.", "#.#..#", "##.##.", "...##.", "###.#.", ".#..#.",
 "#.####", "#.#..#", "##.##.", "...##.", "###..#", ".#.##.", "#.###.", "###..#",
 ".#.##.", "#.###.", "###..#", ".#.##.", "#.###.", "#.#..#", "##.##.", "...##.",
 "#.#..#", "##.##.", ...]
"-------"

That’s really weird - the lines should be getting longer on each iteration, and the grid should always be square. After three iterations the grid is 12 (characters per row) x 12 (number of rows), but after that it goes screwy.

Is the chunk sizing still wrong?

I add some more debugging to the top of the reassemble/1 function and run it again in iex.

def reassemble(grid) do
  IO.inspect length(grid)
  chunk_size = if rem(length(grid), 2) == 0, do: 2, else: 3
  ...
1
4
9
9
36
81
...

Lightbulb moment! 💡

The grids are always squares, and each chunk is a square - so it makes sense that the number of chunks is always a perfect square. The second iteration has four chunks, arranged 2x2 - third iteration, nine chunks in 3x3 - so the chunk size is always the square root of the chunk count.

After Googling how to do square roots in Elixir, I write the following:

chunk_size = :math.sqrt(length(grid)) |> trunc

And now when printing out the final grid on each iteration, everything looks as I would expect.

Can I run the part 2 code again now?

iex(3)> data(21) |> Advent.Day21.part1(18)
3018423

It’s a different number… larger than the previous, which is good. I enter that number on the puzzle page:

That’s the right answer! You are one gold star closer to debugging the printer.

🎉

Summary

This was actually a pretty involved problem, one of the longer code samples I’ve written so far.

Reading over the code I wrote now, I can see several places it can be improved (for example, flipping the rule input to find alternates only needs to be done once, not twice - the second set of alternates is always the same as the first), as well as places I’m not sure exactly what I was thinking and didn’t write it down when taking notes (the first time I fixed reassemble/1… what?)

If you’d like to check out the full code I wrote to solve this puzzle, you can see it here on GitHub. I don’t claim to be the world’s greatest programmer - but if someone learns something from how I break down a problem to solve it, then its all worthwhile :)

I don’t have comments enabled on this blog anymore, but if you’d like to discuss what I’ve written here, hit me up on Twitter!

← Home