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

31–40 of 49 posts

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

#31

Post by qsort »

noxvilleza wrote: post #25
rst wrote: post #16

Earlier quoted context omitted.

It's easy to construct inputs for which the correct solution would not be the LCM of the cycle lengths. (Just take the input you got, and insert a few extra steps between the "start" point for one of the "ghosts" and the point where it enters its otherwise unaltered cycle.) A more general solution is possible -- but it does require a trick that people may not be aware of unless they've studied a little number theory.

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 \gcd(m, n) = 1) and then use the CRT again to find the answer.

Annoying to code, but I've done it a thousand times by hand for math competitions, so it's kind of carved into my skull.

There might be multiple cases, but I don't think there's anything better (please let me know if there is, I'm very interested) -- as a matter of fact, an instance of the original problem can be used to encode an instance of a system of linear congruences, so finding a better algorithm for the latter would imply a better algorithm for the former.

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

#33

Post by Jare »

tialaramex wrote: post #11
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 don't necessarily mind these "reverse engineering" type problems, I think you can consider your input part of the problem statement. In earlier years it was common, particularly in early days, for your input to be on the page itself IIRC, like "Your input is 103053439" rather than a link. One thing that bothers me more though is when the example input is nonsense for Part II or can be solved but in a radically diff…

> I think you can consider your input part of the problem statement

That would be fine if there was only one input. But we have seen countless cases of a solution working for some and not others (including/especially the test input). So the cases and patterns I see in my input may be part of the hidden problem statement, or they may be just an artifact of my particular input. I at least feel more satisfied when I know my solution will solve all inputs.

For that reason, I side with the desire for a bit more purity and closure, vs having to guess, and not being sure about your guess until you go to reddit. Making educated guesses about patterns is a valuable ability, but I don't like the aesthetics of it here.

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

#34

Post by tialaramex »

Jare wrote: post #33
tialaramex wrote: post #11

Earlier quoted context omitted.

I don't necessarily mind these "reverse engineering" type problems, I think you can consider your input part of the problem statement. In earlier years it was common, particularly in early days, for your input to be on the page itself IIRC, like "Your input is 103053439" rather than a link. One thing that bothers me more though is when the example input is nonsense for Part II or can be solved but in a radically diff…

> I think you can consider your input part of the problem statement That would be fine if there was only one input. But we have seen countless cases of a solution working for some and not others (including/especially the test input). So the cases and patterns I see in my input may be part of the hidden problem statement, or they may be just an artifact of my particular input. I at least feel more satisfied when I kno…

This is definitely something where tastes vary, for example you can see below several people assumed you can multiply any numbers, and that actually worked because the numbers are co-prime, but strictly you need LCM (and since I had LCM in my toolkit I used it)

I try to write solutions which would work for inputs like mine but I'm not fussed if, for example, my code panics on hypothetical "valid" inputs that I didn't consider.

So e.g I have panics for nonsense input like, "Pipe networks with more than one Start can't be solved" and "Uneveen seed list cannot work as described in problem" [Yes that's a typo] but I also have "Should not send signals unexpectedly" and "Surely not all the stones have X velocity 0"

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

#35

Post by penteract »

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…

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 well commented as yours, and I haven't integrated it into a solution to day 8.

https://github.com/penteract/adventofcode/blob/master/utils/... .

For more than 2 moduli, the best I can think of is to separate them into 2 roughly equal parts, generate the full lists of allowed remainders for each part, then use this algorithm to combine the parts. There may be better things you can do here (and perhaps you can show that for large sets of allowed remainders across enough different moduli, the solutions are spread out evenly enough there's one you can find by naive linear search).

Dealing with non-coprime moduli is left as an exercise to the reader :).

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

#36

Post by _Wintermute »

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.

I didn't enjoy the puzzles as much as previous years. My guess was they were structured in a way to make them non-trivial to solve with chat-GPT as the leaderboard is taken seriously by many.

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

#37

Post by tialaramex »

dunham wrote: post #28
tialaramex wrote: post #7

Earlier quoted context omitted.

That's correct. In practice it appears that the AoC inputs provide numbers which are always co-prime (ie have no common factors other than 1).

Do you know if there were any inputs on this problem that had non-prime numbers? Like others, I used LCM in my code, but mine were all prime numbers.

I don't know, presumably Topaz (who creates AoC) would know, but isn't telling.

We would probably find out if some inputs aren't co-prime because the naive multiplying solution breaks, but they could be non-prime and yet co-prime, for example 15, 14, 11, 23 is a set of numbers which are co-prime, but neither 15 nor 14 are prime.

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

#38

Post by tialaramex »

_Wintermute wrote: post #36
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.

I didn't enjoy the puzzles as much as previous years. My guess was they were structured in a way to make them non-trivial to solve with chat-GPT as the leaderboard is taken seriously by many.

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 expectation is that the fad has passed, the sort of people who tried Chat GPT in 2022 because it was hot have moved on, the sort of people who resorted to it because they don't like AoC just didn't do AoC in 2023. If you enjoy these puzzles it makes sense for you to solve them, not to ask a machine to do it.

That's what many people who resorted to Z3 found frustrating. A Z3 solution to Day 24 is arguably "correct" and it certainly "works" but it's not very satisfying in terms of feeling like you achieved anything. This is why I wrote a solution which didn't do that even though it was days slower to write.

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

#39

Post by LeonardoTolstoy »

yoru-sulfur wrote: post #24

My favourite solution to this problem was going all in on analyzing the input. Instead of just assuming the set of modules must have cyclic behaviour and running the simulation until you find the periods, look at the input and _really_ understand what its doing. What you will find is that the modules form a set of binary counters (chains of flip flops), with a number encoded into them via whether they are connected t…

Yup. This is a rare pen and paper solution for me. I ran simulations to confirm the first two cycles and that I was reading the binary right, but I got the solution directly from the input by hand.

It is my favorite problem of AoC as well this year mostly because it was the first problem in many years where when part 2 popped I didn't immediately mostly know what algorithm they were going for.

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

#40

Post by LeonardoTolstoy »

tialaramex wrote: post #38
_Wintermute wrote: post #36

Earlier quoted context omitted.

I didn't enjoy the puzzles as much as previous years. My guess was they were structured in a way to make them non-trivial to solve with chat-GPT as the leaderboard is taken seriously by many.

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 while presumably people were doing it there wasn't any discussion on Reddit at least.

I kind of agree with your last point. I try to do all the problems without non-built in python packages myself for exactly the reason you describe. Just feels more satisfying to me.

Post reply on HN