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#。有大量可能的方法。我认为 pad 的解决方案可能是最直接的解决方案，这是一个非常好的起点。如果您需要更通用的东西，那么 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)]（您上面的示例）的模式。

请注意，我使用 Array2D (int[,]) 而不是您的示例中给出的 int[][] 。

于 2012-09-07T12:44:46.177 回答