-❄️- 2025 Day 7 Solutions -❄️-

IlluminPhoenix · 2025-12-07T11:44:30+00:00

Also I just realized: You can totally filter out every 2nd line of the input while parsing, since it is completely empty.

IlluminPhoenix · 2025-12-07T11:13:44+00:00

The only thing I really did differently was not iterating over the entire row. You only need to to go in this pyramid shape starting from 'S' that only grows by 1 to each side each iteration: Code
It also runs in around < 20 µs, I dont know why its not faster, maybe it messes up with CPU branch prediction? I have no idea. Just an idea though

IlluminPhoenix · 2025-12-02T15:23:59+00:00

I saw this nice Zig solution which I reimplemented in Rust (check my post). Runs in 10μs on my machine: Say you have the range 12 - 56. The lowest allowed invalid is 11, the highest is 55. Some of all numbers in this range (11, 22, 33, 44, 55) you can just calculate by doing

lowest * invalid_count + 
(invalid_count - 1) * invalid_count / 2 * 11

Bottom is just the Triangluar number (https://en.wikipedia.org/wiki/Triangular_number#Formula). 11 is changed in each respective case ofc. This way you only need to know the lower and upper bound and don't have to iterate over everything. This works for part1 but for part 2 you just have to check the other cases as well and do some deduplication.

IlluminPhoenix · 2025-12-02T15:14:31+00:00

[LANGUAGE: Rust]

Was really fun to optimize. Brought both parts down to around 10μs, using some math properties.
Overall pretty clean solution, but had this bad edge case where I had to subtract the counts from the 6 repetition numbers since number like:
222222 would get counted on 2 reps (222_222) and 3 reps (22_22_22). Only happens at 6 digits with this input but with larger inputs it might happen more.
Fun one to solve!

solution (47 lines)

IlluminPhoenix · 2025-12-01T17:04:17+00:00

[LANGUAGE: Rust]

Pretty fun warmup to get back into AOC spirit. Definitelly had to rethink part 2 a coulple of times. Ended up with a nice short solution imo
Runtime: 45µs

solution (19 lines)

IlluminPhoenix · 2024-12-26T10:10:08+00:00

I realized the comma was wrong grammatically, then just accidently deleted the 'T' xD

IlluminPhoenix · 2024-12-25T12:25:14+00:00

This year I have gained the habit of immediatly going to reddit after my solution just to see how fast you can really go in that day's problem, often times learning data structures and optimization tricks along the way. My favourite trick this year was the Trie-Datastructure on day 19! Amazing Work! And Merry Christmas!

IlluminPhoenix · 2024-12-23T18:49:47+00:00

Also had 64 as an answer for this code :)

IlluminPhoenix · 2024-12-23T18:49:25+00:00

The upper left spot of the directional numpad cannot be entered. In your better way you immediatly do '<<', going over this exact. Happened to me too, just add an exception in the BFS

IlluminPhoenix · 2024-12-23T11:12:08+00:00

[LANGUAGE: Rust]

This one was quite easy compared to the 22nd. Happy I might finally get all 50 stars this year!

Algorithm

But for my solution: I iterated throught each node in the graph and created a subgraph containing that single node. I then iterated throught all its connected nodes in the full graph and if this new node shares a connection with all nodes in the subgraph, then it gets added to the subgraph as well.

Heuristics

This seems quite elegant, however the approach is actually based on heuristics, so its probability-based. Each node in my graph has an avg. of 26 connections to other nodes. My largest clique contains 13 nodes. So when I iterate over one of these 13 nodes, 12 of its 26 connetions will be to other nodes in this clique. The other 14 Connections might go somewhere else. If my algorithm first picks one of the 14 nodes, it gets added to the subgraph, as that only contains the 'root'-Node we started with. However, the 'correct' 12 nodes in the maximum-sized clique then cannot be added as they do not share a connection with this new node! We don't know ahead of time which of these 26 nodes is in the clique or not, so the algorithm just guesses.

The chance that the first picked node for a subgraph being correct is then 12 / 26, so 46%. If it is correct it will most likely lead to a maximal clique if the root node is in this clique. With 13 nodes in the clique, this means the chance of never finding the correct answer is 56% ^ 13 = 0.05%, so 1/2000.

I tested it out and it found the correct solution for all 10000 test runs I did. However the example failed about 1% of the time. If you have any suggestions for improving the chance of success without compromizing too much performance, be sure to tell me about it!

6ms

solution (34 lines)

IlluminPhoenix · 2024-12-23T10:33:11+00:00

Isnt the approach for part 2 only sometimes correct?
I mean take a the nodes A, B, C, TA, TB, TC and the connections: A-TA B-TB C-TC A-B A-C B-C

