10 commentary
Yeah basically if you were doing DFS and forgot to check if you'd already visited the next node you were solving for pt2, since the rule about the next node always having a value of +1 compared to the current one was already preventing cyclic paths.
10 Code
Hardly a groundbreaking implementation but I hadn't posted actual code in a while so
(* F# - file reading code and other boilerplate omited *)
let mapAllTrails (matrix : int array2d) =
let rowCount = matrix |> Array2D.length1
let colCount = matrix |> Array2D.length2
let rec search (current:int*int) (visited: HashSet<int*int>) (path: (int*int) list) : (int*int) list list=
let (row,col) = current
let currentValue = matrix.[row,col]
// Remove to solve for 10-2
visited.Add (row,col) |> ignore
// If on a 9 return the complete path
if currentValue = 9 then [List.append path [row,col] ]
// Otherwise filter for eligible neihboring cells and continue search
else
[ row-1, col;row, col-1; row, col+1; row+1,col]
|> List.filter (fun (r,c) ->
not (visited.Contains(r,c))
&& r >= 0 && c>=0 && r < rowCount && c < colCount
&& matrix.[r,c]-currentValue = 1 )
|> List.collect (fun next ->
[row,col]
|> List.append path
|> search next visited)
// Find starting cells, i.e. contain 0
matrix
|> Global.matrixIndices
|> Seq.filter (fun (row,col) -> matrix.[row,col] = 0)
// Find all trails starting from those cells and flatten the result
|> Seq.collect (fun trailhead -> search trailhead (HashSet<int*int>()) [])
"./input.example"
|> Common.parse
|> mapAllTrails
|> Seq.length
|> Global.shouldBe 81
"./input.actual"
|> Common.parse
|> mapAllTrails
|> Seq.length
|> printfn "The sum total of trail rankings is %d"
Almost exactly at the start of office hours for me.