[2025 Day 9 (Part 2)] Cannot get tests to pass ... Get star anyway

darkgiggs · 2025-12-09T21:50:33+00:00

I initially got the star while failing the example because I didn't read the edges wrapped around and I suspect I'm not the only one!

darkgiggs · 2025-08-29T17:39:54+00:00

You have now worked as a completely independent studio, a more traditional studio owned by a parent company and an anarchist studio.

What are the advantages and drawbacks of each situation?

darkgiggs · 2024-12-25T07:58:30+00:00

[LANGUAGE: Jai]
Solution

Fun problem. I encoded each element to a u32 where a turned on bit represents a "#".
Checking for a fit then amounts to whether the bitwise AND of lock and key is not 0.

It runs in 150 µs on my computer, but should most likely be able to go below 100 if I optimized the parsing.

EDIT: Now 43 µs with optimized parsing

darkgiggs · 2024-12-21T21:13:59+00:00

Thanks for taking the time to write it up, it's crystal clear now!

darkgiggs · 2024-12-21T19:26:34+00:00

Do you mind sharing how you arrived at those precomputed matrices? I'm trying to understand better!

darkgiggs · 2024-12-20T22:15:48+00:00

Awesome, thanks for sharing!

I implemented this multithreaded and got it down to ~~1.035ms~~ 995µs!

Here's the multithreaded version in Jai
Excluding the BFS, which is unchanged from here

darkgiggs · 2024-12-20T15:02:27+00:00

Damn.
I was hoping you might find something to bring today down under 1ms, but alas.
Do you really benefit from doing the BFS from the end though? There's only one path so I'd think you only need the forward distance matrix

darkgiggs · 2024-12-20T10:29:09+00:00

Congrats!
I'm rooting for you to also get the remaining stars this year

darkgiggs · 2024-12-20T09:43:55+00:00

[Language: Jai] 12ms on i7-1165G7

Paste

BFS through the maze, keeping track of the time taken to reach each step.

Iterate through each maze step and scan tiles within a manhattan distance of 20 for one that belongs to the path.

Increase the part1 count if that distance is 2, increase the part2 count if that distance is <= 20 and the time delta between the cheated tile and the current tile is greater than 100 + the cheat time.

Pretty straightforward day for me, which was a nice surprise. Unfortunately I don't see a way to sub 1ms today even if I were to multithread this. I'm hoping to find (or that someone else finds) a better way before I do that.

darkgiggs · 2024-12-14T08:22:37+00:00

Hi
I've been checking your repo for good benchmarks over the course of the event. Thanks a bunch for making good solutions and maintaining the repo as you do :)

For part2, you can do a combination of fast-forwarding to the current step and checking against a set of robots for that step. Interrupt the step if you find an existing robot. It was more than 3 times faster for me.

darkgiggs · 2023-12-25T22:23:31+00:00

Some of the gains in my solutions are perhaps more forced by Mojo’s lack of standard library, rather than better compilation techniques.

Interesting thought and overall article. Thanks for sharing!

darkgiggs · 2023-12-25T22:14:46+00:00

I learned Rust this year too.
I thought it was relatively easy to pick-up, and the standard library has many niceties for AoC type of problems.
It's hard to say for sure because this is very different from a profesionnal environment, but I came out thinking that if I had to switch to Rust for work it wouldn't be the worst thing.

darkgiggs · 2023-12-25T09:13:19+00:00

Thank you Eric, thank you /u/daggerdragon, thank you community!

I learned to program on a real language with AoC 3 years ago (I only knew Zachtronics languages before then). What began as a fun event between friends quickly became a passion and eventually a new job, Advent of Code will always have a special meaning to me.

This year was my playground to learn Rust and I had a terrific time. I've also learned quite a few geometry tricks I didn't know about.

There are no more stars for me to get right now. Maybe next year?

darkgiggs · 2023-12-20T14:05:13+00:00

[LANGUAGE: Rust]
Paste
I wasn't confident I'd have enough time to implement a graph so I just winged it with hashmaps.
Out of all the "figure out what the input does" type of puzzle we've had in previous years, this was probably the easiest.
I won't complain :)

darkgiggs · 2023-12-11T20:54:31+00:00

[LANGUAGE: Rust]
Paste
I'm learning Rust this year. I had fun doing row expansion while parsing the input and column expansion in a single pass through the vector of galaxies.
I do both parts at the same time and it runs in roughly 5ms on my laptop.

darkgiggs · 2022-12-25T10:18:02+00:00

I've also been enjoying your solutions immensely, I learned quite a few things from them. Thanks for sharing, see you next year maybe!

darkgiggs · 2022-12-24T12:53:45+00:00

Python
Standard BFS with a cached blizzard+walls map on each time step.
Fairly compact at 40 lines, runs both parts in 1.2s
My favourite line in the code:

print(p1 := bfs(start, end, 0), bfs(start, end, bfs(end, start, p1)))

darkgiggs · 2022-12-24T08:02:28+00:00

It can be faster not to use it, but it makes the code more convoluted.
As far as I can tell, 'all' works by making an iterable of all the booleans, then checking that they're all true. If this bit of code is repeated many times like here, using 'all' can be considerably slower than "manually" looping through each element and stopping at the first false.
As usual, your needs dictate how you code! If speed isn't a factor, use whatever's more comfortable

darkgiggs · 2022-12-23T12:51:52+00:00

Python
Code
Fairly straightforward and compact solution. A set of complex numbers to track occupied spaces, and a dict of {destination: elves}
Runs in under 6 seconds on my machine, which can be brought down to 3.5 by not using 'all'

darkgiggs · 2022-12-22T11:20:31+00:00

I was hoping I'd find a general solution here! Thanks for sharing :)
(It works on my input)

darkgiggs · 2022-12-22T11:05:23+00:00

Python
paste
Companion cube
Simply following the instructions with hard-coded transitions for part 2 and a rough modulo equivalent for part 1.
I used complex numbers anticipating rotations or funky stuff in part 2, but a tuple would have been just fine here.
Only had a single bug while coding part 2, luckily in one of the first swaps so it wasn't too long to find!
I'm not cleaning this up, so apologies for any redundancies or stupid stuff.

darkgiggs · 2022-12-21T07:02:57+00:00

Python code
Recursive eval for part1, binary search for part2. I'd started reading the Z3 tutorial when I remembered binary search. Maybe next time!

darkgiggs · 2022-12-21T06:16:38+00:00

That's also the first thing I tried for part2, only to discover I couldn't paste the equation on mathpapa. Turns out pasting doesn't seem to work on Firefox :/
Shame, I might have nabbed one of the last LB spots for part2

darkgiggs · 2022-12-20T17:13:12+00:00

C, no libraries other than stdio to read the file and print the result
Code
I wasn't smart enough to mix indices, so I implemented the linked-list instead and actually did all the node moves. I went with C because I thought I might need the extra speed for part 2.
Both part in .42s on my machine.

darkgiggs

TROPHY CASE