Advent of Code 2024 - Day 17

defmodule Aoc2024.Solutions.Y24.Day17 do
  alias AoC.Input

  import Bitwise

  def parse(input, _part) do
    [registers, program] = String.split(Input.read!(input), "\n\n")
    [a, b, c] = registers |> String.split("\n") |> Enum.flat_map(&extract_numbers/1)
    {extract_numbers(program), %{a: a, b: b, c: c}}
  end

  def part_one({program, registers}) do
    program |> execute(registers, 0, []) |> Enum.join(",")
  end

  def part_two({expected, registers}) do
    solve(expected, registers, expected)
  end

  defp execute(program, registers, counter, output) do
    {opcode, literal} = {Enum.at(program, counter), Enum.at(program, counter + 1)}

    if is_nil(opcode) or is_nil(literal) do
      Enum.reverse(output)
    else
      operation = Map.get(opcodes(), opcode)
      combo = Map.get(combo_operands(), literal)
      result = operation.(combo.(registers), registers, literal, counter, output)
      {output, registers, counter} = result
      execute(program, registers, counter, output)
    end
  end

  defp solve(program, registers, expected) do
    # Looking at the program it can be seen that each output value
    # depends on the lower 10 bits of the value of register A.

    # Generate all possible A register values hat produce the first digit
    initial =
      Enum.map(0..1023, fn e ->
        {e, execute(program, Map.put(registers, :a, e), 0, [])}
      end)

    # Keep discarding the digits that don't match.
    # For each of the surviving elements extend the A register and
    # generate the next digit
    Enum.reduce(expected, {initial, 10}, fn digit, {as, shift} ->
      Enum.flat_map(as, fn {a, d} ->
        if hd(d) == digit do
          Enum.flat_map(0..7, fn value ->
            a_acc = value <<< shift ||| a
            registers = Map.put(registers, :a, a_acc >>> (shift - 7))
            output = execute(program, registers, 0, [])
            [{a_acc, output}]
          end)
        else
          []
        end
      end)
      |> then(&{&1, shift + 3})
    end)
    |> elem(0)
    |> Enum.min()
    |> elem(0)
  end

  defp combo_operands do
    %{
      0 => fn _ -> 0 end,
      1 => fn _ -> 1 end,
      2 => fn _ -> 2 end,
      3 => fn _ -> 3 end,
      4 => fn map -> Map.get(map, :a) end,
      5 => fn map -> Map.get(map, :b) end,
      6 => fn map -> Map.get(map, :c) end,
      7 => fn _map -> nil end
    }
  end

  defp opcodes do
    %{
      0 => fn
        combo, registers, _literal, counter, output ->
          registers = Map.update!(registers, :a, fn a -> trunc(a / :math.pow(2, combo)) end)
          {output, registers, counter + 2}
      end,
      1 => fn
        _combo, registers, literal, counter, output ->
          registers = Map.update!(registers, :b, fn b -> bxor(b, literal) end)
          {output, registers, counter + 2}
      end,
      2 => fn
        combo, registers, _literal, counter, output ->
          registers = Map.update!(registers, :b, fn _b -> rem(combo, 8) end)
          {output, registers, counter + 2}
      end,
      3 => fn
        _combo, registers, literal, counter, output ->
          case Map.get(registers, :a) do
            0 -> {output, registers, counter + 2}
            _a -> {output, registers, literal}
          end
      end,
      4 => fn
        _combo, registers, _literal, counter, output ->
          b = Map.get(registers, :b)
          c = Map.get(registers, :c)
          registers = Map.update!(registers, :b, fn _b -> bxor(b, c) end)
          {output, registers, counter + 2}
      end,
      5 => fn
        combo, registers, _literal, counter, output ->
          {[rem(combo, 8) | output], registers, counter + 2}
      end,
      6 => fn
        combo, registers, _literal, counter, output ->
          a = Map.get(registers, :a)
          registers = Map.update!(registers, :b, fn _b -> div(a, round(:math.pow(2, combo))) end)
          {output, registers, counter + 2}
      end,
      7 => fn
        combo, registers, _literal, counter, output ->
          a = Map.get(registers, :a)
          registers = Map.update!(registers, :c, fn _c -> div(a, round(:math.pow(2, combo))) end)
          {output, registers, counter + 2}
      end
    }
  end

  defp extract_numbers(string, regex \\ ~r/\d+(\.\d+)?/) do
    Enum.flat_map(Regex.scan(regex, string), &Enum.map(&1, fn e -> String.to_integer(e) end))
  end
