Clojurians Log v2

For sample input (from reddit):

'029A': 82050061710 * 29
'980A': 72242026390 * 980
'179A': 81251039228 * 179
'456A': 80786362258 * 456
'379A': 77985628636 * 379

result: 154115708116294

matches my solution too

So this was a real mind bender... I have pages and pages of papers covered in symbols x) Runtime with cold caches: 3ms part1, 45ms part2. EDIT: DRY-ing

After a huge mess I made it readable. It runs in 5ms (cold). https://github.com/zelark/AoC/blob/master/src/zelark/aoc_2024/day_21.clj

I'm just getting started. I took one look last night and realized I'd much rather do it on a saturday morning than a friday night 🙂

I can see by the lack of responses here I made the right call 🙂

@erdos if you're willing and have some time, i would love some commentary on your code for today. I literally solved today and I still don't get what you're doing x) And it looks so clean and concise, too...

hey @malaingreclement I am happy to share here. Today took the longest for me as well, as I missed a lot of details early on. Code is on github: https://github.com/erdos/advent-of-code/blob/master/2024/day21.clj I like writing these small solutions without dependencies. I defined a bunch of helpers for this task: • code-numeric function just calculates numeric score of a code to be used later. • directional-mapping and numeric-mapping are mappings of button code to coordinates of buttons. I figured that shifting the grids so that button A gets to [0 0] would simplify things later. These could have been written programmatically but sometimes hard-coding mappings is quicker/shorter. • sequences-step function calculates the direction between two coordinates. For example, if the source is left to target, then direction is [>], if above, then [v], if both then [> v] • Function pos-step is used to move a point by a button press. • loc-sequences function calculates all the possible shortest sequences of button presses needed to get from one coordinate to another. For example, to get from [0 0] to [1 1] , it gives us ([> v] [v >]) The solution is just using dynamic programming with memoize : • If there are no robots involved and we are pressing the buttons directly, then the number of button presses equals to the length of the code. • Otherwise, the code is just a list of consecutive button presses. We have to calculate (recursively) the robot's path from A to a desired button and then press A on the level above to activate the robot. All these paths have a cost, and we are looking for the minimum of the cost. The worst thing I missed was that there are empty gaps on the keypads which are illegal positions. For the example cases, there actually exist paths that are shorter, but those start with << which would move the robot to the gap. I am filtering for these in the condition in loc-sequences . I had another implementation that actually enumerated all the paths and then selected the shortest one. It was really slow for the example cases and then I lost patience when running it for the actual input. So I rewrote it to select the shortest one with (min-key count %) but then the one it selected was not always optimal for deeper levels of recursion - this approach was good with all but the last test case, which led me down the rabbit hole for another hour of debugging.

Thank you for this very comprehensive breakdown :) I'm really in awe at how you always seem to pick the correct data structure to attack the second part of the day.

interesting (defn map-pairs [f s] (map f s (next s)))! Never thought about it and always reach for partition

gosh i loved this problem so much

I assume I got it the intended way. reduced the key sequences to a CFG, each "step" or indirection expands the string, certain button transitions have optimal routes (e.g. going from 0 to 7 you go up up up left not up left up up), then split the string apart at the "A"s, and use the stone/lanternfish counting mechanism. my code is pretty ugly, I haven't had a chance to clean it up.

https://github.com/tildedave/advent-of-code/blob/main/src/advent2024/day21.clj - I'll have to do a pass to try to clean it up later, lots of duplicated logic now.

I don't really understand why in cases where there's ambiguity in terms of a "best" path (for example going from A to v you can go ^>A or >^A and they both expand to the same size at the next robot) it doesn't matter which one you choose.

@tildedave because they are located at the same distance from A.

I thought that “exploding” commands through the levels wouldn’t be a viable approach but it was. I assumed that there would be an error there caused by the remaining existing state after finishing one command to prevent the next one from being so simply derived. Initially I went into a totally different direction where I wanted to translate moves from [\x \y \A \A \A \A] => [\adj-to-x \adj-dir \A \A \A \A] = cost([\y \A \A \A] => [\adj-dir \A \A \A]) + 1 and then search that space, but that had so much complexity I couldn’t get it to work.

@jvuillermet yeah (partition 2 1 xs) is definitely better than (map f xs (next xs), I tend to forget about it and when I remember, I screw up the parameters 🙂

Oh my goodness Day 21 https://github.com/bhauman/adv2024/blob/main/src/adv2024/day21/sol.clj Part 2 13ms

Used recursion memoization. It’s too bad bc I started going in that direction at the start but I didn’t grok one certain thing about it. I did try frequencies and got it to work for the example but it ran way to long. but in the process learned more about the structure of the problem. Anyway that was an adventure.

now for day 22

https://gitlab.com/maximoburrito/advent2024/-/blob/main/src/day21/main.clj Taking these a bit more casually... Finally catching up.

Yeah. Good luck, it's definitely a Week-end Puzzle ™️

Here’s hoping