I am given (yet another) 2D grid whose elements are risk scores, and I must find the best path (i.e. the one with the lowest total risk) from the top left to the bottom right. Although it’s not explicitly stated, the path can meander, i.e. move up and to the left as well as directly toward its terminus. Thus, a path is a minimum-cost spanning tree for the given grid.

Note after struggling through the work below: I don’t like this
problem. The description doesn’t give me any grounds to believe that
there is a unique solution, yet this is what the puzzle expects me to
find. As will become clear below, this is a serious defect for trying
to reason about this puzzle. (I suspect that the puzzle input is
generated under some invisible constraints that ensure that there *is*
a unique MCST, but I don’t have access to that information.) Thus, the
following is wrong-headed, since I began by assuming a unique
solution, when I really have to assume the existence of many
solutions, then refine the solutions down to a single candidate.

A classic way to tackle such a problem is with a greedy (frugal, in this case) algorithm–something along the vague lines of “to find the safest path, take the safest step at each point in the graph”. But it is by no means obvious at this point that a greedy algorithm will find the best path. I’ll try to be more formal, so that I can state a condition that has to hold for this approach to work.

What follows are tools for reasoning, so please forget about efficiency. I first define a way to find the best path from a list all possible candidates.

```
type Path = [(ℕ × ℕ)]
type Grid = [[ℕ]]
least_risk : Grid → Path
least_risk g = minWith (risk g) (candidates g)
minWith : Ord α ⇒ (α → β) → [α] → α
minWith f = let { smaller f x y = if f x ≤ f y then x else y } in
foldr1 (smaller f)
risk : Grid → Path → ℕ
risk g = sum ∘ map (λ (x, y) → ((g !! x) !! y))
```

A path is a sequence of coordinates describing a path from (0, 0), the top left corner of a grid, to (max-x, max-y), the bottom right corner. Total risk is computed by looking up each point of a path in the given grid and summing the results.

Given a metric *f*, *minWith f* returns the least element of a
non-empty list. There is ambiguity here; the version above
returns the first minimum element, but this is really a
non-deterministic function in disguise.

*candidates* is the core of the specification; it generates all
possible complete paths.

```
candidates : Grid → [Path]
candidates g = filter (complete g) (all_paths g)
all_paths : Grid → [Path]
all_paths g =
let blocked ps = null (neighbors g ps)
step = concatMap ∘ extend g
in until (all (complete ∨ blocked)) step [(0, 0)]
complete : Grid → Path → Bool
complete (p ∷ _) = is_bottom_right g p
extend : Grid → Path → [Path]
extend g ps = map (∷ ps) (neighbors g ps)
neighbors : Grid → Path → [(ℕ × ℕ)]
neighbors g ps@(p ∷ _) = filter (∉ ps) (adjacents g p)
adjacents : Grid → (ℕ × ℕ) → [(ℕ × ℕ)]
is_bottom_right : Grid → (ℕ × ℕ) → Bool
```

There is quite a bit here. *candidates* extends each of a list
of paths until all of them have either reached the destination
or are “out of moves”.

The *neighbors* function produces the list of available next steps
for a given list, filtering out nodes already visited. It uses
*adjacents*, which produces a list of two (for a corner position)
or four adjacent positions.

[Note: After further reading, I found that this is known as Kruskal’s algorithm.]

Having specified all of that, I can specify the greedy approach
as a fusion of *least_risk*:

```
least_risk g = minWith (risk g) (candidates g)
= minWith (risk g) (filter (complete g) (all_paths g))
```

While it’s easy enough to fuse the *minWith* and *filter* components
(both of which are folds), I’m left with the problem of fusing a
fold with *all_paths*, an *until* expression. There is no clear way
to do this, since the corecursion of *until* does not mirror the
recursion of a right fold.

The only way I see to proceed is to generalize *minWith* and thus
the whole problem to nondeterministic functions or relations. I’ll
try to return to this problem when I’m more familiar with the
reasoning processes for those.