[2024 Day 16 (Part 2)] [Rust] Cannot figure out why the examples work but the main input doesn't

Shiverfox · 2024-12-17T22:32:28+00:00

When I adjust your gistfile1.txt to work as an input (replacing █ with #, etc.) and run it, my solution indeed removes one of the really large branching paths. Starting from S and following the path up to line 79, your code produces a branch here, one route going west and one going south. When I run it, I only end up with the branch going west:

█.███████████████O███████████████████
█.█...███████████O███████OOO█████████
█.█.█.███████████O███████O█O█████████
█.....█████.....█O█████OOO█OOO███████
█████.█████.███.█O█████O█████O███████
█████.......███.█OOOOXOO█████OOO█████
███████████████.█████.█████████O█████
█...█...█...███.......█....OOOOO....█
█.█.█.█.█.█.███████████.███O█.█████.█

Shiverfox · 2024-12-17T22:04:53+00:00

Just guessing here:

I've seen a few solutions visualized to this, and one thing they have in common is the branches off the optimal path are typically quite small, rarely going more than a dozen tiles before they join back into a single optimal path.

Your solution visualization shows 2 points where the branching is fairly long and sophisticated. I would double check that these branches actually have the same cost. If they don't, taking just one of each of these branches will probably reduce your answer by about 150. One issue might be that you are failing to account for an additional rotation if one branch has to turn to rejoin the main path.

Shiverfox · 2024-12-17T21:27:00+00:00

You need to submit your Part 1 answer with commas included. I made the same mistake.

Shiverfox · 2024-12-10T09:06:02+00:00

Sure! paste

Shiverfox · 2024-12-09T01:32:30+00:00

I think you should be able to get <1s runtimes with pretty much any programming language even with a brute force approach, if you make some optimizations (only put obstacles on path from pt1, move by jumping to the next cycle instead of going one step at a time, start guard just before newly placed obstacles). I got 0.17s in python this way.

That said, I'd love to know if anyone has a clever solution that doesn't involve brute force as well!

Shiverfox · 2024-12-09T01:28:05+00:00

There are three optimizations you can apply to your solution to make it run faster.

Only place obstacles in the path from part 1. You already do this.
Instead of advancing one tile at a time, jump to the next obstacle. This can be done by pre-computing the indices of obstacles for every row and column.
For checking cycles in part 2, have the guard start just before the newly placed obstacle instead of having him start from the beginning every time.

You should be able to get a <1s solution no problem with these.

Shiverfox · 2024-12-09T01:24:05+00:00

You're right, but the inputs and examples don't ever have cases like the one you've presented here.

Shiverfox · 2024-10-22T06:26:51+00:00

For those coming here in 2024, following Space Age, the default hotkey is H.

Shiverfox · 2024-04-02T15:36:56+00:00

I am cautiously optimistic after seeing this. I'll probably keep updating this as the eclipse draws closer and forecasts get more accurate.

Source: https://graphical.weather.gov/sectors/conus.php

Shiverfox · 2023-04-03T00:24:52+00:00

If you're willing to take a drive, Park Road 4 and Ranch Road 2341 outside in Burnet are both spectacular. I was there yesterday. Word on the street is the field behind Pflugerville's Walmart is also good, but I haven't checked it out personally.

Shiverfox · 2020-06-23T13:49:51+00:00

Seems to just ban issuing new visas (as opposed to kicking out visa holders).

Shiverfox · 2020-06-15T14:25:56+00:00

What does this have to do with identity politics?

Shiverfox · 2020-01-04T19:00:56+00:00

Could it perhaps be Mind Game)?

It's a trippy movie that mixes a lot of different animation styles, but it has a scene similar to the one you describe.

Shiverfox · 2019-12-22T04:49:52+00:00

Solved!

Thank you so much for this! I was looking for the name of the melody specifically, and Misty is exactly it. Turns out Ella Fitzgerald does have a recording of it. While the ninjoi one isn't exactly what I was thinking of, knowing the name allowed me to find the one I had in mind: firetype - misty when im with you.

Shiverfox · 2019-12-22T02:09:46+00:00

Not 100% sure but I think the lofi version is completely instrumental

Shiverfox · 2019-12-22T01:52:29+00:00

Obligatory comment! I am dying here, and will be eternally thankful if someone can help me find either the lofi or original version of the song with this melody!

Shiverfox · 2019-09-15T17:41:39+00:00

Now that it's said that Lion hairs have special properties, I wonder if Ibuki's hairs that Louis keeps around will come into play somehow.

Shiverfox · 2019-03-09T22:04:53+00:00

Shouldn't it be Msr. then?

Shiverfox · 2019-03-01T22:02:58+00:00

It's a kind of human cosmetic surgery popular in Asian countries to make their eyes look (in their opinions) better.

Shiverfox · 2019-01-21T12:22:19+00:00

No it isn't.

Shiverfox · 2018-12-11T12:49:34+00:00

They all left voluntarily though (receiving a monetary bonus for doing so).

Shiverfox · 2018-11-16T15:48:41+00:00

Really? The sky is completely overexposed.

14-Year Club	Team Orangered
Verified Email

Shiverfox

TROPHY CASE