1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
edgesText = File.stream!("inputs/day9.txt")
costs =
Enum.reduce(edgesText, %{}, fn line, acc ->
[_, a, b, distance] = Regex.run(~r/(\w+) to (\w+) = (\d+)/, line)
{distance, ""} = Integer.parse(distance)
{_, newAcc} =
Map.get_and_update(acc, a, fn
nil -> {nil, %{b => distance}}
aToBeDistances -> {aToBeDistances, Map.put(aToBeDistances, b, distance)}
end)
{_, newAcc} =
Map.get_and_update(newAcc, b, fn
nil -> {nil, %{a => distance}}
bToADistances -> {bToADistances, Map.put(bToADistances, a, distance)}
end)
newAcc
end)
defmodule MemoizedTravellingSanta do
use Agent
def start do
Agent.start_link(fn -> %{} end, name: __MODULE__)
end
def findShortestPath(costs) do
pathCosts =
Enum.map(costs, fn {start, _} ->
shortestStartingHere =
MemoizedTravellingSanta.findShortestPath(costs, MapSet.new([start]), start)
shortestStartingHere
end)
min =
Enum.map(pathCosts, fn {min, _} -> min end)
|> Enum.min()
max =
Enum.map(pathCosts, fn {_, max} -> max end)
|> Enum.max()
{min, max}
end
def findShortestPath(costs, visited, current) do
if map_size(costs) == MapSet.size(visited) do
{0, 0}
else
cached_value = Agent.get(__MODULE__, &Map.get(&1, {costs, visited, current}))
if cached_value do
cached_value
else
leavingCosts = Map.get(costs, current, %{})
pathCosts =
Enum.filter(leavingCosts, fn {next, _} -> !MapSet.member?(visited, next) end)
|> Enum.map(fn {next, cost} ->
{minSubcost, maxSubcost} =
MemoizedTravellingSanta.findShortestPath(
costs,
MapSet.put(visited, next),
next
)
{cost + minSubcost, cost + maxSubcost}
end)
min =
Enum.map(pathCosts, fn {min, _} -> min end)
|> Enum.min()
max =
Enum.map(pathCosts, fn {_, max} -> max end)
|> Enum.max()
result = {min, max}
Agent.update(__MODULE__, &Map.put(&1, {costs, visited, current}, result))
result
end
end
end
end
{:ok, _} = MemoizedTravellingSanta.start()
{min, max} = MemoizedTravellingSanta.findShortestPath(costs)
IO.puts("Shortest distance: #{min}")
IO.puts("Longest distance: #{max}")
|
