summaryrefslogblamecommitdiffstats
path: root/src/day17.exs
blob: 9f9db294135127bdf43c5e4f15700a3549bc1d6d (plain) (tree)






























































































































                                                                                           
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}")