Matching a submatrix in an array. Circuit in circuit

Question

Ok, consider the following:

I have a large array containing arrays, -1, aand b.

-1 means the field is empty:

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

Now I want to check smaller arrays again:

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

To find out if an existing value from boardpattern in matches solutions.

---

Does it match aany pattern?
Does it match bany pattern?

---

Can any of you see a better way than doing a crazy nested loop:

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...
        }
    }
}

---

In this example, I used tic-tac-toe.

But I could be anything.

Answer 1

Very interesting question. +1 :) Here is my example.

http://jsfiddle.net/BuddhiP/J9bLC/ . .

. 0 -1, .

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

.

• , - (a b), .
• Else, , -
• Else, , .

.

, (Ex: [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;
};

, , ZERO, .

, . , _.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() , apply() .

, 4x4 , .

, , , , , - .

Answer 2

, . , , .

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 , .

Answer 3

, : , , , :

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

, (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 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 b 0s a 1s

, 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));