Create a grid with set constraints

Question

I'm building a little grid which needs to be generative to 6x6, but it needs to conform to 4 key constraints. Currently it conforms to 3. I can't work out how to manage the fourth.

So what has to happen here is that:

For each row there can't be more than 2 numbers of the same type consecutively
the numbers are picked randomly
for each column there can't be more than 2 numbers of the same type consecutively
there can be a maximum of 3 of each type of number going by column or row

Here is the current code:

// JavaScript Document
$(document).ready(function () {
    var grid = new anyGrid(6, 6);
    for (var i = 0; i < grid.length; i++) {
        var printIt = "";
        for (var j = 0; j < grid[0].length; j++) {
            printIt += grid[i][j] + "  ";

        }
        console.log(printIt);
    }


});

function anyGrid(rows, cols) {
    var grid = [];
    for (var i = 0; i < rows; i++) {
        grid.push(new Array(cols));
    }
    var row = 0;
    for (var col = 0; col - row < cols; col++) {
        for (var r = row; r >= 0 && col - r < cols;) {
            setBit(grid, r, col - r--);
        }
        if (row < rows - 1) row++;
    }
    return grid;
}

function setBit(grid, row, col) {
    var vInd = calcVerticalIndicator(grid, row, col);
    var hInd = calcHorizontalIndicator(grid, row, col);
    if (isPartiallyRestricted(vInd, hInd)) {
        grid[row][col] = flip(vInd);
    } else if (isFullyRestricted(vInd, hInd)) {
        grid[row][col] = vInd;
        grid[row - 1][col] = flip(vInd);
    } else {
        grid[row][col] = Math.abs(vInd) <= 1
            ? flip(vInd)
            : Math.abs(hInd) <= 1 ? flip(hInd) : anyBit();
    }
}

function isPartiallyRestricted(vInd, hInd) {
    return vInd == hInd;
}

function isFullyRestricted(vInd, hInd) {
    return vInd + hInd == 1;
}

function calcVerticalIndicator(grid, row, col) {
    return calcIndicator(grid, row - 1, col, row - 2, col, 2);
}

function calcHorizontalIndicator(grid, row, col) {
    return calcIndicator(grid, row, col - 1, row, col - 2, 4);
}

function calcIndicator(grid, row1, col1, row2, col2, unrestricted) {
    try {
        return grid[row1][col1] * grid[row2][col2] + (grid[row1][col1] - grid[row2][col2]) * unrestricted;
    } catch (e) {
        return unrestricted;
    }
}

function anyBit() {
    return getRandomInt(0,1);
}

function flip(bit) {
    return bit == 0 ? 1 : 0;
}

function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

The problem:

Currently it satisfies 3 of the 4 conditions, but what is required is that there are not more than 3 of each number in any row or column. How do I amend my code to make this possible?

example outputs:

0  1  1  0  1  0   
1  1  0  0  1  0  
1  0  1  1  0  1  (violation of 4 1s) 
0  0  1  0  0  1  (violation of 4 0s)  
1  1  0  0  1  0   
1  1  0  1  1  0  (violation of 4 1s)
^  ^     ^  ^  ^
Violations

0  0  1  0  1  1   
0  1  1  0  1  1   (violation of 4 1s)
1  0  0  1  0  0   (violation of 4 0s)
0  0  1  0  0  1   
1  1  0  0  1  1   (violation of 4 1s)
1  1  0  1  1  0   (violation of 4 1s)
         ^  ^  ^
      Violations

Patrick · Accepted Answer

This seems to work. Not sure if it is exactly what you are looking for since I removed the horizontal and vertical indicators, but seems to be able to generate a random grid with your constraints. I kept track of the number of times a character/bit appeared in row/col through the usedNumbers object.

I tried to keep a simplistic approach (i.e. an if statement for each of your listed constraints)... I tried to make it configurable for rows/cols in the grid along with "available characters" for the grid values (in case you want to expand). Of course, some solutions won't be possible since you might repeat more than 3 characters if the alphabet is too small and the grid too large (e.g. 0,1 bits for a 7x7). Here is the jsfiddle.