end

I put functions into maps. So I solved part 1 on my own because it was fun.
Used @bjorng shifting algorithm for part 2. I don’t think I would figure this one out on my own. I did try to get the solution for part 2 with naive method (incrementing by 1) but that failed spectacularly. I even tried leaving the laptop running over night but forgot to turn off automatic sleep. Perhaps better even, my poor computer shouldn’t go through such treatment.

Part 2 was fun!

I rewrote the “program” as a pure Elixir function, then started cracking the register A from there.

This is my code (with some explanation of the “program” according to my input).

A, B and C in the markdown are the whole number in registers A, B, and C.
a, b and c are the lowest 3 bits of A, B and C.

https://github.com/Aetherus/advent-of-code/blob/2f04a699725e42fa9df6a874de9bc5ca441bb49d/2024/day-17.livemd

This took me quite a long time..! But probably my favorite puzzle this year so far: advent-of-code-2024/lib/advent_of_code2024/day17.ex at main · ibarakaiev/advent-of-code-2024 · GitHub

Part 1: 7,3,5,7,5,7,4,3,0 in 0.012ms
Part 2: 105734774294938 in 56.83ms

https://github.com/rvnash/aoc2024/blob/main/lib/d17.ex

The way I solved part 2 is also by noticing that A is right-shifted 3-bits on each iteration. So, starting at the end of the list I find all initial values of A in 0..7 that produces the last byte of the program. Then moving up the list to the last 2 bytes, left-shift all the existing values of A 3-bits, and add in 0..7, and record the list of A’s which produce the last two bytes. …and so on up to include the whole program. Then take the min of that list. It executes quite fast.

Fun fact: for my puzzle there were 84 possible solutions.

Here are the main parts of my solution :

defmodule Y2024.D17 do
  use Day, input: "2024/17", part1: ~c"c", part2: ~c"c"

  @bits 3
  @mod 2 ** @bits

  # Because of the static A = A / 2^3 (truncated)
  @iteration_factor 2 ** 3

  defp part1(input) do
    {registers, program} = parse_input(input)

    %{
      rest: program,
      whole: program,
      registers: registers,
      output: []
    }
    |> run()
    |> Map.get(:output)
    |> Enum.join(",")
  end

  defp part2(input) do
    {registers, program} = parse_input(input)

    program
    |> Enum.count()
    |> backtrack(registers, program)
    |> Enum.min()
  end

  defp untrunc(n, factor), do: Range.new(n * factor, (n + 1) * factor - 1)

  defp backtrack(0, _, _), do: [0]

  defp backtrack(size, registers, program) do
    size
    |> Kernel.-(1)
    |> backtrack(registers, program)
    |> Enum.flat_map(&untrunc(&1, @iteration_factor))
    |> Enum.uniq()
    |> Enum.filter(fn a ->
      %{output: output} =
        run(%{
          rest: program,
          whole: program,
          registers: %{registers | a: a},
          output: []
        })

      output == Enum.take(program, -size)
    end)
  end

  defp run(%{rest: []} = state), do: state
  defp run(%{rest: [_]} = state), do: state

  defp run(%{rest: [op, operand | rest]} = state) do
    state
    |> Map.replace!(:rest, rest)
    |> opcode(op, operand)
    |> run()
  end

  defp opcode(state, 0, operand), do: adv(state, operand)
  defp opcode(state, 1, operand), do: bxl(state, operand)
  defp opcode(state, 2, operand), do: bst(state, operand)
  defp opcode(state, 3, operand), do: jnz(state, operand)
  defp opcode(state, 4, operand), do: bxc(state, operand)
  defp opcode(state, 5, operand), do: out(state, operand)
  defp opcode(state, 6, operand), do: bdv(state, operand)
  defp opcode(state, 7, operand), do: cdv(state, operand)

  defp adv(state, operand) do
    Map.update!(
      state,
      :registers,
      fn %{a: a} = registers -> %{registers | a: trunc(a / 2 ** combo(operand, registers))} end
    )
  end

  defp bxl(state, operand) do
    Map.update!(
      state,
      :registers,
      fn %{b: b} = registers -> %{registers | b: Bitwise.bxor(b, literal(operand))} end
    )
  end

  defp bst(state, operand) do
    Map.update!(
      state,
      :registers,
      &Map.replace!(&1, :b, rem(combo(operand, &1), @mod))
    )
  end

  defp jnz(%{registers: %{a: 0}} = state, _), do: state

  defp jnz(%{whole: whole} = state, operand) do
    Map.replace!(
      state,
      :rest,
      Enum.drop(whole, literal(operand))
    )
  end

  defp bxc(state, _) do
    Map.update!(
      state,
      :registers,
      fn %{b: b, c: c} = registers -> %{registers | b: Bitwise.bxor(b, c)} end
    )
  end

  defp out(%{registers: registers} = state, operand) do
    Map.update!(
      state,
      :output,
      fn output -> output ++ [rem(combo(operand, registers), @mod)] end
    )
  end

  defp bdv(state, operand) do
    Map.update!(
      state,
      :registers,
      fn %{a: a} = registers -> %{registers | b: trunc(a / 2 ** combo(operand, registers))} end
    )
  end

  defp cdv(state, operand) do
    Map.update!(
      state,
      :registers,
      fn %{a: a} = registers -> %{registers | c: trunc(a / 2 ** combo(operand, registers))} end
    )
  end

  defp literal(n), do: n

  defp combo(4, %{a: a}), do: a
  defp combo(5, %{b: b}), do: b
  defp combo(6, %{c: c}), do: c
  defp combo(n, _), do: literal(n)

  # Some parsing stuff...
