匹配數組中的子數組。方案在方案

Question

好吧，想想看：

我有一個包含arrays，-1，a和b一個大陣。

的-1意味着該字段爲空：

var board = [ 
    [-1,-1, a], 
    [-1,-1, b], 
    [ b,-1, a] 
] 

現在我要檢查較小的陣列agains這樣的：

var solutions = [ 
    [ 
     [1, 1, 1] 
    ], 
    [ 
     [1], 
     [1], 
     [1] 
    ], 
    [ 
     [1], 
     [0,1], 
     [0,0,1] 
    ], 
    [ 
     [0,0,1], 
     [0,1], 
     [1] 
    ] 
] 

從board比賽中solutions格局看是否存在價值。

---

a是否匹配任何模式？
b是否匹配任何模式？

---

任何你能看到比發出瘋狂的嵌套循環更好的方法：

var q,w,e,r,t,y; 

q=w=e=r=t=y=0; 

for(; q < 3; q++) { 
    for(; w < 3; w++) { 
     for(; e < SOLUTIONS.length; e++) { 
      .... and so on... 
     } 
    } 
} 

---

在這個例子中，我已經使用井字棋。

但我可以是任何東西。

Answer 1

非常有趣的問題。 +1 :)這是我的承諾。

查看我的小提琴http://jsfiddle.net/BuddhiP/J9bLC/獲取完整解決方案。我會試着在這裏解釋一下主要觀點。

我從這樣一塊板子開始。我使用0而不是-1，因爲它更容易。

var a = 'a', b = 'b'; 
    var board = [ 
     [a, 0, a], 
     [b, b, b], 
     [a, 0, a] 
     ]; 

我的策略很簡單。

1. 檢查是否有任何行具有相同的玩家（a或b），如果是的話我們有贏家。
2. 否則，檢查是否有任何列具有相同的球員
3. 否則，檢查對角線有一個球員

這些都是三個打贏官司。

首先，我創建了一個函數，它可以接受一組行（例如：[a，0，b]），並檢查整行是否包含相同的值，如果該值不爲零（或-1案件）。

checkForWinner = function() { 
    lines = Array.prototype.slice.call(arguments); 
    // Find compact all rows to unique values. 
    var x = _.map(lines, function (l) { 
     return _.uniq(l); 
    }); 
    // Find the rows where all threee fields contained the same value. 
    var y = _.filter(x, function (cl) { 
     return (cl.length == 1 && cl[0] !== 0); 
    }); 
    var w = (y.length > 0) ? y[0] : null; 
    return w; 
}; 

在這裏我採取了連續的唯一值，如果我只能找到一個不爲零的唯一值，那麼他就是贏家。

如果在行中沒有優勝者，我然後檢查列。爲了重用我的代碼，我使用_.zip（）方法將列轉換爲行，然後使用上面相同的函數來檢查我們是否有贏家。

var board2 = _.zip.apply(this, board); 
winner = checkForWinner.apply(this, board2); 

如果我仍然沒有找到勝利者，請檢查對角線的時間。我已經寫了這個函數來從板上提取兩個對角線作爲兩行，並使用相同的checkForWinner函數來查看對角線是否被任何玩家支配。

extractDiagonals = function (b) { 
    var d1 = _.map(b, function (line, index) { 
     return line[index]; 
    }); 
    var d2 = _.map(b, function (line, index) { 
     return line[line.length - index - 1]; 
    }); 
    return [d1, d2]; 
}; 

最後，這是我真正把該板的贏家：

// Check rows 
winner = checkForWinner.apply(this, board); 
if (!winner) { 
    var board2 = _.zip.apply(this, board); 

    // Check columns, now in rows 
    winner = checkForWinner.apply(this, board2); 
    if (!winner) { 
     var diags = extractDiagonals(board); 
     // Check for the diagonals now in two rows. 
     winner = checkForWinner.apply(this, diags); 
    } 
} 

如果你們想知道爲什麼我用apply（）方法，而不是直接調用該函數，原因是應用（ ）允許您將數組元素作爲參數列表傳遞給函數。

我相信這應該適用於4x4或更高的matrics，儘管我沒有測試它們。

我沒有多少時間來測試解決方案，所以請讓我知道，如果你發現任何錯誤。

Answer 2

不，你只能做需要三個嵌套循環：一個循環在你的模式，和兩個循環的二維的比賽場地：

function checkPatterns(patterns, player, field) { 
    pattern: for (var p=0; p<patterns.length; p++) { 
     for (var i=0; i<patterns[p].length; i++) 
      for (var j=0; j<patterns[p][i].length; j++) 
       if (patterns[p][i][j] && player !== field[i][j]) 
        continue pattern; 
     // else we've matched all 
     return p; 
    } 
    // else none was found 
    return -1; 
} 
function getSolution(player) 
    return SOLUTIONS[checkPatterns(SOLUTIONS, player, currentBOARD)] || null; 
} 

OK，您可能需要爲玩家第四圈（players.any(getSolution)），但這並不會讓它變得更瘋狂，並且可能只會爲兩名玩家內聯。

但是，它可能比制定「模式陣列」構建算法模式本身更容易：

