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.
- 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) {
// ...
}
- Can you write the entry_at function to run in constant space and constant time?
- 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);
}
}
Posts
