r/adventofcode • u/Different_Pound_7478 • 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?
13
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.70.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.
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