How to improve this unblock me / rush hour solver without any major change in search algorithm?

Question

This is my first complete program written in F# (I was from C# and occasionally do interop) And I believe there are quite a few places I didn't tackle well in terms of coding practice.

Problem Unblock Me / Rush Hour

    5   b   b       k   j   
    4   c   c   c   k   j   
    3   a   a       k   i   l
    2   d       g   g   i   l
    1   d       f   h   h   l
    0   e   e   f           
        0   1   2   3   4   5

A player can move horizontal bricks horizontally, vertical bricks vertically. The aim is to move the brick denoted by aa to the rightmost.

I used depth limited search to solve this problem, the full running code is attached. It is Slow (depth 7 takes 2 sec), and I know there are better algorithms to the problem. However my objective is to learn F# well, so could someone shed some light on me how to improve the code without making to much tweaks on the algorithm itself please.

module Unblock
open System
open System.Collections.Generic
open System.IO
open System.Diagnostics


type Position = int * int // (RowID, ColumnID)

type Brick = char * int // (Name, Length)

type State = Position[]
type BrickInfo = Brick[]

type Direction = 
    | Up
    | Down
    | Left
    | Right

    override this.ToString() =
        match this with
        | Up -> "Up"
        | Down -> "Down"
        | Left -> "Left"
        | Right -> "Right"

type Move = int * Direction

//module myFunction =

let checkBoth target length current =
    if current > target || current + length - 1 < target then true else false



let test (initialState: State) (brickInfo: Brick[]) (horizontalBricks: int[][], verticalBricks: int[][]) (rowNum, columnNum) =
    //let sw = new StreamWriter("output.csv");
    let (redRowNum, _) = initialState.[0]
    let (_, redLength) = brickInfo.[0]
    let mySet = new HashSet<_>(HashIdentity.Structural)

    let horizontalBricksAll = horizontalBricks |> Array.concat
    let verticalBricksAll = verticalBricks |> Array.concat

    let rec solveDFS (currentState: State) (lastBrick, lastDirection) depth =

        let generateState i (newPosition: Position) =
            let nextState = currentState |> Array.copy
            nextState.[i] <- newPosition
            nextState

        let isDuplicated (set: HashSet<_>) =
            if set.Contains (currentState) then true
            else
                //let f = currentState |> Array.map (fun elem -> sw.Write("{0},{1} ", fst elem, snd elem))
                //sw.WriteLine()
                ignore (set.Add currentState)
                false

        let checkVacancy (rowID, columnID) =         
            let checkHorizontal i = 
                let (_, length) = brickInfo.[i]
                let (_, startColumn) = currentState.[i]
                checkBoth columnID length startColumn
            let checkVertical i =
                let (_, length) = brickInfo.[i]
                let (startRow, _) = currentState.[i]
                checkBoth rowID length startRow
            (horizontalBricks.[rowID] |> Array.forall checkHorizontal) && (verticalBricks.[columnID] |> Array.forall checkVertical)

        let generateRight i =
            let (_, length) = brickInfo.[i]
            let (rowID, columnID) = currentState.[i]
            if columnID + length >= columnNum then None
            else Some ((rowID, columnID + length), (rowID, columnID + 1))
        let generateLeft i =
            let (_, length) = brickInfo.[i]
            let (rowID, columnID) = currentState.[i]
            if columnID = 0 then None
            else Some ((rowID, columnID - 1), (rowID, columnID - 1))
        let generateUp i =
            let (_, length) = brickInfo.[i]
            let (rowID, columnID) = currentState.[i]
            if rowID + length >= rowNum then None
            else Some ((rowID + length, columnID), (rowID + 1, columnID))
        let generateDown i =
            let (_, length) = brickInfo.[i]
            let (rowID, columnID) = currentState.[i]
            if rowID = 0 then None
            else Some ((rowID - 1, columnID), (rowID - 1, columnID))

        if depth < 7
            && not (isDuplicated mySet)
            &&
             (
                let (_, columnLeft) = currentState.[0]
                [|columnLeft + redLength .. columnNum - 1|] |> Array.forall (fun columnID -> checkVacancy (redRowNum, columnID))
                ||
                horizontalBricksAll |> Seq.tryFind (fun elem ->
                                                        (match generateRight elem with                              
                                                         | Some (a,b) when checkVacancy a -> solveDFS (generateState elem b) (elem, Right) (depth + 1)
                                                         | _ -> false)
                                                        ||
                                                        (match generateLeft elem with
                                                         | Some (a,b) when checkVacancy a -> solveDFS (generateState elem b) (elem, Left) (depth + 1)
                                                         | _ -> false)
                                                    )
                                    |> Option.isSome
                ||
                verticalBricksAll |> Seq.tryFind (fun elem ->
                                                        (match generateUp elem with                              
                                                         | Some (a,b) when checkVacancy a -> solveDFS (generateState elem b) (elem, Up) (depth + 1)
                                                         | _ -> false)
                                                        ||
                                                        (match generateDown elem with
                                                         | Some (a,b) when checkVacancy a -> solveDFS (generateState elem b) (elem, Down) (depth + 1)
                                                         | _ -> false)
                                                 )
                                    |> Option.isSome
             )
             then 
                 Console.WriteLine("Brick Name {0} Direction {1}", fst brickInfo.[lastBrick], lastDirection)
                 true
             else 
                ignore (mySet.Remove(currentState))
                false
    Console.WriteLine (solveDFS initialState (0, Right) 0) // the output would have an additional line of useless information (0, Right)



