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

11–20 of 49 posts

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

#11

Post by tialaramex »

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 different way because it has very different properties than the inputs people are given for real. Contrast day 19, where the example input has a rational answer, which you are told about for the Part II, against day 20 where the example input is completely irrelevant for Part II and good luck.

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

#12

Post by noxvilleza »

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.

The same is true with part 2 of problem 8 and problem 21 which both are generally much harder problems which are made easier by carefully constructed test cases. I also find it somewhat annoying, but par for the course with advent given the same test data for part 1 & 2; and the fact that you actually see the only test case -- it's not hidden test cases like in other programming competitions.

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

#13

Post by flurie »

noxvilleza wrote: post #12
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.

The same is true with part 2 of problem 8 and problem 21 which both are generally much harder problems which are made easier by carefully constructed test cases. I also find it somewhat annoying, but par for the course with advent given the same test data for part 1 & 2; and the fact that you actually see the only test case -- it's not hidden test cases like in other programming competitions.

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...

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

#14

Post by epiccoleman »

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…

Yeah, it's always rough when you write a solution for part 2, and it passes all the samples, but then has issues with the real input.

One thing I've tried to do when I run into those kinds of problems is to write a little benchmark to illustrate the difference between approaches. It's always kinda fun to watch your initial brute force solution start chugging while your shiny new solution seems to handle whatever you toss at it - great lesson in choosing effective algorithms.

I use Elixir to do the puzzles, so I've used Benchee for this, and it works very well. So easy to set up too.

Here's an example benchmark, which also has the output. As the input size increases you start getting some pretty crazy ratios between the two algorithms (the "smart" version was 200,000 times faster than the "naive" one on the largest test input!)

https://github.com/epiccoleman/advent_of_code_ex/blob/master...

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

#16

Post by rst »

flurie wrote: post #13
noxvilleza wrote: post #12

Earlier quoted context omitted.

The same is true with part 2 of problem 8 and problem 21 which both are generally much harder problems which are made easier by carefully constructed test cases. I also find it somewhat annoying, but par for the course with advent given the same test data for part 1 & 2; and the fact that you actually see the only test case -- it's not hidden test cases like in other programming competitions.

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...

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.

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

#17

Post by noxvilleza »

flurie wrote: post #13
noxvilleza wrote: post #12

Earlier quoted context omitted.

The same is true with part 2 of problem 8 and problem 21 which both are generally much harder problems which are made easier by carefully constructed test cases. I also find it somewhat annoying, but par for the course with advent given the same test data for part 1 & 2; and the fact that you actually see the only test case -- it's not hidden test cases like in other programming competitions.

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 cycle (~10^13).

This solution might not work if your cycles weren't constant length -- for example imagine when walking your graph you found your i_th Z-node after {6, 7, 6, 7, 6, 7, 6, 7 ...} steps; or perhaps {6, 7, 7, 7, ...}. In the test data, this didn't occur - it was always {n, n, n, n, ...}.

I can give another example perhaps - consider you're asked to find the last 3 digits of 2^n for n >= 1. You start off calculating: 002, 004, 008, ... eventually you get to 2^103 which ends in 008. This means that the cycle length would be {103, 101, 101, 101, 101, ...} since it'll never get back to 002 or 004. Solving this is a bit more difficult than the constant cycle lengths, since it's not a simple LCM.

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

#18

Post by hfuaiobfa »

I had a difficult time with both part 1&2 of Day 20. At first I just mentally modeled the circuit as "clock-based" where the Flip-Flops flip only when all previous pulses are processed and a synchronizing clock signal is given,

e.g. a flip-flop (default to low) with 2 input ports, on first clock signal (time 1) both ports receives a low pulse; second clock signal (time 2) the flip-flop inspects 2 inputs and decides to give a low (two flips) at the end.

Frustratingly, this model passes the 2 examples flawlessly but fails for the real input.

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

#19

Post by Barrin92 »

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 problem that nobody explicitly tells you about. Much prefer it to the 'here are the exact five keywords so you know what CS class algorithm you need to use' kind of thing.

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

#20

Post by penteract »

rst wrote: post #16
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...

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.

It gets even more interesting if you start worrying about ghosts that could finish at multiple points within each cycle. There are potentially too many combinations to try out each one individually.
Post reply on HN