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.