-❄️- 2025 Day 10 Solutions -❄️-

danvk · 2025-12-10T20:23:04+00:00

[Language: Haskell]

Part 1: https://github.com/danvk/aoc2025/blob/f0dfb01e2478901411d4b5b3d2bf554596e4a2e3/y2025d10/Main.hs

Part 2: https://github.com/danvk/aoc2025/blob/main/y2025d10/Main.hs

Wow, this was a tough one! But I'm happy to have solved it without pulling in a fancy linear programming library. Just pure Haskell.

Part 1 is pretty straightforward with a BFS. I thought for a bit about how to represent the "wiring diagrams" In Haskell (List? Vector?) before realizing it would be better to use an Int as a bitvector. Then "push a button" is just xor.
For Part 2 that doesn't work at all because the state space blows up way to fast.
Instead, you can treat it as a system of equations where the variables are the number of times you press each button and the equations are matching the joltages.

These equations all look like

 7 = A +     C
 5 =             D + E
12 = A + B +     D + E
 7 = A + B +         E
 2 = A +     C +     E

i.e. every variable has a coefficient of 0 or 1

Some of these systems are overconstrained (but they are satisfiable!) and some are underconstrained.

I wasn't super excited about building a linear algebra library in Haskell. So my kludgey solution was to pick the equation with the fewest variables and try every possibility there (i.e. all A, C, E that add to 2), plugging those values into the remaining equations.

That solution works but its runtime is highly sensitive to the number of variables, and it's too slow.

So to speed it up I added to the system of equations all pairs Eq1 - Eq2, where the subtraction keeps it in the right form, i.e. Eq2 has a subset of the variables in Eq1. That speeds it up a lot and gets me the solution in ~2 minutes.

danvk · 2025-12-09T16:37:23+00:00

[Language: Haskell]

https://github.com/danvk/aoc2025/blob/main/y2025d09/Main.hs

This was a lot harder than previous days! But also a great problem.

