How to do pattern /shape match / recognition on a board (20x20)?

Question

The board is int[][] and I would like to find this shape

  1
    1
    1

with all 4 of it's symmetric (rotational) variants from the board and log the positions. e.g.

      ...
      ...
  ... x x x x x x ...
  ... x x 1 1 x x ...
  ... x 1 x x x x ...
  ... x x x x x x ...
      ...
      ...

Is it better to use F# to deal with these kinds of problems?

Below is my c# code for checking patterns vertically only (the code to check horizontally is simillar)

    List<Position> GetMatchVertical(int reelID)
    {
        List<Position> ret = new List<Position>();

        var myReel = board[reelID];
        var leftReel = reelID - 1 >= 0 ? board[reelID - 1] : null;
        var rightReel = reelID + 1 < boardSize ? board[reelID + 1] : null;

        int currentColor = myReel[0];

        for (int reelPosition = 1; reelPosition < boardSize; reelPosition++)
        {
            int nextColor = myReel[reelPosition];
            if (currentColor == nextColor)
            {
                if (leftReel!=null)
                {
                    if (reelPosition + 1 < boardSize && leftReel[reelPosition + 1] == currentColor)
                    {
                        ret.Add(logPosition(...));
                    }
                }
                if (rightReel!=null)
                {
                    if (reelPosition - 2 >= 0 && rightReel[reelPosition - 2] == currentColor)
                    {
                        ret.Add(logPosition(...));
                    }
                }
            }
            else
            {
                currentColor = nextColor;
            }
        }

        return ret;
    }

Answer 1

This is definitely a great fit for functional programming and F#. There is a large number of possible approaches. I think the solution by pad is probably the most direct one and it is a really good starting point. If you need something more general, then the solution by Huusom is quite nice.

There is even more general approach, which is to build a domain specific language (DSL) for detecting patterns in an array. This is more advanced functional technique, but it works really nicely for your example. If you did that, then you could express quite complex patterns in a really concise way. Here is an example:

// Create a detector that tests if a location
// contains 1 and returns 'false' when out of range
let one = border false (equals 1)

// A shape detector for your pattern
let pattern = 
  around (0, 0) one <&> around (1, 0) one <&> 
  around (-1, 1) one

// Test pattern with any rotation: Combine 
// 4 possible rotations with logical or.
let any = 
  pattern <|> rotate pattern <|> 
  rotate (rotate pattern) <|> 
  rotate (rotate (rotate pattern))

This sample uses various primitives to build a declarative specification of the pattern. The value any represents a function that you can run to test whether the pattern occurs at a given location. It handles all rotations of the pattern and it also does bounds checks. You'd also need to add mirrored patterns, but that would be quite easy extension.

Explaining the implementation would probably need a full blog post, but here is a commented source code that should be quite readable:

/// A type that represents a function that tests
/// whether an array contains some pattern at a 
/// specified location. It gets the location to 
/// test & the array as arguments and returns bool.
type ShapeDetector = SD of (int -> int -> int[,] -> bool)

/// A primitive that tests whether the value at the
/// current location contains a value 'v'
let equals v = SD (fun x y arr -> arr.[x,y] = v)

/// A combinator that takes 'ShapeDetector' and 
/// creates a new one that returns 'def' when 
/// accessing outside of the array bounds
let border def (SD f) = SD (fun x y arr -> 
  if x < 0 || y < 0 || x >= arr.GetLength(0) || y >= arr.GetLength(1) 
  then def else f x y arr)

/// A combinator that calls a given ShapeDetector
/// at a location specified by offset dx, dy
let around (dx, dy) (SD f) = SD (fun x y arr ->
  f (x + dx) (y + dy) arr)

/// A combinator that takes a ShapeDetector and
/// builds a new one, which is rotated by 90 degrees
let rotate (SD f) = SD (fun x y arr ->
  f -y x arr)

/// Creates a shape detector that succeeds only
/// when both of the arguments succeed.
let (<&>) (SD f1) (SD f2) = SD (fun x y arr ->
  f1 x y arr && f2 x y arr)

/// Creates a shape detector that succeeds 
/// when either of the arguments succeed.
let (<|>) (SD f1) (SD f2) = SD (fun x y arr ->
  f1 x y arr || f2 x y arr)

Finally, here is an example that runs the pattern detector on a sample 2D array:

// Create a 2D array as a sample input
let inp = 
  array2D [ [ 0; 0; 1 ]
            [ 0; 1; 0 ]
            [ 0; 1; 0 ] ]

// Get the underlying function and run it
// for all possible indices in the array
let (SD f) = any
for x in 0 .. 2 do
  for y in 0 .. 2 do
    printfn "%A %A" (x, y) (f x y inp)

Answer 2

You can find horizontal shapes using pattern matching in F# like this (do similarly for vertical shapes):

/// Try to match with horizontal shapes
/// 1 x x  and 1 1 x
/// x 1 1      x x 1
///
/// 1 1 x and x x 1
/// x x 1     1 1 x
/// could be found by reversing matched sub-arrays 
let matchHorizontalShapes (board: _ [] []) =
    let positions = ResizeArray()
    for i in 0..board.Length - 2 do
        for j in 0..board.[0].Length - 3 do
            match [|board.[i].[j..j+2];
                    board.[i+1].[j..j+2]|] with
            | [|[|1; 1; _|];
                [|_; 1; 1|]|] -> positions.Add((i, j), (i+1, j+1), (i+1, j+2))
                                 positions.Add((i, j), (i, j+1), (i+1, j+2))
            | [|[|1; _; _|];
                [|_; 1; 1|]|] -> positions.Add((i, j), (i+1, j+1), (i+1, j+2))
            | [|[|1; 1; _|];
                [|_; _; 1|]|] -> positions.Add((i, j), (i, j+1), (i+1, j+2))
            | _ -> ()
    positions.ToArray()