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
|
defmodule Day17 do
defmodule Computer do
@derive Inspect
@enforce_keys [:a, :b, :c, :out, :instructions, :pointer]
defstruct @enforce_keys
def from_data(data) do
[a, b, c | instructions] = Regex.scan(~r/\d+/, data)
|> Enum.map(&String.to_integer(hd(&1)))
%Computer{a: a, b: b, c: c, out: [], instructions: instructions, pointer: 0}
end
def run(comp) do
case instruction(comp) do
{:halt, comp} ->
comp
{:ok, comp} ->
run(comp)
end
end
defp instruction(comp) do
case comp.instructions |> Enum.drop(comp.pointer) do
[] ->
{:halt, comp}
[0, r | _] ->
cr = combo(comp, r)
{:ok, %Computer{comp | a: Bitwise.bsr(comp.a, cr), pointer: comp.pointer+2}}
[1, r | _] ->
{:ok, %Computer{comp | b: Bitwise.bxor(comp.b, r), pointer: comp.pointer+2}}
[2, r | _] ->
cr = combo(comp, r)
{:ok, %Computer{comp | b: rem(cr, 8), pointer: comp.pointer+2}}
[3, r | _] ->
if comp.a == 0 do
{:ok, %Computer{comp | pointer: comp.pointer+2}}
else
{:ok, %Computer{comp | pointer: r}}
end
[4, _ | _] ->
{:ok, %Computer{comp | b: Bitwise.bxor(comp.b, comp.c), pointer: comp.pointer+2}}
[5, r | _] ->
cr = combo(comp, r)
{:ok, %Computer{comp | out: [rem(cr, 8) | comp.out], pointer: comp.pointer+2}}
[6, r | _] ->
cr = combo(comp, r)
{:ok, %Computer{comp | b: Bitwise.bsr(comp.a, cr), pointer: comp.pointer+2}}
[7, r | _] ->
cr = combo(comp, r)
{:ok, %Computer{comp | c: Bitwise.bsr(comp.a, cr), pointer: comp.pointer+2}}
end
end
defp combo(comp, v) do
case v do
0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> comp.a
5 -> comp.b
6 -> comp.c
7 -> raise "Invalid combo operand (7)"
end
end
end
def part1(data) do
data
|> Computer.from_data()
|> Computer.run()
|> then(& &1.out)
|> Enum.reverse()
|> Enum.join(",")
end
def part2(data) do
data
|> Computer.from_data()
|> then(& &1.instructions)
|> Enum.reverse()
|> solve2(0)
end
defp solve2(rout, a) do
case rout do
[] ->
a
[h | t] ->
# I deduced the following by hand for my input, but maybe it could
# have been done programatically. An important takeway is that
# (for my input, and probably for all) `a` incerases by 3 bits for each
# iteration of the program. AS such, we can only need to check the
# possibilities over the last 3 bits (a..a+7) in each iteration ourselves
a = Bitwise.bsl(a, 3)
possible = a..a+7
|> Enum.filter(fn a ->
Bitwise.band(a, 7)
|> Bitwise.bxor(5)
|> Bitwise.bxor(6)
|> Bitwise.bxor(Bitwise.bsr(a, Bitwise.band(a, 7) |> Bitwise.bxor(5)))
|> Bitwise.band(7) == h
end)
case possible do
[] ->
:none
possible ->
possible
|> Enum.map(& solve2(t, &1))
|> Enum.find(& &1 != :none)
|| :none
end
end
end
end
data = IO.read(:stdio, :eof)
{time1, ans1} = :timer.tc(fn -> Day17.part1(data) end)
IO.puts("Time : #{time1 / 1000000}")
IO.puts("Answer: #{ans1}")
{time2, ans2} = :timer.tc(fn -> Day17.part2(data) end)
IO.puts("Time : #{time2 / 1000000}")
IO.puts("Answer: #{ans2}")
|
