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

Question

The int[][] board, and I would like to find this form

  1 1 1 

with all four of them symmetrical (rotational) options from the board and log positions. eg.

  ... ... ... xxxxxx ... ... xx 1 1 xx ... ... x 1 xxxx ... ... xxxxxx ... ... ... 

Is it better to use F # to solve these problems?

Below is my C # code for checking patterns only vertically (the code for checking 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 great for functional programming and F #. There are many possible approaches. I think the pad decision is probably the most straightforward, and that is a really good starting point. If you need something more general then Huusom's solution is pretty nice.

There is an even more general approach, which is to create a domain (DSL) for defining patterns in an array. This is a more advanced functional technique, but it works great for your example. If you did, you could express rather complex patterns in a very 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 example uses various primitives to create a declarative specification for the template. The value any is a function that you can run to check if a pattern is occurring in a specific place. It handles all the rotation of the template, and also checks the boundaries. You will also need to add mirror templates, but this will be a fairly simple extension.

An explanation of the implementation will probably require a full blog post, but here is the code with comments, which should be 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 xy 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 xy arr -> if x < 0 || y < 0 || x >= arr.GetLength(0) || y >= arr.GetLength(1) then def else fxy arr) /// A combinator that calls a given ShapeDetector /// at a location specified by offset dx, dy let around (dx, dy) (SD f) = SD (fun xy 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 xy arr -> f -yx arr) /// Creates a shape detector that succeeds only /// when both of the arguments succeed. let (<&>) (SD f1) (SD f2) = SD (fun xy arr -> f1 xy arr && f2 xy arr) /// Creates a shape detector that succeeds /// when either of the arguments succeed. let (<|>) (SD f1) (SD f2) = SD (fun xy arr -> f1 xy arr || f2 xy arr) 

Finally, here is an example that runs a 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) (fxy inp) 

Answer 2

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

 /// Try to match with horizontal shapes /// 1 xx and 1 1 x /// x 1 1 xx 1 /// /// 1 1 x and xx 1 /// xx 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() 

Answer 3

If you create a set of correlation offsets based on a template, you can get the values ​​and compare the result with a known set of values.

 let find_matches board pattern = let xb = Array2D.length1 board let yb = Array2D.length2 board // safe lookup on board let get_value= function | (x, _) when (x < 0) || (x >= xb) -> None | (_, y) when (y < 0) || (y >= yb) -> None | (x, y) -> Some (Array2D.get board xy) // do a patten match on board. let has_pattern = function | [Some 1; Some 1; Some 1] -> true | _ -> false // se if a given coordinate is a match let is_match (x,y) = pattern |> List.map (fun (x',y') -> (x+x', y+y')) // expand the coordinat to a list of coordinates |> List.map get_value // find the values coordinates |> has_pattern // match to pattern [for x in 0..(xb-1) do for y in 0..(yb-1) -> x, y] |> List.filter is_match 

These functions work with the pattern [(0,0); (1, -1); (1, -2)] [(0,0); (1, -1); (1, -2)] [(0,0); (1, -1); (1, -2)] (your example is above).

Note that I use Array2D (int [,]) instead of int [] [] in your example.