aoc2022day16

day16.exs

Mix.install([:libgraph])

{valves, graph} =
  File.read!("input2.txt")
  |> String.trim()
  |> String.split("\n")
  |> Enum.reduce({%{}, Graph.new(type: :undirected)}, fn line, {vs, g} ->
    [v, e] = line |> String.split(";")
    [v, f] = v |> String.split("=")
    f = String.to_integer(f)
    [v | _] = v |> String.split(" ") |> Enum.drop(1)

    neighbors =
      e
      |> String.split(", ")
      |> Enum.map(fn x ->
        x |> String.split(" ") |> List.last()
      end)

    g1 =
      neighbors
      |> Enum.reduce(g, fn n, gg ->
        Graph.add_edge(gg, v, n)
      end)

    vs1 =
      if f > 0 do
        Map.put(vs, v, f)
      else
        vs
      end

    {vs1, g1}
  end)

dist =
  valves
  |> Map.keys()
  |> Enum.reduce(%{}, fn dest, acc ->
    Map.put(acc, {"AA", dest}, length(Graph.get_shortest_path(graph, "AA", dest)) - 1)
  end)

vk = Map.keys(valves)

pairs = for v1 <- vk, v2 <- vk, do: {v1, v2}

dist =
  pairs
  |> Enum.filter(fn {v1, v2} -> v1 != v2 end)
  |> Enum.reduce(dist, fn {v1, v2}, acc ->
    Map.put(acc, {v1, v2}, length(Graph.get_shortest_path(graph, v1, v2)) - 1)
  end)

defmodule Search do
  import Bitwise

  def search(_dist, _valves, [], _cur, _min, total), do: total

  def search(dist, valves, vleft, cur, minleft, total) do
    vpossible =
      vleft
      |> Enum.map(fn dest ->
        nml = minleft - Map.fetch!(dist, {cur, dest}) - 1
        {dest, nml, Map.fetch!(valves, dest) * nml}
      end)
      |> Enum.filter(fn {_, nml, _} ->
        # whether possible to open the valve at `dest` (and can gain)
        nml > 0
      end)

    if length(vpossible) == 0 do
      total
    else
      vpossible
      |> Enum.map(fn {new_cur, new_minleft, gain} ->
        search(dist, valves, vleft -- [new_cur], new_cur, new_minleft, total + gain)
      end)
      |> Enum.max()
    end
  end

  def search1(dist, valves) do
    search(dist, valves, Map.keys(valves), "AA", 30, 0)
  end

  def search2(dist, valves) do
    vk = Map.keys(valves)

    1..Integer.pow(2, length(vk) - 1)
    |> Task.async_stream(fn dd ->
      %{true => worker1, false => worker2} =
        vk
        |> Enum.with_index()
        |> Enum.group_by(
          fn {_, idx} ->
            (dd >>> idx &&& 1) == 1
          end,
          fn {v, _} -> v end
        )

      search(dist, valves, worker1, "AA", 26, 0) + search(dist, valves, worker2, "AA", 26, 0)
    end)
    |> Enum.max_by(fn {:ok, v} -> v end)
  end
end

Search.search2(dist, valves)
|> IO.inspect()