# 2022 Day 12: Hill Climbing Algorithm

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.

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.

1 Like

I lost time on that, tooā¦

1 Like

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

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............
................................................................................................................................................^<<<<<<<<<<............
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................
.......................................................................................................................................................................
``````

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<..............
..........................................................................................................................................^<<<<<<<...............
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
.................................................................................................................................................................
``````

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.

1 Like

Thatās a clever way to handle Part 2!

1 Like

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.

5 Likes

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

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

2 Likes