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

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.

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)

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

Less than 100 LOC in the end!

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