6 ms·
Day 20: My favourite problem from Advent of Code 2023
- ynniv 3y agoFirst I started by modelling the devices as objects. Starting with a single base class that has most of the common behaviour. Object oriented programming has ruined us
- rapfaria 3y agoWhat ruins folks these days? Functional?
- lionkor 3y agoTo expand on this: The issue is that OOP easily leads you to model your problem into your solution. This has the desired effect of solving the problem, but the likely undesired side effect that your solution encodes a specific problem description. Thats why this is an issue
- chongli 3y agoYeah. Generally the best code in OOP languages tends to favour composition over inheritance. In other words, it uses functional ideas and works around some of the clunkiness of OOP to build generic structures and algorithms. This is what really successful packages in OOP languages look like (such as numpy and friends).
- ynniv 3y agoThere are a few problems with OOP. The one that bothers me the most is that there is immediately boilerplate complexity. How is this bag of data addressed? What does it behave like? How is each piece of it read and written? Now you need collection generics. There’s complexity everywhere, and it’s expensive. It hampers concurrency, and doesn’t work on GPUs. What do we get for it? Implicit control flow, and it isn’t even clear to me that this is a benefit let alone worth the costs. Any time performance is remotely a concern, object orientation should be the first thing removed.
- jansimonek 3y agoI think the problem is not OOP - the author approached the problem bottom-up, they were trying to foresee usage for code they were writing. The resulting code is a bit of a mess, not OOP (there’s even instanceof) Instead we should start with the usage, with the code creating the value and then filling in the details. In this problem, if we choose to simulate the circuit I would start with the simulator code, introducing abstractions for components only if it would help the simulator. I liked the demonstration of this approach in Chapter 6 of Robert C. Martin’s Agile Software Development: Principles, Patterns and Practices. It’s available online here: https://people.scs.carleton.ca/~jeanpier//Fall2021/Topic%201%20-%20TDD/3c-%20long%20TDD%20example/TDD-BowlingScore.pdf https://people.scs.carleton.ca/~jeanpier//Fall2021/Topic%201...
- Yajirobe 3y ago> But if we multiply the numbers together we get a number that is divisible by every number in the table. Wouldn’t LCM be the correct/more general approach? The periods could have common factors, right?
- tialaramex 3y agoThat'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).
- dunham 3y agoDo 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.
- tialaramex 3y agoI 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.
- noxvilleza 3y agoOne thing to note is that periodicity need not all be prime numbers, so you can't always find the product of their periods -- you might need to find their LCM.
- qsort 3y agoI 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 agoI 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 agoYeah, 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
- hfuaiobfa 3y agoI 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.
- mcherm 3y agoI regret that I cannot read this article. At least not for another day or so... I only just finished #19.
- yoru-sulfur 3y agoMy 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 to a "hub" node of the chain (a conjunction). You can parse the module structure and traverse the graph to extract that number. The connections to the hub are the bits of the number (1 if module is connected, 0 if not). Do that for all the counters and LCM (or multiply since they are all coincidentally co-prime) them together to get your answer. No simulation required.
- LeonardoTolstoy 3y agoYup. 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.
- nrabulinski 3y agoI 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.
- _Wintermute 3y agoI 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.
- tialaramex 3y agoLots 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.
- LeonardoTolstoy 3y agoAs 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.
- x86x87 3y agoI was half expecting someone to model this in VHDL and to synthesize it in a FPGA to get the answer to part 2