Advent of Code: What's the difference between a strip club and a ballet studio?

The straightforward solution ## The problem ## Reframing the problem ## Forward Count ## Backward count ## Combine forward and backward ## Python ## Back to the original repo ## Summary Advent of Code is an annual coding puzzle. We're going to deal with AoC 2025 Day 1: Secret Entrance, Part 2. The straightforward solution is a run-length-encoded list unrolling algorithm. On some inputs - which we'll see later - this approach is quite slow (here's a Rust snippet from an author, I came across his code in his pretty good code walkthrough video): Disclaimer: It wasn't ever supposed to be run on this input. There's nothing wrong with using the run-length-encoded list unrolling algorithm for the AoC inputs. The Other Guys is a Hollywood movie about Ballet. Can this Hollywood movie help us? The puzzle is a bit tricky... it involves a clock, and moving the clock's pointer... The moves of the clock are a bit complicated, so you have to watch out for edge cases. The naive solution solves this in the perfect way. It does simple one clockwise or one counterclockwise: So this is an awesome algo which always detects those pesky 0-passes, and it is speedy for the AoC input: But... for non-AoC inputs, it is slow: Essentially the algo creates a multi-billion storied building under itself, then it just aims for the bushes. Which - I want to stress - is entirely cool for normal AoC inputs!!! The code is not really CPU-bound (it isn't doing anything complex), but mostly memory-bound. But... there's even a worse thing. If the flatMap-ing is not optimized away, and the list actually materializes (i.e. no optimization of temporary lists), then it can run out of space pretty fast. I think the problem is that we built ourself a mental cage with clocks. The author seems to be of Slavic origin though, which gave me an idea. What are the top 3 things associated with Slavic people? I am not Slavic though, so... I am bad at Heroes of Might and Magic 3. I also don't know what Slavs mean with the symbol of Zorro ℤ100, groups, rings and whatnot. So, I'll stick to tiptoeing Tchaikovsky, and numbers 0, 1, 2, 3, which even I can understand: Yep. I warned you. I'm a simpleton. So let's rephrase our question in my dumb way: We want to disqualify the head from the answer, because otherwise we would count the ballerina's starting position as a new position. Of course, the Ballerina could've chosen the other direction too: So with that aside, in summary there are two ways: These two ways don't necessarily give the same result, so we must be careful: Why is this Tchaikovsky nonsense good for us?! We can get the answer without unrolling, hopefully in less than O(ΔX) time and space. If we can pull off this neat Slavic trick, we can cut down the problem of generating crazy long lists! So now the question is: Can we define those functions forwardCount / backwardCount? Before we dive into this... This will get a bit number crunchy, but don't worry: We are going to solve this The Freedom Fries, Free American Way! We are not going to do math. Just try observing patterns, how colors change, how things kind of shift/rotate around. Below is a question, restated in a general manner (remember we don't want to count H itself, as that's where the ballerina starts the pirouette): Now, instead of math-ing, I tabulated some results for H=0 and H=1. Please observe below, that H=1 is just a shifted version of the same H=0 (Look for the rainbow colored thingies). I hope you saw that there's a pattern to how H shifts/rotates the solution. I compressed and summarized all H into a table, so that you can eyeball the general form (look for the arrows! We are just plugging in the H): So, we defined forwardCount. Job done. Let's move on to backwardCount! Once again, please don't get too hung up on numbers, try to see patterns. We are going to solve it exactly the same way as we did the forward, simply this time... well... it is going to be backwards. Let's restate the question in a general form: Once again, I suck at math, so we tabulate and look for patterns: And finally - once again - we do that compressed and summarized table to eyeball a general form: So, we defined backwardCount. Job done. So we have two formulas, which are almost the same (no, I don't know what an integer overflow is yet): But... the above thingy is too general. In our case: Fixing these parameters yields a short special form: Each "round" we can use that count function to calculate 0-passes or 0-landings in one fell swoop. So basically, we just iterate on the normal input and we play The Ancient Babylonian Game of Fronthand-Backhand in each round, based on whether the command starts with R or L. In the below Python code: We don't unroll the commands, so we are speedy-ish even on crazy inputs: The author said a lot of well-intentioned design goals in his README: I completely get what this developer wants. In my opinion, this developer is a good cop, in the most noble meaning of the phrase. I want to focus on a specific line of his, to demonstrate why: The code is kept vertical, so it stays within a regular monitor size, no need for endless zooming, scroling nonsense The author seems to be really fixated on Vertical. Here's horizontal code (AoC '23 Day 09 Part A and Part B): So I can only reply to the vertical "good cop" author with the following: This is a ballet studio, Terry. These poles are horizontal. Note: The above Haskell code isn't truly strict neither spine nor element wise, and it also uses String and singly linked lists, so it is a live grenade. The author wrote Haskell for Part 1 like this (source): So for example he would say that (in arrow notation, which is a more generic version of the & trick): It "flows" from left to right. Which feels pipeline-y. But with function composition (.) we would say that: It "flows" from right to left. "The answer is the first row of the matrix's inverse." Which feels definition-y. The second version has a unique property, which the first does not have: British traffic rules. All in all it is just a matter of preference. Imperative, Declarative? Which one should we do? I think there's no good or bad choice: But if you observe the codes I wrote, they have: Yeah! Imperative John Wick and Declarative Ballerina were so convincing in their argument, that I did a desk pop! But honestly: Imperative or Declarative? Kotlin, Rust or Gleam? LLMs unfortunately can't help us here, because they don't have the most important thing in human history: Personal Opinion So the LLM says ¯\(ツ)/¯. Choose what you like. Templates let you quickly answer FAQs or store snippets for re-use. Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink. Hide child comments as well For further actions, you may consider blocking this person and/or reporting abuse CODE_BLOCK: #!/usr/bin/env python3 def count(x, dx): if dx >= 0: return (dx + ((100 + x) % 100)) // 100 else: return (-dx + ((100 - x) % 100)) // 100 def main(): a = 0 b = 0 x = 50 with open("input.txt", "r") as f: a = 0 b = 0 for line in f: line = line.strip() if not line: continue dx = (int(line[1:]) if line[0] == "R" else -int(line[1:])) b = b + count(x, dx) x = (x + dx) % 100 if x == 0: a = a + 1 print("A") print(a) print("B") print(b) if __name__ == "__main__": main() Enter fullscreen mode Exit fullscreen mode CODE_BLOCK: #!/usr/bin/env python3 def count(x, dx): if dx >= 0: return (dx + ((100 + x) % 100)) // 100 else: return (-dx + ((100 - x) % 100)) // 100 def main(): a = 0 b = 0 x = 50 with open("input.txt", "r") as f: a = 0 b = 0 for line in f: line = line.strip() if not line: continue dx = (int(line[1:]) if line[0] == "R" else -int(line[1:])) b = b + count(x, dx) x = (x + dx) % 100 if x == 0: a = a + 1 print("A") print(a) print("B") print(b) if __name__ == "__main__": main() CODE_BLOCK: #!/usr/bin/env python3 def count(x, dx): if dx >= 0: return (dx + ((100 + x) % 100)) // 100 else: return (-dx + ((100 - x) % 100)) // 100 def main(): a = 0 b = 0 x = 50 with open("input.txt", "r") as f: a = 0 b = 0 for line in f: line = line.strip() if not line: continue dx = (int(line[1:]) if line[0] == "R" else -int(line[1:])) b = b + count(x, dx) x = (x + dx) % 100 if x == 0: a = a + 1 print("A") print(a) print("B") print(b) if __name__ == "__main__": main() CODE_BLOCK: Programming style, code characteristics, philosophy Pipeline programming Data-oriented programming Functional-like programming Declarative-like programming Side-effect isolation (I/O only in main) Expression-oriented programming Structured, composable functions No mutable global state Prefer not to have even local mutable state unless absolutely needed to gain smth much more valuable Prefer not to have explicit source code-level loops unless absolutely needed to gain smth much more valuable Pure functions Minimal branching, maximal transformation Clean, predictable control flow Lean functional patterns Less code means better. Keep code dense. Code is a liability, not an asset The code is not opimized to gain maximum raw speed The code is kept vertical, so it stays within a regular monitor size, no need for endless zooming, scroling nonsense The code is opimized for correctness, simplicity and clarity The code is straightforward like do 1, do 2, do 3, get result Enter fullscreen mode Exit fullscreen mode CODE_BLOCK: Programming style, code characteristics, philosophy Pipeline programming Data-oriented programming Functional-like programming Declarative-like programming Side-effect isolation (I/O only in main) Expression-oriented programming Structured, composable functions No mutable global state Prefer not to have even local mutable state unless absolutely needed to gain smth much more valuable Prefer not to have explicit source code-level loops unless absolutely needed to gain smth much more valuable Pure functions Minimal branching, maximal transformation Clean, predictable control flow Lean functional patterns Less code means better. Keep code dense. Code is a liability, not an asset The code is not opimized to gain maximum raw speed The code is kept vertical, so it stays within a regular monitor size, no need for endless zooming, scroling nonsense The code is opimized for correctness, simplicity and clarity The code is straightforward like do 1, do 2, do 3, get result CODE_BLOCK: Programming style, code characteristics, philosophy Pipeline programming Data-oriented programming Functional-like programming Declarative-like programming Side-effect isolation (I/O only in main) Expression-oriented programming Structured, composable functions No mutable global state Prefer not to have even local mutable state unless absolutely needed to gain smth much more valuable Prefer not to have explicit source code-level loops unless absolutely needed to gain smth much more valuable Pure functions Minimal branching, maximal transformation Clean, predictable control flow Lean functional patterns Less code means better. Keep code dense. Code is a liability, not an asset The code is not opimized to gain maximum raw speed The code is kept vertical, so it stays within a regular monitor size, no need for endless zooming, scroling nonsense The code is opimized for correctness, simplicity and clarity The code is straightforward like do 1, do 2, do 3, get result COMMAND_BLOCK: import Data.List (foldl') main :: IO () main = interact $ unlines . (\x -> ["A", a x, "B", b x]) . fmap (fmap read . words) . lines a :: [[Int]] -> String a = show . sum . fmap extrapolate b :: [[Int]] -> String b = show . sum . fmap (extrapolate . reverse) extrapolate :: [Int] -> Int extrapolate = sum . foldl' (flip (scanl (-))) [] Enter fullscreen mode Exit fullscreen mode COMMAND_BLOCK: import Data.List (foldl') main :: IO () main = interact $ unlines . (\x -> ["A", a x, "B", b x]) . fmap (fmap read . words) . lines a :: [[Int]] -> String a = show . sum . fmap extrapolate b :: [[Int]] -> String b = show . sum . fmap (extrapolate . reverse) extrapolate :: [Int] -> Int extrapolate = sum . foldl' (flip (scanl (-))) [] COMMAND_BLOCK: import Data.List (foldl') main :: IO () main = interact $ unlines . (\x -> ["A", a x, "B", b x]) . fmap (fmap read . words) . lines a :: [[Int]] -> String a = show . sum . fmap extrapolate b :: [[Int]] -> String b = show . sum . fmap (extrapolate . reverse) extrapolate :: [Int] -> Int extrapolate = sum . foldl' (flip (scanl (-))) [] CODE_BLOCK: main :: IO () main = readFile "day1_part1.txt" >>= \contents -> contents & lines & map trim & filter (not . null) ... Enter fullscreen mode Exit fullscreen mode CODE_BLOCK: main :: IO () main = readFile "day1_part1.txt" >>= \contents -> contents & lines & map trim & filter (not . null) ... CODE_BLOCK: main :: IO () main = readFile "day1_part1.txt" >>= \contents -> contents & lines & map trim & filter (not . null) ... COMMAND_BLOCK: answer = matrixInverse >>> firstRow Enter fullscreen mode Exit fullscreen mode COMMAND_BLOCK: answer = matrixInverse >>> firstRow COMMAND_BLOCK: answer = matrixInverse >>> firstRow CODE_BLOCK: answer = firstRow . matrixInverse Enter fullscreen mode Exit fullscreen mode CODE_BLOCK: answer = firstRow . matrixInverse CODE_BLOCK: answer = firstRow . matrixInverse - Heroes of Might and Magic 3 - Great mathematicians - We the clock has 100 ticks so N=100 - We are counting zeroes so K=0 - I didn't inline the count function, which does the counting for Question 2. - while the ballerina's new x is simply calculated using the simple mod / % routine from Question 1. - We collect zero landings into a. - We collect zero traverses or landings into b. - You compute the inverse of the matrix - And return its first row - You can be an imperative John Wick - Or you can be declarative Ballerina - optimistic parsing, - overflows, underflows, all kinds of flows, - the formula which is still not simplified, - zero proof of correctness.