ShareMyScreen/AdventOfCode/2022/12/HillClimbingAlgorithm

The Problem << >>

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.