Advent of Code 2023 - Day 23

Mix.install([{:libgraph, "~> 0.16.0"}])

defmodule Main do
  def run() do
    get_input()
    |> Enum.map(&String.to_charlist/1) |> mkgrid() |> prep()
    # |> solve1()
    |> solve2()
	end

  def get_input() do
    # "testinput23"
    "input23"
    |> File.read!() |> String.trim() |> String.split("\n")
  end

  def mkgrid(ls) do
    for {row, r} <- Enum.with_index(ls),
        {val, c} <- Enum.with_index(row),
        into: %{}, do: {{r,c}, val}
  end

  def addt({a,b},{c,d}), do: {a+c,b+d}
  def minust({a,b}), do: {-a,-b}

  # params: grid, todo:[{pt,dir}, ...], found_edges:[{from,dir,to,len},...]
  # retval: found_edges[]
  def graph_edges(_,[],es), do: es
  def graph_edges(g,[{pt,dir}|todo],es) do
    {{tr,tc},dist,ntodo} = follow_path(g,[{pt,dir}],pt,0)
    ebgs = es |> Enum.map(fn {p,d,_,_} -> {p,d} end)
    nftodo = ntodo |> Enum.filter(fn {p,d} -> {p,d} not in ebgs end)
              |> Enum.filter(fn {p,d} -> {p,d} not in todo end)
    graph_edges(g, todo ++ nftodo, [{pt,dir,{tr,tc},dist}|es])
  end

  @dirs [{-1,0},{1,0},{0,1},{0,-1}]
  @chdirs %{ {-1,0}=>?^, {1,0}=>?v, {0,1}=>?>, {0,-1}=>?< }
  def follow_path(g,[{pt,dir}],_,n) do
    npt = addt(pt,dir)
    if npt not in Map.keys(g) do {pt, n, []}
    else
      pndirs = @dirs # potential new dirs (filter out # and nil)
        |> List.delete(minust(dir))
        |> Enum.map(fn d -> {d,g[addt(npt,d)]} end)
        |> Enum.filter(fn {_,c} -> c != ?# and c != nil end)
      ndirs = pndirs
        |> Enum.filter(fn {d,c} -> c == ?. or c == @chdirs[d] end)
        |> Enum.map(fn {d,_} -> {npt,d} end)
      if length(pndirs) >= 2 do {npt,n+1,ndirs}
      else follow_path(g,ndirs,npt,n+1) end
    end
  end
  def follow_path(_,ndirs,ppt,n), do: {ppt,n,ndirs}

  def mkgraph(edges) do
    vertmap = edges |> Enum.reduce(%{}, fn {f,_,t,l},acc ->
      Map.merge(acc,%{f=>[{t,l}],t=>[]}, fn _k,l1,l2 -> l1++l2 end) end)
    {vertmap,edges}
  end

  def bellman_ford(vtxs,edges,st) do # use negative of weights to find max
    dists = Map.from_keys(vtxs,10000)
    dists = Map.put(dists,st,0)
    for _i <- 1..(length(vtxs)-1), reduce: dists do dts ->
      for {f,_,t,w} <- edges, reduce: dts do dtss ->
        if dtss[f] - w < dtss[t], do: Map.put(dtss,t,dtss[f] - w), else: dtss
      end
    end
  end

  def prep(grid) do
    st = {0,1}
    {rmax,_} = Enum.max_by(Map.keys(grid), &elem(&1,0))
    {_,cmax} = Enum.max_by(Map.keys(grid), &elem(&1,1))
    ed = {rmax,cmax-1}
    {vertexmap,edges} = graph_edges(grid,[{st,{1,0}}],[]) # 2.5 secs on input23
                        |> mkgraph()
    {vertexmap,edges,st,ed}
  end

  def solve1({vmap,edges,st,ed}) do
    dists = bellman_ford(Map.keys(vmap),edges,st)
    - dists[ed]
  end

  def path_length([a,b|rest],g,sum) do
    wt = g |> Graph.edge(a,b) |> Map.get(:weight,0)
    path_length([b|rest], g, sum+wt)
  end
  def path_length([_vtx],_g,sum), do: sum

  def solve2({_vmap,edges,st,ed}) do
    gr = for {f,_,t,w} <- edges, reduce: Graph.new(type: :directed) do
      g -> g |> Graph.add_edge(f,t,weight: w) |> Graph.add_edge(t,f,weight: w) end
    Graph.Pathfinding.all(gr,st,ed) # this does not work with undirected graphs!! # 25 secs
      |> Enum.map(&path_length(&1,gr,0))
      |> Enum.max()
  end

end

:timer.tc(&Main.run/0)
|> IO.inspect(charlists: :as_lists)

defmodule Part1 do
  @deltas [{1, 0}, {0, 1}, {-1, 0}, {0, -1}]

  def parse(input) do
    lines = String.split(input, "\n", trim: true)
    size = length(lines)

    map =
      for {line, y} <- Enum.with_index(lines),
          {char, x} <- String.to_charlist(line) |> Enum.with_index(),
          char != ?#,
          into: %{} do
        {{y, x}, char}
      end

    {map, size}
  end

  def find_nodes(map, size) do
    map
    |> Map.keys()
    |> Enum.filter(fn {y, x} ->
      y == 0 or y == size - 1 or
        @deltas
        |> Enum.map(fn {dy, dx} -> {y + dy, x + dx} end)
        |> Enum.count_until(fn {y, x} -> Map.has_key?(map, {y, x}) end, 3) == 3
    end)
  end

  def find_edges(map, nodes, directed \\ true), do: find_edges(map, nodes, directed, nodes, %{})
  def find_edges(_, _, _, [], acc), do: acc

  def find_edges(map, nodes, directed, [node | rest], acc) do
    acc =
      for delta <- @deltas,
          {start, finish} <- find_edge(map, nodes, directed, node, delta),
          reduce: acc do
        acc ->
          Map.update(acc, start, [finish], fn existing ->
            [finish | existing]
            |> Enum.uniq()
          end)
      end

    find_edges(map, nodes, directed, rest, acc)
  end

  def find_edge(map, nodes, directed, start, delta),
    do: find_edge(map, nodes, directed, start, 0, start, [delta])

  def find_edge(_, _, _, _, _, _, []), do: []

  def find_edge(map, nodes, directed, start, len, {y1, x1} = prev, [{dy1, dx1} | prev_deltas]) do
    next = {y1 + dy1, x1 + dx1}
    char = map[next]

    cond do
      char == nil ->
        find_edge(map, nodes, directed, start, len, prev, prev_deltas)

      directed and
          ((char == ?^ and dy1 == 1) or
             (char == ?< and dx1 == 1) or
             (char == ?v and dy1 == -1) or
             (char == ?> and dx1 == -1)) ->
        []

      Enum.member?(nodes, next) ->
        if directed,
          do: [{start, {next, len}}],
          else: [{start, {next, len}}, {next, {start, len}}]

      true ->
        next_deltas = Enum.reject(@deltas, fn {dy2, dx2} -> dy2 == -dy1 and dx2 == -dx1 end)
        find_edge(map, nodes, directed, start, len + 1, next, next_deltas)
    end
  end

  def find_paths(edges, size), do: find_paths(edges, size, [[{{0, 1}, 0}]], [])
  def find_paths(_, _, [], acc), do: acc

  def find_paths(edges, size, [[{{y, _} = prev, _} | _] = path | rest], acc) do
    if y == size - 1 do
      find_paths(edges, size, rest, [path | acc])
    else
      next =
        edges[prev]
        |> Enum.reject(fn {neighbor, _} ->
          Enum.any?(path, fn {visited, _} -> neighbor == visited end)
        end)
        |> Enum.map(&[&1 | path])

      find_paths(edges, size, next ++ rest, acc)
    end
  end

  def path_length(path) do
    path
    |> Enum.map(&elem(&1, 1))
    |> Enum.sum()
    |> Kernel.+(length(path) - 1)
  end

  def html(map, size, nodes \\ []) do
    text =
      for y <- 0..(size - 1) do
        for x <- 0..(size - 1) do
          case map[{y, x}] do
            nil ->
              ?#

            char ->
              if Enum.member?(nodes, {y, x}) do
                ~c"<b>O</b>"
              else
                char
              end
          end
        end
        |> List.flatten([?\n])
      end
      |> Enum.join()

    color = if length(nodes) > 0, do: "gray", else: "lightgray"

    Kino.HTML.new("""
    <style>
      html {
        font-size: 7px;
      }
      pre {
        color: #{color};
        background-color: black;
        padding: 5px;
        line-height: 1em;
        letter-spacing: 0.3em;
      }
      b {
        color: white;
      }
    </style>
    <pre><code>#{text}</code></pre>
    """)
  end
end

{map, size} = Part1.parse(input)
nodes = Part1.find_nodes(map, size)

Kino.render(Part1.html(map, size, nodes))

edges = Part1.find_edges(map, nodes)
paths = Part1.find_paths(edges, size)

paths
|> Enum.map(&Part1.path_length/1)
|> Enum.max()

edges = Part1.find_edges(map, nodes, false)
paths = Part1.find_paths(edges, size)

paths
|> Enum.map(&Part1.path_length/1)
|> Enum.max()