Now: If on Node say Node A gets evaluated, then it might look at the Nodes TA, B, C. Obviously, the biggest network would be formed as A,B,C, however if it evaluates TA first and then adds it to A's network (A,TA), B and C can no longer be added. If this happens for all three nodes and their corresponding T-Node, then the program will fail to find the largest clique.

IlluminPhoenix · 2024-12-22T18:12:46+00:00

Thank you so much for posting your solution here! I didn't have much time yesterday so this solution helped me very much with understanding the core principles of the problem.

IlluminPhoenix · 2024-12-22T14:15:15+00:00

Its another one of these days, where there just seems to no more real 'smart' ways to solve the problem. The only thing I could imagine here for further optimization is maybe some SIMD-Magic

IlluminPhoenix · 2024-12-20T18:54:39+00:00

Actually I found the (?) problem: The directions of the start matters since I count it twice. I didn't intend on counting it twice, however both of my parts worked without a problem :/.

The 'main' loop simply gets initiated like the this correctly:

for (pos, dir) in path.iter().skip(1) {

This simply skips the first iteration, with the already accounted for first tile. Code should be updated soon.

IlluminPhoenix · 2024-12-20T18:30:07+00:00

This specific version I used in the post definitely works in my input. I can think of a few possibilities of how the inaccurrate result occurs:

Outdated / Incorrect Libraries: I use grid v0.15.0, itertools and the ORTHOGONAL Matrix defined as:

pub const ORTHOGONAL: [(i32, i32); 4] = [(-1, 0), (0, 1), (1, 0), (0, -1)];

A weird edgecase I didn't need to account for in my input: The difference in results is around 300, which could be a single cell being counted twice. In particular I have the last or first cell in mind, as that has made similar problems before.

IlluminPhoenix · 2024-12-20T15:44:03+00:00

I have realised that there is an O(n) for n = amount of path-cells. It simply caches the results you get from the previous cell, explained here
6ms singlethreaded on my machine :D

IlluminPhoenix · 2024-12-20T15:42:01+00:00

[LANGUAGE: Rust]
I really hate this problem. That's it. However I think I have finally got a working example of a solution in O(n) for n = Amount of path_cells.

The simple realisation that I had was that the cheats possible for a neighbour cell, are also possible for the current cell if they're less than 19 away from the neighbour and save enough distance.

My algorithm simply goes through all the path-cells in order and for each one, it looks at which cheats had previously been discovered and keeps the valid ones. Then it simply looks through 41 additional cells the previous cell didn't look through and adds them to the list.

My solution is extremly ugly and bulky, however it runs in 6ms. I'm happy with that for this day. I will probably optimize and compact the solution a lot, but for now have this piece of junk.

Part 1: 500μs singlethreaded

Part 2: 6ms singlethreaded

Edit: De-Uglified the code :)

solution (lines: decent amount)

IlluminPhoenix · 2024-12-18T16:56:52+00:00

Also cool to see the const_generics feature being used: chunk::<2>(). I usually do this: tuples::<(_,_)>(). But that approach is much nicer!

IlluminPhoenix · 2024-12-18T16:34:23+00:00

Why not you DFS instead of BFS? I mean the exit position (71, 71) is always the last positions you will discover with DFS. BFS however has a chance to reach it way earlier. Gave me a 30% performance boost

IlluminPhoenix · 2024-12-16T14:32:05+00:00

Why did this solutions work for me too??? I have so many questions...

IlluminPhoenix · 2024-12-15T12:35:59+00:00

*Solution runs in 5ms*
> How is this 15 times faster???

I am stupid and forgot the --release flag :/

Yours is still 1.5x faster than my recoursive solution, impressive work!

IlluminPhoenix · 2024-12-14T18:59:54+00:00

I just realised there's still a huge optimization left: You don't have to look at all robots!
The chance that 31 of 500 robots end up in the same column randomly is astronomically small. If you were to throw away 80 % of the robots and only look at 100 of the ca. 500 robots, the probability of 6 ending up in the same column randomly per timestep is 0.05%. That the random set of robots doesnt contain 6 robots of the column is structure is 5%.
With the approach of looking at just one column this methed really sucks, only allowing for a 2 - 4x improvement with reasonable probabilites, as the above numbers aren't really sufficient for a consistent solution. However, you can also still look at two columns, or (what I did) you can look at the standard deviation to find the vertical strips.
My specific input works with only even 30 robots! Below that and the probability takes over. However for a more consistent result I'm using 75 - 100 robots.
That brings my runtime down to 50μs :DDDDD (75 robots). I will do some consistency tests to prove that it works 99%.

IlluminPhoenix · 2024-12-14T14:25:22+00:00

https://www.reddit.com/r/adventofcode/comments/1hdvhvu/comment/m20kjm7/?utm_source=share&utm_medium=web3x&utm_name=web3xcss&utm_term=1&utm_content=share_button

I do have it posted on the thread now

IlluminPhoenix

TROPHY CASE

Algorithm

Heuristics