2
\$\begingroup\$

Story:

I build a kind of labyrinth. This labyrinth is divided in seven steps. You start with the first, then second, and so on to the seventh. You cannot go back to a previous step. Each step contains 3 to 5 rooms. Every room of a step is connected to at least one room of the next step. As well, every room of a step is connected to at least one room of the previous one. No hallway (connection between rooms) can cross another hallway. No room can have more than 3 source-rooms, neither more than 3 destination-rooms.

Implementation:

My point is to create a matrix (two-dim array) which depict the connection of a step to its successor. Rows represent the rooms of the source step, and columns the destination step. As I want to practice it, F# is required.

Decisions:

The matrix will only contains 3 values:
- M[i,j] = 1 means that source-room #i is connected to destination-room #j
- M[i,j] = 0 means that source-room can not be connected to destination-room
- M[i,j] = -1 means that source-room can be connected (but is not) to destination-room

Constraints:

  1. Because hallways cannot be crossed, first source-room is imperatively connected to the first destination-room ; same for last rooms.
  2. Because rooms can not have more than three destination-room, the first source-room can only be connected to the three first destination-rooms, and the last destination-room can only be connected to the three last source-rooms.

Code:

module MapConnections =
    let IsUncertain array row col =
        Array2D.get array row col = -1

    let IsDisconnected array row col =
        Array2D.get array row col = 0

    let IsConnected array row col =
        Array2D.get array row col = 1

    let ListUncertain array =
        let mutable list : (int*int) list = list.Empty
        for i  in 0 .. Array2D.length1 array - 1 do
            for j in 0 .. Array2D.length2 array - 1 do
                if IsUncertain array i j then
                    list <- list @ [(i,j)]
        list

    let ListDisconnected array =
        let mutable list : (int*int) list = list.Empty
        for i  in 0 .. Array2D.length1 array - 1 do
            for j in 0 .. Array2D.length2 array - 1 do
                if IsDisconnected array i j then
                    list <- list @ [(i,j)]
        list

    let ListConnected array =
        let mutable list : (int*int) list = list.Empty
        for i  in 0 .. Array2D.length1 array - 1 do
            for j in 0 .. Array2D.length2 array - 1 do
                if IsConnected array i j then
                    list <- list @ [(i,j)]
        list

    let CountUncertain array =
        ListUncertain array |> Seq.length<int*int>

    let CountDisconnection array =
        ListDisconnected array |> Seq.length<int*int>

    let CountConnection array =
        ListConnected array |> Seq.length<int*int>

    let Disconnect array row col =
        if IsUncertain array row col then
            Array2D.set array row col 0
        IsDisconnected array row col

    // Check no-cross rule
    let Connect array row col =
        if IsUncertain array row col then
            Array2D.set array row col 1
            // Disconnect all 'top-right' connections
            for i in 0 .. row - 1 do
                for j in col + 1 .. Array2D.length2 array - 1 do
                    Disconnect array i j |> ignore
            // Disconnect all 'bottom-left' connections
            for i in row + 1 .. Array2D.length1 array - 1 do
                for j in 0 .. col - 1 do
                    Disconnect array i j |> ignore
        IsConnected array row col

    // Check no-more-than-three rule
    let Create rows cols =
        let matrix = Array2D.create rows cols -1
        Connect matrix 0 0 |> ignore
        Connect matrix (rows - 1) (cols - 1) |> ignore
        for i in 3 .. rows - 1 do
            Disconnect matrix i 0 |> ignore
        for i in 0 .. rows - 4 do
            Disconnect matrix i (cols - 1) |> ignore
        for j in 3 .. cols - 1 do
            Disconnect matrix 0 j |> ignore
        for j in 0 .. cols - 4 do
            Disconnect matrix (rows - 1) j |> ignore
        matrix

What I want to be sure:

I want to follow the F# conventions. For example, if lists are non-mutable, I presume that a mutable list is something to avoid?

\$\endgroup\$
2
\$\begingroup\$

I'm not sure, I understand what the purpose of your code is, so here are some general thoughts:


You have 3 identical functions except for a predicate:

