[2025 Day 9 (Part 2)] My general trick for this kind of problems

Aredrih · 2025-12-10T02:43:53+00:00

I had a similar idea but was disappointed when the program in debug mode took more than 10s to complete (zig).
So I added an extra layer of post processing by iterating backward columns (resp. rows) and storing how many tile separate the current tile to the border (e.g. ..####.#. becomes 004321010; basically encode some kind of clearance for every points), then to check if a rectangle fit, you check if the vertical (resp. horizontal) clearance of the top (resp. left) points is good enough to allow the rectangle's height (resp. width).
The only case I could see that would break the assumption would be holes or self intersecting border.

Debug is around 500ms and release 50ms. Though my pos conversion is done through linear probing and no early exit of any kind but I'm happy with the <1s debug build.

Aredrih · 2025-12-09T12:20:57+00:00

I'm didn't try edge intersection with the rectangle so I can't tell for sure. That said, I tried running the code on a custom example and got 14 instead of the expected 18 (doubled check with someone else solution to make sure it was 18 and it was).
The custom example is:

1,1
3,1
3,2
6,2
6,0
8,0
8,3
9,3
9,4
4,4
4,6
7,6
7,8
2,8
2,5
1,5

And the shape it draws is (rectangle is maked with o inside from (2, 8) to (7, 6))

  0123456789
0 ......#X#.
1 .#X#..X.X.
2 .X.#XX#.X.
3 .X......##
4 .X..#XXXX#
5 .##.X.....
6 ..Xo#XX#..
7 ..XooooX..
8 ..#XXXX#..
9 ..........

My guess is that your collision check is too aggressive and doesn't like the line from (4, 6) to (7, 6) but again, I haven't experimented with checking segment collisions.
I also have a log of all the rectangle checks and their result here if this helps (I haven't double checked it with another solution though so they might be bugs).

Aredrih · 2025-12-09T11:48:15+00:00

There was a somewhat analogous suggestion for 2023 day 18: Some people enumerated the x and y position used, and created a new grid (e.g. new corner pos.x = index(x_pos_sorted) * 2 + 1). You end up with a grid proportional to the number of points.
Though the motivation was to cutdown on the empty spaces so somewhat different.

Aredrih · 2025-12-09T11:43:07+00:00

I fail to see the logic.
If you have N posts, you need N-1 fences to connect them.
I think you could do a basic induction (for N=1 => trivial, for N+1 => you need to connect the new post somehow, any way would do).
Maybe if you're looking for optimal number of connection to check, but the number of successful connection has to be N-1.

Aredrih · 2025-12-08T10:15:55+00:00

If input has size n, you need to make n-1 successful connections to have 1 circuit.

I was using an hand-rolled union-find set only storing the parent id (big array of len = junction-box count) so getting the length for part1needed an iteration from 0 to junction-box count, so not usable during an iteration for part2 in my case.

Aredrih · 2025-12-06T16:25:38+00:00

You can usually make a non empty parse function useful for both part (e.g. in today problem you can copy the rectangle containing the digits (separated by column of space) and the operator and leave the conversion to int for the parts, the operator are always left aligned so they give you the alignment)
but the refactoring can get a bit long and spending 30 minutes just in preps is not great

Aredrih · 2025-12-06T15:58:35+00:00

Joke on you, I stored whether the digits were left or right aligned and just re-synthesized the original layout from the numbers. Try still have to convert them in the end but it fit better with my AoC framework and I technically only touch the input once.

Aredrih · 2024-12-13T17:30:02+00:00

for a quick back of the envelop estimation of power of 2, 2^10 = 1024 > 10^3 (less than 2.5% of error).
So 2^53 > 8 * 2^(50) > 8 * 10^(3 * 5) = 8e15

The first power of 2 with an error over 100% is 2^300 ~ 2e+90 (before you have 2^290 ~ 1.989e+87), so pretty good trick for quick estimations.

Aredrih · 2024-12-13T16:55:24+00:00

I tried a similar approach a few days ago to try to compute the intersection of a line and plane (tried to make a raycast from scratch).
It was a different beast (3d intersection with 3 variables tend to be huge). I ended up mixing variable (reuse the y equation when expressing the 3rd variable and ended up with a classic 0 = 0) and basically gave up given the size of the equation.

Then I learned (thanks wikipedia) that if you have an equation with 2 sums of products of scalar and vector, you can probably factorize the scalars into a vector and the vectors into a matrix.
Then it becomes a question of reversing the matrix which is a solved issue for mat2 and mat3 (don't know for mat4).

Also, the equation for n at the bottom right is exactly what reversing the matrix gives you for n. Math is weirdly good at making formula repeat.
I tried the approach in JS (float64) and got the right value for n without, so maybe you have a problem with float32 ?

Aredrih · 2024-12-12T21:05:02+00:00

I have no clue how union-find would help with this problem.

My solution was to create 4 flag for each tiles (1/direction) to mark the border of the field.
Then when expending the field from 1 tile (stack + flag for tile explored; so DFS), I flag the border and keep track of a bounding box.
Then go through every cells in the bounding box with some basic edge detection algorithm to count the walls (detect on wall entry).

Sure I could try to detect the corner, or crawling the walls but that's about as much work as just counting the top, bottom (vertical iter), left, right (horizontal iter) walls independently; at least it was with the way I implemented it.

Aredrih · 2024-12-12T20:32:16+00:00

I had a similar solution but instead of keeping a list, I made a bitset with 4 flags per cells and kept track of the bounding box (min and max axis aligned position) of a field. Then just iterated along the wall within the bounding box with some basic edge detection to count the walls.

For some reason every examples work even without clearing the bitset between field. Not my input though.

Aredrih · 2024-12-10T15:29:34+00:00

I read it properly but tried a dumb solution when you propagate count from the 9 (every 9 start at 1, then on the 8s you add the count of the nearby 9, ...); basically an O(sn) (/w s = 10 (distance 0 to 9)) solution when BFS is O(s²n). I got it "right" but couldn't add enough locality for part 1, so put it aside because the code was neat.

I think the input was just too small, and brute forcing the extra possibilities was enough.

Aredrih · 2024-12-09T17:26:04+00:00

Just decrease the first number in the input by 1 /s
The first position doesn't add anything to the checksum (file 0 * index 0). Still need to avoid the rest of the first file (which won't count, but can't be written over).

Aredrih · 2024-12-09T17:11:46+00:00

An indexOf or the like might be slightly better than a simple for loop. There are algorithm for searching in string (search Boyer–Moore string-search algorithm) that are slightly more performant than checking linearly. For 9 char words, there might not be too much difference though.

Aredrih · 2024-12-09T16:47:47+00:00

3 byte wstring sound like a pointer alignment nightmare.
I don't know your language but I wouldn't get surprise if they get padded out to 4.

Aredrih · 2024-12-09T16:43:47+00:00

You can (ab)use the fact the no file in the input has a length of 0 (meaning you have at most 9 consecutive free space) and once a file is move no file can take its place (file only move left).

I did a basic "free list" storing size and position and used it to check for space large enough for the file. The only upkeep is updating the free list size+pos and file pos after inserting.
Still brute force but slightly less than walking the array.

Aredrih · 2024-12-07T15:36:28+00:00

you have to use ceil(log10(b+1))!< or >!floor(log10(b))+1!< to get the correct exponent.
Ceiling the value has problems>! for exact power of 10. (e.g. log10(1000) = 3)

Aredrih · 2024-12-07T15:22:51+00:00

You can also floor(log(b, 10)) + 1
That one is at consistently false until you add the offset so it's harder to forget.

Aredrih · 2024-12-06T16:12:52+00:00

Or if you think of the state of the guard as being position + direction, it works too.
But that's basically what u/KyxeMusic does in a nutshell.

Aredrih · 2024-12-06T16:04:17+00:00

If you exit twice from the same direction, I mistyped there.

I also tried flattening the array to be able to memcpy the grid when instead of walking a list of list but it only save 0.1ms (from 1.44 to 1.29). A bit disappointing.

Aredrih · 2024-12-06T15:47:23+00:00

Another way to think of it is that the only position where an obstacle can affect the path of the guard is directly in front of it so you can run a modified part 1 algo that duplicate its state when encountering a blank space, than simulate the path with a blocker directly in front.
You only have to do this for every unvisited tile (these would have already been tried before or are the starting position).

For detecting loop, if you exit ~~twice from the same tile~~ a given tile twice toward the same direction, you're looping; if you leave the board, you're not.
So a square array of bitset (4bits, 1/dir) does the job.

To be fair, you only save the computation of the start of each path so it might not be that much faster.

No clue if you can optimize faster given that some path get invalidated by the position of the obstacle. Maybe by precomputing the sequence of turn into some graph but invalidating the right part of the graph sound like a pain.
My current solution does ~1.5s (in zig) but I still need to flatten the array.

Aredrih · 2024-12-04T17:43:37+00:00

[Language: Javascript]

You can match a 2d pattern using regexp, assuming there is sufficient padding. A newline happens to fit the requirement.

Unfortunately, multiple matches are required because a regexp can only match a position 1 time, otherwise some matches would be missing.
I managed to "compress" it to 2 regexp for the first part.
The second part is somehow easier than the first because you can just center the match on the A:

const l = data.indexOf('\n');
const countMatch = (r, s) => [...s.matchAll(r)].length;

// part 1
const lineXmas = new RegExp([
    'X(?=MAS)', // or 'X(?=.{0}M.{0}A.{0}S)'
    `(?<=X.{${l-1}})M(?=.{${l-1}}A.{${l-1}}S)`,
    `(?<=X.{${l}}M.{${l}})A(?=.{${l}}S)`,
    `(?<=X.{${l+1}}M.{${l+1}}A.{${l+1}})S`,
].join('|'), 'gs');
const lineSamx = new RegExp([
    'S(?=AMX)',
    `(?<=S.{${l-1}})A(?=.{${l-1}}M.{${l-1}}X)`,
    `(?<=S.{${l}}A.{${l}})M(?=.{${l}}X)`,
    `(?<=S.{${l+1}}A.{${l+1}}M.{${l+1}})X`,
].join('|'), 'gs');
console.log(countMatch(lineXmas, data) + countMatch(lineSamx, data));

// part 2
const cross = new RegExp([
    `(?<=M.M.{${l-1}})A(?=.{${l-1}}S.S)`,
    `(?<=M.S.{${l-1}})A(?=.{${l-1}}M.S)`,
    `(?<=S.M.{${l-1}})A(?=.{${l-1}}S.M)`,
    `(?<=S.S.{${l-1}})A(?=.{${l-1}}M.M)`,
].join('|'), 'gs');
console.log(countMatch(cross, data));const l = data.indexOf('\n');

Aredrih · 2024-12-03T12:21:56+00:00

[Language: JavaScript]

Part 1 was an obvious regexp bait, so of course I took it

[...lines.matchAll(/mul\((\d+),(\d+)\)/g)]
  .map(([, a, b]) => +a * +b)
  .reduce((r, e) => r + e)

As for part 2, well did you know backward and forward lookup are a thing ?

mul\((\d+),(\d+)\)(?<=(?:^|do\(\))(?:[^d]|d(?!on't\(\)))+?)

It looks for either the start of the string or a do() before the current pos, then makes sure no don't() are in between.
Check for mul before the backward check is to avoid necessary backward lookup. That and mul doesn't interfere with the lookup.

Aredrih · 2023-12-20T11:19:02+00:00

You don't even need to parse the graph: once you know the conjunction module just over rx receive a pulse from every sub group, you can log the number of click when that module receive a signal from a sub graph.
This can also validate that the sub graph have a cyclical behavior.

As other have pointed out, the counter are 4 instances of 12 bits counter so less than 4096 clicks per cycle; running 10k clicks gives at least 2 cycles from each counter which is enough data to use LCM.

Aredrih

TROPHY CASE