Sunday, June 13, 2010

Matrix Challenge

Here is an interesting challenge posted on the website of a company called Rapleaf:

We wish to find, for an arbitrary N, an N x N matrix with the following property: each entry in the matrix is the smallest non-negative number which does not appear either above the entry or to its left.
  1. Write a function that computes the entry in a particular row and column. That is, complete the following:






    int entry_at(int row, int column) {
        // ...
    }
  2. Can you write the entry_at function to run in constant space and constant time?
  3. Can you prove that your algorithm is correct?

 For instance, here is a 6x6

I posted a solution before, which was wrong, because I only looked at a 6x6, and my solution failed for larger matrices. Thanks to whomever posted the comment pointing out that my solution was broken. So I rewrote it in Java, after looking at some larger matrices.  Here is a printout of the 32x32 matrix produced by the program.

 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
 1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30 
 2  3  0  1  6  7  4  5 10 11  8  9 14 15 12 13 18 19 16 17 22 23 20 21 26 27 24 25 30 31 28 29 
 3  2  1  0  7  6  5  4 11 10  9  8 15 14 13 12 19 18 17 16 23 22 21 20 27 26 25 24 31 30 29 28 
 4  5  6  7  0  1  2  3 12 13 14 15  8  9 10 11 20 21 22 23 16 17 18 19 28 29 30 31 24 25 26 27 
 5  4  7  6  1  0  3  2 13 12 15 14  9  8 11 10 21 20 23 22 17 16 19 18 29 28 31 30 25 24 27 26 
 6  7  4  5  2  3  0  1 14 15 12 13 10 11  8  9 22 23 20 21 18 19 16 17 30 31 28 29 26 27 24 25 
 7  6  5  4  3  2  1  0 15 14 13 12 11 10  9  8 23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24 
 8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7 24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23 
 9  8 11 10 13 12 15 14  1  0  3  2  5  4  7  6 25 24 27 26 29 28 31 30 17 16 19 18 21 20 23 22 
10 11  8  9 14 15 12 13  2  3  0  1  6  7  4  5 26 27 24 25 30 31 28 29 18 19 16 17 22 23 20 21 
11 10  9  8 15 14 13 12  3  2  1  0  7  6  5  4 27 26 25 24 31 30 29 28 19 18 17 16 23 22 21 20 
12 13 14 15  8  9 10 11  4  5  6  7  0  1  2  3 28 29 30 31 24 25 26 27 20 21 22 23 16 17 18 19 
13 12 15 14  9  8 11 10  5  4  7  6  1  0  3  2 29 28 31 30 25 24 27 26 21 20 23 22 17 16 19 18 
14 15 12 13 10 11  8  9  6  7  4  5  2  3  0  1 30 31 28 29 26 27 24 25 22 23 20 21 18 19 16 17 
15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 
17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30  1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14 
18 19 16 17 22 23 20 21 26 27 24 25 30 31 28 29  2  3  0  1  6  7  4  5 10 11  8  9 14 15 12 13 
19 18 17 16 23 22 21 20 27 26 25 24 31 30 29 28  3  2  1  0  7  6  5  4 11 10  9  8 15 14 13 12 
20 21 22 23 16 17 18 19 28 29 30 31 24 25 26 27  4  5  6  7  0  1  2  3 12 13 14 15  8  9 10 11 
21 20 23 22 17 16 19 18 29 28 31 30 25 24 27 26  5  4  7  6  1  0  3  2 13 12 15 14  9  8 11 10 
22 23 20 21 18 19 16 17 30 31 28 29 26 27 24 25  6  7  4  5  2  3  0  1 14 15 12 13 10 11  8  9 
23 22 21 20 19 18 17 16 31 30 29 28 27 26 25 24  7  6  5  4  3  2  1  0 15 14 13 12 11 10  9  8 
24 25 26 27 28 29 30 31 16 17 18 19 20 21 22 23  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7 
25 24 27 26 29 28 31 30 17 16 19 18 21 20 23 22  9  8 11 10 13 12 15 14  1  0  3  2  5  4  7  6 
26 27 24 25 30 31 28 29 18 19 16 17 22 23 20 21 10 11  8  9 14 15 12 13  2  3  0  1  6  7  4  5 
27 26 25 24 31 30 29 28 19 18 17 16 23 22 21 20 11 10  9  8 15 14 13 12  3  2  1  0  7  6  5  4 
28 29 30 31 24 25 26 27 20 21 22 23 16 17 18 19 12 13 14 15  8  9 10 11  4  5  6  7  0  1  2  3 
29 28 31 30 25 24 27 26 21 20 23 22 17 16 19 18 13 12 15 14  9  8 11 10  5  4  7  6  1  0  3  2 
30 31 28 29 26 27 24 25 22 23 20 21 18 19 16 17 14 15 12 13 10 11  8  9  6  7  4  5  2  3  0  1 
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0 

