LeetCode 773. Sliding Puzzle in F#

URL

https://leetcode.com/problems/sliding-puzzle/description/?envType=daily-question&envId=2024-11-25

Code

https://github.com/syohex/dotnet-study/blob/master/fsharp/leetcode/challenge/202411/sliding_puzzle/main.fsx

let slidingPuzzle (board: int[,]) : int =
    let nexts = [| [ 1; 3 ]; [ 0; 2; 4 ]; [ 1; 5 ]; [ 0; 4 ]; [ 1; 3; 5 ]; [ 2; 4 ] |]
    let goal = [| 1; 2; 3; 4; 5; 0 |]

    let rec slidingPuzzle' q steps visited =
        match q with
        | [] -> -1
        | _ ->
            if List.exists ((=) goal) q then
                steps
            else
                let visited = q |> List.fold (fun acc v -> Set.add v acc) visited

                let q =
                    q
                    |> List.fold
                        (fun acc v ->
                            let zeroPos = Array.findIndex ((=) 0) v

                            nexts.[zeroPos]
                            |> List.fold
                                (fun acc i ->
                                    let next = Array.copy v
                                    let tmp = next.[i]
                                    next.[i] <- next.[zeroPos]
                                    next.[zeroPos] <- tmp
                                    next :: acc)
                                acc)
                        []
                    |> List.filter (fun v -> not <| Set.contains v visited)

                slidingPuzzle' q (steps + 1) visited

    let q = [ board |> Seq.cast<int> |> Seq.toArray ]
    slidingPuzzle' q 0 Set.empty