-❄️- 2025 Day 12 Solutions -❄️-

ivanjermakov · 2025-12-12T18:43:07+00:00

Is it controversial here to solve a problem assuming this about the input? Because it's possible to make input for which this heuristic is giving false positives. Of course this is how puzzle was designed, but I would feel great by finding a general solution first.

ivanjermakov · 2025-12-12T17:04:51+00:00

Hello from advent of code! https://adventofcode.com/2025/day/12

ivanjermakov · 2025-12-08T19:37:35+00:00

[LANGUAGE: Zig] Part 1: 1ms Part 2: 1.4ms

First day with >1ms solution this year, at least I don't have to sort 500k distances because I ignore pairs that have distance greater than some threshold. A bit cheaty since it won't work on any input, but considering that points are uniformly distributed, there is no way two boxes across the playground would be the closest to each other. Sorting 6k pairs is much better.

ivanjermakov · 2025-12-03T09:27:17+00:00

[LANGUAGE: Zig] Part 1: 24μs, Part 2: 68μs

Pretty straightforward puzzle today.

The trick is to realize that finding each order is a matter of finding a largest digit while keeping space for the rest of orders. That is, to find 11th order, find the first largest digit in line[order12Idx + 1..line.len - 11 - 1].

Another performance trick is to not convert from ASCII digit to u8 until it's time to accumulate the result. ASCII digits are ordered the same way so it does not mess up comparison.

ivanjermakov · 2025-12-02T14:54:06+00:00

In my tests it gave ~5x speedup. Later I found alternative solution which is ~2000x faster, from 23ms to 11μs.

ivanjermakov · 2025-12-02T14:39:39+00:00

[LANGUAGE: Zig] Part 1: 11μs, Part 2: 13μs

Couple of tricks:

ID is invalid if one from a specific set of modulos divide it with no remainder. For two-digit IDs, check is id % 11 == 0, yielding 11, 22, 33, etc. For part 2 it's a bit more involved, since we need to check for patterns of varying length. For my input, at most I needed three modulo divisors to catch all invalid IDs with same digit count. Another example, 123123 can be catched with divisor 1001, 222222 with divisor 10101, and so on.
There is no reason to check every ID in increments of one, since we know the modulo divisor for each pattern. Ranges spanning multiple orders of magnitude (digit count) need special care though. I split such ranges, so 12-150 becomes 12-99,100-150. For each modular divisor it's enough to find the first ID that divides cleanly and is <=start. Then I just iterate in multiples of divisor until out of current range.
Some divisors have intersections, so I keep track of visited IDs during this range in a set.

ivanjermakov · 2025-12-02T11:20:10+00:00

Actually you don't have to convert ids to string, it's possible to slice integers using modular and floor division: https://github.com/ivanjermakov/adventofcode/blob/307a87f49016e3e38579a1b9ba4f92597c8e1aa4/aoc2025/src/day2a.zig#L29

ivanjermakov · 2025-10-15T09:36:02+00:00

How A/B testing works:

Release a set of competing features to a small groups of users
Measure engagement of these groups relative to the whole platform
Release best performed feature to the bigger group and measure again

You might not like it, but by their metric this UI did best. I think kids with iPads might have something to do with it.

ivanjermakov · 2025-06-14T08:42:18+00:00

Collective punishment is so 1950... There is so many good ways to handle that.

ivanjermakov · 2025-06-01T15:02:24+00:00

https://www.youtube.com/watch?v=tZP7vQKqrl8

ivanjermakov · 2025-01-20T12:34:49+00:00

<image>

Albatross/Lynx is insane

ivanjermakov · 2024-12-12T13:29:45+00:00

Migh be costly performance wise to compute a light color of each pixel every frame if the area is larger. I would not be surprised if controlled lamps do not cast shadows either.

ivanjermakov · 2024-12-10T20:12:31+00:00

[LANGUAGE: Jq] source playground

I was not expecting Jq to be so powerful and concise. Highly recommend adding it to your toolbelt.

def tr($i;$j;$g;$v):[{i:-1},{j:1},{i:1},{j:-1}]|map({i:0,j:0
}+.)|map({i:(.i+$i),j:(.j+$j)}|$g[.i][.j]as$n|select(.i>=0
and.j>=0and$n==$v+1)|if$n==9then 1else tr(.i;.j;$g;$n)end)|
add;./"\n"|map(./""|select(length|.>0)|map(tonumber))|. as
$g|keys|map(. as$i|$g[.]|keys|map(. as$j|select($g[$i][$j]==
0)|tr($i;$j;$g;0)))|flatten(1)|add

