You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
82 lines
2.0 KiB
Elixir
82 lines
2.0 KiB
Elixir
defmodule Day23 do
|
|
def run do
|
|
connections =
|
|
File.read!("data.txt")
|
|
|> String.trim()
|
|
|> String.split("\n")
|
|
|> Enum.map(fn el -> String.split(el, "-") end)
|
|
|
|
all_computers = connections |> Enum.concat() |> Enum.uniq()
|
|
|
|
# build a map of computers -> all their connected computers
|
|
map =
|
|
Enum.reduce(all_computers, %{}, fn el1, map ->
|
|
friends =
|
|
Enum.filter(all_computers, fn el2 ->
|
|
Enum.member?(connections, [el1, el2]) || Enum.member?(connections, [el2, el1])
|
|
end)
|
|
|
|
Map.put(map, el1, friends)
|
|
end)
|
|
|
|
part1 =
|
|
expand(map, connections)
|
|
|> Enum.filter(fn set -> Enum.any?(set, fn el -> String.starts_with?(el, "t") end) end)
|
|
|> length
|
|
|
|
dbg(part1)
|
|
|
|
part2 =
|
|
loop_expand(map, connections)
|
|
|> hd()
|
|
|> Enum.join(",")
|
|
|
|
dbg(part2)
|
|
end
|
|
|
|
defp loop_expand(map, sets) do
|
|
case expand(map, sets) do
|
|
[] -> sets
|
|
x -> loop_expand(map, x)
|
|
end
|
|
end
|
|
|
|
defp expand(map, sets) do
|
|
# look at an element in every set (e.g. the first element)
|
|
# check all of its connections
|
|
# if any of those connected computers are connected to all of the set members, you've increased the set size by 1!
|
|
Enum.reduce(sets, [], fn set, acc ->
|
|
connections = Map.get(map, hd(set), [])
|
|
|
|
res =
|
|
Enum.reduce(connections, [], fn con, acc3 ->
|
|
# if it is connected to each member of the set, we've enlarged the set
|
|
if Enum.all?(set, fn set_el -> is_connected(map, set_el, con) end) do
|
|
[[con | set] | acc3]
|
|
else
|
|
acc3
|
|
end
|
|
end)
|
|
|
|
if Enum.empty?(res) do
|
|
acc
|
|
else
|
|
if is_list(Enum.at(res, 0)) do
|
|
Enum.concat(res, acc)
|
|
else
|
|
[res | acc]
|
|
end
|
|
end
|
|
end)
|
|
|> Enum.map(fn l -> Enum.sort(l) end)
|
|
|> Enum.uniq()
|
|
|> Enum.sort_by(fn a -> Enum.join(a) end)
|
|
end
|
|
|
|
defp is_connected(map, a, b) do
|
|
Map.get(map, a, []) |> Enum.member?(b)
|
|
end
|
|
end
|
|
|
|
Day23.run()
|