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
|
defmodule Utils do
def comb(acc \\ [], l, 2) do
case l do
[h | t] ->
Enum.reduce(t, acc, fn x, acc -> [{h, x} | acc] end)
|> comb(t, 2)
_ ->
acc
end
end
end
defmodule Day08 do
defmodule Grid do
defstruct [:grid, :height, :width]
def from_data(data) do
grid = data
|> String.split("\n", trim: true)
|> Enum.map(& &1 |> String.codepoints() |> :array.from_list())
|> :array.from_list()
height = :array.size(grid)
width = :array.size(:array.get(0, grid))
%Grid{grid: grid, height: height, width: width}
end
def at(grid, i, j) do
:array.get(j, :array.get(i, grid.grid))
end
def in?(grid, i, j) do
i >= 0 and i < grid.height and j >= 0 and j < grid.width
end
def find_elements(grid, regex) do
for i <- 0..grid.height-1,
j <- 0..grid.width-1,
v = at(grid, i, j) do
if String.match?(v, regex) do
{v, i, j}
end
end
|> Enum.filter(& &1 != nil)
end
end
def part1(data) do
grid = data
|> Grid.from_data()
grid
|> Grid.find_elements(~r/[[:alnum:]]/)
|> Enum.group_by(fn {k, _, _} -> k end, fn {_, i, j} -> {i, j} end)
|> Enum.flat_map(fn {_, antennas} -> antinodes1(antennas, grid) end)
|> Enum.uniq()
|> Enum.count()
end
defp antinodes1(antennas, grid) do
antennas
|> Utils.comb(2)
|> Enum.flat_map(fn {{a, b}, {c, d}} -> [{a+a-c, b+b-d}, {c+c-a, d+d-b}] end)
|> Enum.filter(fn {a, b} -> Grid.in?(grid, a, b) end)
end
def part2(data) do
grid = data
|> Grid.from_data()
grid
|> Grid.find_elements(~r/[[:alnum:]]/)
|> Enum.group_by(fn {k, _, _} -> k end, fn {_, i, j} -> {i, j} end)
|> Enum.flat_map(fn {_, a} -> antinodes2(a, grid) end)
|> Enum.uniq()
|> Enum.count()
end
defp antinodes2(antennas, grid) do
antennas
|> Utils.comb(2)
|> Enum.flat_map(fn {a, b} -> antinodes2(a, b, grid) end)
end
defp antinodes2({ai, aj}, {bi, bj}, grid) do
di = abs(ai - bi)
dj = abs(aj - bj)
cond do
di == 0 ->
0..grid.width-1
dj == 0 ->
0..grid.height-1
true ->
g = Integer.gcd(di, dj)
di = div(di, g)
dj = div(dj, g)
antinodes2(ai, aj, -di, if aj < bj do -dj else dj end, grid)
|> antinodes2(ai, aj, di, if aj < bj do dj else -dj end, grid)
end
end
defp antinodes2(acc \\ [], i, j, di, dj, grid) do
if Grid.in?(grid, i, j) do
antinodes2([{i, j} | acc], i+di, j+dj, di, dj, grid)
else
acc
end
end
end
data = IO.read(:stdio, :eof)
{time1 , ans1} = :timer.tc(fn -> Day08.part1(data) end)
IO.puts("Time : #{time1 / 1000000}")
IO.puts("Answer: #{ans1}")
{time2 , ans2} = :timer.tc(fn -> Day08.part2(data) end)
IO.puts("Time : #{time2 / 1000000}")
IO.puts("Answer: #{ans2}")
|