let ListUncertain array =
    let mutable list : (int*int) list = list.Empty
    for i  in 0 .. Array2D.length1 array - 1 do
        for j in 0 .. Array2D.length2 array - 1 do
            if IsUncertain array i j then
                list <- list @ [(i,j)]
    list

let ListDisconnected array =

let ListConnected array =

So a generalization is appropriate:

let toFilteredList predicate array =
    let mutable list : (int*int) list = list.Empty
    for i  in 0 .. Array2D.length1 array - 1 do
        for j in 0 .. Array2D.length2 array - 1 do
            if predicate array i j then
                list <- list @ [(i,j)]
    list

which then could be called from each specialized function like:

let ListUncertain array = array |> toFilteredList IsUncertain

etc.


Building a list by repeated concatenations of single item lists is rather expensive and in general in functional programming mutable objects should be avoided:

list <- list @ [(i,j)]

Instead it may be better to use higher order functions like:

let toSeq<'a> = Seq.cast<'a>

let filterBy cellType array =
    array 
    |> Array2D.mapi (fun r c x -> (r, c, x)) 
    |> toSeq<int*int*int>
    |> Seq.where (fun (r, c, x) -> cellType = x) 
    |> Seq.map (fun (r, c, _) -> (r, c))

where cellType is -1, 0 or 1 and then call it as:

let ListUncertain array = array |> filterBy -1

As an alternative you can "yield" a sequence like:

let filterBy predicate array =
    seq {for i  in 0 .. Array2D.length1 array - 1 do
            for j in 0 .. Array2D.length2 array - 1 do
                if predicate array i j then
                    yield (i,j)}

which is maybe a better solution?


Overall I think I would use a discriminated union type instead of -1, 0, 1 as cell types:

type CellType =
| Uncertain
| Disconnected
| Connected

let getAt array row col = Array2D.get array row col
let setAt array row col value = Array2D.set array row col value

let IsUncertain array row col = Uncertain = getAt array row col

let IsDisconnected array row col = Disconnected = getAt array row col

let IsConnected array row col = Connected = getAt array row col

let filterBy predicate array =
    seq {for i  in 0 .. Array2D.length1 array - 1 do
            for j in 0 .. Array2D.length2 array - 1 do
                if predicate array i j then
                    yield (i,j)}

let ListUncertain array = array |> filterBy IsUncertain

let ListDisconnected array = array |> filterBy IsDisconnected

let ListConnected array = array |> filterBy IsConnected


let CountUncertain array = ListUncertain array |> Seq.length

let CountDisconnection array = ListDisconnected array |> Seq.length

let CountConnection array = ListConnected array |> Seq.length

let Disconnect array row col =
    match getAt array row col with
    | Uncertain -> 
        setAt array row col Disconnected
        true
    | Connected -> false
    | Disconnected -> true

// Check no-cross rule
let Connect array row col =
    if IsUncertain array row col then
        setAt array row col Connected
        // Disconnect all 'top-right' connections
        for i in 0 .. row - 1 do
            for j in col + 1 .. Array2D.length2 array - 1 do
                Disconnect array i j |> ignore
        // Disconnect all 'bottom-left' connections
        for i in row + 1 .. Array2D.length1 array - 1 do
            for j in 0 .. col - 1 do
                Disconnect array i j |> ignore
    IsConnected array row col

// Check no-more-than-three rule
let Create rows cols =
    let matrix = Array2D.create rows cols Uncertain
    Connect matrix 0 0 |> ignore
    Connect matrix (rows - 1) (cols - 1) |> ignore
    for i in 3 .. rows - 1 do
        Disconnect matrix i 0 |> ignore
    for i in 0 .. rows - 4 do
        Disconnect matrix i (cols - 1) |> ignore
    for j in 3 .. cols - 1 do
        Disconnect matrix 0 j |> ignore
    for j in 0 .. cols - 4 do
        Disconnect matrix (rows - 1) j |> ignore
    matrix

The most significant improvement is, that there are no "magic numbers" left in the code - they are replaced with descriptive union types.

There may be other - smarter - ways to do it all, but this is what I can contribute with.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.