function hasWon(player, field) { 
    vert: for (var i=0; i<field.length; i++) { 
     for (var j=0; j<field[i].length; j++) 
      if (field[i][j] !== player) 
       continue vert; 
     return "vertical"; 
    } 
    hor: for (var j=0; j<field[0].length; j++) { 
     for (var i=0; i<field.length; i++) 
      if (field[i][j] !== player) 
       continue hor; 
     return "horizontal"; 
    } 
    for (var i=0, l=true, r=true, l=field.length; i<l; i++) { 
     l == l && field[i][i] === player; 
     r == r && field[l-i-1][l-i-1] === player; 
    } 
    if (l || r) 
     return "diagonal"; 
    return null; 
} 

Answer 3

你可以做的是編譯模式的速度。與相同語言相同的方式允許爲速度編譯正則表達式。

function compile(pattern) { 
    var code = "matcher = function(a) { return " 
    var first = null 
    for (var n = 0; n < pattern.length; n++) { 
     for (var m = 0; m < pattern[n].length; m++) { 
      if (pattern[n][m] == 0) continue 
      var nm = "["+n+"]["+m+"]" 
      if (first == null) { 
       code += "a" + nm + " != -1"; 
       first = " && a" + nm + " == " 
      } 
      code += first + "a" + nm 
     } 
    } 
    code += "; }"; 
    eval(code); 
    return matcher 
} 

那麼這是幹什麼的？

例如

compile([[1],[0,1],[0,0,1]]).toString() 

將創建下列函數

"function (a) { return a[0][0] != -1 && a[0][0] == a[0][0] && a[0][0] == a[1][1] && a[0][0] == a[2][2]; }" 

那麼你如何使用它？

要匹配你的董事會職位如下

var patterns = solutions.collect(function(each) { return compile(each); }) 
var matches = patterns.any(function(each) { return each(board); }) 

 

NB，使用它的最後剪斷上述假設你正在使用的許多流行的高階編程庫之一，例如lodash，以便在數組原型上提供collect和any函數，而不是使用plain old for循環。

Answer 4

你可以有你的主板是一個字符串：

var board = 
    "-1,-1,a, 
    -1,-1,b, 
    b,-1,a" 

和您的解決方案可能是一個字符串數組（類似於板）

var solutions = [ 
    "1,1,1, 
    0,0,0, 
    0,0,0" 
    , 
    "1,0,0, 
    0,1,0, 
    0,0,1" 

]

然後爲了進行比較，用-1代替-1和b，用1代替a，然後簡單地比較字符串

這比在另一個迴路內有10個不同的迴路要快得多

Answer 5

你總是需要循環才能通過這一切。您可以簡化閱讀和更靈活。下面的代碼適用於大於1的任意數量的行/列，並且對於2個以上的玩家也可以進行簡單的調整。

var board1 = [ 
[-1,-1, 'a'], 
[-1,-1, 'b'], 
['b',-1, 'a'] 
]; 
var board2 = [ 
['a','a', 'a'], 
[-1,-1, 'b'], 
['b',-1, 'a'] 
]; 
var board3 = [ 
[-1,'b', 'a'], 
[-1,'b', 'b'], 
['b','b', 'a'] 
]; 
var board4 = [ 
['a',-1, 'a'], 
[-1,'a', 'b'], 
['b',-1, 'a'] 
]; 

var solutions = [ 
[ 
    [1, 1, 1] 
], 
[ 
    [1], 
    [1], 
    [1] 
], 
[ 
    [1], 
    [0,1], 
    [0,0,1] 
], 
[ 
    [0,0,1], 
    [0,1], 
    [1] 
] 
]; 

function checkForWinner(playfield) { 
    var sl = solutions.length; //solutions 
    var bl = playfield.length; //board length 
    var bw = playfield[0].length; //board width 
    while(sl--) { 
     //foreach solution 
     var l = solutions[sl].length; 

     if (l==1) { 
      //horizontal 
      //loop trough board length to find a match 
      var tl = bl; 
      while(tl--) { 
       var pat = playfield[tl].join('') 
       var r = checkRow(pat) 
       if (r!==false) 
        return r; 
      } 
     } else { 
      //vertical or diagonal 
      var l1 = solutions[sl][0].length; 
      var l2 = solutions[sl][1].length; 

      if (l1==l2) { 
       //vertical     
       var tw = bw; 
       while (tw--) { 
        //loop for each column 
        var pat = ""; 
        var tl = l; 
        while(tl--) { 
         //loop for vertical 
         pat += playfield[tl][tw]; 
        } 

        var r = checkRow(pat) 
        if (r!==false) 
         return r; 
       } 

      } else { 
       //diagonal 
       var pat = ""; 
       while(l--) { 
        //loop for vertical 
        var tw = solutions[sl][l].length; 
        while (tw--) { 
         //loop for horizontal      
         if (solutions[sl][l][tw]!=0) 
          pat += playfield[l][tw]; 
        } 
       } 

       var r = checkRow(pat) 
       if (r!==false) 
        return r; 
      } 
     } 
    } 
    return 'no winner'; 
} 

function checkRow(pat) { 
    if (!(pat.indexOf('a')>=0 || pat.indexOf('-1')>=0)) { 
     //only b on row. player B won 
     return 'B'; 
    } 

    if (!(pat.indexOf('b')>=0 || pat.indexOf('-1')>=0)) { 
     //only a on row. player A won 
     return 'A'; 
    } 

    return false; 
} 

console.log(checkForWinner(board1)); 
console.log(checkForWinner(board2)); 
console.log(checkForWinner(board3)); 
console.log(checkForWinner(board4));