Solution to OYUN16 problem #3

pentagons.js

var coordinates = [
    /*  0 */ [0, 0],
    /*  1 */ [0, 1],
    /*  2 */ [0, 2],
    /*  3 */ [0, 3],
    /*  4 */ [1, 0],
    /*  5 */ [1, 1],
    /*  6 */ [1, 2],
    /*  7 */ [1, 3],
    /*  8 */ [1, 4],
    /*  9 */ [2, 0],
    /* 10 */ [2, 1],
    /* 11 */ [2, 2],
    /* 12 */ [2, 3],
    /* 13 */ [3, 0],
    /* 14 */ [3, 1],
    /* 15 */ [3, 2],
    /* 16 */ [4, 1]
];
var connections = [
    /*  0 */ [1, 2, 3, 4, 9, 13],
    /*  1 */ [0, 2, 3, 4, 5, 10, 14, 16],
    /*  2 */ [0, 1, 3, 5, 6, 9, 11, 15],
    /*  3 */ [0, 1, 2, 6, 7, 10, 12, 13],
    /*  4 */ [0, 1, 5, 6, 7, 8, 9, 13],
    /*  5 */ [1, 2, 4, 6, 7, 8, 9, 10, 14, 16],
    /*  6 */ [2, 3, 4, 5, 7, 8, 10, 11, 13 ,15],
    /*  7 */ [3, 4, 5, 6, 8, 11, 12, 14],
    /*  8 */ [4, 5, 6, 7, 12, 15, 16],
    /*  9 */ [0, 2, 4, 5, 10, 11, 12, 13],
    /* 10 */ [1, 3, 5, 6, 9, 11, 12, 13, 14, 16],
    /* 11 */ [2, 6, 7, 9, 10, 12, 14, 15],
    /* 12 */ [3, 7, 8, 9, 10, 11, 15, 16],
    /* 13 */ [0, 3, 4, 6, 9, 10, 14, 15],
    /* 14 */ [1, 5, 7, 10, 11, 13, 15, 16],
    /* 15 */ [2, 6, 8, 11, 12, 13, 14, 16],
    /* 16 */ [1, 5, 8, 10, 12, 14, 15]
];


function intersects(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
    // returns true if two line segments intersects
    var side1 = (bx2-bx1)*(ay1-by2)-(by2-by1)*(ax1-bx2);
    var side2 = (bx2-bx1)*(ay2-by2)-(by2-by1)*(ax2-bx2);

    var side3 = (ax2-ax1)*(by1-ay2)-(ay2-ay1)*(bx1-ax2);
    var side4 = (ax2-ax1)*(by2-ay2)-(ay2-ay1)*(bx2-ax2);

    return side1*side2 <= 0 && side3*side4 <= 0;
}

Array.prototype.min = function() {
  return Math.min.apply(null, this);
};
Array.prototype.rotate = function(n) {
  for (var i=0; i < n; i++) {
    this.push(this.shift());
  }
} 


var pentagons = [];

for (var i1=0; i1 < connections.length; i1++) {
    var p1 = i1;
    for (var i2=0; i2 < connections[p1].length; i2++) {
        var p2 = connections[p1][i2];
        for (var i3=0; i3 < connections[p2].length; i3++) {
            var p3 = connections[p2][i3];
            for (var i4=0; i4 < connections[p3].length; i4++) {
                var p4 = connections[p3][i4];
                for (var i5=0; i5 < connections[p4].length; i5++) {
                    var p5 = connections[p4][i5];

                    // can visit points only once
                    if (p1 == p2 || p1 == p3 || p1 == p4 || p1 == p5 ||
                        p2 == p3 || p2 == p4 || p2 == p5 ||
                        p3 == p4 || p3 == p5 || p4 == p5) {
                        continue;
                    }

                    // should be closed
                    if (connections[p5].indexOf(p1) == -1) {
                        continue;
                    }

                    var points = [p1, p2, p3, p4, p5];
                    
                    // two consecutive points cannot be on same line. there is
                    // only one edge not two in following example: 0 -- 1 -- 2
                    var on_sameline = false;
                    for (var j=0; j < 5; j++) {
                        var pos1 = coordinates[points[j]];
                        var pos2 = coordinates[points[(j+1) % 5]];
                        var pos3 = coordinates[points[(j+2) % 5]];

                        if ((pos3[1] - pos1[1])*(pos2[0] - pos1[0]) == (pos2[1] - pos1[1])*(pos3[0] - pos1[0]) ||
                            (pos3[1] - pos1[1])*(pos2[0] - pos1[0]) == -(pos2[1] - pos1[1])*(pos3[0] - pos1[0])) {
                            on_sameline = true;
                            break;
                        }
                    }
                    if (on_sameline) {
                        continue;
                    }

                    // 
                    var has_intersection = false;
                    for (var j=0; j < 3 && !has_intersection; j++) {
                        var pos1 = coordinates[points[j]];
                        var pos2 = coordinates[points[j+1]];

                        for (var k=j+2; k < (j == 0 ? 4 : 5); k++) {
                            var pos3 = coordinates[points[k]];
                            var pos4 = coordinates[points[(k+1) % 5]];
                            
                            if (intersects(pos1[0], pos1[1], pos2[0], pos2[1], pos3[0], pos3[1], pos4[0], pos4[1])) {
                                has_intersection = true;
                            }
                        }
                    }
                    if (has_intersection) {
                        continue;
                    }

                    // add to list if not exists
                    var copy = points.slice();
                    copy.rotate(copy.indexOf(copy.min()));
                    if (copy[1] > copy[4]) {
                        copy.reverse();
                        copy.rotate(4);
                    }
                    var hash = copy.join();

                    if (pentagons.indexOf(hash) >= 0) {
                        continue;
                    }
                    pentagons.push(hash);

                    console.log(points.join());
                }
            }
        }
    }
}

