2022 Day 12: Hill Climbing Algorithm

cantanima · December 12, 2022, 8:47am

Big-time spoilers that would have helped me finish a lot sooner. Most are available elsewhere; e.g., the subreddit.

I made the mistake of thinking about it briefly and concluding that BFS would take longer than DFS. Then, when DFS took a ridiculously long time, I tried to optimize it, optimized it badly, and ended up getting the wrong answer.
Read the problem carefully: you can go up only one level, but you can go down any number of levels.
For part 2, start from the end and look for any a position… but remember that going backwards means that the test for a good next step is essentially reversed.

rommudoh · December 12, 2022, 8:52am

Most time wasted for misreading “at most one higher” as “at most differ by one”

I implemented a basic Dijkstra algorithm for this one. Part 2 by brute force checking distance for every possible start candidate.

cantanima · December 12, 2022, 8:58am

I lost time on that, too…

rommudoh · December 12, 2022, 9:53am

Just had an Idea while going on a walk on how to optimize my brute force attempt for part 2, and came up with a simpler solution. sometimes fresh air helps thinking

rommudoh · December 12, 2022, 10:51am

Another update, I added a procedure for printing the calculated path.

Test Data, Part 1 differs from the example path, but there might just be multiple valid solutions:

>v.v<<<<
.v.vv<<^
.v.v>E^^
.>v>>>^^
..>>>>>^

and here the output for the test data for part 2:

...v<<<<
...vv<<^
...v>E^^
.>v>>>^^
>^>>>>>^

And the real data part 1:

............................................>>>>>>>>>>v................................................................................................................
............................................^.........>>v....................................................................................>>>>>>>>>v................
............................................^...........>>v..............................................................................>>>>^........>v...............
..........................................>>^.............v.........................................................................>>>>>^.............>>v.............
.........................................>^...............v.......................................................................>>^....................v.............
........................................>^................>v......................................................................^......................v.............
........................................^..................v.........................................................>>>>>>>>>>>>>^......................v.............
......................................>>^..................>v................................>>>>>>>>>>>>>>>>>>>>>>>>^...................................>v............
....................................>>^.....................v...............................>^...................................................>>>>>>>v.>v...........
...................................>^.......................>v..............................^...................................................>^......>v.v...........
...................................^.........................>>>v...........................^.................................................>>^........v.v...........
...................................^............................>>>v........................^........................................>>>>>>>>>^>>>>>>>>v.v.>v..........
..............................>>>>>^...............................>v.......................^........................................^..>>>>>>>^.......>vv..v..........
.............................>^.....................................v....................>>>^........................................^..^...............vv..>>>v.......
............................>^......................................>v...................^...........................................^..^.>>>>>>>>>>>v..v>v....v.......
.....................>>>>>>>^........................................v...................^...........................................^..^.^..........v..v.>v...v.......
....................>^...............................................v...................^...........................................^..^.^..........v..>v.>>v.>>v.....
....................^................................................>>>>v...............^...........................................^..^.^..........v...v...v...v.....
....................^....................................................v..............>^...........................................^..^.^..........>>>v>v..>v..v.....
....................^....................................................>>>>>v........>^............................................^..^.^.............v.>v..v..v.....
>>>>>>>>>>>>>>>>>>>>^.........................................................>>>>>>>>>^.............................................^..^.^......E......v..v..v..v.....
.....................................................................................................................................^..^.^......^.....v<..v..v..v.....
.....................................................................................................................................^..^.^..>>>>^....v<..v<..v..v.....
.....................................................................................................................................^..^.^..^<.......v..v<..v<.v<.....
.....................................................................................................................................^..^.^...^<<....v<..v..v<..v......
.....................................................................................................................................^..^.^<....^<..v<..v<..v...v......
.....................................................................................................................................^..^..^.....^<<<..v<..v<.v<<......
.....................................................................................................................................^..^<.^<..........v..v<..v........
.....................................................................................................................................^<..^<.^<<<<<.....v..v..v<........
......................................................................................................................................^...^<<<<<.^<<<<<<.v<v<<.........
......................................................................................................................................^<.......^<........v.v...........
.......................................................................................................................................^<<<.....^.......v<v<...........
..........................................................................................................................................^<....^<<<<<<<<v<............
...........................................................................................................................................^<<<<<........v.............
................................................................................................................................................^.......v<.............
................................................................................................................................................^<<<<<<<<..............
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................

Part 2:

