Starwar Challenge

starwar.js

function standardDeviation(values) {
    var avg = average(values);

    var squareDiffs = values.map(function (value) {
        var diff = value - avg;
        var sqrDiff = diff * diff;
        return sqrDiff;
    });

    var avgSquareDiff = average(squareDiffs);

    var stdDev = Math.sqrt(avgSquareDiff);
    return stdDev;
}

function average(data) {
    var sum = data.reduce(function (sum, value) {
        return sum + value;
    }, 0);

    var avg = sum / data.length;
    return avg;
}
String.prototype.levenshtein = function (str) {
    core = this.split('').filter(function (el, i, arr) {
        return arr.indexOf(el) === i;
    }).sort().join();
    str = str.split('').filter(function (el, i, arr) {
        return arr.indexOf(el) === i;
    }).sort().join();
    deviation = standardDeviation([core.length, str.length]);
    mean = average([core.length, str.length]) / 2;
    var cost = new Array(),
        str1 = str,
        str2 = core,
        n = str1.length,
        m = core.length,
        i, j;

    var minimum = function (a, b, c) {
        var min = a;
        if (b < min) {
            min = b;
        }
        if (c < min) {
            min = c;
        }
        return min;
    }

    if (n == 0) {
        return;
    }
    if (m == 0) {
        return;
    }

    for (var i = 0; i <= n; i++) {
        cost[i] = new Array();
    }

    for (i = 0; i <= n; i++) {
        cost[i][0] = i;
    }

    for (j = 0; j <= m; j++) {
        cost[0][j] = j;
    }

    for (i = 1; i <= n; i++) {

        var x = str1.charAt(i - 1);

        for (j = 1; j <= m; j++) {

            var y = str2.charAt(j - 1);

            if (x == y) {

                cost[i][j] = cost[i - 1][j - 1];

            } else {

                cost[i][j] = 1 + minimum(cost[i - 1][j - 1], cost[i][j - 1], cost[i - 1][j]);
            }

        }//endfor

    }//endfor
    return (cost[n][m] + deviation) < mean;
}

function relative(me, you) {
    return me.levenshtein(you);
}
var bigO = 0;
function seeking(records) {
    var planets = {};
    var ancient = records[0];
    ancient.birth = new Date(ancient.birth);
    for (var i = 0; i < records.length; i++) {
        var member = records[i];
        member.birth = new Date(member.birth);
        if (ancient.birth > member.birth) {
            ancient = member;
        }
        var members = planets[records[i]['planet']] ? planets[records[i]['planet']] : [];
        members.push(records[i]);
        planets[records[i]['planet']] = members;
    }
    var ancients = planets[ancient.planet];
    delete planets[ancient.planet];
    var lastStand = ancient;
    for (i = 0; i < ancients.length; i++) {
        ancients[i]['family'] = [];
        Object.keys(planets).forEach(function (j) {
            for (k = 0; k < planets[j].length; k++) {
                if (relative(planets[j][k]['name'], ancients[i]['name'])) {
                    ancients[i]['family'].push(planets[j][k]);
                    if(lastStand.birth < planets[j][k].birth)
                    	lastStand = planets[j][k];
                    planets[j].splice(k, 1);
                }
            }
        });
    }
    console.log(ancients);//Jedi
    console.log(planets);//Sith
    return lastStand.planet;//last stand
}
var records = [
    {name: "Unkar Lop", birth: "1727-01-25", planet: "Felucia"},
    {name: "lowatp", birth: "1723-11-10", planet: "Coruscant"},
    {name: "npoolno", birth: "1726-01-04", planet: "Felucia"},
    {name: "alnappopaw", birth: "1460-10-01", planet: "Hoth"},
    {name: "supwwlanabohum", birth: "1129-05-28", planet: "Tatooine"},
    {name: "jplooe", birth: "1614-03-15", planet: "Felucia"},
    {name: "walollpace", birth: "1503-05-24", planet: "Tatooine"},
    {name: "preiolsha", birth: "1609-06-04", planet: "Coruscant"},
    {name: "ypirumolpa", birth: "1134-11-19", planet: "Hoth"},
    {name: "mopuamangl", birth: "1731-07-05", planet: "Tatooine"},
    {name: "lnpooto", birth: "1455-01-06", planet: "Tatooine"}
];
console.log(seeking(records));