Advent of Code 2023

Mix.install([
  {:req, "~> 0.3.2"}
])

Day 12

input =
  "https://adventofcode.com/2023/day/12/input"
  |> Req.get!(headers: [cookie: "session=#{System.get_env("AOC_COOKIE")}"])
  |> Map.get(:body)

sample = """
???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1
"""

Solution

defmodule Day12 do
  def part1(input) do
    setup_memo()

    input
    |> parse()
    |> Enum.map(&solve/1)
    |> Enum.sum()
    |> memo_stats()
  end

  def part2(input) do
    setup_memo()

    input
    |> parse()
    |> unfold(5)
    |> Enum.map(&solve/1)
    |> Enum.sum()
    |> memo_stats()
  end

  defp parse(input) do
    input
    |> String.split("\n", trim: true)
    |> Enum.map(&String.split(&1, " "))
    |> Enum.map(fn [springs, groups] ->
      {springs, groups |> String.split(",") |> Enum.map(&String.to_integer/1)}
    end)
  end

  defp unfold(rows, n) do
    rows
    |> Enum.map(fn {springs, groups} ->
      springs =
        springs
        |> List.duplicate(n)
        |> Enum.intersperse("?")
        |> Enum.join()

      groups =
        groups
        |> List.duplicate(n)
        |> List.flatten()

      {springs, groups}
    end)
  end

  defp setup_memo() do
    if :ets.whereis(:memo) != :undefined do
      :ets.delete(:memo)
    end

    if :ets.whereis(:memo_stats) != :undefined do
      :ets.delete(:memo_stats)
    end

    :ets.new(:memo, [:set, :protected, :named_table])
    :ets.new(:memo_stats, [:set, :protected, :named_table])
    :ets.insert(:memo_stats, {:add_memo, 0})
    :ets.insert(:memo_stats, {:get_memo, 0})
    :ets.insert(:memo_stats, {:miss, 0})
  end

  defp memoize(key, value) do
    :ets.insert(:memo, {key, value})
    :ets.update_counter(:memo_stats, :add_memo, 1)
  end

  defp has_memo?(key) do
    :ets.member(:memo, key)
    |> tap(fn hit? ->
      if ! hit? do
        :ets.update_counter(:memo_stats, :miss, 1)
      end
    end)
  end

  defp get_memo(key) do
    [{_, value}] = :ets.lookup(:memo, key)
    :ets.update_counter(:memo_stats, :get_memo, 1)
    value
  end

  defp memo_stats(output) do
    :ets.lookup(:memo_stats, :add_memo) |> hd() |> elem(1) |> IO.inspect(label: "cache entries")
    hits = :ets.lookup(:memo_stats, :get_memo) |> hd() |> elem(1) |> IO.inspect(label: "cache hits")
    misses = :ets.lookup(:memo_stats, :miss) |> hd() |> elem(1) |> IO.inspect(label: "cache misses")
    (hits / misses) |> Float.round(3) |> IO.inspect(label: "hit rate")
    output
  end

  def solve({springs, groups}) do
    solve(springs, groups)
  end

  def solve(springs, [] = _groups) do
    # if there are no groups left and no more broken springs we're good
    if String.contains?(springs, "#"), do: 0, else: 1
  end

  def solve(springs, groups) do
    cond do
      String.length(springs) < Enum.sum(groups) + length(groups) - 1 ->
        # not enough springs to match groups
        0

      has_memo?({springs, groups}) ->
        get_memo({springs, groups})

      String.first(springs) == "." ->
        # consume operational springs
        # we want to find the next # or ? to denote a group
        solve(String.trim_leading(springs, "."), groups)

      true ->
        total = 0

        n = hd(groups)
        re = ~r/^[#?]{#{n}}($|[.?])/

        total =
          if String.match?(springs, re) do
            # we matched a group, continue matching groups
            total + solve(String.replace(springs, re, ""), tl(groups))
          else
            total
          end

        total =
          if String.first(springs) != "#" do
            # consume non broken spring and try to find more matches
            total + solve(String.split_at(springs, 1) |> elem(1), groups)
          else
            total
          end

        memoize({springs, groups}, total)

        total
    end
  end
end

Day12.part1(sample)

Day12.part1(input)

Day12.part2(sample)

Day12.part2(input)