Advent of Code 2021 - Day 20

This topic is about Day 20 of the Advent of Code 2021.

We have a private leaderboard (shared with users of Erlang Forums):

https://adventofcode.com/2021/leaderboard/private/view/370884

The entry code is:
370884-a6a71927

I wasted a lot of time by using a “smart” and efficient representation - a list of numbers and bitwise operators. That worked fine for the example, but not for my input because I failed to handle infinity properly. With a padding hack I could get it to work for part 1, but not for part 2.

I ended up scrapping my part 1 solution and implementing the more obvious solution of using a map to represent the image grid.

Part 2 runs in ~3s. I took too long to realize I should have used a Map instead of a MapSet… (Maybe a MapSet can be used, but it would probably make the code more complicated).

defmodule AdventOfCode.Day20 do
  def part1(input) do
    {algo, image} = parse_input(input)

    image
    |> make_output(algo, 1)
    |> make_output(algo, 2)
    |> Map.values()
    |> Enum.count(&(&1 == "#"))
  end

  def part2(input) do
    {algo, image} = parse_input(input)

    Enum.reduce(1..50, image, fn n, acc ->
      make_output(acc, algo, n)
    end)
    |> Map.values()
    |> Enum.count(&(&1 == "#"))
  end

  def make_output(image, algo, n) do
    {min_x, max_x} = image |> Map.keys() |> Enum.map(fn {x, _} -> x end) |> Enum.min_max()
    {min_y, max_y} = image |> Map.keys() |> Enum.map(fn {_, y} -> y end) |> Enum.min_max()

    Enum.reduce(
      for(x <- (min_x - 1)..(max_x + 1), y <- (min_y - 1)..(max_y + 1), do: {x, y}),
      Map.new(),
      fn point, acc ->
        bin = point |> get_nbs(image, n) |> Enum.join() |> String.to_integer(2)
        Map.put(acc, point, Map.get(algo, bin))
      end
    )
  end

  def get_nbs({x, y}, image, n) do
    Enum.map(
      [{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {0, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}],
      fn {x1, y1} ->
        case Map.get(image, {x + x1, y + y1}) do
          "#" -> 1
          "." -> 0
          nil -> if rem(n, 2) == 0, do: 1, else: 0
        end
      end
    )
  end

  def parse_input(input) do
    [algo, image] = String.split(input, "\n\n", trim: true)

    algo =
      algo
      |> String.codepoints()
      |> Enum.reject(&(&1 == "\n"))
      |> Enum.with_index()
      |> Map.new(fn {v, k} -> {k, v} end)

    image =
      image
      |> String.codepoints()
      |> Enum.reduce({Map.new(), 0, 0}, fn
        "\n", {acc, _x, y} -> {acc, 0, y + 1}
        point, {acc, x, y} -> {Map.put(acc, {x, y}, point), x + 1, y}
      end)
      |> elem(0)

    {algo, image}
  end
end
1 Like

yeah, ended up doing a very straight-forward giant map solution, where initially I thought I’d be clever by only storing the 1s, but only when dealing with actual data I realised that the outside is “blinking”, so had to change it to also store the zeroes, and to figure out a cleverish way to tell the Map.get(src, {x,y}, default) what that default should be.

1 Like

A mix of structs and bitwise operations

1 Like

Christmas is nearing, motivation is dropping. And I’m not even ashamed anymore:

1 Like
1 Like