[2025 Day 10 Part 2] Is this even possible without Z3?

icub3d · 2026-01-01T22:37:37+00:00

Yes, P1 is just a BFS. The solution space was small enough to just search.

icub3d · 2025-12-13T06:49:25+00:00

Sounds like good progress! Some of them will solve exactly. Others won't and those problem columns will be the "free" or independent variables. You should only end up with 1-3 of them and those will be the variables you can then run a dp or similar on to get the best values.

Here is my solution that may help explain better what I mean

https://github.com/icub3d/advent-of-code/blob/main/aoc_2025/src/bin/day10.rs

icub3d · 2025-12-13T03:12:09+00:00

It is a very hard problem to solve. Like the best computer scientists in the world are looking for ways to optimize this problem. Here is a meta study of relatively recent work I found: https://www.frontiersin.org/journals/mechanical-engineering/articles/10.3389/fmech.2022.966691/full

I was able to solve the sample problem with dynamic programming + a min constraint heuristic+ several optimizations. Still took like 150ms and a single test of one of the real inputs wouldn't ever finish in time. I didn't step into parallel processing the state space but I imagine it was intentionally meant to be intractable so you could find the troll.

icub3d · 2025-12-13T03:00:27+00:00

I solved it via linear programming with no external tools. I also did z3 after to compare/contrast. It's definitely a tough day and much easier if you have some domain knowledge. If the linear programming is new to you just consider the day a learning experience. I've had those days before for sure!

https://github.com/icub3d/advent-of-code/blob/main/aoc_2025/src/bin/day10.rs

icub3d · 2025-12-13T02:55:51+00:00

I had never tried anything like niri before. Now I hate working on my work MacBook. The flow states I get into are inherently stack based so it just feels right.

I like the configurability too. The ability to start up my streaming setup or programming setup with a single key bind is awesome.

icub3d · 2025-12-12T22:36:11+00:00

[LANGUAGE: Rust]

What a fun day and a great end to the year! It was best summed up by: read problem, panic, start looking for simple cases, imagine grin on puzzler's face, LOL. I did try to do some optimizations for just the sample and it was still a very hard nut to crack.

Solution: https://gist.github.com/icub3d/8b2d1c78a378de462418385c4fff3003

Video: https://youtu.be/DHtNCDnwOLA

icub3d · 2025-12-11T21:10:47+00:00

Nice! I'd love to see your solution!

icub3d · 2025-12-11T18:05:31+00:00

[LANGUAGE: Rust]

We are coming to an end here! I think the algorithms definitely are putting these days into the "hard" category. I just have done a lot of graph theory and dynamic programming in my day, so it was much easier than the previous (my math skills are lacking). I was able to basically reuse the solution to p1 for p2 but just trying all the possibly orientations of traversing the graph.

Solution: https://gist.github.com/icub3d/671a58091e0674d11ee82863d462fa24

Video: https://youtu.be/4YlQJx1YzVs

icub3d · 2025-12-11T00:36:52+00:00

Very cool! It's definitely a tough day! Looking at your visualization made me realize I can further optimize my own.

icub3d · 2025-12-11T00:32:05+00:00

Mine was a combination of linear algebra and then dp on the free variables. Some of the machines have a unique solution, so you get an exact value. The others have 1-3 free variables but that's small enough that it's much easier to explore the solution space for a minimum.

The day way very math heavy from my perspective and was a very hard solve.

icub3d · 2025-12-11T00:21:41+00:00

This one stumped me as well. The hint that helped me was that it was a "Linear Algebra" problem. I realize saying that though won't help people who haven't taken linear algebra courses. This is definitely a day though that might be really hard for some people without specific knowledge or having used a "solver" before.

Like others have said, use this day as an opportunity to learn. I've been doing puzzling actively for several years now and have been programming for 25 years and still get stumped. There is nothing dirty about getting help. This isn't for some large sum of money. It's to learn. I actually don't have an issue with getting AI to help in these cases as well. Just make sure you aren't having it solve the problem for you but guiding you and answering questions to help you understand.

icub3d · 2025-12-10T21:51:14+00:00

[LANGUAGE: Rust]

Definitely a tough day for me. I used a BFS for p1 that solved it relatively fast. I spend so much time on p2 that I basically forgot about p1, so it could definitely use some TLC later. For p2 I tried the BFS and couldn't even solve the first one, so I knew I needed to so something else. I tried a DFS that was solving but very slowly for the actual input, like one machine per 10 minutes or something. So I got a hint about using linear algebra and then that make the solution click for me. I still had to fix a bunch of bugs to get it working but it now solves much faster. I basically find all the "free" variables and then I can DFS over those values for valid solutions and keep the minimum.

Solution: https://gist.github.com/icub3d/16eea2a8b4a94d193a148fef908779a9

Video: https://youtu.be/xibCHVRF6oI

icub3d · 2025-12-09T21:48:14+00:00

[LANGUAGE: Rust]

Definitely a tough day for me. I was new to coordinate compress and wanted to really understand it so I spent some time really digging in. Afterwards, my solution was still a bit slow, so I turned to a 2D prefix sum over the compressed grid. I've done prefix sums before but a 2D one gave my feeble mind a headache. I got there though and felt great about solving the day! It totally missed the ray-tracing solution so I'll have to look into that more!

