Solving systems of linear equations

Question

I am working on the following problem (http://www.enigmagroup.org/missions/programming/9/).

You have a 6x6 table where the first 5 columns and rows are comprised of different types of shapes, 5 total. The sixth row contains the sum of the values of the shapes for all columns for each column. And the sixth column contains the sum of the values of the shapes for all rows for each row.

I have to figure out the values for each of the shapes, and trying to do this by solving a system of five linear equations. Right now my problem is a brute force approach but it's not working out very well -- it freezes the browser (in Firefox scratchpad) when I try to run it.

How can I make it more efficient?

"use strict";

var CIRCLE = 1; 
var HEART = 2;
var SQUARE = 3;
var TRIANGLE = 4;
var STAR = 5; 
var BLANK = 6; 

var tableData = [];  // 5x5, length = 25
var sumRight = [];   // 1x5, length = 5 
var sumBottom = [];  // 5x1, length = 5

var countCircle = 0;
var countHeart = 0;
var countSquare = 0;
var countStar = 0; 
var countTriangle = 0; 
var countBlank = 0; 


var removeTags = function(s) {
    return s.replace(/<([^>]+)>/ig, '');
}; 

var at = function(x, y) {
    var index = y*5 + x;
    return (index >= 0 && index < tableData.length) ? tableData[index] : 0; 
}; 

var validSolution = function(v) {
    var right = []; 
    var bottom = []; 

    v[BLANK] = 0;
    v[CIRCLE] = v["CIRCLE"];
    v[SQUARE] = v["SQUARE"];
    v[TRIANGLE] = v["TRIANGLE"];
    v[STAR] = v["STAR"];

    for (var y = 0; y < 5; y++) {
        var rowSum = 0; 
        for (var x = 0; x < 5; x++)
            rowSum += v[at(x, y)]; 
        right.push(rowSum);
    }; 

    for (var x = 0; x < 5; x++) {
        var colSum = 0; 
        for (var y = 0; y < 5; y++)
            colSum += v[at(x, y)]; 
        bottom.push(colSum); 
    }

    return right == sumRight && bottom == sumBottom; 
}; 

var table = document.getElementById("game_grid");


// Parse input data into a readable format
for (var r = 0; r < table.rows.length; r++) {
    for (var c = 0; c < table.rows[r].cells.length; c++) {
        var cell = table.rows[r].cells[c]; 

        if (r < 5 && c < 5) {
            var img = cell.getElementsByTagName('img'); 

            if (img.length == 0) {
                tableData.push(BLANK); 
                countBlank++;
            }
            else {
                var src = img[0].src.split("/"); 
                src = src[src.length - 1];

                switch (src) {
                    case "circle.png":
                        tableData.push(CIRCLE); 
                        countCircle++; 
                        break;

                    case "heart.png":
                        tableData.push(HEART);
                        countHeart++; 
                        break;

                    case "square.png":
                        tableData.push(SQUARE);
                        countSquare++; 
                        break;

                    case "triangle.png":
                        tableData.push(TRIANGLE);
                        countTriangle++; 
                        break;

                    case "star.png":
                        tableData.push(STAR); 
                        countStar++; 
                        break;
                }
            }
        }

        else if (r == 5 && c < 5)
            sumBottom.push(parseInt(removeTags((cell.innerHTML))));

        else if (c == 5 && r < 5)
            sumRight.push(parseInt(removeTags((cell.innerHTML))));
    }
}


// Calculate a solution
var K = sumRight.concat(sumBottom).reduce(function(a, b) { return a + b; }); 
var minBound = 1; 
var maxBound = 300; 

var solution = (function() {
    for (var vC = minBound; vC <= maxBound; vC++) {
        if (vC*countCircle <= K) { 
            for (var vH = minBound; vH <= maxBound; vH++) {
                if (vC*countCircle + vH*countHeart <= K) {
                    for (var vT = minBound; vT <= maxBound; vT++) {
                        if (vC*countCircle + vH*countHeart + vT*countTriangle <= K) {
                            for (var vSQ = minBound; vSQ <= maxBound; vSQ++) {
                                if (vC*countCircle + vH*countHeart + vT*countTriangle + vSQ*countSquare <= K) {
                                    for (var vSR = minBound; vSR <= maxBound; vSR++) {
                                        if (vC*countCircle + vH*countHeart + vT*countTriangle + vSQ*countSquare + vSR*countStar == K) {
                                            var solution = {
                                                CIRCLE: vC, HEART: vH, TRIANGLE: vT,
                                                SQUARE: vSQ, STAR: vSR 
                                            }; 

                                            if (validSolution(solution)) return solution; 
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return null; 
})(); 


// Submit the solution
alert(solution);

Answer 1

1. I'm not a JavaScript developer but two things which could help: another algorithm, as RobH mentioned in his comment or running the calculations in a background thread. Web workers might fit but I'm not familiar with the topic. Maybe there are other solutions too.

2. In the solution function you could use guard clauses to make the code flatten and readable

   for (var vC = minBound; vC <= maxBound; vC++) {
       if (vC*countCircle > K) {
           continue;
       }
       for (var vH = minBound; vH <= maxBound; vH++) {
           if (vC*countCircle + vH*countHeart > K) {
               continue;
           }
           for (var vT = minBound; vT <= maxBound; vT++) {
               ...
           }
       }
   }
   

3. As far as I see vC*countCircle is calculated in every inner loop, vH*countHeart is calculated every inner loop except the first one, etc. but their values are rarely change. I don't know how far modern JavaScript engines optimize these loops but you could use local variables to avoid the unnecessary multiplications.

   for (var vC = minBound; vC <= maxBound; vC++) {
       var s1 = vC*countCircle;
       if (s1 > K) {
           continue;
       }
       for (var vH = minBound; vH <= maxBound; vH++) {
           var s2 = s1 + vH*countHeart;
           if (s2 > K) {
               continue;
           }
           for (var vT = minBound; vT <= maxBound; vT++) {
               var s3 = s2 + vT*countTriangle;
               if (s3 > K) {
                   continue;
               }
               ...
           }
       }
   }
   

   Use better variable names than s1, s2 etc. It would make the code readable. (Clean Code by Robert C. Martin, G19: Use Explanatory Variables; Refactoring: Improving the Design of Existing Code by Martin Fowler, Introduce Explaining Variable)