CODEWITHSUNDEEP
f#
David_001
David_001

Reputation: 5812

Traversing an F# 2D Array

I'm creating a board(type) game in F#, and am having a bit of trouble traversing the array in a "functional" way.

I have an array that looks, for example, like:

val myArray : int [,] = [[1; 1; 0; 0; 0]
                         [0; 0; 1; 0; 0]
                         [2; 0; 0; 0; 3]
                         [0; 0; 0; 0; 0]
                         [0; 1; 0; 0; 1]]

I want to create a new array based on the above, where:

  1. If the item is > 0, then in the new array should be the number 1
  2. If the item is = 0, then:
    1. If an item to the left or right or above or below is > 1, then in the new array the number should be 2
    2. Otherwise, if an item to the left of right or above or below is = 1, then in the new array the number should be 3
    3. Otherwise, the number should be 4

This should create a new array which looks like:

val myArray : int [,] = [[1; 1; 3; 4; 4]
                         [2; 3; 1; 3; 2]
                         [1; 2; 3; 2; 1]
                         [2; 3; 4; 4; 2]
                         [3; 1; 3; 3; 1]]

I can't see any simple way in F# of achieving this. In C# I'd just create a for loop to do this, but I thought there might be a sneaky way of doing it in F#, using things like the map functions - mapi looked promising but it only seems to give access to the current piece under consideration and its indices, not the entire array...

My issue seems to be that the rules of the game are dependent on the surrounding area, whereas the standard traversal methods don't seem to give access to the surrounding area - what's the best way to achieve what I'm doing?

Upvotes: 6

Views: 4044

Answers (2)

Yin Zhu
Yin Zhu

Reputation: 17119

some of my thoughts:

Array is designed to be accessed via indexing. If you use array to store your data, then accessing it via indexing is the most convenient way.

What you want is a data structure in which a element knows where its neighbors are. This data structure is not a simple array. You can design such a data structure by augmenting an array:

type NArray(A: int [,]) = 
    member x.Item with get (i,j) = (A.[i,j], i, j, A)

and you can also explicitly add the four neighbors to an element:

type NArray(A: int [,]) = 
    let get i j di dj = 
        let newI = i + di
        let newJ = j + dj
        if newI < 0 || newI > A.GetLength(0) then None
        elif newJ < 0 || newJ > A.GetLength(1) then None
        else Some (A.[newI, newJ])

    member x.Item with get (i,j) = (A.[i,j], get i j 0 1, get i j 0 -1, get i j 1 0, get i j -1, 0)

The same problem arises when you want a sequence or a list to know its neighbors. They are designed not to know. If an element in a list knows its previous node, then it is not a single linked list anymore.

When you choose a data structure, then you inherit its advantages and its shortness. For array, you get fast indexing, while its elements do not have a notion of position themselves. Other data structures, say threaded-binary trees or doublely linked lists, their elements know where they are. But the cost is that more storage is used.

Upvotes: 2

cfern
cfern

Reputation: 6006

I don't think I pulled any sneaky stunt in this solution. I used Array2D.init to build a new array. The function required by init determines the array value at each position.

Furthermore, I put gathering the neighbors in a separate function. In the neighbors function I used a list comprehension and yielding only valid neighbors, avoiding troubles around corners and edges.

This is what I came up with (warning: it will fail when the 2D-array is 1x1 or empty, I'll leave it to the reader to guard against this case):

let neighbors r c (A:'a[,]) =
    [if r > 0 then yield A.[r-1,c]
     if r < Array2D.length1 A - 1 then yield A.[r+1,c]
     if c > 0 then yield A.[r,c-1]
     if c < Array2D.length2 A - 1 then yield A.[r,c+1]]

let newArray A =
    Array2D.init (Array2D.length1 A) (Array2D.length2 A) 
        (fun r c ->
            if A.[r,c] > 0 then 1 
            else
                match neighbors r c A |> List.max with
                | 1 -> 3
                | 0 -> 4
                | _ -> 2
        )

Test in F# interactive:

let myArray = array2D [[1; 1; 0; 0; 0]
                       [0; 0; 1; 0; 0]
                       [2; 0; 0; 0; 3]
                       [0; 0; 0; 0; 0]
                       [0; 1; 0; 0; 1]]

let result = newArray myArray

result:

val result : int [,] = [[1; 1; 3; 4; 4]
                        [2; 3; 1; 3; 2]
                        [1; 2; 3; 2; 1]
                        [2; 3; 4; 4; 2]
                        [3; 1; 3; 3; 1]]

Upvotes: 5

Related Questions