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
|
defmodule Day18 do
defmodule Game do
@derive Inspect
@enforce_keys [:obj, :source, :target, :w, :h]
defstruct @enforce_keys
def from_data(data, source, target) do
obj = data
|> String.split("\n", trim: true)
|> Enum.map(&integer_list/1)
|> Enum.map(&List.to_tuple/1)
{w, h} = target
%Game{obj: obj, source: source, target: target, w: w, h: h}
end
defp integer_list(s), do: String.split(s, ",") |> Enum.map(&String.to_integer/1)
def shortest(game, count_obj \\ nil) do
obj =
if count_obj == nil do
game.obj
else
Enum.take(game.obj, count_obj)
end
%Game{game | obj: MapSet.new(obj)}
|> shortest(0, [game.source], MapSet.new([game.source]))
end
defp shortest(game, i, q, v) do
case q do
[] ->
:none
q ->
if Enum.member?(q, game.target) do
i
else
for n <- q, reduce: {[], v} do
{q, v} ->
neighbors(game, n)
|> Enum.reject(&MapSet.member?(v, &1))
|> Enum.reduce({q, v}, fn n, {q, v} -> {[n | q], MapSet.put(v, n)} end)
end
|> then(fn {q, v} -> shortest(game, i+1, q, v) end)
end
end
end
defp neighbors(game, {x, y}) do
[{x+1, y}, {x-1, y}, {x, y+1}, {x, y-1}]
|> Enum.filter(fn {x, y} -> x >= 0 and x <= game.w and y >= 0 and y <= game.h end)
|> Enum.reject(&MapSet.member?(game.obj, &1))
end
end
def part1(data) do
data
|> Game.from_data({0, 0}, {70, 70})
|> Game.shortest(1024)
end
def part2(data) do
game = data
|> Game.from_data({0, 0}, {70, 70})
part2(game, 1, Enum.count(game.obj))
end
defp part2(game, l, r) do
if l == r do
Enum.at(game.obj, l-1)
|> then(fn {x, y} -> "#{x},#{y}" end)
else
m = div(l + r, 2)
if Game.shortest(game, m) != :none do
part2(game, m+1, r)
else
part2(game, l, m)
end
end
end
end
data = IO.read(:stdio, :eof)
{time1, ans1} = :timer.tc(fn -> Day18.part1(data) end)
IO.puts("Time : #{time1 / 1000000}")
IO.puts("Answer: #{ans1}")
{time2, ans2} = :timer.tc(fn -> Day18.part2(data) end)
IO.puts("Time : #{time2 / 1000000}")
IO.puts("Answer: #{ans2}")
|
