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

The Professional Web Codebase

One of the major advantages of the high career mobility in SF … Cross pollination. Yet each new codebase I comes to seems to lack a few of the following. So I figured I’d list out the essentials that every web codebase should have.

  1. The Obvious: Git, IDE, MV*, relational DB, 3 environments that match production.
  2. Language regularization:Each language has its own idiosyncrasies. Learn your languages weakness and make helper functions to accommodate. In PHP, these weaknesses include single-threaded, bad undefined index default behavior.My preferred solution to PHP’s single-threaded limitations is to make use of a job queue. This will emulate additional threads for heavy tasks (e.g. sending emails to all of your user base) or high-latency tasks that ideally should be asynchronous (e.g. certain API calls). I’ve seen this done well, and I’ve seen it done poorly. From experience, I’d point out the following lessons: don’t use a message queue as a job queue and the DB is a great place to store a home-grown job queue [because it provides great visibility, resilience, can be controlled programatically, can be exported to disk, is atomic, etc].

    In PHP, out-of-bound reads on arrays return null and log a notification to the event log. As this is never the engineer’s intent, I always write two helper functions. One that looks up an key and returns a specific value if the key isn’t found (for cases where you’re using the array as a set). The other function looks up the key and returns an exception if the key is not found (for normal cases where the key should always be present).

    I strongly believe once you handle these edge cases most popular languages are pretty interchangeable (javascript, java, php, python, ruby).

  3. A powerful, generic staging environmentOne of the most impressive and useful technologies I saw was something we called humblebrag. It was a script that caught all requests to *.company.com/…. It then took the *, checked-out the corresponding git branch, and mapped the request to that particular branch. Thus in effect, we had a zero-effort way to have all branches usable simultaneously on a single server, even by non-engineers.Doing this can be a little harder in more complex environments with versioned services listening on ports, if you don’t plan for it early.
  4. A circuit breaker. Download one from github.
  5. An ability to do cross-server mutexes.
  6. A simple, generic read-through-caching function.
  7. A powerful logging system connected to an alerting system
  8. An A/B test system. Even if you’re not doing A/B tests on user-experience, it can be a great way to rollout to a small portion of users or internal-testers to ensure stability on a new environment.

 

 

Returning random ordered results in MS access

You may be shocked to hear, but back when I was young I used the now-hated Visual Basic and Access. In fact, moving these applications to PHP on the job is how I first learned PHP.

Anyways, once I was trying to return random results in an sql query to an Access MDB from VB / vba and I scoured the internet and found nothing. Then I devised this little number, which probably for all practical purposes does the trick:

ORDER BY right(right(now*10000000000, 4) ^ (1/ID),4)

where ID is the unique id for the given table. Right(now*100000000000,4) basically gets you a pseudo-random 4-digit value, the current milliseconds. We combine this with the row ID to give a different but constantly changing number for each row.