Day 12

Setup

Mix.install([
  {:kino, "~> 0.4.1"}
])

Small example:

start-A
start-b
A-c
A-b
b-d
A-end
b-end

Medium example:

dc-end
HN-start
start-kj
dc-start
dc-HN
LN-dc
HN-end
kj-sa
kj-HN
kj-dc

Large example:

fs-end
he-DX
fs-he
start-DX
pj-DX
end-zg
zg-sl
zg-pj
pj-he
RW-he
fs-DX
pj-RW
zg-RW
start-pj
he-WI
zg-he
pj-fs
start-RW

Real input:

cz-end
cz-WR
TD-end
TD-cz
start-UM
end-pz
kb-UM
mj-UM
cz-kb
WR-start
WR-pz
kb-WR
TD-kb
mj-kb
TD-pz
UM-pz
kb-start
pz-mj
WX-cz
sp-WR
mj-WR

input = Kino.Input.textarea("Puzzle Input")

Process Input

path_map =
  input
  |> Kino.Input.read()
  |> String.split("\n", trim: true)
  |> Enum.map(
    &(&1
      |> String.split("-")
      |> List.to_tuple())
  )
  |> Enum.reduce(%{}, fn {a, b}, acc ->
    Map.update(acc, a, MapSet.new([b]), fn set -> MapSet.put(set, b) end)
    |> Map.update(b, MapSet.new([a]), fn set -> MapSet.put(set, a) end)
  end)

:ok

Part 1 Module first try

defmodule Day12 do
  def grow(mapping) do
    for(starter <- mapping["start"], do: [starter, "start"])
    |> grow(mapping)
  end

  defp grow(paths, mapping) do
    new_paths =
      paths
      |> Enum.flat_map(&amp;grow_path(&amp;1, mapping))

    invalid_paths =
      Enum.filter(new_paths, fn [h | t] ->
        String.match?(h, ~r/^[a-z]+$/) and h in t
      end)

    valid_paths = new_paths -- invalid_paths

    if valid_paths == paths, do: valid_paths, else: grow(valid_paths, mapping)
  end

  defp grow_path(["end" | _tail] = path, _mapping), do: [path]

  defp grow_path([current | _tail] = path, mapping) do
    for next <- mapping[current] do
      [next | path]
    end
  end
end

Part 1 exec

Day12.grow(path_map)
|> Enum.count()

Part 2 Module first try

defmodule Day12b do
  def grow(mapping) do
    for(starter <- mapping["start"], do: {[starter, "start"], :new})
    |> grow(mapping)
  end

  defp grow(paths, mapping) do
    new_paths =
      paths
      |> Enum.flat_map(&amp;grow_path(&amp;1, mapping))
      |> Enum.reject(fn {_path, status} -> status == :invalid end)

    if Enum.any?(new_paths, fn {_, status} -> status in [:new, :once] end) do
      grow(new_paths, mapping)
    else
      new_paths
    end
  end

  defp grow_path({path, :ended}, _mapping), do: [{path, :ended}]

  defp grow_path({[current | _tail] = path, status}, mapping) do
    for next <- mapping[current], next != "start" do
      small_cave_revisit = String.match?(next, ~r/^[a-z]+$/) and next in path

      cond do
        next == "end" ->
          {[next | path], :ended}

        small_cave_revisit and status == :new ->
          {[next | path], :once}

        small_cave_revisit and status == :once ->
          {[next | path], :invalid}

        true ->
          {[next | path], status}
      end
    end
  end
end

Part 2 exec

Day12b.grow(path_map)
|> Enum.count()

Jose Way

edges =
  input
  |> Kino.Input.read()
  |> String.split("\n", trim: true)
  |> Enum.reduce(%{}, fn line, acc ->
    [left, right] = String.split(line, "-")
    acc = Map.update(acc, left, [right], &[right | &1])

    # Map.update(acc, right, [left], &[left | &1])

    if left == "start" or right == "end" do
      acc
    else
      Map.update(acc, right, [left], &[left | &1])
    end
  end)

# :ok

one = %{
  "TD" => ["pz", "kb", "cz", "end"],
  "UM" => ["pz", "mj", "kb", "start"],
  "WR" => ["mj", "sp", "kb", "pz", "start", "cz"],
  "WX" => ["cz"],
  "cz" => ["WX", "kb", "TD", "WR", "end"],
  "end" => ["pz", "TD", "cz"],
  "kb" => ["start", "mj", "TD", "WR", "cz", "UM"],
  "mj" => ["WR", "pz", "kb", "UM"],
  "pz" => ["mj", "UM", "TD", "WR", "end"],
  "sp" => ["WR"],
  "start" => ["kb", "WR", "UM"]
}

two = %{
  "TD" => ["pz", "kb", "cz", "end"],
  "UM" => ["pz", "mj", "kb"],
  "WR" => ["mj", "sp", "kb", "pz", "start", "cz"],
  "WX" => ["cz"],
  "cz" => ["WX", "kb", "TD", "WR", "end"],
  "end" => ["pz"],
  "kb" => ["start", "mj", "TD", "WR", "cz", "UM"],
  "mj" => ["WR", "pz", "kb", "UM"],
  "pz" => ["mj", "UM", "TD", "WR", "end"],
  "sp" => ["WR"],
  "start" => ["kb", "WR", "UM"]
}

nil

defmodule Once do
  def recur(edges) do
    recur(edges["start"], edges, MapSet.new(), ["start"], 0)
  end

  defp recur(["end" | caves], edges, seen, path, count) do
    recur(caves, edges, seen, path, count + 1)
  end

  defp recur([cave | caves], edges, seen, path, count) do
    count =
      cond do
        cave == "start" or cave in seen ->
          count

        lowercased?(cave) ->
          recur(edges[cave], edges, MapSet.put(seen, cave), [cave | path], count)

        true ->
          recur(edges[cave], edges, seen, [cave | path], count)
      end

    recur(caves, edges, seen, path, count)
  end

  defp recur([], _edges, _seen, _path, count) do
    count
  end

  defp lowercased?(cave), do: String.downcase(cave, :ascii) == cave
end

Once.recur(edges)

defmodule Twice do
  def recur(edges) do
    recur(edges["start"], edges, MapSet.new(), false, ["start"], 0)
  end

  defp recur(["end" | caves], edges, seen, once?, path, count) do
    recur(caves, edges, seen, once?, path, count + 1)
  end

  defp recur([cave | caves], edges, seen, once?, path, count) do
    count =
      cond do
        cave == "start" or (cave in seen and once?) ->
          count

        cave in seen ->
          recur(edges[cave], edges, MapSet.put(seen, cave), true, [cave | path], count)

        lowercased?(cave) ->
          recur(edges[cave], edges, MapSet.put(seen, cave), once?, [cave | path], count)

        true ->
          recur(edges[cave], edges, seen, once?, [cave | path], count)
      end

    recur(caves, edges, seen, once?, path, count)
  end

  defp recur([], _edges, _seen, _path, _once?, count) do
    count
  end

  defp lowercased?(cave), do: String.downcase(cave, :ascii) == cave
end

Twice.recur(edges)