Day 12: Passage Pathing

Intro

https://adventofcode.com/2021/day/12

Input

defmodule Input do
  def prepare(s) do
    s
    |> String.split("\n", trim: true)
    |> Enum.map(fn s -> String.split(s, "-") end)
    |> Enum.reduce(Map.new(), fn [a, b], map ->
      map =
        if Map.has_key?(map, a) do
          %{map | a => Map.fetch!(map, a) ++ [b]}
        else
          Map.put(map, a, [b])
        end

      if Map.has_key?(map, b) do
        %{map | b => Map.fetch!(map, b) ++ [a]}
      else
        Map.put(map, b, [a])
      end
    end)
  end
end

{:module, Input, <<70, 79, 82, 49, 0, 0, 9, ...>>, {:prepare, 1}}

input_test1 =
  """
  start-A
  start-b
  A-c
  A-b
  b-d
  A-end
  b-end
  """
  |> Input.prepare()

%{
  "A" => ["start", "c", "b", "end"],
  "b" => ["start", "A", "d", "end"],
  "c" => ["A"],
  "d" => ["b"],
  "end" => ["A", "b"],
  "start" => ["A", "b"]
}

input_test2 =
  """
  dc-end
  HN-start
  start-kj
  dc-start
  dc-HN
  LN-dc
  HN-end
  kj-sa
  kj-HN
  kj-dc
  """
  |> Input.prepare()

%{
  "HN" => ["start", "dc", "end", "kj"],
  "LN" => ["dc"],
  "dc" => ["end", "start", "HN", "LN", "kj"],
  "end" => ["dc", "HN"],
  "kj" => ["start", "sa", "HN", "dc"],
  "sa" => ["kj"],
  "start" => ["HN", "kj", "dc"]
}

input_test3 =
  """
  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
  """
  |> Input.prepare()

%{
  "DX" => ["he", "start", "pj", "fs"],
  "RW" => ["he", "pj", "zg", "start"],
  "WI" => ["he"],
  "end" => ["fs", "zg"],
  "fs" => ["end", "he", "DX", "pj"],
  "he" => ["DX", "fs", "pj", "RW", "WI", "zg"],
  "pj" => ["DX", "zg", "he", "RW", "start", "fs"],
  "sl" => ["zg"],
  "start" => ["DX", "pj", "RW"],
  "zg" => ["end", "sl", "pj", "RW", "he"]
}

input =
  """
  ey-dv
  AL-ms
  ey-lx
  zw-YT
  hm-zw
  start-YT
  start-ms
  dv-YT
  hm-ms
  end-ey
  AL-ey
  end-hm
  rh-hm
  dv-ms
  AL-dv
  ey-SP
  hm-lx
  dv-start
  end-lx
  zw-AL
  hm-AL
  lx-zw
  ey-zw
  zw-dv
  YT-ms
  """
  |> Input.prepare()

%{
  "AL" => ["ms", "ey", "dv", "zw", "hm"],
  "SP" => ["ey"],
  "YT" => ["zw", "start", "dv", "ms"],
  "dv" => ["ey", "YT", "ms", "AL", "start", "zw"],
  "end" => ["ey", "hm", "lx"],
  "ey" => ["dv", "lx", "end", "AL", "SP", "zw"],
  "hm" => ["zw", "ms", "end", "rh", "lx", "AL"],
  "lx" => ["ey", "hm", "end", "zw"],
  "ms" => ["AL", "start", "hm", "dv", "YT"],
  "rh" => ["hm"],
  "start" => ["YT", "ms", "dv"],
  "zw" => ["YT", "hm", "AL", "lx", "ey", "dv"]
}

Part 1

defmodule S1 do
  def find("end", _conns, visited) do
    {:complete, visited ++ ["end"]}
  end

  def find(elem, conns, visited) do
    to_visit =
      Map.fetch!(conns, elem)
      |> Enum.filter(fn e -> e not in visited or String.upcase(e) == e end)

    if length(to_visit) == 0 do
      nil
    else
      to_visit
      |> Enum.map(fn e -> find(e, conns, visited ++ [elem]) end)
      |> Enum.filter(fn path -> path != nil end)
    end
  end
end

{:module, S1, <<70, 79, 82, 49, 0, 0, 9, ...>>, {:find, 3}}

i = input_test1
r = S1.find("start", i, [])
s = List.flatten(r)
length(s) == 10

true

i = input_test2
r = S1.find("start", i, [])
s = List.flatten(r)
length(s) == 19

true

i = input_test3
r = S1.find("start", i, [])
s = List.flatten(r)
length(s) == 226

true

i = input
r = S1.find("start", i, [])
s = List.flatten(r)
length(s)

3779

Correct: 3779

Part 2

defmodule S2 do
  def find("end", _conns, visited, _extra_visit_used) do
    {:complete, visited ++ ["end"]}
  end

  def find(elem, conns, visited, extra_visit_used) do
    to_visit =
      Map.fetch!(conns, elem)
      |> Enum.filter(fn e ->
        e not in visited or
          String.upcase(e) == e or
          (e in visited and extra_visit_used == false)
      end)
      |> Enum.filter(fn e -> e != "start" end)

    if length(to_visit) == 0 do
      nil
    else
      to_visit
      |> Enum.map(fn e ->
        if String.upcase(e) == e or e not in visited do
          find(e, conns, visited ++ [elem], extra_visit_used)
        else
          find(e, conns, visited ++ [elem], true)
        end
      end)
      |> Enum.filter(fn path -> path != nil end)
    end
  end
end

{:module, S2, <<70, 79, 82, 49, 0, 0, 12, ...>>, {:find, 4}}

i = input_test1
r = S2.find("start", i, [], false)
s = List.flatten(r)
length(s) == 36

true

i = input_test2
r = S2.find("start", i, [], false)
s = List.flatten(r)
length(s) == 103

true

i = input_test3
r = S2.find("start", i, [], false)
s = List.flatten(r)
length(s) == 3509

true

i = input
r = S2.find("start", i, [], false)
s = List.flatten(r)
length(s)

96988

Correct: 96988