Bir tahtada desen/şekil eşleşmesi/tanıma nasıl yapılır (20x20)?

Question

tahta int[][] ve ben her şeyi 4 ile bu şekli

1 
    1 
    1 

bulmak istiyoruz simetrik (dönme) bulunuyor kurulu varyantları ve pozisyonları açın. , ör.

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

o sorunların bu tür başa F # kullanmak daha mı? Aşağıda

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

Bu, fonksiyonel programlama ve F # için kesinlikle mükemmel bir seçimdir. Çok sayıda olası yaklaşım var. Pad ile çözüm muhtemelen en direkt olanıdır ve gerçekten iyi bir başlangıç ​​noktasıdır. Eğer daha genel bir şeye ihtiyacınız varsa, o zaman Huusom'un çözümü gayet güzel. Bir dizi içinde kalıpları algılamak için etki alanına özgü bir dilde (DSL) oluşturmak için daha genel bir yaklaşım vardır. Bu daha gelişmiş bir fonksiyonel tekniktir, ancak örneğiniz için gerçekten güzel çalışır. Bunu yaptıysanız, oldukça karmaşık kalıpları gerçekten özlü bir şekilde ifade edebilirsiniz. Bu örnek model bir bildirim özellikleri oluşturmak için çeşitli ilkelleri kullanır

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

: Burada bir örnektir. any değeri, belirli bir konumda desen olup olmadığını sınamak için çalıştırabileceğiniz bir işlevi temsil eder. Desenin tüm dönüşlerini işler ve ayrıca sınır kontrolleri yapar. Aynca, yansıtılmış desenler eklemeniz gerekir, ancak bu oldukça kolay bir uzantı olacaktır.

uygulanmasını açıklayan muhtemelen tam blog yazısı gerekir, ancak burada oldukça okunaklı olmalıdır yorumladı kaynak kodu olacaktır: Nihayet

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

, burada örnek bir 2D üzerinde desen dedektör çalışan bir örnektir dizi:

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

Sen (dikey şekiller için benzer yapmak) böyle F # eşleştirme kalıbı kullanarak yatay şekiller bulabilirsiniz (yatay kontrol etmek kod simillar olan) dikey sadece desenleri kontrol etmek için benim C# kodu:

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

o zaman değerlerini almak ve değerlerin bilinen bir dizi sonucu eşleşebilir desen dayalı koordinat uzaklıklar bir dizi oluşturursanız.

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 

Bu işlevler (yukarıdaki adresinin örneğin) [(0,0); (1, -1); (1, -2)] bir desen ile çalışır.

Örneğinizde verilen int [] [] yerine Array2D (int [,]) kullandığımı unutmayın.