triangle finder

by Ryan

JavaScript

//diamond
var e1 = [
    [1, 2, 3],
    [0, 2, 4],
    [0, 1, 3, 4],
    [0, 2, 4],
    [1, 2, 3]
];

//bowtie
var e2 = [
    [1, 2],
    [0, 2],
    [0, 1, 3, 4],
    [2, 4],
    [2, 3]
];

//square
var e3 = [
    [1, 3],
    [0, 2],
    [1, 3],
    [0, 2]
];

//square with a diagonal
var e4 = [
    [1, 2, 3],
    [0, 2],
    [0, 1, 3],
    [0, 2]
];

getIntersection = function(list1, list2){
    le = {};
    list1.forEach(function(e1){
        var te1 = le[e1];
        if(te1 != null){
            le[e1][0] += 1; //store a count for each one in 1
        } else {
            le[e1] = [1,0];
        }
    });
    list2.forEach(function(e2){
        var te = le[e2];
        if(te != null && te[0] > 0){
            le[e2][1] += 1;
            le[e2][0] -= 1;
        }
    });
    var toReturn = [];
    for(var k in le){
        if(le[k][1] > 0){
            for(var i=0; i<le[k][1]; i++){
                toReturn.push(k);
            }
        }
    }
    return toReturn;
};

getTriangleCount = function(edges){
    var count = 0;
    edges.forEach(function(elements, a){
        elements.forEach(function(b){
            // a - b is an edge
            var aList = edges[a];
            var bList = edges[b];
            var iList = getIntersection(aList, bList);
            count += iList.length;
        });
    });

    //div by 6 because each vertex counts its triangle and both directions are counted
    return count/6; 
};

console.log("Diamond should have 4 triangles: " + getTriangleCount(e1));
console.log("Bowtie  should have 2 triangles: " + getTriangleCount(e2));
console.log("Square  should have 0 triangles: " + getTriangleCount(e3));
console.log("Sq w/Di should have 2 triangles: " + getTriangleCount(e4));