Advent of Code 2023 - Day 23

For part 2 I transformed the map into a graph because I wanted to see it and check if there was a bottleneck point or something.

But no, so I guess the code for P1 would have worked too, the only difference is that I run all possible states 1 step ahead to the next intersection (instead of running just one), and then I keep only the 3000 longest.

This is the optimized solution. In the initial attempt, I employed a regular DFS and made good progress in part 1. However, encountering issues in part 2 led me to refactor part 1, adopting a compressed graph approach (i.e., retaining only intersections in the graph). Despite having only one line of code differentiating part 2 from part 1, part 2 still took 30 seconds to run. :joy:

Part 1 execution time: 131755 microseconds
Function result: 2218
Part 2 execution time: 33962603 microseconds
Function result: 6674

According to Wikipedia, the longest path problem is NP-hard. Fortunately, the reduced graph (with all straight-line garden paths reduced into single vertices) is sufficiently small that it is practical to calculate the length of all possible graphs. After optimizing my solution it solves both parts in 16 seconds on my computer.

I assume that there is a divide-and-conquer approach for finding the longest path for this particular graph much faster, but I didn’t pursue it.

1 Like

Like others, parsed the given map into a graph, with vertices being the intersections (plus the start and the end), each path between two intersections being an edge whose weight is the length of the path. Then for part 1 I used Bellman-Ford with negative weights. For part 2 I got lazy to things myself, and employed libgraph’s Pathfinding.all function which calculates all simple paths from the start to the end, and then just found the longest.

Part 1 runs in 2.5 seconds (almost all of which is parsing the map - I suppose I do something silly there); part 2 almost 30 seconds.

code
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)

Similar to everyone else, I built a graph for the map by finding the junctions and the edges between them. I initially thought that I would need to handle both directed and undirected edges for part 1. However, I rendered the map and the junctions with Kino.HTML and saw that all of the edges were directed. Funny that my code would have needed almost no changes for part 2 if I had implemented that behavior in part 1!

Part 1
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()
Part 2
edges = Part1.find_edges(map, nodes, false)
paths = Part1.find_paths(edges, size)

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