write 0's and 1's on each line where the last 2 weren't the same

Question

There's an error in the logic of what I've build at the moment. What should be happening is that my code should display a grid of 0's and 1's. Like so:

001001
101101
010110
110010
001101

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

edit: to further clarify ok so I have a row like this: 0 1 0 1 1 0 - As you can see there will always be 3 x 1, and 3 x 0 - the order of numbers is picked randomly (so it might go 0 1, or 1 1, or 0 0 to start etc) - there can never be more than 2 numbers of the same type consecutively, for instance if it's 001100, you can see that there were 2 0's, then it had to display a 1, but then there were 2 1's, so it had to display an 0. So 011100 couldn't happen (3 1's consecutively) or 000101 (3 0's consecutively)

• Based upon this, but for now not essential, the same no 2 numbers consecutively must apply in columns (so in my successful example it goes 001001 across, there are at most 2 0's consecutively. But looking down you get 010101 (that is to say, once again, no more than 2 consecutively)

So my code is as follows:

    import java.util.Random;

public class Main {

    public static void main(String[] args) {
        int l = 6;
        int w = 6;
        Random rd = new Random();

        // Create a grid that is 6 x 6
        int[][] grid = new int[l][w];
        // for each row
        for (int i = 0; i < l; i++) {
            int zCount = 0;
            int oCount = 0;
            int current;
            int lastA = 2;
            int lastB = 2;
            // for each item in the row
            for (int j = 0; j < w; j++) {
                // set the current item to either 0 or 1
                current = rd.nextInt(2);
                // make sure there aren't already (e.g. 3 items out of 6)
                // items in the row
                if (j % 2 == 1) {
                    // hold every second element
                    lastA = current;
                } else {
                    // hold every first element
                    lastB = current;
                }
                if (current == 1) {
                    if (oCount != 3) {
                        if (lastA != lastB) {
                            // if the two previous items aren't the same
                            grid[i][j] = current;
                            // add to the counter
                            oCount++;
                        }
                    }
                }
                if (current == 0) {
                    if (zCount != 3) {
                        if (lastA != lastB) {
                            // if the two previous items aren't the same
                            grid[i][j] = current;
                            // add to the counter
                            zCount++;
                        }
                    }
                }
                System.out.print(grid[i][j]);
            }
            System.out.println(" ");
        }
    }
}

The problem is it generates as follows:

010010 
100001 
100010 
000010 
100001 
001000 

So obviously it doesn't conform to the first, third or fourth points. I have absolutely no idea why! Except for the columns (third point) which I haven't initialised.

Can anybody work out what the logical failure is in my code?

Thanks for your help!

Answer 1

Here is my procedural solution which tries to keep the amount of required code as small as possible. It is capable of computing 2D-Arrays with arbitrary rows and columns like [6, 6] or [4, 7] or [3, 8] for example. The complexity of the algorithm is O(n) with n = rows * columns.

The program computes an arbitrary 2D-Array (grid) populated with either a 0 or 1. The grid guarantees the following characteristics, formulated mathematically:

∀ r,c ∈ Integer | 0 ≤ r < grid.rows, 0 ≤ c < grid.columns :

r - 2 ≥ 0 ⇒ cardinality( distinct( grid[r][c], grid[r-1][c], grid[r-2][c] )) = 2

r + 2 < grid.rows ⇒ cardinality( distinct( grid[r][c], grid[r+1][c], grid[r+2][c] )) = 2

c - 2 ≥ 0 ⇒ cardinality( distinct( grid[r][c], grid[r][c-1], grid[r][c-2] )) = 2

c + 2 < grid.columns ⇒ cardinality( distinct( grid[r][c], grid[r][c+1], grid[r][c+2] )) = 2

or in other words:

the grid does neither contain a row nor a column which has three or more consecutive 0's or 1's.

Below the Java code I will explain how the algorithm works and why it is designed as it is:

public static void main(String[] args) {
    int[][] grid = anyGrid(8, 13);
}

private static int[][] anyGrid(int rows, int cols) {
    int[][] grid = new int[rows][cols];
    int row = 0;
    for (int col = 0; col - row < cols; col++) {
        for (int r = row; r >= 0 && col - r < cols;) {
            setBit(grid, r, col - r--);
        }
        if (row < rows - 1) row++;
    }
    return grid;
}

private static void setBit(int[][] grid, int row, int col) {
    int vInd = calcVerticalIndicator(grid, row, col);
    int 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();
    }
}

private static boolean isPartiallyRestricted(int vInd, int hInd) {
    return vInd == hInd;
}

private static boolean isFullyRestricted(int vInd, int hInd) {
    return vInd + hInd == 1;
}

private static int calcVerticalIndicator(int[][] grid, int row, int col) {
    return calcIndicator(grid, row - 1, col, row - 2, col, 2);
}

private static int calcHorizontalIndicator(int[][] grid, int row, int col) {
    return calcIndicator(grid, row, col - 1, row, col - 2, 4);
}

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

private static int anyBit() {
    return (int) (Math.random() * 2);
}

private static int flip(int bit) {
    return bit == 0 ? 1 : 0;
}

The challenge we face is not to ensure that there are no three consecutive 0's or 1's in a row only or in a column only. The challenge is to ensure that no three consecutive 0's or 1's are neither in a row nor in a column by providing an efficient algorithm.

The tricky situation we may run into looks like this:

Let's consider the situation where all the cells at the top and to the left of the cell outlined in blue are already populated and do not violate the rules define above.