............................................>>>>>>>v...................................................................................................................
..........................................>>^......v.........................................................................................>>>>>>>>>>>v..............
........................................>>^........>v........................................................................................^..........v..............
........................................^...........>>>>>v...................................................................................^..........v..............
........................................^................v..............................................................................>>>>>^..........v..............
........................................^................>>v...........................................................................>^...............>v.............
........................................^..................v.......................................................>>>>>>>>>>>>>>>>>>>>^.................>v............
.......................................>^..................>>>>>>>>>>v.......................>>>>>>>>>>>>>>>>>>>>>>^......................................v............
.......................................^.............................>v.....................>^...................................................>>>>>>>v.v............
.......................................^..............................v.....................^...................................................>^......>v>v...........
......................................>^..............................>>v...................^.................................................>>^........v.v...........
......................................^.................................>>v.................^........................................>>>>>>>>>^>>>>>>>>v.v.v...........
......................................^...................................v.................^........................................^..>>>>>>>^.......>vv.>v..........
>>>>>>>>>>>>>>>>>>>v................>>^...................................v.............>>>>^........................................^..^...............vv..>v.........
...................>>>>>>>>>>>>>>>>>^.....................................>v............^............................................^..^.>>>>>>>>>>>v..v>v..>>v.......
...........................................................................v............^............................................^..^.^..........v..v.>v...>v......
...........................................................................>>>v.........^............................................^..^.^..........v..>v.>>v..v......
..............................................................................v.........^............................................^..^.^..........v...v...v..v......
..............................................................................v........>^............................................^..^.^..........>>>v>v..>v.>v.....
..............................................................................>>>v....>^.............................................^..^.^.............v.>v..v..v.....
.................................................................................>>>>>^..............................................^..^.^......E......v..v..v..v.....
.....................................................................................................................................^..^.^......^.....v<..v..v..v.....
.....................................................................................................................................^..^.^..>>>>^....v<..v<..v..v.....
.....................................................................................................................................^..^.^..^<.......v..v<..v<..v.....
.....................................................................................................................................^..^.^...^<<....v<..v..v<...v.....
.....................................................................................................................................^..^.^<....^<..v<..v<..v...v<.....
.....................................................................................................................................^..^..^.....^<<<..v<..v<..v<......
.....................................................................................................................................^..^<.^<..........v..v<.v<<.......
.....................................................................................................................................^<..^<.^<<<<<.....v..v..v.........
......................................................................................................................................^...^<<<<<.^<<<<<<.v<.v<.........
......................................................................................................................................^<.......^<........v.v<..........
.......................................................................................................................................^<<<.....^.......v<.v...........
..........................................................................................................................................^<....^<<<<<<<<..v...........
...........................................................................................................................................^<<<<<.........v<...........
................................................................................................................................................^.........v............
................................................................................................................................................^<<<<<<<<<<............
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................

cantanima · December 12, 2022, 1:26pm

I have yet a different route for the example input. I think it’s related to how one enqueues.

Example

Part 1

v..v<<<<
>v.vv<<^
.v.v>E^^
.>v>>>^^
..>>>>>^

Part 2

...v<<<<
...vv<<^
...v>E^^
.>v>>>^^
>^>>>>>^

Puzzle

Part 1

.................................................................................................................................................................
..............................................................................................................................>>>>>>>>>>>>>v.....................
..............................................................................................................................^............>v....................
..............................................................................................................................^.............>>>>v................
..............................................................................................................................^.................v................
..............................................................................................................................^.................>>v..............
...........................................................................................................................>>>^...................>v.............
...........................................................................................................................^.......................>v............
.........................................................................................................................>>^............>>>>>>>>>v..v............
.........................................................................................................................^........>>>>>>^........>v.>v...........
.........................................................................................................................^......>>^...............v..v...........
.........................................................................................................................^.....>^........>>>>>>>v.>v.v...........
.........................................................................................................................^.....^..>>>>>>>^......>v.v.>v..........
.........................................................................................................................^.....^..^..............v.v..>v.........
.....................................................................................................................>>>>^.....^..^..>>>>>>>>>>v.v.>v..v.........
................................>>>>>>>>v......>>v................................................................>>>^.........^..^..^.........v.v..>v.>>v.......
..............................>>^.......>>>>>>>^.>v...............................................................^............^..^..^.........v.v...>v..>v......
..............................^...................>>>>>>>>>>v.....................................................^............^..^..^.........v.>>v..>v..v......
..............................^.............................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>v...................^............^..^..^.........>>v.>v..>v.>v.....
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>^...............................................................>>v.............>>>>^............^..^..^...........>v.>v..v..v.....
^...............................................................................................>>>>>>>>>>>>>>^................^..^..^.....E......v..v..v..v.....
...............................................................................................................................^..^.>^..>>>^......v..v..v..v.....
...............................................................................................................................^..^.^...^........v<..v..v..v.....
...............................................................................................................................^..^.^...^.......v<..v<..v..v.....
...............................................................................................................................^..^.^...^<<<...v<..v<...v..v.....
...............................................................................................................................^..^.^<.....^...v..v<..v<<.v<.....
...............................................................................................................................^..^..^<<<<<^<<<<.v<..v<..v<......
...............................................................................................................................^..^<......^<.....v..v<..v<.......
...............................................................................................................................^<..^<......^.....v..v..v<........
................................................................................................................................^...^<<<<<.^<<<<<<.v<.v<.........
................................................................................................................................^<.......^<<.......v..v..........
.................................................................................................................................^<<<<<<...^<.....v<.v<..........
.......................................................................................................................................^<<..^<<<<<<..v...........
.........................................................................................................................................^<<........v<...........
...........................................................................................................................................^<.......v............
............................................................................................................................................^<<<<<<<<............
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................

