Programmatically step through every permutation of a 4x4 black and white grid

I’ve been getting refamiliarized with processing after a long stint away and have hit the limits of combining tutorials and my foggy memory.

My goal is: 1) create a 4 x 4 grid 2) Programmatically step through all 16k+ binary black/white states of the grid 3) output each state to file.

I’ve got 1 figured out but I’m struggling to programmatically step through the states. I’d really appreciate some help on 2 and may eventually want help on 3. Any takers?

1 Like
int i;

void setup(){
  size(400,400);
  i = 0; // 65500 to test ending.
  noStroke();
}

void draw(){
  int t = 0;
  for(int y=0; y<4; y++){
    for(int x=0; x<4; x++){
      fill(boolean(i&(1<<t++))?0:255);
      rect(x*width/4, y*height/4, width/4, height/4);
    }
  }
  i++;
  // save(); // saveFrame(); // ???
  if(i==65536){
    exit();
  }
}

You can work out saving each frame yourself. Check the reference.

3 Likes

Thanks

How does the << work again?

<< is a bit shift to the left by some number of positions.

Since 1 in binary is …0001, 1<<1 is …0010

This code works by using this single binary 1 to get a single bit of information out of a standard int. That is, the numbers 0 to 65536, in binary, represent all the 2^16 possible combinations. And so each square, each frame, is colored black or white depending on the binary representation of the value of i.

2 Likes

Okay, so i goes from 0
To 65535 and we implicitly convert it to binary by using &

when the value at the t position is 1, boolean() returns true.

So the & checks whether the t Position inside the binary of i is 1 and the
1<<t just moves the 1 left inside the binary of 1.

And t++ just increases t so it runs from 0 to 15 representing each cell in the 4x4 grid

Can you please write a simpler / less dense version of this?

Hello,

The code provided by @TfGuy44 can be modified to display the value of i instead of a rectangle to see the index of that position:

image

There are other ways to do get the index as well.
See this reference:
https://processing.org/tutorials/pixels

You can then extract the binary bit position (index) of your value (2^16 possible values) using string manipulation or bit manipulation.

Examples:

int i;

void setup(){
  size(400, 400);
  i = 0; 
  frameRate(1); // Slow things down.
}

void draw(){
  // Display 16 bits in decimal, binary and hex
  println(i, hex(i, 4), binary(i, 16), boolean(i)); 
  
  //String manipulation
  String s = binary(i, 16);
  for(int j = 0; j<16; j++)
    {
    print(s.charAt(j));  // Use this with an if() to see if it is a char '1' or '0'
    }
    println();
    
  // Bit manipulation 0 
  for(int j = 0; j<16; j++)
    {
    int check = i&(1<<j);  // Masks everything except the bit being checked
    print(check!=0 ? 1:0); // Check if !=0 otherwise it is 0 and print
    }    
  println();
  
  // Bit manipulation 1
  // Variation of above; you could also change the for loop to decrement
  for(int j = 0; j<16; j++)
    {
    int check = i&(1<<(15-j));
    print(check!=0 ? 1:0);
    }    
  println();
  
  // Bit manipulation 2 
  for(int j = 0; j<16; j++)
    {
    int check = (i>>j)&1; // Shifts the bit to the LSB position and masks everything else
    print(check);         // Print it 
    }    
  println();  
  
  i++;
  println(); 
}

Once you have a handle on how to get the binary value (0 or 1) from that index and you can then use that in your code to modify the grid at that same location.

References:
https://en.wikipedia.org/wiki/Bit_manipulation
https://en.wikipedia.org/wiki/Mask_(computing)
https://en.wikipedia.org/wiki/Bitwise_operation
https://processing.org/reference/#math-bitwise-operators
https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html There is a >>> also!

Topic using bit manipulation:
https://discourse.processing.org/t/how-to-do-the-same-as-uint16-t-read-data-8192-in-processing/31891/22

Bit manipulation can be a challenge… at first.
I took the above approach out for a test run and first did this with string manipulation and then progressed to bit manipulation.
This approach worked with my captive audience… strings were easy and bit manipulation took some effort.

This is in C but a good reference:
https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

:)

same basic idea (to make a bit number representing the 16 colors of the grid)
but then with String s2 representing the 16 bits

Full Code


int counterTo65535 = 0;

void setup() {
  size(400, 400);
  counterTo65535 = 0; // 65500 to test ending.
  noStroke();
  frameRate(10);
}

void draw() {

  // make a bit number representing the color 
  String s1 = Integer.toBinaryString(counterTo65535);
  String s2 = s1;

  // fill String with leading Zero's
  while (s2.length() < 16) 
    s2 = "0" + s2; 

  println(s2);

  int counterTo16 = 0; // cell number 

  // loop over grid 
  for (int y=0; y<4; y++) {
    for (int x=0; x<4; x++) {

      if (s2.charAt(counterTo16) == '0')
        fill(0); 
      else 
      fill(255);

      rect(x*width/4, y*height/4, width/4, height/4);

      // next cell 
      counterTo16++;
    }//for
  }//for 

  // next bit pattern 
  counterTo65535++;

  // save(); // saveFrame(); // ???

  // if (counterTo65535==122) {
  if (counterTo65535 == 65536) {
    exit();
  }
}
//

1 Like

Hi,

this

could be replaced by

  String s2 = String.format("%16s",s1).replace(' ', '0');

Cheers
— mnse

1 Like

Also that from …

can be written as

  for(int t=0; t<16; t++){
      fill(boolean(i&(1<<t))?255:0); // also changed color from black on white to white on black
      rect((t%4)*width/4, (t/4)*height/4, width/4, height/4);
  }

or if we want it even more compact and have more flexibility regarding rows and cols…

int dim  = 100;
int rows = 2;
int cols = 8;

void settings() {
  // consider limitations for size min 100x100
  size(dim*cols,dim*rows);
}

void setup(){
  noStroke();
}

void draw(){
  for(int t=0; t<16; t++){
      fill(boolean(frameCount&(1<<t))?255:0);
      // for top down use
      //rect((t%cols)*dim, (t/cols)*dim, dim, dim);
      // for bottom up use
      rect((cols-1-t%cols)*dim, (rows-1-t/cols)*dim, dim, dim);
  }
  // save(); // saveFrame(); // ???
  // just corrected ... and always better ask for >= instead of ==
  if(frameCount>=65535){
    exit();
  }
}

Cheers
— mnse