ボード（20x20）のパターン/形状一致/認識を行う方法は？

Question

ボードはint[][]であり、私はそれがすべて4が対称（回転）だと、この形状

1 
    1 
    1 

を見つけたいボードから変異体および位置を記録します。例：

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

このような問題に対処するためにF＃を使用する方がよいですか？

以下

は垂直方向にのみパターンをチェックするための私のC＃コードである（水平にチェックするためのコードが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

これは間違いなく関数型プログラミングとF＃に最適です。可能なアプローチは多数あります。私はパッドによる解決策がおそらく最も直接的なものだと思います。それは本当に良い出発点です。より一般的なものが必要な場合は、Huusomによる解決策はかなりいいです。

アレイ内のパターンを検出するために（DSL）というドメイン固有の言語を構築することがさらに一般的なアプローチです。これはより高度な機能テクニックですが、あなたの例ではうまく機能します。あなたがそれをしたら、非常に複雑なパターンを本当に簡潔な方法で表現できます。このサンプルでは、​​パターンの宣言型仕様を構築するために、様々なプリミティブを使用しています

// 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)) 

：ここでは一例です。値anyは、パターンが特定の場所にあるかどうかをテストするために実行できる関数を表します。それはパターンのすべての回転を処理し、またチェックを行います。また、ミラーリングされたパターンを追加する必要がありますが、それは非常に簡単な拡張になります。実装を説明する

はおそらく完全なブログ記事を必要とするが、ここではかなり読みやすいべきであるコメントのソースコードであるでしょう：

/// 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) 

は最後に、ここではサンプル2Dにパターン検出を実行する例です。配列：

// 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

あなたは（垂直形状についても同様に行う）。このようなF＃でパターンマッチングを使用して水平方向の形状を見つけることができます。

/// 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() 

Answer 3

あなたがパターンに基づいてcoordinatオフセットのセットを作成した場合、あなたは値を取得し、値の既知のセットに結果を一致させることができます。

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 x y) 

    // 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 

この機能は（上からあなたの例）[(0,0); (1, -1); (1, -2)]のパターンで動作します。

私は、あなたの例で与えられたint [] []の代わりにArray2D（int [、]）を使用しています。