Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Day 20: My favourite problem from Advent of Code 2023

mliezun.github.io

Post reply on HN
Print view View original

41–49 of 49 posts

Re: Day 20: My favourite problem from Advent of Code 2023

#41

Post by qsort »

penteract wrote: post #35
qsort wrote: post #31

Earlier quoted context omitted.

I actually wrote the code to solve it in full generality ( https://github.com/edoannunziata/jardin/blob/master/misc/Aoc... ) -- CRT is the idea but it's actually the "generalized" case of CRT, because you could have moduli that are not coprime. So you have to use the CRT "in reverse" to break each linear congruence into its components (using the fact that \mathbb{Z}_m \times \mathbb{Z}_n \cong \mathbb{Z}_{mn} \iff \g…

It's possible to answer "find the minimum n such that n%a is in s1 and n%b is in s2, assuming a and b are coprime" in runtime around O(n1+log(n1)*n2) where n1 is the size of s1 and n2 is the size of s2. n1*n2 can get at least as big as a*b/8 without a naive linear search being guaranteed to be fast, so this roughly square roots the runtime of 'CRT on all pairs' if n1 is close to n2. Here's the code, sorry it's not as…

Wow, thanks! I'll check it out.

Re: Day 20: My favourite problem from Advent of Code 2023

#42

Post by tialaramex »

LeonardoTolstoy wrote: post #40
tialaramex wrote: post #38

Earlier quoted context omitted.

Lots of people have speculated that this is true, but the creator of the puzzles (Topaz) has indicated that they did not concern themselves with Chat GPT or LLMs beyond specifying that if you do just use an LLM you should not attempt to claim top leaderboard spots which are for humans only. In fact I didn't see people wrestling with LLMs trying to get them to solve early days and I can't believe it's impossible. My e…

As a small counterpoint early on I do remember people trying and failing to use LLMs which prompted some of the speculation about the competition being made LLM-proof. As early as I think day 2 there was a big discussion about how no matter what people did the SotA LLMs could not give a correct solution for part 2. After that at least on the subreddit discussions involving LLMs were downvoted intentionally and so whi…

Interesting about the LLMs. I admit I don't read very much early AoC Reddit because I am most likely to be reading if I have questions after a few hours (like, wait, are these huge numbers prime or am I bad at arithmetic? Does my approach work and I screwed up, or am I an idiot and I'm on the wrong track entirely?) and in the first ten days or so I often don't have any questions.

Re: Day 20: My favourite problem from Advent of Code 2023

#43

Post by epiccoleman »

Barrin92 wrote: post #19
qsort wrote: post #9

I don't really like problems like these. I love Advent of Code and have got 50/50 stars on Christmas day this year -- but this type of problem grinds my gears. The intended solution only works because the input is more constrained than what the problem statement says (the problem in full generality is PSPACE-hard). If you give me a problem to solve, I'd rather have all the hypotheses, all at once.

I like them a lot because they inject a little bit of empirical or heuristic thinking into problems. For this particular problem I immediately reached for graphviz to get an idea of what the circuit looks like and it made it obvious what the solution was. It's much closer to how real world engineering problems work where you have to do a little bit of investigation and maybe find some creative way to constrain your p…

Yes, yes, yes for graphviz.

I _love_ when one of these problems encourages me to reach for a tool like that. (At least, when it's one I'm already aware of and I have time to dedicate to grokking and solving the puzzle).

I used graphviz on one of last years problems and found it pretty helpful. It just feels so cool when you learn a new "spell" to help you feel out the problem.

Another example was from 2020, where I used lexx/yacc to generate a parser for the expressions in the input. This was honestly probably slower than just doing it myself but it felt so cool to solve it with a tool - and it's neat to plant little signposts in your brain that will light up when you run across a similar class of problem in your real work.

Another thing I often do is use vim to munge the input and save myself some parsing code, which is a very generically useful branch of "magic" to have under your fingers.