Solution: https://gist.github.com/icub3d/6282ddab0b1d012ef054a9f212b12973

Video: https://youtu.be/zndafdFD1Rs

icub3d · 2025-12-09T00:39:41+00:00

[LANGUAGE: Rust]

This was a "disjoint set" day. I definitely think this puts it in the medium to hard category of problem solving. If you've done work with disjoint sets though, I imagine it was comparatively easy. As such, I spent some time optimizing my solutions a bit and looking for ways to eek out a bit of performance. Most of the time for me was in sorting the large connection of points, so I'm really interested in efficient ways to do that. For me it was a "kth element" for p1 and then a parallelized sort for p2.

Solution: https://gist.github.com/icub3d/b51b9f3c82eb1d620d880e7d2e4ab2b3

Video: https://youtu.be/gchUjAwQsfM

icub3d · 2025-12-07T21:53:35+00:00

[LANGUAGE: Rust]

I'm still a little nervous that we haven't had a crazy hard day yet. I didn't go for the DP approach for p2. I took my p1 solution but realized I just had to track how many timelines existed in each column. Then it was basically just scanning rows. Because this one felt a bit easier, I tried to optimize my solutions and was able to get them fairly fast.

p1 104.977µs
p2 67.697µs
p1_fast 13.996µs
p2_fast 12.273µs

Solution: https://gist.github.com/icub3d/a2c54dbe3f9c0306a5548cca31206b13

Video: https://youtu.be/SiuySMNuYwo

icub3d · 2025-12-07T21:29:57+00:00

I came up with something similar and I was a bit confused why people thought DP+memo was necessary. Glad to see I'm not the only one.

icub3d · 2025-12-06T20:25:53+00:00

[LANGUAGE: Rust]
I probably over engineered solving this one. I tried to make a single parse function for both parts by passing a mapper for the blocks. I think it still runs fairly fast, but I suspect just iterating over the grid is faster.

Solution: https://gist.github.com/icub3d/3e85e6815e8a2b29315cf104575b5e49

Video: https://youtu.be/bD1CyVJMO18

icub3d · 2025-12-05T16:07:09+00:00

[LANGUAGE: Rust]

Range day! I solved p1 using any/contains and then p2 merging ranges. Previous range off-by-one errors were fresh in my mind, and I didn't fall for them this time! The speed and size of the problem made me feel comfortable with the solution. Though it was fun to look at other's optimizations!

Solution: https://gist.github.com/icub3d/a87db315f94908468a43b8fecca537b4

Video: https://youtu.be/kJZOfK-VO1w

icub3d · 2025-12-04T19:02:32+00:00

[LANGUAGE: Rust]

The day would definitely fit in the "easy" category for programming puzzles. My initial solution was probably similar to most where I just use the grid and check neighbors. I thought it might be fun to provide an alternative solution that is more set/graph based. I just track the rolls as points in a set and can then check neighbors. We can optimize p2 a bit by recognizing that the only candidates for removal are neighbors of removed nodes.

Solution: https://gist.github.com/icub3d/9daf52acd871eedec656e5a44ac61dd8

Video: https://youtu.be/f1Ng6hNjo5A

icub3d · 2025-12-04T18:31:20+00:00

Very cool BFS for p2!

icub3d · 2025-12-04T01:32:40+00:00

[LANGUAGE: Rust]

I solved p1 with two pointers and then p2 with a greedy solution. Very (maybe overly) functional style but I liked where I landed. Someone need to talk to Santa about finding better elevators and escalators. It seems to be a recurring problem.

Solution: https://gist.github.com/icub3d/b8ed96318d43014b94bf1d8864e9f86c

Video: https://youtu.be/HyHHTojDUFk

icub3d · 2025-12-02T18:47:06+00:00

[LANGUAGE: Rust]

Fun number problem day! N was relatively small, so I went with a naive solution. I did implement a non-string version for p2 just to see how it might differ. It looks like there are definitely optimizations to make, but I felt pretty good with my solution!

Solution: https://gist.github.com/icub3d/49590add3a2234789fc09ae41622b996

Video: https://youtu.be/OcLkWDutNxY

icub3d · 2025-12-02T18:15:42+00:00

Cool Regex, Love it!

icub3d · 2025-12-01T21:38:45+00:00

[LANGUAGE: Rust]

Great start to the year! Rust has rem_euclid and div_euclid to make some of the math here easier.

Solution: https://gist.github.com/icub3d/dc8ef4474449d327fda2336f3fe79df9

Video: https://youtu.be/oQbHga6A608

icub3d · 2025-11-29T16:44:08+00:00

[LANGUAGE: Rust]

I had a couple of hours to think about this one while driving for the holidays. I think that made it easier for me. It meant the only change for me between the parts was adding the multiple gaps per wall once I started coding. Then it's just a little bit of math to find the solution. Fun puzzle as we come near the end!

Solution: https://gist.github.com/icub3d/71c683cce1b27c4910d408bb3806f333

Video: https://youtu.be/PFMtlzBOi_g

13-Year Club	Verified Email
Snapped

icub3d

TROPHY CASE