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

21–30 of 49 posts

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

#21

Post by chongli »

lionkor wrote: post #5
ynniv wrote: post #2

First 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

To 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

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

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

#22

Post by harshreality »

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…

Is there any theorem that puts limits on how irregular the cycles can be in a general case of tape length L with N options corresponding to N outputs from each graph node?

What has to be constant is the cycle length for (node, tape instruction #) pairs, because all the state to determine every future step is based on the current node and tape position; if both are the same, the path will be the same as before. I think, at least without advanced math, the only thing to rely on for "true" loops is identical pairs of (instr #, node), not just instr # or tape steps or node individually.

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

#23

Post by noxvilleza »

harshreality wrote: post #22
noxvilleza wrote: post #17

Earlier quoted context omitted.

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…

Is there any theorem that puts limits on how irregular the cycles can be in a general case of tape length L with N options corresponding to N outputs from each graph node? What has to be constant is the cycle length for (node, tape instruction #) pairs, because all the state to determine every future step is based on the current node and tape position; if both are the same, the path will be the same as before. I thin…

I haven't spent that much time thinking about it, but my guess is that there may or may not be:

* a "tail" -- some initial part of the path before you get into a true cycle (like the 002, 004 in the example above)

* an inner repeating cycle before you reach a node you've seen before.

In the case given |t| = 0 and |c| = 1, but it's easy to construct a more complex example with nodes (A, B, C, D), edges (A->B, B->C, C->D, D->B), and 'ending nodes' being B and D. In this case left and right paths go to the same node. This case would have a tail of length 1, and then the inner cycles would be of length {2, 1, 2, 1 ...}.

As a result, valid 'ending states' (Z-nodes) for this graph would be after {1, 3, 4, 6, 7, 9, 10, ...} steps.

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

#24

Post by yoru-sulfur »

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

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

#25

Post by noxvilleza »

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.

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

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

#26

Post by harshreality »

noxvilleza wrote: post #23
harshreality wrote: post #22

Earlier quoted context omitted.

Is there any theorem that puts limits on how irregular the cycles can be in a general case of tape length L with N options corresponding to N outputs from each graph node? What has to be constant is the cycle length for (node, tape instruction #) pairs, because all the state to determine every future step is based on the current node and tape position; if both are the same, the path will be the same as before. I thin…

I haven't spent that much time thinking about it, but my guess is that there may or may not be: * a "tail" -- some initial part of the path before you get into a true cycle (like the 002, 004 in the example above) * an inner repeating cycle before you reach a node you've seen before. In the case given |t| = 0 and |c| = 1, but it's easy to construct a more complex example with nodes (A, B, C, D), edges (A->B, B->C, C-…

You can have an inner seemingly-repeating cycle by node, but not by (node, tape instr #) pair.

Initial tails are something they should've done, which would've foiled the naive "find the cycle lengths and use lcm" approach.

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

#27

Post by ynniv »

lionkor wrote: post #5
ynniv wrote: post #2

First 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

To 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

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

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

#28

Post by dunham »

tialaramex wrote: post #7
Yajirobe wrote: post #6

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

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.

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

#29

Post by jansimonek »

lionkor wrote: post #5
ynniv wrote: post #2

First 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

To 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

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

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

#30

Post by nrabulinski »

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.
Post reply on HN