#adventofcode2024 — Public Fediverse posts

I had a little time today to revisit part 2, which I had previously only solved by hand by visually analyzing the graph of gates.

I can now solve this in code by classifying the gates into layers:

Layer 1: XOR and AND gates connected to the inputs
Layer 2: AND gates not in Layer 1
Layer 3: OR gates
Layer 4: XOR gates not in Layer 1

Each gate in the layers must be followed by a defined set of gates:

Layer 1 XOR: needs to be followed by a Layer 2 AND and a Layer 4 XOR
Layer 1 AND: needs to be followed by a Layer 3 OR
Layer 2 AND: needs to be followed by a Layer 3 OR
Layer 3 OR: needs to be followed by a Layer 2 AND and a Layer 4 XOR
Layer 4 XOR: must output z

Considering edge cases in the first and last rows, if any of these rules are violated, the gate's output is incorrect.

I even went as far as trying to swap all the combinations of bad gates to fix the circuit completely (although this is not required for the solution, where we only need to identify the bad gate, not how to swap the outputs to fix the circuit).

https://github.com/nharrer/AdventOfCode/blob/main/rust/src/year2024/day24.rs

#AdventOfCode
#AdventOfCode2024
#AoC

I had a little time today to revisit part 2, which I had previously only solved by hand by visually analyzing the graph of gates.

I can now solve this in code by classifying the gates into layers:

Layer 1: XOR and AND gates connected to the inputs
Layer 2: AND gates not in Layer 1
Layer 3: OR gates
Layer 4: XOR gates not in Layer 1

Each gate in the layers must be followed by a defined set of gates:

Layer 1 XOR: needs to be followed by a Layer 2 AND and a Layer 4 XOR
Layer 1 AND: needs to be followed by a Layer 3 OR
Layer 2 AND: needs to be followed by a Layer 3 OR
Layer 3 OR: needs to be followed by a Layer 2 AND and a Layer 4 XOR
Layer 4 XOR: must output z

Considering edge cases in the first and last rows, if any of these rules are violated, the gate's output is incorrect.

I even went as far as trying to swap all the combinations of bad gates to fix the circuit completely (although this is not required for the solution, where we only need to identify the bad gate, not how to swap the outputs to fix the circuit).

https://github.com/nharrer/AdventOfCode/blob/main/rust/src/year2024/day24.rs

#AdventOfCode
#AdventOfCode2024
#AoC

Part 2 took me an embarrassingly long time to figure out. At first I thought I could randomly try a bunch of additions, see which wires outputs were wrong, get all of their inputs, and then take the intersection of all the wrong inputs and that would be the answer. But that didn't work.

Finally, I attacked it by figuring out what a binary adder should look like, as a circuit, and then finding where the circuit we had was malformed. It took a lot of trial and error before I got a reasonable looking solution, and the first time I did it was right, so I don't know if I am lucky or actually have a principled approach, but I'm sticking with it.

Total runtime for both about 40ms.

#AdventOfCode2024 #AdventOfCode #Python

Part 2 took me an embarrassingly long time to figure out. At first I thought I could randomly try a bunch of additions, see which wires outputs were wrong, get all of their inputs, and then take the intersection of all the wrong inputs and that would be the answer. But that didn't work.

Finally, I attacked it by figuring out what a binary adder should look like, as a circuit, and then finding where the circuit we had was malformed. It took a lot of trial and error before I got a reasonable looking solution, and the first time I did it was right, so I don't know if I am lucky or actually have a principled approach, but I'm sticking with it.

Total runtime for both about 40ms.

#AdventOfCode2024 #AdventOfCode #Python

Ah, the last full day of #AdventOfCode2024, Day 24, wasn't too bad. The first part was very similar to 2015 Day 7, which is is one of my all-time favorite AoC puzzles, but the second part was ... not.

Part 1 can be solved recursively with memoization. Since ultimately each output ("z") value must depend on a known input value ("x" or “y”), you can recursively resolve the operands, using memoization to make sure you only calculate each operand once.

#AdventOfCode #Python

Ah, the last full day of #AdventOfCode2024, Day 24, wasn't too bad. The first part was very similar to 2015 Day 7, which is is one of my all-time favorite AoC puzzles, but the second part was ... not.

Part 1 can be solved recursively with memoization. Since ultimately each output ("z") value must depend on a known input value ("x" or “y”), you can recursively resolve the operands, using memoization to make sure you only calculate each operand once.

#AdventOfCode #Python

And I just realized that all of the duplicates in Part 1 were being caused by 3-node cliques that contain multiple nodes that start with “t”, so just filtering those out directly would save a lot of effort. The code (in the screenshot, and updated in Github) runs even faster now.

#AdventOfCode2024 #AdventOfCode #Python

And I just realized that all of the duplicates in Part 1 were being caused by 3-node cliques that contain multiple nodes that start with “t”, so just filtering those out directly would save a lot of effort. The code (in the screenshot, and updated in Github) runs even faster now.

#AdventOfCode2024 #AdventOfCode #Python

