Connect 4 – illustration of Matrix rotation in js

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

My programming challenge

 

TRY IT OUT -> Zennish <- TRY IT OUT

A programming puzzle inspired by a programming career

Professional programming involves balance between the opposing philosophies of architecture (GRASP, SOLID) and pragmatism (KISS, YAGNI). Over-architected code front-loads difficulty to solve problems that won’t necessarily ever come. Under-architected code causes exponentially more pain with each new requirement, like a house on a bad foundation. Finding the middle ground consistently, our job, is hard. 

But in the real world the changes you have to make over your code are so spaced out and forgotten. Thus the feedback loop on your coding decisions may be months or years. Welcome to the garden of practice. When you make choices in this low-stakes sandbox it’ll only take minutes to reap what you have sewn. 

I also see this an alternative to traditional coding challenges (e.g. codility, google code jam) that challenges the traditional valuation of engineers on academic math-intensive skills. Expert engineering is not about plugging a sequence of numbers into the OEIS; it’s creative composition.

Try it out

Refactoring with Functional Programming Like a Boss in Javascript

An example case for refactoring with javascript with functional programming.

Let’s consider an issue that recently came up for a game I was working on. I wanted to effectively create a gradient across the time dimension (i.e. that is a smooth color transition over time). This can create a flashing effect or be used for a number of other cases. In order to make this versatile I decided I wanted a function that would take two colors, and a float (0 to 1) that would represent how much of color2 should be used in the mixture (the rest would be color 1). Thus at partial_mix(c1, c2, 0) we should get just c1, and at partial_mix(c1, c2, 1) we should get just c2.

A sample solution ***BAD CODE***:


/**
* A bad solution to this problem
*/
partial_mix: function(c1, c2, pct_b) {
var red1, blue1, green1, red2, blue2, green2; 
red1 = parseInt(c1.substr(0,2));
green1 = parseInt(c1.substr(2,2));
blue1 = parseInt(c1.substr(4,2));

red2 = parseInt(c2.substr(0,2));
green2 = parseInt(c2.substr(2,2));
blue2 = parseInt(c2.substr(4,2));

var mixture = mix(red1, red2, pct_b) + mix(green1, green2, pct_b) + mix(blue1, blue2, pct_b);
}

function mix(n1, n2, pct_b){
return (n1 + (n2 - n1) * pct_b).to2dhex();
}

Problem 1: Not dry across Red, Green, and Blue. We did the exact same thing to red, green, and blue, yet we copy pasted to handle the redundancy. Not good. Better to use arrays (with the added benefit of easing the process of adding an alpha color later):


var x, color1 = [], color2 = [], result=[];
for (x=0; x < 3; x++) {
color1[x] = parseInt(c1.substr(2*x, 2*(x+1)), 16 );
color2[x] = parseInt(c2.substr(2*x, 2*(x+1)), 16) ;
result[x] = mix(color1[x], color2[x], pct_b);
}
return result.join("");

Problem 2: Code assumes 6 digit format. What if we want to be able to pass 3 character formats too (for either, neither, or both parameters)?

It should be apparent pretty quickly that it’s not pretty to make the code we have versatile in this respect. Instead let’s regularize our input so that it always is 6 digit then leave our code intact:


var doubleString = function(str) { return "" + str + str;}; 
var toSixDigitColor = function(color) { 
    if (color.length < 6) {
      return color.split("").map(doubleString).join("");
    }
   return color;
}

c1 = toSixDigitColor(c1);
c2 = toSixDigitColor(c2);
.
.
.
}

Problem 3: Still duplicates the code performed on color1 and color2:

mix_colors: function(c1, c2, pct_b) {
var mix = function (c1, c2) { ... };
var doubleString = function (str) {...}; 
var toSixDigitColor = function (color) {...};

var shades = [c1,c2].map(function(color) {
color = toSixDigitColor(color);
return color.split("").chunk(2).map(function(a) { return parseInt(a.join(""),16); }); /* convert to an array of 3 values */
});

return _.zip(shades[0],shades[1]).map2red(mix).join("");
}

And that’s what I call leveraging functional programming in javascript. We know it’s well-written code because when we ask what we have to do to add an alpha color, we realize the answer is nothing, it’s versatile enough to do it automatically (even when we combine the requirements of allowing single-digit colors). Notice I pull in underscore for zip, and write two custom functions: map2red and chunk.


Number.prototype.to2dhex = function() { return ("0" + parseInt(this).toString(16)).substr(-2); };

// More on a more general solution to this later
Array.prototype.map2red = function(func) { return this.map(function(v) { return v.reduce(func); }) };

// Breaks an array into sub arrays of length = size
//this is begging to be rewritten as a right apply on divide composed with parseInt passed to _.groupBy
Array.prototype.chunk = function(size) { 
var tmp = [], x; 
for (x=0; x < this.length; x++) {
  tmp[parseInt(x/size)] = tmp[parseInt(x/size)] || []; 
  tmp[parseInt(x/size)].push(this[x]);
} 
return tmp; 
};