Clojurians Log v2

For some reason I get a wrong answer for Part 1. Is it a correct format to submit 4,4,4,3,0,6,6,2,1?

Yes

Guys, I'm really stuck. Maybe I made a stupid mistake and can't see it. I get right answers for the example and the tests, but not for my input. Can anyone look at it? https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_17.clj

I'm in worse shape. I have an answer that produces produces the right output for part2 but aoc is rejecting it...

Does aoc say it's too high?

yes. but it's not a multiple of the thing

so it's not the obvious mistake I thought

@zelark The only think I think I see, is that it looks like you are treating every operand as a combo-operand (you're setting operand to that on line 40). But instructions 1 (bxl) and 3 (jnz) operate on literal operands.

oh - I got it - wheee

@norman Are you sure there isn't a lower number that works?

OK, cool 🙂

yes. that was the thing

thanks - just asking the first question got me too it

I'm stuck on part 2 completely. I can't wrap my head around trying to reverse-engineer the "code".

Looking at the code gave me the general idea, but if you just iterate through the first 256 or so as you might get the idea

@rjray thanks, I use the case, so it should works fine

(case operand
    (0 1 2 3) operand
    4 (state :a)
    5 (state :b)
    6 (state :c)
    ...

@zelark But that isn't the same as a literal operand. A literal operand value of "7" is 7. A literal op value of 5 is 5 (not the content of b).

Stupid me, I got it. It seems I need more sleep

Got a star, @rjray thank you a lot!

https://gitlab.com/maximoburrito/advent2024/-/blob/main/src/day17/main.clj I really shouldn't have stayed up for part 2. I have to be up early....

Same. I haven't seen the pattern yet, as you hinted. Might sleep on it and resume in the morning.

think about when it goes from 1 digit output to 2 digit output and 2 digit output to three digit output

Yeah, I just noticed that.

Part 1 was so punishing because I am a clumsy typist

Made a copy paste error and a couple of other errors when programming commands

For part 2 I fully reverse engineered the calculation, but after I solved it, I see now that there is no need for that

Wow, seems I know how to solve part 2

https://gist.github.com/RokLenarcic/8cc1683fe5037e681d84535fe90ad2cf

Man, this was SUPER fun. Spoilers, because I included an explanation in my part2.

Just solved it! I did DFS for part 2 https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_17.clj

@malaingreclement very nice and short implementation of the computer

btw I see a lot of people use pow and Math/pow

it’s just bit-shift-left

Yeah I know, but I wanted to keep the wording of the code close to the puzzle description, to help navigating between the two.

Might rewrite it now that I'm done, so that it feels more assmebly-y.

@roklenarcic yeah bit-shift-left, and bit-and for mod

It's even a bit-shift-right, since we're dividing by powers of 2.

@roklenarcic edited, it is cleaner. I think it would actually have helped to implemented like this from the beginning ><

you are right

I’ve updated my gist to clean it up a bit, now it’s shorter

With only 8 instructions in the program, and 2 "free" registers, I wonder how the puzzle maker generates unique inputs for everyone playing. There's got to be a lot of collision.

Randomize all the instructions that mangle the number

keep just div by 8 intact

Well, you need the first instruction to be store A mod 8 in something, the penultimate one to be outB , and the last one to be jnz 0 . That leaves you with 5 instructions to "mangle" the number. The only thing they have that is not easily reversible in modulo operations is xors. You can only xor easily with numbers from 0 to 7. Then maybe a store mod8 at some point. All I'm saying is that it seems rather few possibilities in the end, when you have more than 10k competitors.

Great hacking day. I'm not sure if my solution is suitable for every input. After "source code" analysis it came out that up to 10 bits generates the number in my case. This nicely limits the search space. https://github.com/genmeblog/advent-of-code/blob/master/src/advent_of_code_2024/day17.clj

@malaingreclement just checked your program (opcodes and operands) as you left it in your solution. It's completely matched with mine. Even xors and their constants,

@malaingreclement Looking at source code of your input and comparing with mine we have xor of 3 LSB and some numbers, some higher bits based on B (0-7), and in my case also with next 3 bits from A. But generally the result relies on up to 10 bits.

I enjoyed this, I always like the reverse engineering ones even though they tend to always make my head hurt. read the source code, saw the answers would be in the range 8^15 -> 8^16, briefly thought about a direct attack, realized going from reverse was easy, got to essentially the same DFS approach upthread. https://github.com/tildedave/advent-of-code/blob/main/src/advent2024/day17.clj#L204-L237

I did spend "too much time" implementing the machine, lots of silly bugs.

only happy about this part of the code that relies on merge order

state-up (case instruction
                        0 {:A (quot A (int (math/pow 2 combo-operand)))} 
                        1 {:B (bit-xor B literal-operand)}
                        2 {:B (mod combo-operand 8)}
                        3 (if (zero? A) {} {:pointer literal-operand})
                        4 {:B (bit-xor B C)}
                        5 {:output (conj output (mod combo-operand 8))}
                        6 {:B (quot A (int (math/pow 2 combo-operand)))}
                        7 {:C (quot A (int (math/pow 2 combo-operand)))})]
         (recur (merge state {:pointer (+ 2 pointer)} state-up))

after some past AoC years, I will say that it is kind how quickly all these programs terminated.

I think they were constrained by how the number would have to be 2^70 to be just one digit longer... Which on most architectures is a nightmare.

I suppose making it based on powers of 4 wasn't easy to generate? It would have given them a lot more room.

@norman your solution is helping me, thanks for sharing! but I dont understand how your expand function doesn't infinitely loop for a A=0 input

@jvuillermet each call to expand checks 8 cases. Each case can recurse, but only if out has one more digit in the output that matches.

OMFG I just debugged my p1 for ages, just now realized I was submitting without the commas (e.g. “012” instead of “0,1,2")

> With only 8 instructions in the program, and 2 “free” registers, I wonder how the puzzle maker generates unique inputs for everyone playing. There’s got to be a lot of collision. @malaingreclement he’s stated before he generates “a lot” of i/o pairs, many people get the same ones.

Here’s todays: https://github.com/bhauman/adv2024/blob/main/src/adv2024/day17/sol.clj Part 2 in 2.5s Binary search to find the window of correct length results. Then reduce the window around a maximum match val match val is

(defn matching-digits-val [n n2]
  (reduce + (map #(if (= %1 %2)
                    (long (Math/pow 10 %3))
                    0) n n2 (range))))

@bhauman living that bruteforce life. Respect.

is the solution really to iterate through all the numbers in the range? I was thinking there might be some math trick to do a reverse computation on the program input. hmmm

I manually tweaked the first octets until I found a decent range to search in, then let the computer do the rest 🙂 not ideal, but hey, I got my star

my solution builds the output in reverse, wasn't too bad (and easier than thinking about bit munging)

@felipecortezfi if you check out my code , Itried to explain the "trick" I came up with. Like tildewave, I build the output in reverse.

@malaingreclement yep, that’s kind of what I did too, but I was wondering if you can simply calculate the numbers instead of doing a search. the example in part 2 makes me think you can

It reminds me 2017

https://aoc.xhyrom.dev/ first red 🙂

Nice resource! I didn't know about it.