• picture a) we want to populate the cell having a blue outline. The two cells at it's top are populated with two 0's while the cells at it's left are populated with two 1's. Which value should we choose? Due to symmetry it doesn't matter if we choose a 0 or a 1. Hence, let's go with a 0.

• picture b) populating the cell outlined in blue with a 0 violates one rule defined above: the grid does not contain a column with three or more consecutive 0's or 1's. Hence we have to change the value of one of the two cells above of the blue cell.

• picture c) say we change the value of the cell which is immediately above the blue cell, from 0 to 1. This could result in the violation of some rules, caused by the already populated cells to the left of the modified cell.

• picture d) but a violation would mean that both cells to the left must have a value of 1.

• picture e) this would imply that both cells to their top must have a value of 0 which is a contradiction to a situation we assumed. Therefore, changing the cell immediately at the top of the cell outlined in blue will not cause any violation of the rules.

To address the precondition, that no cells to the right of the modified cell are already populated, the algorithm populates the grid in a diagonal way. The population of cells occur in the order as shown below:

The final thing I like to explain is how the algorithm decides which values are available to choose from for each cell. For each cell it inspects the two top-most and two left-most cells and calculates an indication value. This value is used to determine the possible values for a cell by using arithmetic calculation as follows:

• if the two cells inspected are both populated with 0's return an indicator value of 0.

• if the two cells inspected are both populated with 1's return an indicator value of 1.

I have selected those two values because they communicate the fact, that this values are not permitted, in an intuitive way.

Then I selected a function to communicate if both, the column cells and the row cells, restrict the cell to populate by the same value. This is the case if both indicator values are equal. Keep this characteristic in mind, because we have to find values for the situation when no restriction applies from the column cells or the row cells.

If both indicators restrict the value to populate the cell with by a different value, the sum of them is 1. This is the second characteristic we have to keep in mind when searching for proper indicator values when no restriction applies.

The last thing the algorithm has to achieve is to find proper values when no restriction applies without compromising the unique indicators defined above.

• Preserving the indication when the cell is restricted by the same value can be achieved by selecting values for the row and column indicators which are different from 0 and 1 and different from each other.

• Preserving the indication when the cell is restricted by both values can be achieved by selecting values being greater than 1 and having a delta to each other of at least 2.

The algorithm does indicate no restriction for a row by the values 2 and -2 and for a column by the values 4 and -4. This values do not conflict with the operations used to identify the other two cases.

I hope this documentation helps to understand the whole program and how it does solve the problem statement. I am glad to hear your comments.

Answer 2

Many of the solutions given are extremely long and complicated. Here's a solution with very minimal code (Ideone Example here):

int row, col, n = 8;
int[][] grid = new int[n][n], cCount = new int[n][2], rCount = new int[n][2];
Deque<Entry<Integer,Integer>> freeInd = new ArrayDeque<Entry<Integer,Integer>>();
Random rand=new Random();
for(int i = 0; i < grid.length; i++){
    for(int j = 0; j < grid[0].length; j++){
        // Calcualte constraints: row, col = {-1, 0, 1},  -1 => no constraint.
        row = j > 1 && grid[i][j-2] == grid[i][j-1] ? (grid[i][j-1] == 0 ? 1:0):  
             (rCount[i][0] >= n/2 ? 1:                           // too many 0's
             (rCount[i][1] >= n/2 ? 0:-1));                      // too many 1's
        col = i > 1 && grid[i-2][j] == grid[i-1][j] ? (grid[i-1][j] == 0 ? 1:0):
             (cCount[j][0] >= n/2 ? 1:                           // too many 0's
             (cCount[j][1] >= n/2 ? 0:-1));                      // too many 1's
        grid[i][j] = row == -1 && col == -1 ? rand.nextInt(2):(row > -1 ? row:col);

        // Handle Constraints
        if( row == -1 && col == -1){                              // no constraint
            freeInd.push(new SimpleEntry<Integer,Integer>(i, j)); // add to free indices
        } else if( (row > -1 && col > -1 && row != col)           // constraint conflict
                || (row > -1 && rCount[i][row] >= n/2)            // count conflict
                || (col > -1 && cCount[j][col] >= n/2)){          // count conflict
            Entry<Integer, Integer> last = freeInd.pop();         // grab last free index
            while(i > last.getKey() || j > last.getValue()){
                j = (j-1+ n)%n;                                   // step indices back
                i = (j == n-1) ? i-1:i;   
                rCount[i][grid[i][j]]--;                          // reduce counters
                cCount[j][grid[i][j]]--;
            }
            grid[i][j] = grid[i][j] == 0 ? 1:0;                   // flip value
        }       
        rCount[i][grid[i][j]]++;                                  // increment counters
        cCount[j][grid[i][j]]++;
    }
}

The idea here is that you walk along each row of the matrix adding 0's and 1's abiding by the following rules:

1. If the current index is unconstrained (i.e. it can be 0 or 1) we choose a value randomly.
2. If the current index is constrained we force it to have the constrained value.
3. If there are multiple constraints that do not agree, we revert back to the last unconstrained index (freeInd) by first incrementally stepping backwards along the rows of the matrix, decrementing the count for the given value (0 or 1). E.g. this is done for rows with rCount[i][grid[i][j]]--. When the unconstrained vertex is finally reached, flip it's value.
4. Finally, increment the count of the value (0 or 1) for the current row and column. E.g. this is done for rows with rCount[i][grid[i][j]]++