8

ボードはint[][]、この形を見つけたいです

  1
    1
    1

ボードからの対称（回転）バリアントの4つすべてを使用して、位置をログに記録します。例えば

      ...
      ...
  ... 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# コードです (水平方向にチェックするコードも同様です)。

    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;
    }
4

3 に答える 3

15

これは間違いなく、関数型プログラミングと 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)
于 2012-09-07T14:01:57.193 に答える
4

次のように、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()
于 2012-09-07T11:39:48.737 に答える
1

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

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[,]) を使用していることに注意してください。

于 2012-09-07T12:44:46.177 に答える