AOJ 0121 Seven Puzzle

gistfile1.fs

module Util =
  let toStr x = Array.fold (fun x y -> x + string y) "" x
  let fordir (arr : int[]) x f =
    for (i, d) in List.mapi (fun a b -> (a, b)) [ 1; -1; 4; -4 ] do
      if not(x%4=0 && i=1) && not(x%4=3 && i=0) && x+d<8 && x+d>=0 then
        let arr = arr.Clone() :?> int[]
        let t = arr.[x]
        arr.[x] <- arr.[x + d]
        arr.[x + d] <- t
        f arr

open Util

let goal = [| 0; 1; 2; 3; 4; 5; 6; 7 |]
let input = System.Console.ReadLine().Split([|' '|]) |> Array.map int
let zeroPos xs = Array.findIndex ((=) 0) xs
let dtable = System.Collections.Generic.Dictionary<string, int>()
let queue = System.Collections.Generic.Queue<int[]*int>()

dtable.[toStr goal] <- 0
queue.Enqueue(goal, 0)

let c = ref 0
while queue.Count <> 0 do
  let (state, d) = queue.Dequeue()
  fordir state (zeroPos state) <| fun x ->
    let s = toStr x
    if not (dtable.ContainsKey s) then 
      dtable.[s] <- d + 1
      queue.Enqueue(x, d + 1)

printfn "%A" dtable.[toStr input]