Stepping Stone Algorithm in F#, Part 2

These are only a few points of information regarding the previous post.

Data Structures

The makeDict function creates a lookup table where the values are sequences. In a real-world setting it may be worth checking if it isn’t more efficient to make them lists. The modification of the function itself is easily made.

let makeDict keySelector valSelector lst =
    lst
    |> Seq.groupBy keySelector
    |> Seq.map (fun (key, valSeq) -> (key, valSeq |> Seq.map valSelector |> Seq.toList))
    |> dict

This requires all the subsequent calls to Seq.tryPick to be replaced by List.tryPick. Seq.tryPick will still work, but if there should be any efficiency gain in switching to lists, then there’s no point in still treating them as generic sequences.

Simplifying the Recursive Search Functions

There is only one version of makeDict, even if the keys and values to be extracted out of the initial solution list are quite different for rows and columns. This was achieved by passing some functionality into makeDict, and supplying different functions (or rather, a different order of the same functions) when creating each lookup table.

The two nested functions findInRow and findInCol within findPath also look quite similar, and they are really symmetric. Is there a way to simplify them in the same way and only have one single function? I have been trying around with this, and the best (only) solution I could come up with is the following.

let findPath ((targetRow, targetCol) as targetRowCol) lstStones =

    let rowColDict = [|lstStones |> makeDict fst snd; lstStones |> makeDict snd fst|]

    let rec findInRowCol selFix selMov ((currentRow, currentCol) as currentRowCol) =
        let dict = rowColDict.[selFix (0,1)]
        dict.[selFix currentRowCol] 
        |> Seq.tryPick (fun idx ->
            if idx=selMov currentRowCol then None
            else
                let cellRowCol = (selFix (currentRow, idx), selFix (idx, currentCol))
                if idx=selMov targetRowCol then Some([cellRowCol])
                else
                    match findInRowCol selMov selFix cellRowCol with
                    | Some(l) -> Some(cellRowCol::l)
                    | _ -> None)

    findInRowCol snd fst (targetRow, targetCol)

So yes, it is certainly possible, but I think this needs some more research to see if there is something that can be done to also make it aesthetically pleasing. I am not explaining the code here, be it a riddle.