ShareMyScreen/AdventOfCode/2022/12/HillClimbingAlgorithmJP
Entire solution
i12=: freads '12.txt'
NB. parse input: return start;end;field, (start and end being linear indices)
par=: [: ((0 27 <@i.&1@:="0 _ ,) (,<) (1>.26<.])) ('S',(~.tolower Alpha_j_),'E')&i. ;._2
NB. Part 1: find length of shortest path S-E
shifth =: , ,~ ((0,+.0j1^i.4) ,@(|.!._1) i.@$) NB. shift in 1+4 directions, append height
neigh =: [: ; <@({.,. _1 -.~ }.@}:)"1@|: NB. boxed 5-connected neighbor pairs
one =: ({: (] #~ 1>:(-/"1)@:{~) neigh)@shifth NB. ones (in adjacency mat)
bfs =: {{ NB. bfs goes backwards, from e to closest index in s; x: s;end ;y: height matrix
's e' =. x NB. start end
'p c' =. (|:one y) NB. parents, children
gn =. (c #~ p&e.) NB. verb: get reachable neighbors for any index in y
it=. 0 NB. at each it, also path length (1 it= 1 step)
rr=. ,e NB. reachable initially only E
while. -.+./ s e.~ rr do. NB. none of start not reachable
it=. >: it [ rr=. gn rr
end.
}}
part1=: (}: bfs >@{:)@par NB. bfs@par
NB. Part 2: find location at lowest level closest to E
addas =: 1&{ ,~ {. (,I.@(=<./)@,)&.> {: NB. add all a's to start positions
part2=:(addas bfs >@{:)@par
(part1;part2)i12
Parsing
Lets work with the test data, which gives elevation values as letters (to paste and execute things from the clipboard in jQT, use F8 after copying):
tst=:{{)n
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
}}
The aim of part 1 is finding the shortest way from start square S to end square E, taking steps going up by a maximum of 1 (but could go down as far as wanted).
For starting the problem I convert the letters to heights, and find the start and end square. For this, I create a verb that first converts to numbers, then uses those numbers to get the elevations and the indices of the start and end. As usual, I started experimenting in the terminal, gradually building up par as written above, but for explaining, I will take it apart as follows:
par=: [: (inds (,<) elev) tonum
For each line, I look up the letters in the list 'SabcdefghijklmnopqrstuvwxyzE' (which, seeing it now would have been only marginally longer than my wording below):
tonum=: ('S',(~.tolower Alpha_j_),'E')&i. ;._2 NB. Alpha_j_ is A-Z,a-z
Finding the indices of S and E is simply finding where the result of tonum is 0 and 27:
inds =: 0 27 <@i.&1@:="0 _ ,
I decided to use linear indices (i.e. indices in the raveled version of the input), since the coordinates themselves are not really needed later on. This will speed up matters considerably. Not that it really matters here, but I used i.&1@:= to trigger a special combination, in this case a fast list operation (FLO). This stops comparing items when a match is found. Lastly I box the indices individually (due to the rank "0 _) because it will come in handy later (could be my initial solution did not box them).
Last step: the problem poses that S and E are respectively at elevation a and z. In the result of tonum, this is not yet the case, S is 0, while a is 1, and E is 27 where z is 26. Elev takes care of this: It clamps all values between 1 and 26, forcing S and E to be at 1 and 26. Subtracting 1 to make a correspond to elevation 0 is not needed, since only relative heights matter.
elev=: 1>.26<.]
So now, using par on tst gets us:
par tst
┌─┬──┬────────────────────┐
│0│21│1 1 2 17 16 15 14 13│
│ │ │1 2 3 18 25 24 24 12│
│ │ │1 3 3 19 26 26 24 11│
│ │ │1 3 3 20 21 22 23 10│
│ │ │1 2 4 5 6 7 8 9│
└─┴──┴────────────────────┘
(}: ({,)&> {:)par tst NB. S and E indices looked up in raveled elevation field.
1 26
Part 1
My first thought was: "I know this, there's an essay on this stuff", so I looked up the essay on the Floyd-Warshall algorithm. It iteratively calculates a distance matrix between every pair of points. Though when trying to do so, it was quickly clear that the solutions of that essay were too general and thus too slow: I don't need the distances between every pair of points!
What I was after, and failed to remember properly, was Dijkstra's algorithm, which finds the distance between a source point and a destination point.
The variant I initially wrote worked from S to E, but I rewrote it the other way around such that part 2 would be easier to implement (The only changes required were to adapt the "one" verb to define the elevation based filter of the steps in the other way, i.e. allowing decending max 1, rather than ascending max 1, and to bfs to swap end and start, and swap start and end in "bfs").
For this we need to know the neighbours of each point in four directions. This is actually the first time I realised that for this kind of problem, I do not need to work with the coordinates explicitly, and can just work with linear indices. I think this speeds up calculations a lot.
For knowing the possible moves, first we have to find the 4 neighbors that are adjacent:
shifth =: , ,~ ((0,+.0j1^i.4) ,@(|.!._1) i.@$) NB. shift in 1+4 directions, append height
This verb takes the elevation array, and creates an index array the same shape as the elevation array. The directions to shift in are on the left, 0 0 and all one step directions, conveniently derived with powers of the complex number 0j1 (or 0+1i). ,@(|.!._1) rotates the index array by the directions on the left, padding with _1 and linerises those, resulting in a 5 x #points array. Lastly I append the elevations for each element as a last row, because I'll need it when selecting which of the neighbours on the 2D map are actually reachable destinations.
As the shifth verb was getting almost as wide as my phone screen, and I need to use the elevations in determining the actually reachable neighbours, I chose to do further filtering in two verbs: "neigh" eliminates padding as neighbours, and "one" selects reachable neighbours (which happen to be ones in the adjacency matrix, hence the name).
In shiftb's output, each column corresponds to the possible neighbours of a single point. Now, I'd like to get a list of each pair of parent (i.e. every index) and child (i.e. neighbour) nodes. I don't need them boxed so I can run them all together after creation (Note opening directly after boxing at rank 1 makes again use of a special combination).
NB. raze par ,. rem pad child for each point (discarding elevations)
neigh =: [: ; <@({. ,. _1 -.~ }.@}:)"1@|:
Now that we have possible candidates, selecting only those who are at most one unit lower (remember we're going backwards) than the parent:
one =: ({: (] #~ 1>:(-/"1)@:{~) neigh)@shifth NB. ones (in adjacency mat)
This verb one puts it all together: it takes the elevation field on the right, and uses shifth to get rows of own index, candidates (4x) and elevation. The fork on the left gives the middle verb the elevations on the left, and the list of neighbours on the right. Based on those, the middle tine filters the neighbours, where the elevation of the parent minus the elevation of the child is less than one, i.e. the step down is max 1 (as we're going backwards). The eventual result is a list of allowable moves to go from E to S.
Due to all this preparation I managed to perform all the calculation part in an non-loopy, array-based wording, leaving the actual traversal extremely simple. I think it needs only a little more explanation than the comments in the code. It takes as x the start/end indices and as y the elevation field:
bfs =: {{ NB. bfs goes backwards, from e to closest index in s; x: s;end ;y: height matrix
's e' =. x NB. start and end indices
'p c' =. |: one y NB. parents, children, as returned bz one
gn =. (c #~ p&e.) NB. verb: get reachable neighbors for any index in y
it=. 0 NB. Step count: 1 iteration = 1 step
rr=. ,e NB. initially only E is reachable
while. -.+./ s e.~ rr do. NB. none of start not reachable
it=. >: it [ rr=. gn rr NB. take one step, adding nodes and increment step count
end.
}}
The only thing to note is a nice J trick: the return value of a verb is the last evaluated result that's not in a T-block (even if that's an assignment). As we'd like to return iterations, that is the assignment that should happen last. Using [ is another trick to put several noun assignments on a line (but does not work for verbs).
I noticed that due to using gn, there will be duplicated nodes in the set of reachable nodes rr (for part 2, there's roughly a 4x duplication). Nevertheless, using ~. after getting the neighbours turns out considerably slower.
I also tried removing the loop, writing the last five lines of bfs as follows:
{. (>:@{. , gn@}.)^:(-.@(+./)@(e.&s)@}.)^:_] 0,e
It's a fraction faster, and while I'm an enormous fan of tacit programming (might be obvious from my code), often clarity is more important than brevity, especially if the code is in fact loopy in nature. You choose.
Eventually, the solution is:
part1=: (}: bfs >@{:)@par
Part 2
Part 2 modifies the start point to be any point at elevation a. This is the exact reason I preferred to run bfs backwards from E to S, as it checks whether the destination (in this case S, or any point at elevation a) is within the reachable points.
For adding all a's to the start set of the x argument of bfs, I wrote addas for replacing }: in part 1. It takes the parsed input, based on the field, finds the indices of the minimum values (i.e. elevation a), adds them to the start values, and appends the end field again.
addas =: 1&{ ,~ {. (,I.@(=<./)@,)&.> {:
part2 =: (addas bfs >@{:)@par