let x0 = ('a',2)
let x1 = ('b',2)
let x2 = ('c',3)
let x3 = ('d',2)
let x4 = ('e',2)
let x5 = ('f',1)
let x6 = ('g',2)
let x7 = ('h',2)
let x8 = ('i',2)
let x9 = ('j',2)
let x10 = ('k',3)
let x11 = ('l',3)

let brickInfo = [|x0;x1;x2;x3;x4;x5;x6;x7;x8;x9;x10;x11|]
let horizontalBricks = [|[|4|];[|7|];[|6|];[|0|];[|2|];[|1|]|]
let verticalBricks = [|[|3|];[||];[|5|];[|10|];[|8;9|];[|11|]|]
let rowNum = 6
let columnNum = 6

let p0 = (3,0)
let p1 = (5,0)
let p2 = (4,0)
let p3 = (1,0)
let p4 = (0,0)
let p5 = (0,2)
let p6 = (2,2)
let p7 = (1,3)
let p8 = (2,4)
let p9 = (4,4)
let p10 = (3,3)
let p11 = (1,5)


let initialState =[|p0;p1;p2;p3;p4;p5;p6;p7;p8;p9;p10;p11|]

[<EntryPoint>]
let main argv = 
    printfn "%A" argv
    let sw = new Stopwatch()
    sw.Start()

    ignore (test (initialState) (brickInfo) (horizontalBricks, verticalBricks) (rowNum, columnNum))
    sw.Stop()

    Console.WriteLine(sw.Elapsed)
    0 // return an integer exit code

Update @ Jack P.

1. Most books I read recommend to use curry form when let binding.
2. I normally inline at the release stage.
3. thx, I forget there exists tryFind for Array.
4. Again many books I read recommend use jagged array than 2D
5. thx again for the refactor of check().. yes i found it scary when I had to use lots of && || due to lack of break continue
6. thx again for the appropriate functional if then else indentation form.

Answer 1

There are some places you could tweak the code to squeeze out more performance and/or adhere to better F# style.

---

If you're not going to use a function in curried form -- i.e., you're always going to pass all of the arguments at once -- it's better to define the function as such. Doing so allows the F# compiler to compile the function into a single .NET method, rather than a bunch of closures.

For example, change this:

let rec solveDFS (currentState: State) (lastBrick, lastDirection) depth =

to this:

let rec solveDFS (currentState : State, lastBrick, lastDirection, depth) =

I don't think this'll make much of a difference for your code, but it will make a difference for larger codebases.

---

inline the generateRight, etc. functions -- they're fairly small and only used once so it'd be better to avoid the overhead of a function call.

---

When your input is an array, it's better to use functions in the Array module instead of the Seq module, because the Array functions are optimized for arrays. So, change the Seq.tryFind calls to Array.tryFind.

---

If you can, it'd be better to use 2d arrays ([,]) instead of jagged arrays ([][]). The reason is that a 2d array is stored as a contiguous block of memory and only requires a few more arithmetic operations to access than a 1d array, whereas a jagged array is stored in non-contiguous chunks so you have an additional indirection and poor memory locality (i.e., doesn't work as well with the CPU cache).

I didn't make this change to the code I posted below, but this could provide a noticeable improvement in your code since you're frequently accessing the arrays.

Note that there is an Array2D module for working with 2d arrays.

---

Here's your code with the changes I described, other than the modification for 2d arrays:

module Unblock
open System
open System.Collections.Generic
open System.IO
open System.Diagnostics


type Position = int * int // (RowID, ColumnID)

type Brick = char * int // (Name, Length)

type State = Position[]
type BrickInfo = Brick[]

type Direction = 
    | Up
    | Down
    | Left
    | Right

    override this.ToString() =
        match this with
        | Up -> "Up"
        | Down -> "Down"
        | Left -> "Left"
        | Right -> "Right"

type Move = int * Direction

//module myFunction =

let inline checkBoth target length current =
    if current > target || current + length - 1 < target then true else false



