Advent of Code - Day 18

Mix.install([
  {:kino_aoc, "~> 0.1"}
])

Introduction

–> Content

Puzzle

{:ok, puzzle_input} =
  KinoAOC.download_puzzle("2023", "18", System.fetch_env!("LB_AOC_SESSION"))

Parser

Code - Parser

defmodule Parser do
  def parse(input) do
    String.split(input, "\n", trim: true)
    |> Enum.map(fn line ->
      [direction, distance_string, color_raw] = String.split(line, " ", trim: true)

      %{
        direction: direction,
        distance: String.to_integer(distance_string),
        color: Regex.replace(~r/\(|\)/, color_raw, "")
      }
    end)
  end

  def parse_pt2(input) do
    String.split(input, "\n", trim: true)
    |> Enum.map(fn line ->
      [_, _, color] = String.split(line, " ", trim: true)

      dist_and_dir_str = Regex.replace(~r/\(|\#|\)/, color, "")
      {distance_encoded, direction_encoded} = String.split_at(dist_and_dir_str, 5)

      %{
        direction: decode_direction(direction_encoded),
        distance: decode_distance(distance_encoded)
      }
    end)
  end

  defp decode_direction(direction_encoded) do
    %{"0" => "R", "1" => "D", "2" => "L", "3" => "U"}
    |> Map.get(direction_encoded)
  end

  defp decode_distance(distance_encoded) do
    # String.to_integer(distance_encoded)
    distance_encoded
    |> Integer.parse(16)
    |> elem(0)
  end
end

Tests - Parser

ExUnit.start(autorun: false)

defmodule ParserTest do
  use ExUnit.Case, async: true
  import Parser

  @input """
  R 6 (#70c710)
  D 5 (#0dc571)
  L 2 (#5713f0)
  D 2 (#d2c081)
  R 2 (#59c680)
  D 2 (#411b91)
  L 5 (#8ceee2)
  U 2 (#caa173)
  L 1 (#1b58a2)
  U 2 (#caa171)
  R 2 (#7807d2)
  U 3 (#a77fa3)
  L 2 (#015232)
  U 2 (#7a21e3)
  """

  @expected [
    %{direction: "R", distance: 6, color: "#70c710"},
    %{direction: "D", distance: 5, color: "#0dc571"},
    %{direction: "L", distance: 2, color: "#5713f0"},
    %{direction: "D", distance: 2, color: "#d2c081"},
    %{direction: "R", distance: 2, color: "#59c680"},
    %{direction: "D", distance: 2, color: "#411b91"},
    %{direction: "L", distance: 5, color: "#8ceee2"},
    %{direction: "U", distance: 2, color: "#caa173"},
    %{direction: "L", distance: 1, color: "#1b58a2"},
    %{direction: "U", distance: 2, color: "#caa171"},
    %{direction: "R", distance: 2, color: "#7807d2"},
    %{direction: "U", distance: 3, color: "#a77fa3"},
    %{direction: "L", distance: 2, color: "#015232"},
    %{direction: "U", distance: 2, color: "#7a21e3"}
  ]

  describe "parse/1" do
    test "simple example" do
      assert parse(@input) == @expected
    end
  end

  describe "parse_pt2/1" do
    test "simple example" do
      assert parse_pt2(@input) == [
               %{direction: "R", distance: 461_937},
               %{direction: "D", distance: 56407},
               %{direction: "R", distance: 356_671},
               %{direction: "D", distance: 863_240},
               %{direction: "R", distance: 367_720},
               %{direction: "D", distance: 266_681},
               %{direction: "L", distance: 577_262},
               %{direction: "U", distance: 829_975},
               %{direction: "L", distance: 112_010},
               %{direction: "D", distance: 829_975},
               %{direction: "L", distance: 491_645},
               %{direction: "U", distance: 686_074},
               %{direction: "L", distance: 5411},
               %{direction: "U", distance: 500_254}
             ]
    end
  end
end

ExUnit.run()

Part One

Code - Part 1

defmodule PartOne do
  def solve(input) do
    IO.puts("--- Part One ---")
    IO.puts("Result: #{run(input)}")
  end

  def run(input_string) when is_bitstring(input_string),
    do: run(Parser.parse(input_string))

  def run(input) do
    map_out_digging_perimeter(input)
    |> fill_in_area()
    |> sum_of_trenches()
  end

  def map_out_digging_perimeter(input) do
    digging_coordinates(input)
    |> coordinates_to_graph()
  end

  def fill_in_area(graph) do
    rows_with_idx = Enum.with_index(graph)

    Enum.map(rows_with_idx, fn {cols, ridx} ->
      cols_with_idx = Enum.with_index(cols)

      Enum.reduce(
        cols_with_idx,
        {[], false, start_of_boundary(graph, hd(cols), ridx, 0)},
        fn {cell, cidx}, {row, inside, start_of_boundary} ->
          if on_boundary?(start_of_boundary) do
            case cell do
              "#" -> still_on_boundary(cell, row, inside, start_of_boundary)
              "." -> now_off_boundary(graph, ridx, cidx, cell, row, inside, start_of_boundary)
            end
          else
            case cell do
              "#" ->
                now_on_boundary(graph, ridx, cidx, cell, row, inside, start_of_boundary)

              "." ->
                if inside do
                  fully_inside(cell, row, inside, start_of_boundary)
                else
                  fully_outside(cell, row, inside, start_of_boundary)
                end
            end
          end
        end
      )
      |> elem(0)
      |> Enum.reverse()
    end)
  end

  defp on_boundary?(start_of_boundary) do
    start_of_boundary
  end

  defp now_on_boundary(graph, ridx, cidx, cell, row, inside, _start_of_boundary),
    do: {[cell | row], inside, start_of_boundary(graph, cell, ridx, cidx)}

  defp still_on_boundary(cell, row, inside, start_of_boundary),
    do: {[cell | row], inside, start_of_boundary}

  defp now_off_boundary(graph, end_ridx, end_cidx, cell, row, inside, start_of_boundary) do
    if was_travelling_alongside_boundary?(end_ridx, end_cidx - 1, start_of_boundary) &&
         boundary_180?(graph, end_ridx, end_cidx - 1, start_of_boundary) do
      # if WAS inside before
      if inside do
        fully_inside(cell, row, inside, nil)
      else
        fully_outside(cell, row, inside, nil)
      end
    else
      # if WAS inside before
      if inside do
        {[cell | row], !inside, nil}
      else
        {["#" | row], !inside, nil}
      end
    end
  end

  defp fully_outside(cell, row, inside, _start_of_boundary), do: {[cell | row], inside, nil}
  defp fully_inside(_cell, row, inside, _start_of_boundary), do: {["#" | row], inside, nil}

  defp start_of_boundary(graph, cell, ridx, cidx) do
    if cell == "#" do
      %{
        cell_above: cell_at(graph, ridx - 1, cidx),
        cell_below: cell_at(graph, ridx + 1, cidx),
        ridx: ridx,
        cidx: cidx
      }
    end
  end

  defp was_travelling_alongside_boundary?(_end_ridx, end_cidx, %{cidx: start_cidx}) do
    start_cidx < end_cidx
  end

  defp boundary_180?(graph, end_ridx, end_cidx, %{
         cell_above: start_cell_above,
         cell_below: start_cell_below
       }) do
    (start_cell_below == "#" &amp;&amp; cell_at(graph, end_ridx + 1, end_cidx) == "#") ||
      (start_cell_above == "#" &amp;&amp; cell_at(graph, end_ridx - 1, end_cidx) == "#")
  end

  defp cell_at(graph, y, x) do
    row = Enum.at(graph, y)
    row &amp;&amp; Enum.at(row, x)
  end

  defp sum_of_trenches(graph) do
    Enum.reduce(graph, 0, fn row, count ->
      count + Enum.count(row, &amp;(&amp;1 == "#"))
    end)
  end

  def digging_coordinates(input) do
    start = {0, 0}
    coords = [start]

    Enum.reduce(input, {coords, start}, fn %{direction: dir, distance: dist},
                                           {coords, current_coord} ->
      {last_y, last_x} = current_coord

      {coordinates_traversed, new_coord} =
        case dir do
          "R" -> {Enum.map((last_x + 1)..(last_x + dist), &amp;{last_y, &amp;1}), {last_y, last_x + dist}}
          "L" -> {Enum.map((last_x - 1)..(last_x - dist), &amp;{last_y, &amp;1}), {last_y, last_x - dist}}
          "D" -> {Enum.map((last_y + 1)..(last_y + dist), &amp;{&amp;1, last_x}), {last_y + dist, last_x}}
          "U" -> {Enum.map((last_y - 1)..(last_y - dist), &amp;{&amp;1, last_x}), {last_y - dist, last_x}}
        end

      {coords ++ coordinates_traversed, new_coord}
    end)
    |> elem(0)
    |> Enum.uniq()
  end

  defp coordinates_to_graph(coordinates) do
    {{_, min_x}, {_, max_x}} = Enum.min_max_by(coordinates, fn {_y, x} -> x end)
    {{min_y, _}, {max_y, _}} = Enum.min_max_by(coordinates, fn {y, _x} -> y end)

    Enum.map(min_y..max_y, fn y ->
      Enum.map(min_x..max_x, fn x ->
        if {y, x} in coordinates do
          "#"
        else
          "."
        end
      end)
    end)
  end
end

Tests - Part 1

ExUnit.start(autorun: false)

defmodule PartOneTest do
  use ExUnit.Case, async: true
  import PartOne

  @raw_input """
  R 6 (#70c710)
  D 5 (#0dc571)
  L 2 (#5713f0)
  D 2 (#d2c081)
  R 2 (#59c680)
  D 2 (#411b91)
  L 5 (#8ceee2)
  U 2 (#caa173)
  L 1 (#1b58a2)
  U 2 (#caa171)
  R 2 (#7807d2)
  U 3 (#a77fa3)
  L 2 (#015232)
  U 2 (#7a21e3)
  """

  @input Parser.parse(@raw_input)

  describe "run/1" do
    test "main example" do
      assert run(@raw_input) == 62
    end
  end

  describe "map_out_digging/1" do
    test "main example" do
      assert map_out_digging_perimeter(@input) == [
               ["#", "#", "#", "#", "#", "#", "#"],
               ["#", ".", ".", ".", ".", ".", "#"],
               ["#", "#", "#", ".", ".", ".", "#"],
               [".", ".", "#", ".", ".", ".", "#"],
               [".", ".", "#", ".", ".", ".", "#"],
               ["#", "#", "#", ".", "#", "#", "#"],
               ["#", ".", ".", ".", "#", ".", "."],
               ["#", "#", ".", ".", "#", "#", "#"],
               [".", "#", ".", ".", ".", ".", "#"],
               [".", "#", "#", "#", "#", "#", "#"]
             ]
    end
  end

  describe "digging_coordinates/1" do
    test "main example" do
      assert digging_coordinates(@input) == [
               {0, 0},
               {0, 1},
               {0, 2},
               {0, 3},
               {0, 4},
               {0, 5},
               {0, 6},
               {1, 6},
               {2, 6},
               {3, 6},
               {4, 6},
               {5, 6},
               {5, 5},
               {5, 4},
               {6, 4},
               {7, 4},
               {7, 5},
               {7, 6},
               {8, 6},
               {9, 6},
               {9, 5},
               {9, 4},
               {9, 3},
               {9, 2},
               {9, 1},
               {8, 1},
               {7, 1},
               {7, 0},
               {6, 0},
               {5, 0},
               {5, 1},
               {5, 2},
               {4, 2},
               {3, 2},
               {2, 2},
               {2, 1},
               {2, 0},
               # {0, 0} at the end is non-uniq, so ignored
               {1, 0}
             ]
    end

    test "simple example" do
      input = """
      R 2 (#70c710)
      D 1 (#0dc571)
      L 2 (#0dc571)
      """

      assert digging_coordinates(Parser.parse(input)) == [
               {0, 0},
               {0, 1},
               {0, 2},
               {1, 2},
               {1, 1},
               {1, 0}
             ]
    end
  end

  describe "fill_in_area/1" do
    test "main example" do
      input = [
        ["#", "#", "#", "#", "#", "#", "#"],
        ["#", ".", ".", ".", ".", ".", "#"],
        ["#", "#", "#", ".", ".", ".", "#"],
        [".", ".", "#", ".", ".", ".", "#"],
        [".", ".", "#", ".", ".", ".", "#"],
        ["#", "#", "#", ".", "#", "#", "#"],
        ["#", ".", ".", ".", "#", ".", "."],
        ["#", "#", ".", ".", "#", "#", "#"],
        [".", "#", ".", ".", ".", ".", "#"],
        [".", "#", "#", "#", "#", "#", "#"]
      ]

      assert fill_in_area(input) == [
               ["#", "#", "#", "#", "#", "#", "#"],
               ["#", "#", "#", "#", "#", "#", "#"],
               ["#", "#", "#", "#", "#", "#", "#"],
               [".", ".", "#", "#", "#", "#", "#"],
               [".", ".", "#", "#", "#", "#", "#"],
               ["#", "#", "#", "#", "#", "#", "#"],
               ["#", "#", "#", "#", "#", ".", "."],
               ["#", "#", "#", "#", "#", "#", "#"],
               [".", "#", "#", "#", "#", "#", "#"],
               [".", "#", "#", "#", "#", "#", "#"]
             ]
    end

    test "example with up, right, down" do
      input = [
        ["#", "#", "#", ".", ".", "."],
        ["#", ".", "#", ".", ".", "."],
        ["#", ".", "#", "#", "#", "."],
        ["#", ".", ".", ".", "#", "."],
        ["#", "#", "#", "#", "#", "."],
        [".", ".", ".", ".", ".", "."]
      ]

      assert fill_in_area(input) == [
               ["#", "#", "#", ".", ".", "."],
               ["#", "#", "#", ".", ".", "."],
               ["#", "#", "#", "#", "#", "."],
               ["#", "#", "#", "#", "#", "."],
               ["#", "#", "#", "#", "#", "."],
               [".", ".", ".", ".", ".", "."]
             ]
    end

    test "example with up, right JUST A BIT, down" do
      input = [
        ["#", "#", ".", ".", "."],
        ["#", "#", ".", ".", "."],
        ["#", "#", "#", "#", "."],
        ["#", ".", ".", "#", "."],
        ["#", "#", "#", "#", "."],
        [".", ".", ".", ".", "."]
      ]

      assert fill_in_area(input) == [
               ["#", "#", ".", ".", "."],
               ["#", "#", ".", ".", "."],
               ["#", "#", "#", "#", "."],
               ["#", "#", "#", "#", "."],
               ["#", "#", "#", "#", "."],
               [".", ".", ".", ".", "."]
             ]
    end
  end
end

ExUnit.run()

Solution - Part 1

PartOne.solve(puzzle_input)

# input = Parser.parse(puzzle_input)

# map = PartOne.map_out_digging_perimeter(input)
# map |> Enum.map(fn row -> IO.puts(Enum.join(row)) end)

# filled_in_map = map |> PartOne.fill_in_area()
# filled_in_map |> Enum.map(fn row -> IO.puts(Enum.join(row)) end)
# filled_in_map |> sum_of_trenches()
# 71485 <- too high, 6.1s
# 61865 <- 6.9s

Part Two

Code - Part 2

defmodule PartTwo do
  def solve(input) do
    IO.puts("--- Part Two ---")
    IO.puts("Result: #{run(input)}")
  end

  def run(input_string, parse_pt1: true) when is_bitstring(input_string),
    do: run(Parser.parse(input_string))

  def run(input_string) when is_bitstring(input_string),
    do: run(Parser.parse_pt2(input_string))

  def run(input) do
    # A = i + (b/2) - 1
    # -> The area A of a polygon
    #    is equal to the inner points i, + half the number of outer points b, minus 1
    #        -> We are looking discrete boxes within the border, i, and on the border, b
    a = shoelace_area(corners(input))
    b = perimeter(input)
    i = a - div(b, 2) + 1

    i + b
  end

  defp shoelace_area(corners) do
    corners
    |> Enum.chunk_every(2, 1, [hd(corners)])
    |> Enum.map(fn [%{x: x1, y: y1, direction_to: _}, %{x: x2, y: y2, direction_to: _}] ->
      (y1 + y2) * (x1 - x2)
    end)
    |> Enum.sum()
    |> div(2)
  end

  defp perimeter(input) do
    Enum.reduce(input, 0, fn %{direction: _direction, distance: distance}, sum ->
      sum + distance
    end)
  end

  def corners(input) do
    initial_coord = %{y: 0, x: 0}

    Enum.reduce(input, [initial_coord], fn %{direction: direction, distance: distance}, res ->
      new_coord =
        case direction do
          "R" ->
            %{
              y: Map.get(hd(res), :y),
              x: Map.get(hd(res), :x) + distance,
              direction_to: direction
            }

          "L" ->
            %{
              y: Map.get(hd(res), :y),
              x: Map.get(hd(res), :x) - distance,
              direction_to: direction
            }

          "D" ->
            %{
              y: Map.get(hd(res), :y) + distance,
              x: Map.get(hd(res), :x),
              direction_to: direction
            }

          "U" ->
            %{
              y: Map.get(hd(res), :y) - distance,
              x: Map.get(hd(res), :x),
              direction_to: direction
            }
        end

      [new_coord | res]
    end)
    |> Enum.reverse()
    |> tl()
  end
end

Tests - Part 2

ExUnit.start(autorun: false)

defmodule PartTwoTest do
  use ExUnit.Case, async: true
  import PartTwo

  @raw_input """
  R 6 (#70c710)
  D 5 (#0dc571)
  L 2 (#5713f0)
  D 2 (#d2c081)
  R 2 (#59c680)
  D 2 (#411b91)
  L 5 (#8ceee2)
  U 2 (#caa173)
  L 1 (#1b58a2)
  U 2 (#caa171)
  R 2 (#7807d2)
  U 3 (#a77fa3)
  L 2 (#015232)
  U 2 (#7a21e3)
  """

  describe "run/1" do
    test "main example" do
      assert run(@raw_input) == 952_408_144_115
    end
  end

  describe "run/2 with part one parser" do
    test "main example" do
      assert run(@raw_input, parse_pt1: true) == 62
    end
  end

  describe "corners/1" do
    test "main example" do
      input = [
        %{direction: "R", distance: 461_937},
        %{direction: "D", distance: 56407},
        #
        %{direction: "R", distance: 356_671},
        #
        %{direction: "D", distance: 863_240},
        #
        %{direction: "R", distance: 367_720},
        #
        %{direction: "D", distance: 266_681},
        #
        %{direction: "L", distance: 577_262},
        #
        %{direction: "U", distance: 829_975},
        #
        %{direction: "L", distance: 112_010},
        %{direction: "D", distance: 829_975},
        %{direction: "L", distance: 491_645},
        %{direction: "U", distance: 686_074},
        %{direction: "L", distance: 5411},
        %{direction: "U", distance: 500_254}
      ]

      assert corners(input) == [
               %{y: 0, x: 461_937, direction_to: "R"},
               %{y: 56_407, x: 461_937, direction_to: "D"},
               %{y: 56_407, x: 818_608, direction_to: "R"},
               %{y: 919_647, x: 818_608, direction_to: "D"},
               %{y: 919_647, x: 1_186_328, direction_to: "R"},
               %{y: 1_186_328, x: 1_186_328, direction_to: "D"},
               %{y: 1_186_328, x: 609_066, direction_to: "L"},
               %{y: 356_353, x: 609_066, direction_to: "U"},
               %{y: 356_353, x: 497_056, direction_to: "L"},
               %{y: 1_186_328, x: 497_056, direction_to: "D"},
               %{y: 1_186_328, x: 5_411, direction_to: "L"},
               %{y: 500_254, x: 5_411, direction_to: "U"},
               %{y: 500_254, x: 0, direction_to: "L"},
               %{y: 0, x: 0, direction_to: "U"}
             ]
    end
  end
end

ExUnit.run()

Solution - Part 2

PartTwo.solve(puzzle_input)