aoc2021_day12.livemd

AoC Day 12 - Passage Pathing

Setup

Mix.install([:kino])

input = Kino.Input.textarea("Please input data:")

format_cave = fn
  "start" ->
    :start

  "end" ->
    :end

  cave ->
    cond do
      cave =~ ~r/[A-Z]+/ -> {:large, cave}
      cave =~ ~r/[a-z]+/ -> {:small, cave}
    end
end

data =
  input
  |> Kino.Input.read()
  |> String.split("\n", trim: true)
  |> Enum.map(&String.split(&1, "-"))
  |> Enum.flat_map(fn [start_cave, end_cave] ->
    s = format_cave.(start_cave)
    e = format_cave.(end_cave)
    [{s, e}, {e, s}]
  end)

map =
  Enum.reduce(data, %{}, fn {s, e}, acc ->
    Map.update(acc, s, [e], fn paths -> [e | paths] end)
  end)

defmodule Pathfinder do
  defp search(steps, _edges, :end, _), do: [{Enum.reverse([:end | steps])}]

  defp search(steps, edges, current_cave, single_visit_twice) do
    possible_paths = edges[current_cave]
    next_steps = [current_cave | steps]

    Enum.flat_map(possible_paths, fn path ->
      cond do
        path == :start ->
          [nil]

        # we do not allow a small cave to be visited twice
        not single_visit_twice and match?({:small, _p}, path) and path in next_steps ->
          [nil]

        # we allow a small cave to be visited twice, but only
        # a specific one
        single_visit_twice and match?({:small, _p}, path) and path in next_steps and
            Enum.frequencies(next_steps)
            |> Enum.any?(fn {cave, visitcount} ->
              match?({:small, _}, cave) and visitcount >= 2
            end) ->
          [nil]

        true ->
          search(next_steps, edges, path, single_visit_twice)
      end
    end)
  end

  def search(edges, single_visit_twice \\ false) do
    search([], edges, :start, single_visit_twice)
    |> Enum.reject(&is_nil/1)
    |> Enum.uniq()
  end
end

Part 1

Pathfinder.search(map) |> Enum.count()

Part 2

Pathfinder.search(map, true) |> Enum.count()