Part 2

.................................................................................................................................................................
.......................................................................................................................................>>>>>>>>>>>>>>>v..........
.......................................................................................................................................^..............v..........
.......................................................................................................................................^..............v..........
.......................................................................................................................................^..............v..........
.......................................................................................................................................^..............v..........
.......................................................................................................................................^..............v..........
....................................................................................................................................>>>^..............v..........
.................................................................................................................................>>>^.......>>>>>>>v..v..........
..........................................................................................................................>>>>>>>^........>>^......v..v..........
..........................................................................................................................^.............>>^........>v.>v.........
..........................................................................................................................^......>>>>>>>^..>>>>>>v..v..v.........
..........................................................................................................................^.....>^........>^.....>v.v..>v........
..........................................................................................................................^.....^..>>>>>>>^.......v.>v..v........
..........................................................................................................................^.....^..^.......>>>>>v.v..>v.>>v......
.....................................>>>>>>>v..>>>>v......................................................................^.....^.>^.>>>>>>^....v.>v..v...>v.....
..................................>>>^......>>>^...v......................................................................^.....^.^..^..........v..>v.>>v..v.....
..................................^................>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>v................................^.....^.^..^..........v...>v..v..v.....
..................................^......................................................>>>>>>>>>>>>>>>>>>v...........>>>^.....^.^..^..........>>v..v..v..v.....
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>^........................................................................v.........>>^........^.^..^............v..v..v..v.....
...........................................................................................................>>>>>>>>>>^..........^.^..^.....E......v..v..v..v.....
................................................................................................................................^.^..^.....^.....v<..v..v..v.....
................................................................................................................................^.^..^.....^...v<<..v<..v..v.....
...............................................................................................................................>^.^.>^..>>>^...v..v<<..v<.v<.....
...............................................................................................................................^..^.^...^......v.v<..v<<..v......
...............................................................................................................................^..^.^...^<<<.v<<v<..v<...v<......
...............................................................................................................................^..^.^......^<<..v..v<..v<<.......
...............................................................................................................................^..^.^<..........v.v<..v<.........
...............................................................................................................................^..^..^<<<<<.....v.v..v<..........
...............................................................................................................................^..^.......^<<<<<<.v..v...........
...............................................................................................................................^..^<<<<<<........v<.v<...........
...............................................................................................................................^<.......^<<.....v<..v............
................................................................................................................................^<<<......^<<<<<<..v<............
...................................................................................................................................^<<<<<.........v<.............
........................................................................................................................................^<<......v<..............
..........................................................................................................................................^<<<<<<<...............
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................

wutka · December 12, 2022, 4:46pm

After getting both A & B correct by using a shortest path algorithm, I think it’s was just Dijkstra’s, I realized that it would be better to just do the distance algorithm once and calculate the distance from the end point to every point in the grid (so instead of stopping when I hit a target, I stop when there are no more places to visit). The old way too 0.278 seconds of CPU time, the new way took 0.004.

Than I folded the best start search into the dijkstra routine to compute the best start as I am finding the distances. No real difference in execution times, but does save a couple of loops.

cantanima · December 12, 2022, 7:10pm

That’s a clever way to handle Part 2!

zertovitch · December 12, 2022, 8:30pm

For part 2 I have set the point E as a start, reversed the rule for climbing and set the stop criterion in Dijkstra’s algorithm as "reached a point with ‘a’ ".

The data is as fascinating as the problem IMHO, with many traps…

Here is a visualisation of the results.

S: the green dot.
E: the blue dot.
The pink dot is the best alternative starting position with elevation ‘a’.
The yellow-tainted path is part 1’s path, the pink-tainted path is part 2’s.
The red-tainted pair of pixels marks a place where the climber falls a bit on his way to the top.

cantanima · December 13, 2022, 8:52am

I really love this and have to sit down and do this with my own solution at some point.

cantanima · December 14, 2022, 8:36pm

Finally had a chance to take care of it! Couldn’t quite match your colors, but I didn’t try that hard, either.