How to use memoization in counting a large number of matrices

Question

I have been given a program, which requires me to count the number of previous states for a matrix.

The given matrix is a boolean matrix. I will use 1 for true and 0 for false to explain the program.

The next state of a cell in a matrix is 1 if, considering these four cells:

• the cell itself
• the cell right to it
• the cell below it
• the cell below it, and to its right,

there is only one 1 in all these 4 cells, i.e., there are exactly 3 0s and exactly 1 1 in these 4 cells.

If the given matrix (M) is :
1 1 0 0 0 0 0 1 0 0 1 0

Then for the first cell (M[0][0]), the four cells to be considered are M[0][0], M[0][1], M[1][0] and M[1][1]. So, the next state of the first cell is 0, because we have 2 1 in these 4 cells.

For the second cell (M[0][1]), the four cells to be considered are M[0][1], M[0][2], M[1][1], M[1][2]. So the next state for this cell is 1 because there is only 1 1 in these four cells.

Going this way, the next state for this matrix(M) would be the matrix (N):

0 1 1 0 1 0

The next state will, obviously, be 1 row and 1 column less than the previous state. Thus, a given state of the matrix can have many previous states, for example, besides matrix M, the given matrix :

1 0 1 0 1 0 0 0 1 1 0 0

will also have the next state N.

I have to count the number of previous states that a given matrix has.

I have written the following code :

public class Answer2 {

static boolean[][] main_array,answer_array; // answer_array is the 2D array given to me. main_array is the 2D array which I recurse through, and then find its solution to compare with answer_array.
static int c; // counter
static int answer_array_height,answer_array_width; // matrix height and matrix width
public static int answer(boolean[][] boolean_array)
{       
    answer_array = boolean_array;
    main_array = new boolean[answer_array.length+1][answer_array[0].length+1];
    c=0;
    answer_array_height = answer_array.length;
    answer_array_width = answer_array[0].length;
    recurse(1,1);
    main_array[0][0] = true;
    recurse(1,1);
    return c;
}

public static String pad(String s, int l){ //Add 0's to the beginning of the string till its length equals l
    for(int i=s.length(); i<l; i++)
        s='0'+s;
    return s;
}

public static void recurse(int w, int h){
    if(w==answer_array_width+1 && h==answer_array_height+1){        
        c++;
        return;
    }  
    //System.out.println(java.util.Arrays.deepToString(main_array).replace("],","],\n").replace("true","1").replace("false","0"));        
    if(h==answer_array_height+1 || h>=w){//Add column
        int x = 0;           
        for(int i=0; i<h; i++) x+=(int)Math.pow(2,i); //This will give me the integer representation of max value(whose binary representation will be used to put values in the matrix) to handle.

        for(int i=0; i<=x; i++){
            String str = pad(Integer.toBinaryString(i),h);
            for(int j=0; j<h; j++){
                main_array[j][w]= str.charAt(j)=='1'; //set main_array[j][w] true wherever the binary representation of i has 1. This recurses through all the combinations.
            }
            if(check(w+1,h,false)){   
                recurse(w+1, h);     
            }else{        
                for(int j=0; j<h; j++){    
                    main_array[j][w]=false;       
                }              
            }          
        }      
    }else{//Add row            
        int x = 0;           
        for(int i=0; i<w; i++) x+=(int)Math.pow(2,i);
        for(int i=0; i<=x; i++){
            String str = pad(Integer.toBinaryString(i),w); 
            for(int j=0; j<w; j++){
                main_array[h][j]= str.charAt(j)=='1';      
            }              
            if(check(w,h+1,true)){         
                recurse(w, h+1);          
            }else{              
                for(int j=0; j<w; j++){    
                    main_array[h][j]=false;         
                }              
            }          
        }      
    }   
}

// w is the effective width, h is the effective height, height_was_increased is true if height was increased, false if width was increased.
//height_was_increased helps to shorten the time used for comparison as the matrix was correct before the width or height was increased. So it just needs to check the increased portion.
public static boolean check(int w, int h, boolean height_was_increased){
    if(height_was_increased){         
        for(int j=0; j<w-1; j++){    
            //I know this part is complex. It just finds out the answer of the four cells to be considered and matches it with the given matrix.
            if(answer_array[h-2][j] != (main_array[h-2][j]^main_array[h-2+1][j]^main_array[h-2][j+1]^main_array[h-2+1][j+1] && !(main_array[h-2][j] && main_array[h-2+1][j]) && !(main_array[h-2][j+1] && main_array[h-2+1][j+1]))) return false;    
        }       
    }else{     
        for(int i=0; i<h-1; i++){      
            if(answer_array[i][w-2] != (main_array[i][w-2]^main_array[i+1][w-2]^main_array[i][w-2+1]^main_array[i+1][w-2+1] && !(main_array[i] [w-2] && main_array[i+1][w-2]) && !(main_array[i][w-2+1] && main_array[i+1][w-2+1]))) return false;   
        }
    }     
    return true; 
}

}