console.log('COUNT: ' + pentagons.length);


/*******************************************************************************
RESULTS
==========

0,1,5,6,13
0,2,5,6,13
0,2,5,10,9
0,2,5,10,13
0,2,5,14,13
0,2,6,10,9
0,2,11,10,13
0,2,11,14,13
0,3,6,11,9
0,3,6,15,13
0,3,7,6,13
0,3,7,11,9
0,3,7,14,13
0,3,10,5,4
0,3,10,14,13
0,3,12,10,13
0,3,12,15,13
0,9,5,6,2
0,9,5,6,3
0,9,5,7,3
0,9,5,10,3
1,2,6,7,14
1,2,6,8,16
1,2,6,13,4
1,2,11,9,4
1,2,11,9,5
1,2,15,13,4
1,2,15,13,10
1,3,6,7,14
1,3,6,11,10
1,3,6,11,14
1,3,6,15,14
1,3,6,15,16
1,3,7,8,16
1,3,7,11,10
1,3,10,5,4
1,3,10,9,4
1,3,10,9,5
1,3,12,9,4
1,3,12,9,5
1,3,12,11,14
1,3,12,15,14
1,3,13,4,5
1,3,13,9,5
1,4,13,6,5
1,10,6,7,3
1,16,12,11,2
2,3,6,11,9
2,3,7,8,15
2,3,7,11,9
2,3,7,14,5
2,3,12,10,5
2,3,12,10,6
2,3,12,16,5
2,3,13,4,5
2,5,4,9,11
2,5,4,13,6
2,5,4,13,15
2,5,14,7,6
2,5,16,8,6
2,5,16,12,11
2,6,7,11,9
2,6,7,12,9
2,6,8,12,9
2,9,10,14,11
2,9,10,14,15
2,9,10,16,15
2,9,12,3,6
2,9,13,10,11
2,9,13,14,11
2,15,13,10,5
2,15,13,10,9
3,6,4,9,12
3,6,5,9,12
3,6,5,10,12
3,6,5,14,7
3,6,5,16,12
3,6,15,8,7
3,7,8,12,10
3,7,8,15,13
3,7,8,16,10
3,7,11,15,13
3,10,11,15,12
3,10,14,11,12
3,10,14,15,12
3,12,11,14,13
3,12,11,15,13
3,12,16,14,13
4,6,10,14,13
4,6,11,14,13
4,7,11,15,13
4,7,12,15,13
4,7,14,10,9
4,8,15,11,9
4,8,16,10,9
4,8,16,14,13
4,13,10,11,6
4,13,10,11,7
4,13,10,12,7
4,13,10,12,8
4,13,10,14,7
5,6,11,12,16
5,6,15,13,9
5,6,15,13,10
5,7,11,12,16
5,7,11,15,14
5,7,11,15,16
5,7,12,15,14
5,7,14,10,9
5,7,14,13,9
5,7,14,13,10
5,8,15,11,9
5,8,15,11,10
5,8,15,13,9
5,8,15,13,10
5,8,16,10,9
5,14,11,12,7
5,14,11,12,8
5,14,11,15,8
6,7,11,15,13
6,7,12,15,13
6,7,12,16,10
6,8,15,11,10
6,8,15,14,10
6,8,15,14,11
6,8,16,10,11
6,8,16,14,11
6,8,16,14,13
6,10,9,13,15
6,10,16,12,11
6,11,12,15,13
6,13,14,16,15
7,8,16,10,11
7,11,10,16,12
9,12,16,14,13
10,12,16,14,13

COUNT: 136

*******************************************************************************/