ShareMyScreen/AdventOfCode/2022/12/HillClimbingAlgorithm
A maze follower. I take a peek at my input and see that it's not huge, so any algorithm should be OK. This problem has no notion of distance, so I will simply start a brushfire at the startpoint and keep track of when it gets to each other point.
I will use
- the map of the terrain
- a table giving the step number at which the fire reached each cell
- the frontier: the cells that were first touched in the previous step
At each step, I will examine the cells neighboring the frontier and update them if they can be reached by a legal move. When the fire has reached the goal, I stop. I could reconstruct a path from start to end using the step-number table but I haven't been asked for that.
Since I must examine the neighbors of the frontier cells, and they might be on the edge of the map, I will add a fringe to the map and step-number table to save testing for the edge case.
I'll read the input.
alp =. 'SabcdefghijklmnopqrstuvwxyzE' map =: alp i. ] onaoclines ]frontier =: ,: ($ #: 0 i.~ ,) map NB. (row,col) of the startpoint, as a table ]steptbl =: _1 ,~ _1 ,"1~ 0 frontier} ($map) $ 1e6 NB. Init to high value (i. e. unvisited) but 0 at startpoint and _1 around the fringe ]map =: 100 ,~ 100 ,"1~ 1 frontier} map NB. move S to elevation a, add fringe
The ($ #: 0 i.~ ,) map is a standard J idiom for finding a position in an array. First I run map into a list and find the 1-dimensional position of the 0; then I use #: to convert the 1-dimensional position into the index list in the array. The added ,:, which converts the list to a table, is one of those touches that you get a feel for as you become a J programmer. I know I want frontier to be a table so I make sure from the start that it is.
Now to go through the maze. I'm getting an idea of how to structure this. I will have a verb that processes one step. It will take in the frontier and produce a new frontier. If it hits the goal, it returns an empty frontier. The verb will be repeatedly called until the frontier is empty.
I write the verb. I could have a noun to hold the step number but I have a strong bias against public names.
mazestep =: {{ NB. y is the frontier, shape (n,2); result is new frontier prevstep =. (< {. y) { steptbl NB. the previous step number fronthgt =. y (<"1@[ { ]) map NB. height at each frontier point if. 27 e. fronthgt do. i. 0 2 return. end. NB. return empty frontier when we hit the E (27) newfrontier =. ,/ y +"1/ (4 2$1 0 _1 0 0 1 0 _1) NB. neighbors of the frontier, as a table nfronthgt =. newfrontier (<"1@[ { ]) map NB. height at each newfrontier point nfrontstep =. newfrontier (<"1@[ { ]) steptbl NB. step number at each newfrontier point newfrontier =. ~. newfrontier #~ (nfrontstep > prevstep) *. (nfronthgt <: 4 # >: fronthgt) NB. cull to unvisited and not too high; remove duplicates steptbl =: (>: prevstep) newfrontier} steptbl NB. mark the frontier as visited in this step newfrontier }}
x (<"1@[ { ]) y is the preferred way to fetch cells of y indexed by the table of index lists x. For +"1/ x has shape (n,2) and y has shape (4 2); the result is the addition table on 1-cells, shape (n,4 2). ,/ runs the first two axes together, leaving the shape ((4*n),2). All 4 of these heights are compared against the height of the cell in the middle. In the final update to steptbl, newfrontier, a table, contains the index lists of the cells to be overwritten.
I run the verb using the Do While construct:
mazestep^:(*@#)^:_ frontier NB. Repeat until result of mazestep is empty steptbl 0 1 2 19 18 17 16 15 _1 1 2 3 20 29 28 27 14 _1 2 3 4 21 30 31 26 13 _1 3 4 5 22 23 24 25 12 _1 4 5 6 7 8 9 10 11 _1 _1 _1 _1 _1 _1 _1 _1 _1 _1 >./ (, steptbl) -. 1e6 31
The number of steps is the largest value found in steptbl after removing any unvisited cells. As it turns out, frontier did not need to be public.
Part 2 is the rightful due of good design. All I have to do is make the initial frontier the set of cells that are 'S' or 'a', and the same program will find the shortest path starting from any of those points.
frontier =: ($ #: 0 1 I.@e.~ ,) map NB. (row,col) of the startpoint, as a table
Everything else stays the same.