F# Manhatten distances between 2 Array2D

Question

so I have 2 boards for example

let startingBoard = [|[|1; 4; 7|];
                     [|6; 3; 5|];
                     [|0; 8; 2|]|]

let goal = [|[|1; 2; 3|];
            [|4; 5; 6|];
            [|7; 8; 0|]|]

and want to find the sum of all the Manhattan distances of like elements between the 2 arrays ( for example the Manhattan distance for the 4 tile would be 2 one move down, one move left) all I have so far is the code below which finds the Manhattan distance for indexes its given.

let totalManhattenDistance board goal =
    let manhattenDistance (x1, y1) (x2, y2) =
        abs(x1 - x2) + abs(y1 - y2)
// solution here

the problem is I cant imagine doing this without for loops, but that seems unidiomatic.

Answer 1

Here's one version

let totalManhattanDistance board goal =
    let manhattanDistance ((x1, y1), (x2, y2)) = abs(x1 - x2) + abs(y1 - y2)
    let indexed xs = xs |> Seq.mapi (fun i -> Seq.mapi (fun j x -> (i, j), x))
                        |> Seq.concat
                        |> Seq.sortBy snd
                        |> Seq.map fst
    Seq.zip (indexed board) (indexed goal)
    |> Seq.map manhattanDistance
    |> Seq.sum

The three Seq operations in the end could be done with just one Array.fold2 but I don't know if this makes the code any clearer

let totalManhattanDistance board goal =
    let manhattanDistance (x1, y1) (x2, y2) = abs(x1 - x2) + abs(y1 - y2)
    let indexed xs = xs |> Array.mapi (fun i -> Array.mapi (fun j x -> (i, j), x))
                        |> Array.concat
                        |> Array.sortBy snd
                        |> Array.map fst
    let folder = fun acc n m -> acc + manhattanDistance n m
    Array.fold2 folder 0 (indexed board) (indexed goal)

Answer 2

Using 2D Arrays the problems seams to be more natural:

let startingBoard = array2D [|[|1; 4; 7|];
                             [|6; 3; 5|];
                             [|0; 8; 2|]|]

let goal = array2D [|[|1; 2; 3|];
                    [|4; 5; 6|];
                    [|7; 8; 0|]|]

Unfortunately there is no findIndex2D function (like Array.findIndex). You have to define it yourself:

let findIndex2D (p:'A -> bool) (a:'A [,]) =
  a |> Array2D.mapi (fun x y v -> x,y,v)
    |> Seq.cast<int*int*'A>
    |> Seq.pick (fun (x,y,v) -> if p v then Some (x,y)  else None)

Straightforward definition of manhatten distance:

let manhattanDistance (x1, y1) (x2, y2) = abs(x1 - x2) + abs (y1 - y2)

And the sum of all manhatten distances:

let totalManhattanDistance board goal =
  board |> Array2D.mapi (fun x y v -> manhattanDistance (x, y)
                                        <| findIndex2D ((=) v) goal)
        |> Seq.cast<int>         // flatten
        |> Seq.reduce (+)

Answer 3

Another version:

let newpos (start : int[][]) (finish:int[][]) (i, j) = 
    let rw = 
        finish |> Array.fold (fun (found, y, x) row -> 
            if found then (found, y, x)
            else
                match row |> Array.tryFindIndex ((=) start.[i].[j]) with 
                | Some nX -> (true, y, nX) 
                | None -> (false, y+1, x)
        ) (false, 0, 0)

    match rw with
    | (true, x, y) -> (x, y)
     | _ -> failwith "Not found"

let totalManhattenDistance board goal =
    let manhattenDistance (x1, y1) (x2, y2) = abs(x1 - x2) + abs(y1 - y2)

    board |> Array.mapi (fun i arr ->
        arr |> Array.mapi (fun j v ->
            let (i1, j1) = newpos board goal (i, j)
            manhattenDistance (i, j) (i1, j1)
        )
    )

totalManhattenDistance startingBoard goal

Answer is

val it : int [] [] = 
[|[|0; 2; 4|]; 
   [|2; 2; 1|]; 
   [|2; 0; 3|]|]

Answer 4

Here's a F# idiomatic (I hope) version, not too dissimilar to mikkoma's:

let flatten a2D =
    a2D |> Array.mapi (fun i1 a1D -> a1D
        |> Array.mapi (fun i2 el -> (el, (i1, i2)) ))
        |> Array.concat |> Array.sortBy fst

let manhattan b1 b2 =
    flatten b1
        |> Array.zip (flatten b2)
        |> Array.sumBy (fun ((_, (i1, j1)), (_, (i2, j2))) -> abs(i2-i1) + abs(j2-j1))

flatten transforms the 2D array into a 1D array where each element is put next to its coordinates on the board.
manhattan then simply zips the 2 1D arrays together and sums up the coordinate offset.