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