Advent of Code - Day 11

Mix.install([
  {:kino_aoc, "~> 0.1"},
  # {:benchee, "~> 1.0", only: :dev}
  {:kino_benchee, github: "akoutmos/kino_benchee", branch: "initial_release_prep"}
])

Introduction

Puzzle

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

Parser

Code - Parser

defmodule Parser do
  def parse(input) do
    rows =
      input
      |> String.split("\n", trim: true)

    {rows
     |> Enum.with_index(1)
     |> Enum.map(fn {line, y} ->
       line
       |> String.split("", trim: true)
       |> Enum.with_index(1)
       |> Enum.reduce([], fn {v, x}, acc ->
         if v == "#", do: [{x, y} | acc], else: acc
       end)
     end)
     |> List.flatten(), Enum.count(rows)}
  end
end

Tests - Parser

ExUnit.start(autorun: false)

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

  @input """
  ...#......
  .......#..
  #.........
  ..........
  ......#...
  .#........
  .........#
  ..........
  .......#..
  #...#.....
  """
  @expected []

  test "parse test" do
    actual = parse(@input)
    assert actual == @expected
  end
end

ExUnit.run()

defmodule GalaxyOperations do
  def expand_empty_space({map, n}, expansion_factor) do
    keys = MapSet.new(map)

    empty_columns =
      Enum.map(1..n, fn x ->
        unless Enum.any?(1..n, fn y ->
                 MapSet.member?(keys, {x, y})
               end),
               do: x
      end)
      |> Enum.reject(&is_nil/1)

    empty_rows =
      Enum.map(1..n, fn y ->
        unless Enum.any?(1..n, fn x ->
                 MapSet.member?(keys, {x, y})
               end),
               do: y
      end)
      |> Enum.reject(&is_nil/1)

    map
    |> Enum.map(fn {x, y} ->
      offset_x = Enum.count(empty_columns, fn col -> x > col end)
      offset_y = Enum.count(empty_rows, fn row -> y > row end)
      {x + offset_x * expansion_factor, y + offset_y * expansion_factor}
    end)
  end

  def find_pairs(map) do
    Enum.reduce(map, MapSet.new(), fn startg, acc ->
      Enum.reduce(map, acc, fn endg, acc ->
        cond do
          startg == endg -> acc
          MapSet.member?(acc, {endg, startg}) -> acc
          true -> MapSet.put(acc, {startg, endg})
        end
      end)
    end)
  end

  def sum_lengths([], acc), do: acc

  def sum_lengths([{{x1, y1}, {x2, y2}} | rest], acc) do
    sum_lengths(rest, acc + abs(x1 - x2) + abs(y1 - y2))
  end
end

Part One

Code - Part 1

defmodule PartOne do
  import GalaxyOperations

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

  def run(input) do
    input
    |> Parser.parse()
    |> expand_empty_space(1)
    |> find_pairs()
    |> Enum.to_list()
    |> sum_lengths(0)
  end
end

Tests - Part 1

ExUnit.start(autorun: false)

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

  @input """
  ...#......
  .......#..
  #.........
  ..........
  ......#...
  .#........
  .........#
  ..........
  .......#..
  #...#.....
  """
  @expected 374

  test "part one" do
    actual = run(@input)
    assert actual == @expected
  end
end

ExUnit.run()

Solution - Part 1

PartOne.solve(puzzle_input)

Part Two

Code - Part 2

defmodule PartTwo do
  import GalaxyOperations

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

  def run(input, expansion_factor) do
    input
    |> Parser.parse()
    |> expand_empty_space(expansion_factor - 1)
    |> find_pairs()
    |> Enum.to_list()
    |> sum_lengths(0)
  end
end

Tests - Part 2

ExUnit.start(autorun: false)

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

  @input """
  ...#......
  .......#..
  #.........
  ..........
  ......#...
  .#........
  .........#
  ..........
  .......#..
  #...#.....
  """

  test "part two 10 expand" do
    assert run(@input, 10) == 1030
  end

  test "part two 100 expand" do
    assert run(@input, 100) == 8410
  end
end

ExUnit.run()

Solution - Part 2

PartTwo.solve(puzzle_input)

Benchmarking

defmodule Benchmarks do
  def part1(input) do
    PartOne.run(input)
  end

  def part2(input) do
    PartTwo.run(input, 1_000_000)
  end
end

Benchee.run(
  %{
    "day11.part1" => &Benchmarks.part1/1,
    "day11.part2" => &Benchmarks.part2/1
  },
  inputs: %{
    "puzzle" => puzzle_input
  },
  time: 1,
  memory_time: 1,
  reduction_time: 1
)