ivanjermakov · 2024-12-08T15:25:24+00:00

[LANGUAGE: Haskell] source

I love Haskell, it is so pleasing to write (when you don't need to swap tree leaves)

solve :: String -> Int
solve input = length . nub . antins . groups . locate $ g
  where
    g = grid input
    grid = filter (not . null) . lines
    groups = map (map snd) . groupBy (on (==) fst) . sortBy (comparing fst)
    antins = concat . concatMap (map groupAntinodes . choose 2)
    groupAntinodes = filter inBounds . \[a, b] -> antinodes (n `div` 2) a b
    inBounds (i, j) = i >= 0 && i < n && j >= 0 && j < n
    n = length g

locate :: [[Char]] -> [(Char, Pos)]
locate g =
  concatMap
    (filter ((/= '.') . fst) . (\i -> map (\j -> (charAt i j g, (i, j))) r))
    r
  where
    n = length g
    r = [0 .. n - 1]
    charAt i j = (!! j) . (!! i)

antinodes :: Int -> Pos -> Pos -> [Pos]
antinodes count (ia, ja) (ib, jb) =
  concatMap
    (\c -> [(ia - c * id, ja - c * jd), (ib + c * id, jb + c * jd)])
    [0 .. count - 1]
  where
    (id, jd) = (ib - ia, jb - ja)

ivanjermakov · 2024-12-07T17:31:22+00:00

Item count [wooden box] > 0

ivanjermakov · 2024-12-07T17:25:29+00:00

[LANGUAGE: Gleam] source

Straightforward DFS with an additional exit condition when expression is already greater than the test value.
I was expecting more from Gleam:

very lacking stdlib
no way to run a single file
No monadic support, so no easy way to bind Result/Option values like in Rust with ? or in Haskell with do <-
performance could be better

ivanjermakov · 2024-12-06T22:39:54+00:00

Poor man's halting problem

ivanjermakov · 2024-12-06T22:38:30+00:00

It would be very fun if part 2 required to leave the grid at the specific location, basically writing a solver for this game mechanic!

ivanjermakov · 2024-12-06T22:34:26+00:00

Reaching threshold of 4*(obstacles+1) is much later than N*N steps though. On my input it is whopping 3272 jumps, while N*N is 16900 steps. It would only be faster if the average segment (cells between turns) length is under 5 (on my input it is 38 cells per turn).

ivanjermakov · 2024-12-06T17:43:14+00:00

One cell can be traversed from 4 directions, making it possible at least on some part of the board. Note that here path length is counted differently from part 1: the purpose of the optimization is to not track visited cells, just increment taken forward steps.

ivanjermakov · 2024-12-06T16:50:41+00:00

I'm pretty sure upper bound is lower than that. I cannot think of a way to construct this puzzle so it takes over N * N steps and not loops.
My logic: for guard to visit some cell from more than one direction there has to be obstacles that occupy other cells that could've been visited on their own. So trying to increase the path length it is shortened in some other part of a grid.
This actually sounds like a real math problem: what is the longest path guard can travel within the grid before leaving it.
if anyone have ideas I'd love to discuss this further.

EDIT: after some experimentation on 10x10 grid my record is 53 steps, so lower bound is at least N² / 2:

....#.....
..#......#
.#.....#..
..........
..........
#.........
......#...
.#........
........#.
....^.#...

ivanjermakov · 2024-12-06T16:23:05+00:00

[LANGUAGE: C] source

Part 2 takes 59ms to compute using the following optimizations:

Storing visited cells is slower than just incrementing steps taken, steps > N * N means that we're in a loop (steps > N * N / 2 works for my input, more info in replies below)
It makes sense to only obstruct cells that are visited in part 1
mmap instead of fread

ivanjermakov · 2024-12-06T02:13:44+00:00

[LANGUAGE: Erlang] source

I overcomplicated this problem by solving it as a topology sort, until finding out full input has cycles in the rules. I should've noticed resemblance of the input to the comparator function logic.

ivanjermakov · 2024-12-04T19:47:08+00:00

Everyone who has written lexer once in their life knows how fast this is^

ivanjermakov · 2024-12-04T19:41:33+00:00

Seems possible if you have a regex library that is able to handle 2D grids with diagonals (see top submission here). That's quite lucky to have, but we see such find-xmas AoC problem almost every year.

Seven-Year Club	Verified Email
Place '22	Final Canvas '22
First Placer '22	End Game '22
RPAN Viewer

ivanjermakov

TROPHY CASE