What it basically does, is that it begins with an empty matrix (of the appropriate size for its next state that gives the matrix asked for) and starts from the top left corner, increasing the effective width and height alternately by 1, and checking if the next state of the matrix till now corresponds to the given state. If not, it skips the rest of the matrix. Then, if a matrix whose next state is the same as the given state is found, it increases the counter by 1.

This code works for small matrices (no. of cells <40), but it takes a lot of time for large matrices. The maximum width of the matrix can be 50 and the maximum height can be 9. So this code doesn't quite work for that purpose.

I know that I have to use memoization here (doing c++ thousands of times is just not right!) But I can't imagine how to implement it. I have previously written programs using dynamic programming, but have no idea where it would be used here. Any help would be appreciated.

Answer 1

There are lot of possible matrices that produce given next state. If next state matrix N is given and initial matrix M is partially filled, for example elements m[x][y+1], m[x+1][y], and m[x+1][y+1] are filled, than possibilities for element m[x][y] are checked with value s = m[x][y+1] + m[x+1][y] + m[x+1][y+1], in a way:

if n[x][y] == 1:
  if s == 0 than m[x][y] = 1
  if s == 1 than m[x][y] = 0
  if s > 1 than m[x][y] can't be filled
if n[x][y] == 0:
  if s == 0 than m[x][y] = 0
  if s == 1 than m[x][y] = 1
  if s > 1 than m[x][y] = 0 or 1

It looks like values 1 in N 'filter' combinations and values 0 in N 'multiply' them.

Since height is bounded by smaller value I suggest approach first to fill last column with possible values, than pass columns backward, fill last column element and than by upper check fill element by element.

Python implementation:

import numpy
from itertools import product

num_results = 0

def fill_xy(m, s, x, y):
    if y < 0:
        fill_x_last(m, s, x-1)
        return
    _sum = s[x+1, y] + s[x+1, y+1] + s[x, y+1]
    if m[x, y] == 1:
        if _sum == 0:
            s[x, y] = 1
        elif _sum == 1:
            s[x, y] = 0
        else:
            return
    else:
        if _sum == 0:
            s[x, y] = 0
        elif _sum == 1:
            s[x, y] = 1
        else:
            s[x, y] = 0
            fill_xy(m, s, x, y-1)
            s[x, y] = 1
    fill_xy(m, s, x, y-1)

def fill_x_last(m, s, x):
    global num_results
    if x < 0:
        print s
        num_results += 1
    else:
        s[x, s.shape[1]-1] = 0
        fill_xy(m, s, x, s.shape[1]-2)
        s[x, s.shape[1]-1] = 1
        fill_xy(m, s, x, s.shape[1]-2)

def solve(m):
    global num_results
    height = m.shape[1]+1
    s = numpy.zeros((m.shape[0]+1, height), dtype=numpy.uint8)
    for p in product((0, 1), repeat=height):
        s[-1, :] = p
        fill_x_last(m, s, s.shape[0]-2)
    print num_results

solve(numpy.array([[0, 1, 1], [0, 1, 0]], dtype=numpy.uint8))