let test (initialState: State, brickInfo: Brick[], horizontalBricks: int[][], verticalBricks: int[][], rowNum, columnNum) =
    //let sw = new StreamWriter("output.csv");
    let (redRowNum, _) = initialState.[0]
    let (_, redLength) = brickInfo.[0]
    let mySet = HashSet<_> (HashIdentity.Structural)

    let horizontalBricksAll = Array.concat horizontalBricks
    let verticalBricksAll = Array.concat verticalBricks

    let rec solveDFS (currentState: State, lastBrick, lastDirection, depth) =

        let generateState i (newPosition: Position) =
            let nextState = Array.copy currentState
            nextState.[i] <- newPosition
            nextState

        let inline isDuplicated (set: HashSet<_>) =
            if set.Contains (currentState) then true
            else
                //let f = currentState |> Array.map (fun elem -> sw.Write("{0},{1} ", fst elem, snd elem))
                //sw.WriteLine()
                ignore (set.Add currentState)
                false

        let checkVacancy (rowID, columnID) =
            horizontalBricks.[rowID]
            |> Array.forall (fun i ->
                let length = snd brickInfo.[i]
                let startColumn = snd currentState.[i]
                checkBoth columnID length startColumn)

            && verticalBricks.[columnID]
            |> Array.forall (fun i ->
                let length = snd brickInfo.[i]
                let startRow = fst currentState.[i]
                checkBoth rowID length startRow)

        let inline generateRight i =
            let length = snd brickInfo.[i]
            let (rowID, columnID) = currentState.[i]
            if columnID + length >= columnNum then None
            else Some ((rowID, columnID + length), (rowID, columnID + 1))
        let inline generateLeft i =
            let length = snd brickInfo.[i]
            let (rowID, columnID) = currentState.[i]
            if columnID = 0 then None
            else Some ((rowID, columnID - 1), (rowID, columnID - 1))
        let inline generateUp i =
            let length = snd brickInfo.[i]
            let (rowID, columnID) = currentState.[i]
            if rowID + length >= rowNum then None
            else Some ((rowID + length, columnID), (rowID + 1, columnID))
        let inline generateDown i =
            let length = snd brickInfo.[i]
            let (rowID, columnID) = currentState.[i]
            if rowID = 0 then None
            else Some ((rowID - 1, columnID), (rowID - 1, columnID))

        // This was refactored from inside the condition of the 'if' statement below.
        // It's marked as 'inline', so it should compile to the exact same IL, but it's
        // much easier to read this way.
        let inline check () =
            let columnLeft = snd currentState.[0]
            [|columnLeft + redLength .. columnNum - 1|]
            |> Array.forall (fun columnID ->
                checkVacancy (redRowNum, columnID))
            ||
            horizontalBricksAll
            |> Array.tryFind (fun elem ->
                (match generateRight elem with
                    | Some (a, b) when checkVacancy a ->
                        solveDFS (generateState elem b, elem, Right, depth + 1)
                    | _ -> false)
                ||
                (match generateLeft elem with
                    | Some (a, b) when checkVacancy a ->
                        solveDFS (generateState elem b, elem, Left, depth + 1)
                    | _ -> false))
                |> Option.isSome
            ||
            verticalBricksAll
            |> Array.tryFind (fun elem ->
                (match generateUp elem with
                    | Some (a, b) when checkVacancy a ->
                        solveDFS (generateState elem b, elem, Up, depth + 1)
                    | _ -> false)
                ||
                (match generateDown elem with
                    | Some (a, b) when checkVacancy a ->
                        solveDFS (generateState elem b, elem, Down, depth + 1)
                    | _ -> false))
            |> Option.isSome

        if depth < 7 && not (isDuplicated mySet) && check () then
            printfn "Brick Name %c Direction %A" (fst brickInfo.[lastBrick]) lastDirection
            true
        else
            mySet.Remove currentState
            |> ignore
            false

    // the output would have an additional line of useless information (0, Right)
    Console.WriteLine (solveDFS (initialState, 0, Right, 0))



let x0 = ('a',2)
let x1 = ('b',2)
let x2 = ('c',3)
let x3 = ('d',2)
let x4 = ('e',2)
let x5 = ('f',1)
let x6 = ('g',2)
let x7 = ('h',2)
let x8 = ('i',2)
let x9 = ('j',2)
let x10 = ('k',3)
let x11 = ('l',3)

let brickInfo = [|x0;x1;x2;x3;x4;x5;x6;x7;x8;x9;x10;x11|]
let horizontalBricks = [|[|4|];[|7|];[|6|];[|0|];[|2|];[|1|]|]
let verticalBricks = [|[|3|];[||];[|5|];[|10|];[|8;9|];[|11|]|]
let [<Literal>] rowNum = 6
let [<Literal>] columnNum = 6

let p0 = (3,0)
let p1 = (5,0)
let p2 = (4,0)
let p3 = (1,0)
let p4 = (0,0)
let p5 = (0,2)
let p6 = (2,2)
let p7 = (1,3)
let p8 = (2,4)
let p9 = (4,4)
let p10 = (3,3)
let p11 = (1,5)


let initialState = [|p0;p1;p2;p3;p4;p5;p6;p7;p8;p9;p10;p11|]

[<EntryPoint>]
let main argv = 
    printfn "%A" argv

    let sw = Stopwatch.StartNew ()

    test (initialState, brickInfo, horizontalBricks, verticalBricks, rowNum, columnNum)
    |> ignore

    sw.Stop()

    Console.WriteLine sw.Elapsed
    0 // return an integer exit code