(function () {
    //Polyfill for Array.indexOf... Needed for older browsers.
    if (!Array.prototype.indexOf) {
        Array.prototype.indexOf = function (searchElement, fromIndex) {
          if ( this === undefined || this === null ) {
            throw new TypeError( '"this" is null or not defined' );
          }

          var length = this.length >>> 0; // Hack to convert object.length to a UInt32

          fromIndex = +fromIndex || 0;

          if (Math.abs(fromIndex) === Infinity) {
            fromIndex = 0;
          }

          if (fromIndex < 0) {
            fromIndex += length;
            if (fromIndex < 0) {
              fromIndex = 0;
            }
          }

          for (;fromIndex < length; fromIndex++) {
            if (this[fromIndex] === searchElement) {
              return fromIndex;
            }
          }

          return -1;
        };
    }

    //availableBits to be used to determine the "alphabet" of characters to generate.
    var availableBits = [0, 1];
    var availLen = availableBits.length;
    //usedNumbers to keep track of how many were used in rows/cols.
    var usedNumbers;

    //How many times to try to generate a grid before failing.
    var numTries = 30;
    var currentTries = 1;
    var success = false;

    //Grid config
    var grid;
    var rows = 6;
    var cols = 6;
      var vThresh = rows/2;
      var hThresh = cols/2;

    //Impossible to generate a solution due to constraint 4. Pigeon-hole principle.
    if (rows / availLen > vThresh || cols / availLen > hTresh) {
        throw new Error("Need to shrink the grid size or add availableBits. There will be more than 3 characters in a row or column.");
    }

    //Try to generate the grid.
    while (!success && currentTries <= numTries) {
        try {
            grid = new anyGrid(rows, cols);
            success = true;
        }
        catch(e) {
            currentTries++;
            if (currentTries > numTries) {
                console.error(e.message);
                console.log("Could not generate anygrid after " + numTries + " attempts.");
            }
        }
    }

    if (success) {
        console.log("Generated anygrid after " + currentTries + " attempts.");
        printGrid(grid);
    }

    function printGrid (grid) {
        for (var i = 0; i < grid.length; i++) {
            var printIt = "";
            for (var j= 0; j < grid[0].length; j++) {
                printIt += grid[i][j] + "   ";
            }
            console.log(printIt);
        }
    }

    function anyGrid (rows, cols) {
        var grid = [];

        //set used numbers
         usedNumbers = {vNumbers: new Array(rows), hNumbers: new Array(cols)};

        for (var i = 0; i < rows; i++) {
            grid.push(new Array(cols));
        }

        var row = 0;
        for (var col = 0; col - row < cols; col++) {
            for (var r = row; r >= 0 && col - r < cols;) {
                setBit(grid, r, col - r--);
            }
            if (row < rows - 1) row++;
        }

        return grid;
    };

    //Complies to the 4 constraints:
    //No 2 numbers consecutively in a row
    //No 2 numbers consecutively in a column
    //Use random when able
    //No more than 3 of a number in a column or row
    function setBit (grid, row, col) {
        var needRandom = true;
        var bit;
        //"Clone" the availableBits to be able to remove characters when calling flip.
        var availClone = availableBits.slice();

        //Constraint 1: First check previous 2 rows
        if ((row - 2) >= 0 && grid[row - 2][col] === grid[row - 1][col]) {
            //Needs to flip
            bit = flip(grid[row - 1][col], availClone);

            needRandom = false;
        }
        //-------------------------------

        //Constraint 2: Check previous 2 cols
        else if ((col - 2) >= 0 && grid[row][col - 2] === grid[row][col - 1]) {
            //Needs to flip
            bit = flip(grid[row][col - 1], availClone);

            needRandom = false;
        }
        //---------------------------------

        //Constraint 3: Attempt a random
        if (needRandom) {
            bit = anyBit(availClone);
        }
        //-------------------------------

        //Constraint 4: Flip if constraint 4 is now violated.
        var vNumber = usedNumbers.vNumbers[row] || {};
        var hNumber = usedNumbers.hNumbers[col] || {};

        while (availClone.length && (vNumber[bit] >= vThresh || hNumber[bit] >= hThresh)) {
            bit = flip(bit, availClone);
        }
        //-------------------------------------

        //Set grid value and update vNumber and hNumber to be used in further iterations.
        grid[row][col] = bit;
        vNumber[bit] = vNumber[bit] + 1 || 1;
        hNumber[bit] = hNumber[bit] + 1 || 1;
        usedNumbers.vNumbers[row] = vNumber;
        usedNumbers.hNumbers[col] = hNumber;
        //----------------------------------
    };

    //Removes a bit from availableBits array and looks to return another random bit.
    function flip (bit, availableBits) {
        var index = availableBits.indexOf(bit);
        //Remove bit from the available bits.
        availableBits.splice(index, 1);

        var length = availableBits.length;

        if (length > 0) {
            //Try another random character
            return anyBit(availableBits);
        }
        //We cannot construct the grid, no more availble characters/bits
        else {
            throw new Error("Could not generate any grid for current configurations. Try again or expand the available characters.");
        }
    };

    //Returns a random bit from the availableBits array.
    function anyBit (availableBits) {
        var length = availableBits.length;
        var randomIndex = getRandomInt(0, length - 1);
        return availableBits[randomIndex];
    };

    //Returns a random integer between min and max.
    function getRandomInt (min, max) {
        return Math.floor(Math.random() * (max - min + 1)) + min;
    };
}());

Edit: Use vThresh and hThresh and set them to rows/2 and cols/2 respectively. Code and fiddle updated.

Create a grid with set constraints

Answers (1)

Related Questions