General Discussions
Discuss any topics that are not product-specific here.
Finally caught up on Day 12! Part 1 was incredibly quick to run... The time taken for part 2 to complete shall remain a secret other than to those that were present in the Alteryx friends & AoC virtual happy hour!
Batch macro to load in all a starts:
Iterative macro - generates possible next steps for the current tile until an end is met:
Part 1 was the same approach without the batch!
Edit: Upon reversing the logic and starting from the End - as suggested by @DavidP and others - my Part 2 actually ran in 18.6 seconds which is a whopping 1,490 times faster than my first attempt!
OK - so this took 1.5 days but it's done. Main snag was a silly logical error on part 2 where instead of running the part 1 once for each new starting point, I was running it once per each cell in each starting point.
Solution summary in spoiler below.
Algo
- Start from a specific cell (s) that you want to investigate (and remember the least cost of getting to this cell).
the first time round, this is only your S cell, and the min cost is 0
- Then figure out which cells you can potentially go to next
- Then look at these cells - if you've never been there before, or if you've now found a cheaper way of getting there than you had previously - then mark these as "good to investigate"
- Repeat from step 1
Eventually you will run out of cells to investigate, and you'll have the minimum cost of getting to every cell from the starting point.
Data Prep:
To do this - I did 2 stages of prep:
Firstly: take the puzzle input into a matrix of cells:
which looks like this:
BTW - using the cell ID instead of Row and Column comes in handy for speed.
Valid moves:
Then I wanted to figure out which were valid moves - so that during the working phase I didn't have to do this every time.
This is pretty simple - it just takes every cell; joins it to each of its neighbours and checks if the move is valid ( based on height).
This gives you a simple list of which transitions from cell X to cell Y are allowed.
So - now we know the starting point, we know which moves are valid - now we just need to do the algo above:
Although this may look kinda complex - it's actually pretty practical:
- The top input is all the cells on the map - with some of them marked as "Investigate"
- The bottom input doesn't change - it's just a list of the valid moves
- Take these "investigate" cells and go to any neighbours which are valid moves.
- if you've been there before via a different route, and this way is cheaper - then mark this neighbour for investigation next round
- if you've never been there before - same
- if this is more expensive than previous attempts - ignore this
- Join this back to the non-investigate nodes and repeat until you have nothing more to investigate
Part 2:
For part 2 I was SUPER lazy. I just looked for every cell that had an 'a' in it, and marked this as the start "S" and ran part 1. So essentially - this was just running part 1 x 1600 times with different starting points.