The valAboveDiag method takes advantage of the fact the matrix is symetric about the main diagonal. For values below the diagonal, the row and column numbers are simply transposed. To compute an arbitrary value in an NxN matrix, the method executes O(log(N)). However, if I always intended to print the entire matrix, I could have rewritten this to take advantage of values already stored in the matrix. In that case, adding a new value to the matrix would occur in constant time. The central idea behind the code below, is that the matrix is built up of matrices whose sizes are powers of 2 (e.g. 2x2,4x4,8x8, etc), organized in a pattern [[A,B][B,A]]. For a given cell, above the main diagonal, the cell is either in quandrant [0,0], [0,1], or [1,1]. Because of the pattern [[A,B][B,A]], this means that quadrant [0,0] is A, quadrant [0,1] is B, and [1,1] is A. Observing that B=A+mid, where "mid" is the "middle value" midway between 0 and the maximum value of the power-of-two block, we can only need to be able to produce A to find any other value in the power-of-two block. This process simply recurses until A is found to be the identity matrix (i.e. [[0,1],[1,0]]).

package random;

import java.util.Arrays;

/**
 *
 * @author geoffreyhendrey
 */
public class MadMatrix {
    int[][] a;

    public MadMatrix(int size){
        a = new int[size][size];
        for(int r=0;r<size;r++){
            for(int c=0;c<size;c++){
                a[r][c] = valAboveDiag(r,c);
            }
        }
    }

    @Override
    public String toString(){
        StringBuilder buf = new StringBuilder();
        for(int[] row:a){
            for(int column:row){
                buf.append(String.format("%2d ", column));
            }
            buf.append("\n");
        }
        return buf.toString();
    }


    private int valAboveDiag(int r, int c) {
        if(r>c){
            int tmp = c;
            c=r;
            r=tmp;
        }
        int order = getOrder(c);
        if(0 == order){
            if(r==c) return 0;
            return 1;
        }
        int mid = 1<<order;
        if(c >=mid && r<mid){
            return valAboveDiag(r, c-mid) + mid;
        }else{
            return valAboveDiag(r-mid, c-mid);
        }
    }

    private static int getOrder(int c){
        int order = 0;
        while(c > 1){
            c >>>=1;
            order++;
        }
        return order;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        MadMatrix mm = new MadMatrix(32);
        System.out.println(mm);
    }

}

5 comments:

  1. Anonymous10:37 AM

    This works for the 6 x 6 matrix provided; however, it fails on an arbitrary N x N matrix.

    For example, consider the value at (6,4). According to your solution, this value should be 10, when in reality it is 2.

    I've provided an 8 x 8 matrix below for reference.

    0 1 2 3 4 5 6 7
    1 0 3 2 5 4 7 6
    2 3 0 1 6 7 4 5
    3 2 1 0 7 6 5 4
    4 5 6 7 0 1 2 3
    5 4 7 6 1 0 3 2
    6 7 4 5 2 3 0 1
    7 6 5 4 3 2 1 0

    ReplyDelete
  2. Anonymous7:11 PM

    Not O(N) though. I see the O(N) solution but working on proving it.

    ReplyDelete
  3. Anonymous7:14 PM

    Doh, I mean "still not O(1) or constant time."

    ReplyDelete
  4. I've come up with a constant space and constant time solution but am having problems with a rigorous proof.

    ReplyDelete
  5. O(1) space and time with proof at http://tech-queries.blogspot.com/2011/08/matrix-madness-smallest-non-negative.html

    ReplyDelete