6 ms·

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.

by qsort 3y ago

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.

tialaramex 3y ago
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.
- epiccoleman 3y ago
  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/test/aoc_2021/day06/day06_benchmarks.exs https://github.com/epiccoleman/advent_of_code_ex/blob/master...
- Jare 3y ago
  > 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.
  - tialaramex 3y ago
    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"
noxvilleza 3y ago
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.
- flurie 3y ago
  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#L27 https://github.com/flurie/aoc-rust/blob/main/src/bin/08.rs#L...
  - rst 3y ago
    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.
    - penteract 3y ago
      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.
    - noxvilleza 3y ago
      Would you use Chinese remainder theory on all possible configurations of the cycles, or something else completely?
      - 3y ago
Barrin92 3y ago
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.
- epiccoleman 3y ago
  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.

by qsort 3y ago

tialaramex 3y ago

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.

epiccoleman 3y ago
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/test/aoc_2021/day06/day06_benchmarks.exs https://github.com/epiccoleman/advent_of_code_ex/blob/master...
Jare 3y ago
> 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.
- tialaramex 3y ago
  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"

noxvilleza 3y ago

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.

flurie 3y ago
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#L27 https://github.com/flurie/aoc-rust/blob/main/src/bin/08.rs#L...
- rst 3y ago
  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.
  - penteract 3y ago
    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.
  - noxvilleza 3y ago
    Would you use Chinese remainder theory on all possible configurations of the cycles, or something else completely?
    - 3y ago

Barrin92 3y ago

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.

epiccoleman 3y ago
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.