summaryrefslogtreecommitdiffstats
path: root/src/day17.exs
diff options
context:
space:
mode:
Diffstat (limited to 'src/day17.exs')
-rw-r--r--src/day17.exs127
1 files changed, 127 insertions, 0 deletions
diff --git a/src/day17.exs b/src/day17.exs
new file mode 100644
index 0000000..9f9db29
--- /dev/null
+++ b/src/day17.exs
@@ -0,0 +1,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}")