For Part 2, I knew enough about graphs to know that what we were looking for was called a clique, so it was a quick Google search to find the Bron-Kerbosch algorithm for finding cliques in a graph (https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm), and then it was just a matter of taking the largest and formatting it the way that the answer required it to be.

All-in-all a fun day, and I learned a new algorithm!

#AdventOfCode2024 #AdventOfCode #Python

For Part 2, I knew enough about graphs to know that what we were looking for was called a clique, so it was a quick Google search to find the Bron-Kerbosch algorithm for finding cliques in a graph (https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm), and then it was just a matter of taking the largest and formatting it the way that the answer required it to be.

All-in-all a fun day, and I learned a new algorithm!

#AdventOfCode2024 #AdventOfCode #Python

Phew! After a couple of rough days that I mostly skipped as I had a busy weekend, #AdventOfCode2024 Day 23 was pretty fun (though ymmv, but I like graph problems a lot).

Initially I was going to brute force Part 1, just using itertools.combinations to examine all three-node combinations to find interconnected ones that had at least one member that started with ’t’, but that ended up being too many, so instead I started with all of the ’t’ nodes, then searched through all the two-node combinations of its neighbors, storing every unique three-node combination I found, which was quite fast to complete.

https://github.com/biesnecker/aoc-anyhow/blob/main/202423.py

#AdventOfCode #Python

Phew! After a couple of rough days that I mostly skipped as I had a busy weekend, #AdventOfCode2024 Day 23 was pretty fun (though ymmv, but I like graph problems a lot).

Initially I was going to brute force Part 1, just using itertools.combinations to examine all three-node combinations to find interconnected ones that had at least one member that started with ’t’, but that ended up being too many, so instead I started with all of the ’t’ nodes, then searched through all the two-node combinations of its neighbors, storing every unique three-node combination I found, which was quite fast to complete.

https://github.com/biesnecker/aoc-anyhow/blob/main/202423.py

#AdventOfCode #Python

I wonder whether anyone of my followers has solved the second star of day 14 of #AdventOfCode2024. It's formulated in such an indefinite way, it's not my cup of tea.
Anyways, I took this year's problems as an opportunity to improve my Kotlin skills (apart from async programming, and with a bonus linear algebra recap), and I'm glad I did, but now it's taking too much of my time (my ToDo list is just too long). Thanks #AdventOfCode, see you next year.

I wonder whether anyone of my followers has solved the second star of day 14 of #AdventOfCode2024. It's formulated in such an indefinite way, it's not my cup of tea.
Anyways, I took this year's problems as an opportunity to improve my Kotlin skills (apart from async programming, and with a bonus linear algebra recap), and I'm glad I did, but now it's taking too much of my time (my ToDo list is just too long). Thanks #AdventOfCode, see you next year.

As with other puzzles we had already this year, we only need the length of shortest key sequence and not the sequence itself.

#AdventOfCode
#AdventOfCode2024
#AoC

As with other puzzles we had already this year, we only need the length of shortest key sequence and not the sequence itself.

#AdventOfCode
#AdventOfCode2024
#AoC

I seem to have been the only person who just sat down, thought about what the easiest sequences must be (in terms of "left" being harder than "right" because it's further from the "A"), handwrote a lookup table and then got pt1 perfect, and pt2 off by just one logic error true/false conditions (ironically, in the bit of the lookup table I wrote some code to generate because I was bored of typing).
Sometimes you don't need to throw a DFS at everything!
#AdventOfCode2024

If you look at the maze, you'll see there is only one path, so no pathfinding is needed. Just begin at the start, check which of the four neighbors is another part of the race track, and repeat.

Imagine the path like a string of pearls, like an array (or list/vector) of positions on the race track. The index of the array serves as a metric for the distance. So, if you subtract the indices of two positions in the array, you get the distance between those two points along the race track.

Now, determine for each position all other possible positions where the Manhattan distance is between 2 and 20. Calculate the distance by subtracting their indices in the array. Ignore all cheats where the distance is negative (jumps back) or where the distance of the cheat is not smaller than the distance along the race track.

#AdventOfCode
#AdventOfCode2024
#AoC

Day 20 was definitely the hardest day of #AdventOfCode2024 I've done so far, but also one of the most enjoyable. Went through a couple of different approaches before I settled on one that worked.

Both parts are basically the same. First, I calculate the shortest path from the destination square to every other square. This gives me the path for the "fair" race, without any cheats, and also the distance from every square to the destination (if there's a path).

Then, for each step along the "fair" path, I search for any square in within 2 (for Part 1) or 20 (for Part 2) steps of the current square, and if the cost to get to the destination from that square is 100 or more steps less than the number of steps I've taken so far plus the number of steps to get to that square, then it's a valid shortcut and I count it.

https://github.com/biesnecker/aoc-anyhow/blob/main/202420.py

#python #AdventOfCode

I realized after posting that looking through all of the possible towels was wasteful, and could be better by putting the towels into a dictionary indexed by the towels first letter, and then only looking through the towels that begin with the same first letter as the pattern fragment. This halved the runtime on my machine, from ~150ms to about ~75ms.

This screenshot shows the input handling and the updated `possible` function.

#AdventOfCode #AdventOfCode2024 #Python