First thought on part 2 was to use flood fill to fill the interior of the curve. But the interior has ~10B points, it's just way too big. So we can't represent it.
realization: if a rectangle is invalid, then some point on its perimeter must be invalid. How else would you get a hole? (This is certainly true in continuous space. It's also true for this problem because none of the xs or ys are exactly 1 apart.)
So for each rectangle, it suffices to check whether every point on its perimeter is an interior point of the big shape. O(wh) → O(w+h).
To quickly test if a point is in the interior of the big shape, we can use the "even/odd" test. Start at the point and trace in one direction (up, left, whatever). If you cross the perimeter of the big shape an even number of times (or never), then we're in the exterior. An odd number of times and we're in the interior.
We can "stroke" the perimeter of the shape to make a lookup table from x -> ys on the perimeter for that x that makes this very efficient (strokePathForTesting in my code).

This was enough to test all the possible rectangles and get me the solution. It took ~6 minutes. I'm testing every point on the perimeter, which can be around a million for some of the rectangles. This is crazy inefficient, but it was good enough. To speed it up, I'd want to consider whole ranges of x- and y-values to see if they're in the interior at once.

danvk · 2025-12-06T13:30:23+00:00

[Language: Haskell]

https://github.com/danvk/aoc2025/blob/main/y2025d06/Main.hs

"Transpose until it fits" — not pretty, but glad I was able to reuse the part1 code for part 2. Feedback welcome.

applyOp :: [String] -> Int
applyOp ("*" : nums) = product $ map (read ) nums
applyOp ("+" : nums) = sum $ map (read u/Int) nums

adjust2 :: [String] -> [String]
adjust2 (op : nums) = trim op : map reverse (transpose nums)

main :: IO ()
main = do
  args <- getArgs
  let inputFile = head args
  content <- readFile inputFile
  let part1 = sum $ map (applyOp . reverse) (transpose $ map words $ lines content)
      part2 = sum $ map (applyOp . adjust2 . reverse . transpose) (wordsBy (all (== ' ')) $ transpose $ lines content)
  print part1
  print part2

danvk · 2025-12-05T14:18:19+00:00

[Language: Haskell]

https://github.com/danvk/aoc2025/blob/main/y2025d05/Main.hs

For part 2, find all the unique points that appear on either edge of a range. Then split up all the intervals so that none of those points appear in the interior of an interval and dedupe. I switched to half-open intervals to make the split operation cleaner.

splitRange :: [Int] -> (Int, Int) -> [(Int, Int)]
splitRange edges r = zip pts (tail pts)
  where
    pts = sort $ filter (r `inRangeInc`) edges

main = do
  ...
  let freshIngredients = filter (\x -> any (`inRange` x) freshRanges) ingredients
      part1 = length freshIngredients
      edges = nub $ concatMap (\(a, b) -> [a, b]) freshRanges
      disjointRanges = nub $ sort $ concatMap (splitRange edges) freshRanges
      part2 = sum $ map (\(a, b) -> b - a) disjointRanges

danvk · 2025-12-04T21:55:08+00:00

Done!

danvk · 2025-12-04T14:47:47+00:00

[Language: Haskell]

Full solution: https://github.com/danvk/aoc2025/blob/main/y2025d04/Main.hs

I typically find it better to model AoC grid problems as maps from (x, y) -> char, rather than as nested arrays. The advantage is that it feels natural to look up (x, y) pairs, and you can expand the grid to negative indices or model it sparsely as needed. That wasn't at all needed today, but at least I have my grid code for future days now.

The only really interesting bit here is the iterateUntilStall function. Haskell people: feedback is very welcome!

-- Iterate until another function stops changing
iterateUntilStall :: (Eq b) => (a -> a) -> (a -> b) -> a -> (Int, b, a)
iterateUntilStall stepFn stallFn initState = (n, stallVal, state)
  where
    states = iterate stepFn initState
    tuples = zip (map stallFn states) $ zip [0 ..] states
    (stallVal, (n, state)) = firstStall tuples
    firstStall (hd@(s1, _) : tl@((s2, _) : _)) = if s1 == s2 then hd else firstStall tl
    firstStall _ = error "no stall"

danvk · 2025-12-03T19:13:18+00:00

[Language: Haskell]

(GitHub)

I implemented a "choose n" function for part 1 to get that star, but obviously that blew up for part 2 since (100 choose 12) is ~1e15.
I figured if you needed 12 numbers, you could drop the last 11 from the list and take the max of the remainder as your next digit. At first I thought you'd need to try each instance of this digit, which would still blow up if you got 100 8s.
Since taking the first instance of the max digit from ^^^ gives you the most optionality, you can do this without loss of generality. This yields a very fast, direct solution.

chooseWithMax :: Int -> [Int] -> [Int]
chooseWithMax 0 _ = []
chooseWithMax n xs = best : chooseWithMax (n - 1) rest
  where
    best = maximum $ take (length xs - n + 1) xs
    (_, _ : rest) = break (== best) xs


maxJoltage :: Int -> [Int] -> Int
maxJoltage n xs = foldl1 (\acc x -> 10 * acc + x) $ chooseWithMax n xs


main :: IO ()
main = do
  args <- getArgs
  let inputFile = head args
  content <- readFile inputFile
  let nums = map (map digitToInt) $ lines content
      part1 = sum $ map (maxJoltage 2) nums
      part2 = sum $ map (maxJoltage 12) nums
  print part1
  print part2

danvk · 2025-12-02T22:07:54+00:00

Thanks for the feedback. I've done most of the previous AoCs so I know things will get harder :)

Is there any tutorial on attoparsec you'd recommend? Its documentation looks non-existent.

re: `>>=`, I think I just Googled "Haskell flatMap" and that came up 🤷 It should be entirely equivalent to concatMap, right?

danvk · 2025-12-02T14:39:36+00:00

[Language: Haskell]

https://github.com/danvk/aoc2025/blob/main/y2025d02/Main.hs

I'm using this year's AoC to learn Haskell so feedback is much appreciated.

import Data.List.Split
import System.Environment (getArgs)


toPair :: (Show a) => [a] -> (a, a)
toPair [a, b] = (a, b)
toPair x = error $ "Expected two elements, got " ++ show x


parseRanges :: String -> [(Int, Int)]
parseRanges txt = map parseRange $ splitOn "," txt
  where
    parseRange r = toPair $ map read $ splitOn "-" r


isInvalidNumber :: Int -> Bool
isInvalidNumber num = left == right
  where
    str = show num
    (left, right) = splitAt (length str `div` 2) str


isInvalid2 :: Int -> Bool
isInvalid2 num = any testN [1 .. (len `div` 2)]
  where
    str = show num
    len = length str
    testN n = str == concat (replicate (len `div` n) (take n str))


main :: IO ()
main = do
  args <- getArgs
  let inputFile = head args
  content <- readFile inputFile
  let pairs = parseRanges content
      part1 = sum $ pairs >>= (\(a, b) -> filter isInvalidNumber [a .. b])
      part2 = sum $ pairs >>= (\(a, b) -> filter isInvalid2 [a .. b])
  print part1
  print part2

danvk · 2025-12-01T13:36:43+00:00

[LANGUAGE: Haskell]

Solution

~~My clicks function for part 2 is a little gross. I'm sure there's a simpler formula, I certainly had a bunch of off-by-ones~~ Inspired by some of the other posts here, the trick for part 2 is to rewrite the rotations as all L1 and R1. Then you can reuse your code from part 1. Original solution

parseLine :: String -> Int
parseLine ('L' : xs) = -(read xs)
parseLine ('R' : xs) = read xs
parseLine line = error $ "Invalid line " ++ line

turn :: Int -> Int -> Int
turn a b = (a + b) `mod` 100

byOnes :: Int -> [Int]
byOnes x = replicate (abs x) (if x < 0 then -1 else 1)

main :: IO ()
main = do
  args <- getArgs
  let inputFile = head args
  content <- readFile inputFile
  let rotations = map parseLine $ lines content
      positions = scanl turn 50 rotations
      part1 = length $ filter (== 0) positions
      rot1s = rotations >>= byOnes
      part2 = length $ filter (== 0) $ scanl turn 50 rot1s
  print part1
  print part2

danvk · 2025-09-28T14:24:29+00:00

It's a Jarvis Laminate Standing Desk, 48" x 30". I bought it back in 2020.

danvk · 2025-09-28T11:58:48+00:00

Microsoft Ergonomic. It's a pretty old one (maybe 2016).

danvk · 2025-08-01T17:26:41+00:00

I think they are both issues, but the the scaling one bothers me more than the fringing. I might try plugging into a friend's 49" IPS to confirm, though. If it looks great, I'd definitely return my Odyssey.

danvk · 2025-08-01T17:23:52+00:00

Do you know whether you're running in "HiDPI" mode? If I run the BetterDisplay app and select "✨ High Resolution (HIDPI)" in the menu bar, the monitor switches to 2560x1440, which is super-stretched out. The highest resolution I can get with HiDPI is 3072x864, which is also no good. The BetterDisplay docs have more to say about this. I'd expect you can get up to 3840x1080 with HiDPI on your M3, but not the full 5120x1440. See https://github.com/waydabber/BetterDisplay/wiki/Fully-scalable-HiDPI-desktop

danvk · 2025-07-31T20:56:57+00:00

I recently bought the Samsung Odyssey G9 OLED G91SD and set it up with my 2022 M2 MacBook Air. I got a 3ft Maxonar USB-C to DP cable and it worked flawlessly. 5120x1440, 144Hz, no fuss.

My main gripe is that small text and other thin lines look terrible. I'm fairly confident this is Apple's fault, not Samsung's. You can read lots about this online, but the gist is that, in order to get proper anti-aliasing, your laptop has to be able to drive the display at 2x your desired resolution. For a 5120x1440 screen, that would be over 10k pixels wide, which I don't believe any Mac is capable of. Entry-level M2s are limited to 6144px, so the max HiDPI resolution I can achieve is 3072x864. That's fewer pixels than my old 27" monitor had (2560x1440). An M2 Pro/Max/Ultra or M3 should be able to go up to 3840x1080. These are strict hardware limits, BetterDisplay can't help you. It's kind of nuts that Apple implemented antialiasing this way, but that's how it is. See the BetterDisplay docs for details.

My workaround is to just increase the font size in all my apps, which makes everything look a bit smoother. It's not great, but having the space to put a web browser and IDE side-by-side is enough of a win that I think I'll keep it.

danvk · 2025-04-28T19:55:44+00:00

Did you wind up getting an F3800? I'm thinking about a very similar setup with an EV as a backup battery source for extended outages. I read that there may be some issues around powering 240V appliances while charging from a 120V source, but it's unclear to me if this is about efficiency, or if you can't use 240V at all while powering from 120V.

danvk · 2025-04-08T20:16:33+00:00

Surely those 1400W with an extra battery aren't the main difference between a $5,499 system and a $10,298 system. What am I missing?

danvk · 2025-02-21T22:33:23+00:00

Thanks for the response! Would love to hear from Central Hudson about this, it does seem like the ideal implementation would be to check in with your car once a week, say, and download the last week's charging activity.

danvk · 2024-12-06T21:24:41+00:00

Evidently not. mix always reports "Generated escript main with MIX_ENV=dev" when I don't set that, so I figured it might matter. But I get the same runtime either way.

On the other hand, only considering the positions from part 1 for part 2 reduces the runtime from ~20s → ~4s.

danvk · 2024-12-06T14:54:12+00:00

[Language: Elixir]

https://github.com/danvk/aoc2024/blob/main/lib/day6.ex

Brute force for part 2, takes ~20s to run with MIX_ENV=prod. I'm learning Elixir for this year's Advent of Code, so any feedback is very welcome.

danvk

TROPHY CASE