Re: Day 20: My favourite problem from Advent of Code 2023

#45

Post by flurie »

noxvilleza wrote: post #17
flurie wrote: post #13

Earlier quoted context omitted.

I'm behind this year, so I haven't looked at any postmortems, but I found an interesting solution to problem 8 part 2[1] after watching the brute force methods stall out. Could you explain what you mean by carefully constructed test cases? [1] https://github.com/flurie/aoc-rust/blob/main/src/bin/08.rs#L...

So in Question 8 part 2 you had multiple cycles through a graph. You started on all "A" nodes and you had to find the first time at which you were entirely on "Z" nodes. The intended solution was seemingly to calculate the length of the cycle (as in, until you were on a "Z" node) for each starting node separately. Once you'd done this, you could find the LCM of these cycle lengths to find the overall period of the cy…

I can see the case of an aperiodic first cycle length, but given that each vertex in the graph created by the input -> output nodes of the traversal path has only one outgoing edge, is it possible for the cyclic graph from a1 to some z1 to have an inconsistent length? And is there ever going to be some z2 for which the aperiodic cycle length from a1 to either z1 or z2 results in a better answer to the problem given that the periodic cycle length of a1 to z1 is shorter than the cycle length of a1 to z2? Please forgive me if I am not using the correct graph theory terms.

Re: Day 20: My favourite problem from Advent of Code 2023

#46

Post by postalrat »

nrabulinski wrote: post #30

I feel like the quality of puzzles has fallen over the years. This year had much more “spot something in the real input which neither the examples nor the puzzle itself states” than any previous I participated in. I really don’t enjoy those sorts of puzzles and, at least for me, it isn’t what I’m participating in AoC for.

Would you rather they re-skin the same puzzles people have memorized?

Re: Day 20: My favourite problem from Advent of Code 2023

#47

Post by nrabulinski »

postalrat wrote: post #46
nrabulinski wrote: post #30

I feel like the quality of puzzles has fallen over the years. This year had much more “spot something in the real input which neither the examples nor the puzzle itself states” than any previous I participated in. I really don’t enjoy those sorts of puzzles and, at least for me, it isn’t what I’m participating in AoC for.

Would you rather they re-skin the same puzzles people have memorized?

I’d rather they either give the assumptions in the puzzle description or at least in the examples. There were a few puzzles which I didn’t enjoy due to personal reasons but those I don’t have anything against, so long as the problem doesn’t boil down to „figure it out based on the real input since the example input doesn’t reflect it”

Re: Day 20: My favourite problem from Advent of Code 2023

#48

Post by WirelessGigabit »

nrabulinski wrote: post #30

I feel like the quality of puzzles has fallen over the years. This year had much more “spot something in the real input which neither the examples nor the puzzle itself states” than any previous I participated in. I really don’t enjoy those sorts of puzzles and, at least for me, it isn’t what I’m participating in AoC for.

Correct.

Part 1: easy.

Apply part 1 solution to example, works.

Apply part 1 solution to real input, works.

Part 2: hard to very hard.

Apply part 2 solution to example, usually works.

Apply part 2 solution to real input, doesn't work due to time / memory constraints.

But having to look at the input to discover a pattern that isn't explained as part of the instructions always irks me.

Re: Day 20: My favourite problem from Advent of Code 2023

#49

Post by noxvilleza »

qsort wrote: post #31
noxvilleza wrote: post #25

Earlier quoted context omitted.

Would you use Chinese remainder theory on all possible configurations of the cycles, or something else completely?

I actually wrote the code to solve it in full generality ( https://github.com/edoannunziata/jardin/blob/master/misc/Aoc... ) -- CRT is the idea but it's actually the "generalized" case of CRT, because you could have moduli that are not coprime. So you have to use the CRT "in reverse" to break each linear congruence into its components (using the fact that \mathbb{Z}_m \times \mathbb{Z}_n \cong \mathbb{Z}_{mn} \iff \g…

Great, thanks!
Post reply on HN