Skip to content

Instantly share code, notes, and snippets.

@aquarhead
Last active December 21, 2022 11:46
Show Gist options
  • Save aquarhead/67911db6038bf6f448761e3b20c1571c to your computer and use it in GitHub Desktop.
Save aquarhead/67911db6038bf6f448761e3b20c1571c to your computer and use it in GitHub Desktop.
aoc2022day16
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment