Gosh this one took me sooo much time.
At first I was trying to iterate each digit independently on the input A number to make digits change in the output. (iterating on a base-8 representation of the input). It looks likes it is kind of possible but I am not sure how.
So finally I just wen another way by trying more numbers. But it takes 3ms in the end so I guess it’s okay 
I wrote a big comment block if it can be useful to some !
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.
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:
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!
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).
Part 1: 7,3,5,7,5,7,4,3,0 in 0.012ms
Part 2: 105734774294938 in 56.83ms
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.
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 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.
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. 
© Copyright Elixir Forum | Terms | Privacy & Cookies
