Once in an interview, I was asked to determine whether a somewhat filled in connect 4 board has a winner. Here’s an elegant solution using an arbitrary rotation function: Rotate the board 0°, 45°, 90°, 135°, and check for 4 in a row in each of those rotations.

Since I couldn’t find a good rotation solution online I decided to post a solution here (javascript):

var _ = require('underscore');

var rotateArray = function(array, degrees) {
    var radians = degrees * Math.PI / 180;
    var round = (f=>parseFloat(f.toFixed(13)));
    var coordinates = _.flatten(array.map((row,y) => row.map((value,x)=>({value,x,y}))));
    var translatedCoordinates = coordinates.map(spot=>({value: spot.value, x: round(spot.x*Math.cos(radians) - spot.y*Math.sin(radians)), y: round(spot.x*Math.sin(radians) + spot.y* Math.cos(radians)) }))
    var rows = _.chain(translatedCoordinates).groupBy(x=>x.y).values().sortBy(x=>parseFloat(x[0].y)).value();
    return rows.map(x=>_.pluck(x,"value"));
}

var hasFourInRow = function(array){
    var vectors = [0, 45, 90, 135];
    var matrixToString = (m => (m.map(r=>r.join("")).join("\n")));
    var versions = vectors.map(degrees => rotateArray(array, degrees)).map(matrixToString);
    return _.any(versions,(b=>b.indexOf("****")!==-1));
}

And to illustrate the use, here’s sample test cases:

var testCases = function(){
    var win1 = [['*','*','*','*'],
                [' ',' ',' ',' '],
                [' ',' ',' ',' '],
                [' ',' ',' ',' ']];
    var win2 = [['*',' ',' ',' '],
                ['*',' ',' ',' '],
                ['*',' ',' ',' '],
                ['*',' ',' ',' ']];
    var win3 = [['*',' ',' ',' '],
                [' ','*',' ',' '],
                [' ',' ','*',' '],
                [' ',' ',' ','*']];
    var win4 = [[' ',' ',' ','*'],
                [' ',' ','*',' '],
                [' ','*',' ',' '],
                ['*',' ',' ',' ']];
    var lose1 = [['*','*','*',' '],
                 ['*',' ','*','*'],
                 [' ','*','*','*'],
                 ['*','*',' ','*']];

    console.log([win1,win2,win3,win4, lose1].map(hasFourInRow));
    //outputs true, true, true, true, false
}

testCases();