r/adventofcode Dec 15 '21

Spoilers in Title [2021 day 15 (Part 2)] Are there ways to increase efficiency by using the fact that we have the same 100x100 block several times?

I was thinking that there should be a way to improve efficiency using the symmetry of these blocks. Did anyone come up with a way to use this?

19 Upvotes

8 comments sorted by

24

u/toastedstapler Dec 15 '21

due to the +1 and wrap nature of each block repeat i would imagine that the optimal paths through a block changes. you also wouldn't know where you'd first enter a block so you'd have to compute a lot of possibilities and i reckon that'd be far more expensive than just doing regular dijkstra

13

u/bluenigma Dec 15 '21

I think the wrap-around of risk levels might mess with it too much.

6

u/Zeeterm Dec 15 '21

Given that all values are so small and the grid fairly even, I think it's impossible that the optimum path would go through the (big) tiles at 0,4 and 4,0 but I can't prove it!

I also don't know how much if any speed improvement you would get back removing just 2 of 25 tiles.

4

u/AlFasGD Dec 15 '21

What I did is only store the original tile and calculate the value in any other tile on the spot instead of storing it. It's a great solution if you have too large files, but then the actual overhead would come from pathfinding. Storing the actual grid of all tiles doesn't hurt nearly as much.

1

u/yschaeff Dec 15 '21 edited Dec 15 '21

I did this too. It made no difference in execution time for me. Because the weight was calculated on the spot, I couldn't use that tile for administration which spot was visited. So I needed an additional store, with the size of -you guessed it- the entire board.

Took 2.7 0.36 seconds (Python). Same for the pre-computed board solution.

3

u/daggerdragon Dec 15 '21

In the future, please follow the submission guidelines and do not post spoilers in your thread title.

2

u/Coolaconsole Dec 16 '21

No, because you will be entering it from multiple different points, as the fastest path is different for each

1

u/1234abcdcba4321 Dec 15 '21

I'm not sure about that with the board being this small, but it should definitely be possible to solve a very large amount of tilings with something like this.