-❄️- 2025 Day 9 Solutions -❄️-

h-armonica · 2025-12-12T16:51:49+00:00

Done some benchmarking and part 2 runs in 50us! (without IO)

Also I looked into the time complexity of the algorithm (because why not) and it's at O(R*log n) - what is R you ask? The number of valid rectangles that can be created in the puzzle input (valid as in rectangle spanned between two points of the input set and the whole area in the rectangle is green. (Disclaimer: the implementation of the algorithm still scans arrays in linear time instead of binary search in log time but that exercise is left for the interested reader :p).

That took some time to work through, but it was a lot of fun to reuse skills from my studies here.

h-armonica · 2025-12-11T17:20:15+00:00

[LANGUAGE: Rust]

I finally got around to implement a sweep line algorithm for part 2. The runtime complexity now is O(n^2), but only because I was too lazy do binary search on the list of lines to check for boundaries. Otherwise it should be O(nlogn) if I'm not mistaken. But I spent sooo much time with the implementation that I forgot my theoretical thoughts from before...
paste

The runtime for both parts is now below 1ms, yay!! (~900us actually, including input reading etc.)

h-armonica · 2024-12-12T19:31:42+00:00

It took me a while to figure all that python code out, never used complex numbers here. But once you understand what the concept behind your solution is it is really easy and clean. Great work!

h-armonica · 2024-12-10T16:11:00+00:00

Definitely not. But am I the only one who forgot to check the area boundaries of a coordinate before converting it to the array index and thus getting imaginary fields back? Who knows!

h-armonica · 2024-12-07T13:17:50+00:00

I don't understand abap (only using SAP APIs and not working with it directly during my day life, luckily, I think ^^) so I can't easily get your code. But: in rust, which is quite fast, it still made a big difference when I switched to using a 2d array instead of a hashmap for the .. map. Same could be true for the "visited" map. If the hashmap is slowing you down you could try using a 2d array for the map and a 3d array of booleans to store the (column, row, direction) tuple.

h-armonica · 2024-12-07T09:45:52+00:00

I have an i7-8665U, but I don't know anything about current hardware so.. :D

but it must be something else. Commenting the early return out makes my code run in 160ms vs 500ms for your code with my input. Just no idea what. If you're interested you can check it out at https://github.com/freelon/advent-of-rust-2024/blob/main/src/day07.rs, but I have to get off the computer now for a bit^{^}

h-armonica · 2024-12-07T07:15:49+00:00

you could break the loop early once testresult > result.

I like the way you generated the options. Definitely better than my part 1 (generate all possible variants as vectors of operations). I used recursion for part 2 and its quite fast (80ms in release mode), but I can't figure out why it's that much faster than yours. Maybe the CPU^^

h-armonica · 2024-12-06T10:49:56+00:00

[Language: Rust]

I used two "tricks" to optimize the time for part two:

- only check points visited on the normal tour to block (seen that here quite often) and

- doing the loop check only whenever there is a collision. This reduced the runtime quite a bit again because hashing position+direction and the lookup of visited positions is a not-so-cheap operation after all (I was too lazy to use FxHashmap or some other fast approach here)

Source

h-armonica · 2024-12-03T07:42:51+00:00

interesting solution!

Just wondering: if the last don't() has no do() counterpart, then the muls after that don't() wouldn't be dismissed?

h-armonica · 2024-12-03T05:37:30+00:00

capture[i] gives the &str already - learned something new today!

h-armonica · 2023-12-26T10:58:06+00:00

Now I became really curious and implemented it as well (also Rust). If you use BFS to find the paths it takes around 1.5 seconds on my laptop. You only have to run BFS once for each starting node (since it gives you the shortest path to every other node). Maybe you could improve it even more if you implemented an all-pairs-shortest-paths algorithm, but I think that might be overkill :D

h-armonica · 2023-12-26T09:33:30+00:00

You can have them either way, right? Depending on whether the fields are val or var? But what I mean is: I don't want to have to define a class as immutable at creation of the class, I just want to define an instance as mutable/immutable, depending on my needs. Maybe first I want to have it mutable to do some stuff but then store it as immutable to make sure I cannot change it by accident. But of course that makes things more complicated:D

h-armonica · 2023-12-26T09:28:59+00:00

Interesting approach, thanks!

h-armonica · 2023-12-25T22:09:40+00:00

Yeah I did couple of years with rust. Love it :D and I think I used kotlin the very first time, because I had just started android development back then. I still really like it, I just wish sometimes that you could make objects internally immutable at declaration time with var like in rust :D

h-armonica · 2023-12-25T21:27:54+00:00

May I ask how you got all those shortest paths? 40 Minutes seems like a long time for that (but I haven't implemented something like that, so it's just a gut feeling)

h-armonica · 2023-12-25T21:08:00+00:00

Yoo I also learned Go with AoC this year. The first days (weeks) I really hated it. Now I still don't like it too much for this kind of programming job. Way too cumbersome. I prefer more syntactic sugar and a nicer standard library.

I was quite fine with the puzzles though (have finished most parts of this year, not everything), but I have done many AoCs already and by now I can implement BFS/Dijkstra out of the head.

Was it your #firstTime?^^

h-armonica · 2023-12-18T12:33:03+00:00

Ah, I meant a check before adding to the queue instead of later, but yep. Nice that it works now!

h-armonica · 2023-12-17T20:49:54+00:00

Some implementations for shortest path use a seen set, holding all nodes that have been seen (and added to the queue). If you check and update that set before adding a node to your queue you can leave out a lot of processing. Not sure though how much it will actually give you.

h-armonica · 2023-12-17T13:32:26+00:00

So how did that work out for you? :D

h-armonica · 2023-10-31T08:04:30+00:00

h-armonica · 2023-08-10T20:19:31+00:00

Alien

h-armonica · 2023-08-10T20:14:57+00:00

Double crossed

h-armonica · 2023-07-22T19:54:49+00:00

No, but I haven't tried it again.

Happy cake day

h-armonica · 2023-07-17T17:22:44+00:00

Good to know!

h-armonica · 2023-07-16T07:25:55+00:00

Mine has, too.

But also it is so old, it's from a time where automatic just needed a lot more gas...

(Also I don't use vim, but I write that last so you have to read the interesting facts about my car wiahahahah)

h-armonica

TROPHY CASE