end

For part 2, once you understand that the final 3, 0 means that the program restarts from the beginning while A != 0 and that A is independant of B and C, it opens many doors.

The most important part is the untrunc/2 function which takes advantage of the static division of A by 2^3 at every loop (for my input).

I had to keep track of every possible predecessor (Enum.filter, not Enum.find) because some outputs are related to multiple inputs and some outputs cannot exist with inputs in the predecessor..(predecessor + 7) range if only the lowest predecessor is kept. For example 0 and 1 inputs both output a 5 but the 4 output needs at least an 11 (which gives it very specific conditions of appearance that could be precluded by keeping only the lower predecessor).

At the end, the backtrack function takes 4ms to find 3 possible starting A (with the lowest being the solution).

This was a good one. I’ve never played so much with bits.

I used Stream.resource produce output from the initial state.

I figured out that all operations could be done with Bitwise:

• division by power of two is bitshift right
• modulo 8 is bitwise AND with 7 (only keeping lowest 3 bits)

https://github.com/liamcmitchell/advent-of-code/blob/773628863a81553bea3e40ff536127bed8f5df5e/2024/17/1.exs#L17-L48

Part2: In the example and my input (prob for everyone else), on every iteration, A is divided by 8 (bitshift right 3 bits) and B and C are generated from A. Looking at the max values, each output is produced from XORing 3-10 of the least significant bits of A.

Many hours later I figured out to iterate over most significant bits first, looking for match with last output, then moving down and checking more affected outputs.

This was really hard to think about, not sure if writing this helps others

https://github.com/liamcmitchell/advent-of-code/blob/773628863a81553bea3e40ff536127bed8f5df5e/2024/17/1.exs#L63-L89

Less than 100 LOC in the end!

I tried a few ways to solve part 2 before I found an approach that would terminate.

My solution seems to be similar to @lud’s, in that I construct possible values for the A register and discard values that don’t work. It’s a little bit different in that I don’t reverse the list of program digits.

https://github.com/bjorng/advent-of-code/blob/main/2024/day17/lib/day17.ex

Part 1 was pretty straightforward, part 2 is one of those reverse engineering nightmare puzzles D: