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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
defmodule Day21 do
defmodule Keypad do
@derive Inspect
@enforce_keys [:type]
defstruct @enforce_keys
def new(type) do
%Keypad{type: type}
end
def shortest_paths(keypad, from, to) do
bfs([[{:nil, from}]], to, keypad)
end
defp bfs(paths, to, keypad) do
finished = Enum.any?(paths, &(elem(hd(&1), 1) == to))
if finished do
Enum.filter(paths, &(elem(hd(&1), 1) == to))
else
for path <- paths, neighbor <- neighbors(keypad, elem(hd(path), 1)) do
[neighbor | path]
end
|> bfs(to, keypad)
end
end
defp neighbors(keypad, from) do
case keypad.type do
:numeric -> neighbors_numeric(from)
:directional -> neighbors_directional(from)
end
end
defp neighbors_numeric(from) do
case from do
"A" -> %{left: "0", up: "3"}
"0" -> %{right: "A", up: "2"}
"1" -> %{right: "2", up: "4"}
"2" -> %{down: "0", left: "1", right: "3", up: "5"}
"3" -> %{down: "A", left: "2", up: "6"}
"4" -> %{down: "1", right: "5", up: "7"}
"5" -> %{down: "2", left: "4", right: "6", up: "8"}
"6" -> %{down: "3", left: "5", up: "9"}
"7" -> %{down: "4", right: "8"}
"8" -> %{down: "5", left: "7", right: "9"}
"9" -> %{down: "6", left: "8"}
end
end
defp neighbors_directional(from) do
case from do
:A -> %{left: :up, down: :right}
:up -> %{right: :A, down: :down}
:left -> %{right: :down}
:down -> %{left: :left, up: :up, right: :right}
:right -> %{left: :down, up: :A}
end
end
end
def part1(data, n \\ 2) do
data
|> String.split("\n", trim: true)
|> Enum.map(fn code ->
{
String.split(code, "A") |> hd() |> String.to_integer(),
shortest_dist(String.codepoints(code), "A", n, %{}) |> elem(0)
}
end)
# |> IO.inspect(charlists: :as_lists)
|> Enum.map(fn {a, b} -> a*b end)
|> Enum.sum()
end
defp shortest_dist(code, start, n, state) do
chunks = [start | code]
|> Enum.chunk_every(2, 1, :discard)
kpadtype = if start == "A" do :numeric else :directional end
{values, nstate} =
for [from, to] <- chunks, reduce: {[], state} do
{values, state} ->
shortest_dist(from, to, n, kpadtype, state)
|> then(fn {v, state} -> {[v | values], state} end)
end
{Enum.sum(values), nstate}
end
defp shortest_dist(from, to, n, keypadtype, state) do
key = {from, to, n, keypadtype}
case Map.get(state, key) do
:nil ->
{values, nstate} =
for path <- paths(from, to, keypadtype), reduce: {[], state} do
{values, state} -> shortest_dist(path, n, state)
|> then(fn {v, s} -> {[v | values], s} end)
end
value = Enum.min(values)
{value, Map.put(nstate, key, value)}
value ->
{value, state}
end
end
defp paths(from, to, keypad) do
case keypad do
:numeric ->
Keypad.new(:numeric)
:directional ->
Keypad.new(:directional)
end
|> Keypad.shortest_paths(from, to)
end
defp shortest_dist(path, n, state) do
if n == 0 do
{Enum.count(path), state}
else
path
|> Enum.map(&(elem(&1, 0)))
|> then(&([:A | &1]))
|> Enum.reverse()
|> tl()
|> shortest_dist(:A, n-1, state)
end
end
def part2(data) do
part1(data, 25)
end
end
data = IO.read(:stdio, :eof)
{time1, ans1} = :timer.tc(fn -> Day21.part1(data) end)
IO.puts("Time : #{time1 / 1000000}")
IO.puts("Answer: #{ans1}") # 184718
{time2, ans2} = :timer.tc(fn -> Day21.part2(data) end)
IO.puts("Time : #{time2 / 1000000}")
IO.puts("Answer: #{ans2}") # 228800606998554
|
