I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Get The Size of X

09.05.2013
| 4404 views |
  • submit to reddit

It's Thursday, so it's time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Create 24

Given a matrix of 1s and 0s, find the largest possible X made from 1's. 
For example in the following matrix 
101
010 
101
The size of X is 3, as the diagonal contains 3 1's.The following would be invalid (i.e. 0) as there is no '1' at the center of an X shape
010
101


Catch up on all our previous puzzlers here

Comments

Mike P(Okidoky) replied on Thu, 2013/09/05 - 8:54pm

Ok, I don't want to go through the pains of proving it, but this reminds of something that an Amiga blitter chip could help with. I'm imagining rendering the array into a monochrome bitmap, where each bit represents that 0 or 1. An int would contain 32 of those, or a long 64 of them. Then some diagonal offset xor "blitting" and see what it does. It's possible to do the same thing what that blitter chip does in software. It involves a lot of shifting and carrying rolled off bits to the next word (int, long, whatever).

To toy around with this, I'd materialize some sort of "Blit Lab" like was seen on the Amiga, and I'd mock with seeing how it could be enhanced further. I'd keep machine code in mind, and make it so that it is possible to implement the algorithm in assembly. I'd call the code from Java through JNI. The end result would be the ultimate fast X finder.

Of course, this is all talk. But my instinct tells me there is something to be gained from converting the array into a bitmap and apply bit shifting. Perhaps Intel MMX instructions could help as well in the machine code.

Way back when, I managed to write an implementation of Conway's game-of-life using the Blitter on the Amiga. The result was a high res 640x200 game of life in real time. Larger even, using scrolling through the Copper-list. Something you could never do that fast using any 68K algorithm. Not at Amiga speeds anyway.

Anyway, for pure performance, a bitmappy thing like this has bits and shifting and xoring written all over it...

Ali Kia replied on Thu, 2013/09/05 - 11:52pm

using bits instead of int and lots of shifting will probably help with performance, but i think most issue in this case will be not seeing the points in matrix where we already seen it. and not doing a work over and over.

think of flowing a line for x and finding its length. and the next point on the line  and ....

i came up with a map that keeps positions for specific length and a Boolean array that saves the points already seen.

at end, we just compare maps to find solution.

public class Xfinder {

 private Map<Integer, List<Point>> toRight = new HashMap<Integer, List<Point>>();
 private Map<Integer, List<Point>> toLeft = new HashMap<Integer, List<Point>>();

 public int solver(int[][] x) {
  generateMaps(x);
  int maxPossible = Math.min(findMaxKey(toRight), findMaxKey(toLeft));
  if (maxPossible == 1) {
   System.out.println("no X is matrix");
   return 0;
  }
  for (int res = maxPossible; res > 1; res -= 2) {
   List<Point> toLeftPoints = toLeft.get(res);
   for (Point point : toRight.get(res)) {
    Point mustBeAt = new Point(point.x, point.y + res - 1);
    if (toLeftPoints.contains(mustBeAt)) {
     System.out.println("X found with center at [x:" + (point.x + (res / 2) + 1) + ",y:" + (point.y + (res / 2) + 1) + "] with length of " + res);
     return res;
    }
   }
  }
  System.out.println("no X is matrix");
  return 0;
 }

 private int findMaxKey(Map<Integer, List<Point>> map) {
  int mx = 1;
  while (map.containsKey(mx + 2)) {
   mx += 2;
  }
  return mx;
 }

 private void generateMaps(int[][] x) {
  int arraySizeX = x.length;
  int arraySizeY = x[0].length;
  boolean[][] rightSeen = new boolean[arraySizeX][arraySizeY];
  boolean[][] leftSeen = new boolean[arraySizeX][arraySizeY];
  for (int i = 0; i < arraySizeX; i++) {
   for (int j = 0; j < arraySizeY; j++) {
    if (x[i][j] == 0) {
     rightSeen[i][j] = true;
     leftSeen[i][j] = true;
    }
   }
  }
  for (int i = 0; i < arraySizeX; i++) {
   for (int j = 0; j < arraySizeY; j++) {
    if (!rightSeen[i][j]) {
     rightSeen[i][j] = true; // can be removed for performace
     for (int distance = 1; (distance < arraySizeX - i) && (distance < arraySizeY - j); distance++) {
      if (x[i + distance][j + distance] != 1) {
       break;
      } else {
       rightSeen[i + distance][j + distance] = true;
       for (int z = 2; z <= distance; z += 2) {
        addToMap(toRight, z + 1, new Point(i + distance - z, j + distance - z));
       }
      }
     }
    }
    if (!leftSeen[i][j]) {
     leftSeen[i][j] = true; // can be removed for performace
     for (int distance = 1; (distance < arraySizeX - i) && (distance < j); distance++) {
      if (x[i + distance][j - distance] != 1) {
       break;
      } else {
       leftSeen[i + distance][j - distance] = true;
       for (int z = 2; z <= distance; z += 2) {
        addToMap(toLeft, z + 1, new Point(i + distance - z, j - distance + z));
       }
      }
     }
    }
   }
  }

 }

 private void addToMap(Map<Integer, List<Point>> map, int length, Point point) {
  if (map.containsKey(length)) {
   map.get(length).add(point);
  } else {
   List<Point> list = new ArrayList<Point>();
   list.add(point);
   map.put(length, list);
  }
 }

}

print?

Nico Tromp replied on Fri, 2013/09/06 - 10:40am

Here is my Java solution. First determine the maximum leg-length (stretching from the center to all four diagonals) and then trying every possible X from the center if there is a 1.

(Just corrected two minor bugs.)

public class TheSizeOfX {

    public static int getMaxLength(int[][] matrix) {
        int bestLegLength = 0;
        int maxLegLength = (Math.min(matrix.length, matrix[0].length) - 1) / 2;
        for (int legLength = 1; legLength <= maxLegLength; legLength++) {
            for (int x = legLength; x < (matrix[0].length - legLength); x++) {
                for (int y = legLength; y < (matrix.length - legLength); y++) {
                    if (matrix[y][x] == 1 && isX(matrix, y, x, legLength)) {
                        if (legLength > bestLegLength) {
                            bestLegLength = legLength;
                        }
                    }
                }
            }
        }
        return bestLegLength == 0 ? 0 : (2*bestLegLength) + 1;
    }

    private static boolean isX(int[][] matrix, int y, int x, int length) {
        for (int i = 1; i <= length; i++) {
            if (matrix[y-i][x-i] == 0 || 
                matrix[y-i][x+i] == 0 || 
                matrix[y+i][x-i] == 0 || 
                matrix[y+i][x+i] == 0) {
                return false;
            }
        }
        return true;
    }

}

And my unit tests.

public class TheSizeOfXTest {

    @Test
    public void shouldFindXOf3() {
        int[][] matrix= {
                {1,0,1}, 
                {0,1,0}, 
                {1,0,1}
            };
        assertEquals(3, TheSizeOfX.getMaxLength(matrix));
    }

    @Test
    public void shouldFindNoX() {
        int[][] matrix= {
                {0,1,0}, 
                {1,0,1}
            };
        assertEquals(0, TheSizeOfX.getMaxLength(matrix));
    }

    @Test
    public void shouldFindXOf5() {
        int[][] matrix= {
                {0,0,0,0,0,0,0,0,0}, 
                {0,0,1,0,0,0,1,0,1}, 
                {0,0,0,1,0,1,0,1,0}, 
                {0,0,0,0,1,0,1,0,1}, 
                {0,0,0,1,0,1,0,0,0}, 
                {0,0,1,0,0,0,1,0,0}, 
                {0,0,0,0,0,0,0,0,0} 
            };
        assertEquals(5, TheSizeOfX.getMaxLength(matrix));
    }

}


Mike P(Okidoky) replied on Fri, 2013/09/06 - 12:28pm in response to: Nico Tromp

Nico, I like your implementation. Just a thought for an optimization. Instead of searching from small to large, how about searching from large to small instead, and then every time you find a cross, change the matrix and poke a 0 at the cross' center. That way, on the next iteration, you don't go measuring the cross for a smaller size when it was already registered as having a larger size.

Another way is that instead of re-searching the entire matrix for crosses of a given length, that the isX becomes more of a measureX method.

Nico Tromp replied on Sat, 2013/09/07 - 3:26am in response to: Mike P(Okidoky)

Hi Mike, sounds like nice optimizations.

Gaurav Joshi replied on Sat, 2013/09/07 - 11:26am

My Unit tests,

package sizeofx;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class TestSizeOfXFinder {
	
	@Test
	public void simpleMatrix(){
		int[] input = {1};
		int size = SizeOfX.find(input,1,1);
		assertEquals(0,size);
	}
	
	@Test
	public void sizeOne(){
		int[] input = {1,1,
			    	   1,1};						 
		int size = SizeOfX.find(input,2,2);
		assertEquals(0,size);
	}
	
	
	@Test
	public void complexMatrixWithX(){
		int[] input ={ 0,1,0,1,0,
				       0,1,1,1,0,
                       0,1,0,1,0,
                       1,1,0,0,1
					};
		int size = SizeOfX.find(input, 5, 4);
		assertEquals(3,size);
	}	
	
	@Test
	public void anotherComplex(){
		int[] input ={ 0,1,0,0,0,0,0,1,0,    
				       0,0,1,0,0,0,1,0,0, 
				       0,0,0,1,0,1,0,0,0,
				       0,0,0,0,1,0,0,0,0,
				       0,0,0,1,0,1,0,0,0,
				       0,0,1,0,0,0,1,0,0,
				       0,1,0,0,0,0,0,1,0,
				       0,0,0,0,0,0,0,0,0
				};
	int size = SizeOfX.find(input, 8, 9);
	assertEquals(7,size);
	}
	
	@Test
	public void shouldFindXOf5() {
	int[] matrix= {
					  0,0,0,0,0,0,0,0,0,
					  0,0,1,0,0,0,1,0,1,
					  0,0,0,1,0,1,0,1,0,
					  0,0,0,0,1,0,1,0,1,
					  0,0,0,1,0,1,0,0,0,
					  0,0,1,0,0,0,1,0,0,
					  0,0,0,0,0,0,0,0,0
	};
	assertEquals(5, SizeOfX.find(matrix,7,9));
	}
	 
}
My Solution


package sizeofx;

public class SizeOfX {

	public static int find(int[] input, int noOfRows, int noOfColumns) {
		if(noOfRows == 1 || noOfRows == 2){
			return 0;
		}else{
			Matrix matrix = new Matrix(input, noOfRows, noOfColumns);
			return findInMatrix(matrix);
		}
	}
	
	private static int findInMatrix(Matrix matrix){
		int result = -1;
		for(int i=0;i<matrix.noOfRows;i++){
			Coordinates starting = new Coordinates(i, 0); 
			Coordinates firstOne = scan(matrix,starting);
			if(firstOne != Coordinates.INVALID_COORDS){
				Coordinates secondOne = scan(matrix,firstOne.nextInRow());
				if(secondOne != Coordinates.INVALID_COORDS && secondOne.row == firstOne.row){
					result = Math.max(potentialX(matrix, firstOne,secondOne),result);
				}
			}			
		}
		return result;		 
	}
	
	
	private static int potentialX(Matrix matrix, Coordinates firstOne, Coordinates secondOne) {
		int noOfElements = (secondOne.column - firstOne.column) + 1;
		if((noOfElements % 2 == 0) && noOfElements != 1){
			return -1;
		}else{
			int xCentrePoint = ((noOfElements - 1)/2+1);			
			Coordinates centreOfX = new Coordinates(xCentrePoint - 1, xCentrePoint);
			int potentialLength = (xCentrePoint - 1)*2+1;
			if(matrix.outOfRange(centreOfX)){
				return 0;
			}else if(matrix.elementAt(centreOfX) != 1){
				return 0;
			}else if(validateX(matrix, firstOne,secondOne,potentialLength)){
				return (xCentrePoint - 1)*2+1;
			}else{
				return 0;
			}
		}
	}

	private static boolean validateX(Matrix matrix, Coordinates firstOne,
			Coordinates secondOne, int potentialLength) {		
		for(int i=0;i<potentialLength-1;i++){
			if(matrix.elementAt(firstOne.row+1, firstOne.column+1) != 1){
				return false;
			}
			
			if(matrix.elementAt(secondOne.row+1,secondOne.column-1) != 1){
				return false;
			}
		}		
		return true;
	}
	

	private static Coordinates scan(Matrix matrix, Coordinates startFrom){
		int dataWithValueOne = matrix.elementAt(startFrom);
		while(startFrom != Coordinates.INVALID_COORDS && dataWithValueOne != 1){
			startFrom = matrix.nextRowWise(startFrom);
			if(startFrom != Coordinates.INVALID_COORDS){
				dataWithValueOne = matrix.elementAt(startFrom);
			}
		}		
		return startFrom;
	}
		
	
	private static class Coordinates{
		private final static Coordinates INVALID_COORDS = new Coordinates(-1, -1);
		private final int row;
		private final int column;
		
		public Coordinates(int row, int column) {
			this.row = row;
			this.column = column;
		}
		
		public Coordinates nextInRow(){
			return new Coordinates(this.row, this.column+1);
		}

		@Override
		public String toString() {
			return "(" + row + ", " + column + ")";
		}		
		
	}
	
	private static class Matrix{
		private final int[] data;
		private final int noOfRows;
		private final int noOfColumns;

		public Matrix(int[] data, int noOfRows, int noOfColumns) {
			this.data = data;
			this.noOfRows = noOfRows;
			this.noOfColumns = noOfColumns;
		}
		
		public int elementAt(Coordinates coord){
			return elementAt(coord.row,coord.column);
		}
		
		public int elementAt(int row, int column){
			return data[(row * noOfColumns) + column];
		}
		
		public Coordinates nextRowWise(Coordinates coordinates){
			assert coordinates.row < noOfRows;
			assert coordinates.column < noOfColumns;
			int row,column = -1;			
			if(coordinates.column == noOfColumns-1){
				column = 0;
				row = coordinates.row +1; 
				if(row == noOfRows){
					return Coordinates.INVALID_COORDS;
				}
			}else{
				row = coordinates.row;
				column = coordinates.column +1;
			}
			return new Coordinates(row, column);
		}
		
		public boolean outOfRange(Coordinates coordinates){
			return coordinates.row >= noOfRows || coordinates.column >= noOfColumns;
		}
	}

}

Ondřej Smola replied on Sat, 2013/09/07 - 12:16pm

Simple Scala solution

object FindX {
  
  val DIRECTIONS = List((1, 1), (1, -1), (-1, 1), (-1, -1))
  
  def countOnesInDirection(start: (Int, Int), direction: (Int, Int), matrix: List[List[Int]]): Int = {
    val (x, y) = (start._1 + direction._1, start._2 + direction._2)
    if (x >= 0 && x < matrix.size && y >= 0 && y < matrix.size && matrix(x)(y) == 1) {
      1 +countOnesInDirection((x, y), direction, matrix)
    } else 0
  }

  def solve(matrix: List[List[Int]]): Option[((Int, Int), Int)] = {
    (for {
      i <- 0 until matrix.size;
      j <- 0 until matrix.size if matrix(i)(j) == 1
    } yield ((i, j), DIRECTIONS.map(d => countOnesInDirection((i, j), d, matrix)).min))
      .foldLeft(None: Option[((Int, Int), Int)]) {
        case (None, el) => if (el._2 > 0) Some(el) else None
        case (Some(((x, y), count)), p) => if (p._2 > count) Some(p) else Some(((x, y), count))
      }
  }

  def main(args: Array[String]) = {
    val matrix = List(
    List(1, 0, 1, 0, 1),
    List(0, 1, 1, 1, 1),
    List(1, 0, 1, 1, 1),
    List(0, 1, 1, 1, 1),
    List(1, 1, 1, 1, 1))
    println(solve(matrix)) // Some(((2,2),2))
  }
}

Andrew Glassman replied on Wed, 2013/09/11 - 1:23pm

I went for a brute force algorithm.  I was going for a straight forward, and easily readable solution.  I tested using the unit tests others provided.  
 My class takes in a 2d array of ints. It then iterates through the matrix, and stores each "root" in an XRep object.  Next, it iterates through all found XRep roots.  It uses a recursive function to expand these XReps to the maximum valid size.  After each XRep is expanded, it is compared the the largest found XRep, and replaces it if it is larger.
import java.util.ArrayList;
import java.util.List;


public class FindX {
	//This class represents an X in the matrix.
	public class XRep
	{
		int x,y,size = 0;
		
		public XRep(int x, int y, int size)
		{
			this.x = x; this.y = y; this.size = size;
		}
		
		@Override
		public String toString(){
			return String.format("Coord: (%s,%s) Size: %s",x,y,getDiagonalSize());
		}

		public int getDiagonalSize() {
			return size*2+1;
		}
	}
	
	int[][] grid;
	
	public FindX(int[][] grid)
	{
		this.grid = grid;
	}
	
	/*
	 * Find all roots, and put them in a list.
	 * A root is any 1 in the matrix.
	 */
	private List<XRep> findRoots()
	{
		List<XRep> roots = new ArrayList<XRep>();
		for(int x = 0; x < grid.length; x ++)
			for(int y = 0; y < grid[0].length; y++)
				if(grid[x][y] == 1)
					roots.add(new XRep(x,y,0));
		
		return roots;
	}
	
	//Find all roots, then iterate through them.
	public XRep findLargestX()
	{
		XRep largestX = null;
		for(XRep root: findRoots())
		{
			exploreXRep(root);
			if(root.size > 0 && (largestX == null || (largestX.size <= root.size)))
			{
				largestX = root;
			}
		}
		return largestX;
	}

	//recursively explore how far X goes.
	private XRep exploreXRep(XRep xRep) {
		int stepSize = xRep.size + 1;
		int leftX = xRep.x - stepSize;
		int rightX = xRep.x + stepSize;
		int upY = xRep.y - stepSize;
		int downY = xRep.y - stepSize;
		try
		{
			if(1 == (	  grid[leftX][upY] 
						& grid[rightX][upY]
						& grid[leftX][downY] 
						& grid[rightX][downY]))
			{
				xRep.size = stepSize;
				return exploreXRep(xRep);
			}
			else
				return xRep;
		} catch (IndexOutOfBoundsException oob)
		{
			return xRep;
		}
	}
	
}

Raju Karappan replied on Thu, 2013/09/12 - 2:44am

My Java solution

public class SizeOfX {

    public static int getSizeOfX(int[][] matrix) {
        int maxX = 0, rows = matrix.length, cols = matrix[0].length;
        for (int i = 1; i < rows - 1; i++) {
            for (int j = 1; j < cols - 1; j++) {
                if (matrix[i][j] == 1) {
                    int maxStep = Math.min(Math.min(i, rows - 1 - i), Math.min(j, cols - 1 - j));
                    for (int step = 1; step <= maxStep; step++) {
                        if (!isOneSquare(matrix, i, j, step)) break;
                        maxX = Math.max(2 * step + 1, maxX);
                    }
                }
            }
        }
        return maxX;
    }

    public static boolean isOneSquare(int[][] matrix, int i, int j, int step) {
        return ((matrix[i - step][j - step] == 1) &&
                (matrix[i - step][j + step] == 1) &&
                (matrix[i + step][j - step] == 1) &&
                (matrix[i + step][j + step] == 1));
    }
}

Luigi Ferrari replied on Thu, 2013/09/12 - 8:53am in response to: Gaurav Joshi

It seems not work. This is my main test: 

public static void main (String args[]){
	    int[] matrix= {
					  0,0,0,0,0,0,0,0,0,
					  0,0,1,0,0,0,1,0,1,
					  0,0,0,1,0,1,0,1,0,
					  0,0,0,0,1,0,1,0,1,
					  0,0,0,1,0,1,0,0,0,
					  0,0,1,0,0,0,1,0,0,
					  0,0,0,0,0,0,0,0,0
	    };
	    System.out.println("Size of x is "+ SizeOfX.find(matrix,7,9));
	   int[] matrix2= {
					  0,0,0,0,0,0,0,0,0,
					  0,0,0,0,0,0,1,0,1,  // a 0 in 3th column
					  0,0,0,1,0,1,0,1,0,
					  0,0,0,0,1,0,1,0,1,
					  0,0,0,1,0,1,0,0,0,
					  0,0,1,0,0,0,1,0,0,
					  0,0,0,0,0,0,0,0,0
	    };
	    System.out.println("Size of x is "+ SizeOfX.find(matrix2,7,9));
	    int[] matrix3= {
					  0,0,0,0,0,0,0,0,0,
					  0,0,1,0,0,0,0,0,1,  // a 0 in 7th column
					  0,0,0,1,0,1,0,1,0,
					  0,0,0,0,1,0,1,0,1,
					  0,0,0,1,0,1,0,0,0,
					  0,0,1,0,0,0,1,0,0,
					  0,0,0,0,0,0,0,0,0
	    };
	    System.out.println("Size of x is "+ SizeOfX.find(matrix3,7,9));
	}
Result: Size of x is 5  // correct Size of x is 0  // wrong!! Size of x is 7  // wrong!!

Nico Tromp replied on Thu, 2013/09/12 - 9:30am in response to: Mike P(Okidoky)

Hi Mike,

actually if you start with the maximum possible size and try them until reaching a length of 1, there is no need to store a '0' at the center. You find the biggest X as the first X, so you can bail out of the loop as soon you find a X. See my adjusted solution below.

My guess is that it should be possible to optimize the method 'isX' by remembering the largest X found. And taking that size into account when trying smaller Xes. (A X with size 5 centered in a matrix of 9x9 for example)


public class TheSizeOfX {

    public static int getMaxLength(int[][] matrix) {
        int maxLegLength = (Math.min(matrix.length, matrix[0].length) - 1) / 2;
        for (int legLength = maxLegLength; legLength >= 1; legLength--) {
            for (int x = legLength; x < (matrix[0].length - legLength); x++) {
                for (int y = legLength; y < (matrix.length - legLength); y++) {
                    if (matrix[y][x] == 1 && isX(matrix, y, x, legLength)) {
                        return (2*legLength) + 1;
                    }
                }
            }
        }
        return 0;
    }

    private static boolean isX(int[][] matrix, int y, int x, int length) {
        for (int i = 1; i <= length; i++) {
            if (matrix[y-i][x-i] == 0 || 
                matrix[y-i][x+i] == 0 || 
                matrix[y+i][x-i] == 0 || 
                matrix[y+i][x+i] == 0) {
                return false;
            }
        }
        return true;
    }

}

Gaurav Joshi replied on Thu, 2013/09/12 - 1:27pm in response to: Luigi Ferrari

Thanks for showing me the mistakes. Also, I feel other people implementation is far better than mine :) Below is the corrected code!

package sizeofx;

public class SizeOfX {

	public static int find(int[] input, int noOfRows, int noOfColumns) {
		if(noOfRows == 1 || noOfRows == 2){
			return 0;
		}else{
			Matrix matrix = new Matrix(input, noOfRows, noOfColumns);
			return findInMatrix(matrix);
		}
	}
	
	private static int findInMatrix(Matrix matrix){
		int result = -1;
		for(int i=0;i<matrix.noOfRows;i++){
			Coordinates starting = new Coordinates(i, 0); 
			Coordinates firstOne = scan(matrix,starting);
			if(firstOne != Coordinates.INVALID_COORDS){
				Coordinates secondOne = scan(matrix,firstOne.nextInRow());
				if(secondOne != Coordinates.INVALID_COORDS && secondOne.row == firstOne.row){
					result = Math.max(potentialX(matrix, firstOne,secondOne),result);
				}
			}			
		}
		return result;		 
	}
	
	
	private static int potentialX(Matrix matrix, Coordinates firstOne, Coordinates secondOne) {
		int noOfElements = (secondOne.column - firstOne.column) + 1;
		if((noOfElements % 2 == 0) && noOfElements != 1){
			return -1;
		}else{
			int row = firstOne.row + (noOfElements - 1)/2 ;
			int column = firstOne.column+ (secondOne.column - firstOne.column)/2;
			Coordinates centreOfX = new Coordinates(row,column);
			int potentialLength = noOfElements;
			if(matrix.outOfRange(centreOfX)){
				return 0;
			}else if(matrix.elementAt(centreOfX) != 1){
				return 0;
			}else if(validateX(matrix, firstOne,secondOne,potentialLength)){
				return potentialLength;
			}else{
				return 0;
			}
		}
	}

	private static boolean validateX(Matrix matrix, Coordinates firstOne,
			Coordinates secondOne, int potentialLength) {		
		if(firstOne.row + (potentialLength-1) >= matrix.noOfRows){
			return false;
		}
		for(int i=1;i<potentialLength;i++){
			if(matrix.elementAt(firstOne.row+i, firstOne.column+i) != 1){
				return false;
			}
			
			if(matrix.elementAt(secondOne.row+i,secondOne.column-i) != 1){
				return false;
			}
		}		
		return true;
	}
	

	private static Coordinates scan(Matrix matrix, Coordinates startFrom){
		int dataWithValueOne = matrix.elementAt(startFrom);
		while(startFrom != Coordinates.INVALID_COORDS && dataWithValueOne != 1){
			startFrom = matrix.nextRowWise(startFrom);
			if(startFrom != Coordinates.INVALID_COORDS){
				dataWithValueOne = matrix.elementAt(startFrom);
			}
		}		
		return startFrom;
	}
		
	
	private static class Coordinates{
		private final static Coordinates INVALID_COORDS = new Coordinates(-1, -1);
		private final int row;
		private final int column;
		
		public Coordinates(int row, int column) {
			this.row = row;
			this.column = column;
		}
		
		public Coordinates nextInRow(){
			return new Coordinates(this.row, this.column+1);
		}

		@Override
		public String toString() {
			return "(" + row + ", " + column + ")";
		}		
		
	}
	
	private static class Matrix{
		private final int[] data;
		private final int noOfRows;
		private final int noOfColumns;

		public Matrix(int[] data, int noOfRows, int noOfColumns) {
			this.data = data;
			this.noOfRows = noOfRows;
			this.noOfColumns = noOfColumns;
		}
		
		public int elementAt(Coordinates coord){
			return elementAt(coord.row,coord.column);
		}
		
		public int elementAt(int row, int column){
			return data[(row * noOfColumns) + column];
		}
		
		public Coordinates nextRowWise(Coordinates coordinates){
			assert coordinates.row < noOfRows;
			assert coordinates.column < noOfColumns;
			int row,column = -1;			
			if(coordinates.column == noOfColumns-1){
				column = 0;
				row = coordinates.row +1; 
				if(row == noOfRows){
					return Coordinates.INVALID_COORDS;
				}
			}else{
				row = coordinates.row;
				column = coordinates.column +1;
			}
			return new Coordinates(row, column);
		}
		
		public boolean outOfRange(Coordinates coordinates){
			return coordinates.row >= noOfRows || coordinates.column >= noOfColumns;
		}
	}

}
Corresponding Unit tests
package sizeofx;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class TestSizeOfXFinder {
	
	@Test
	public void simpleMatrix(){
		int[] input = {1};
		int size = SizeOfX.find(input,1,1);
		assertEquals(0,size);
	}
	
	@Test
	public void sizeOne(){
		int[] input = {1,1,
			    	   1,1};						 
		int size = SizeOfX.find(input,2,2);
		assertEquals(0,size);
	}
	
	
	@Test
	public void complexMatrixWithX(){
		int[] input ={ 0,1,0,1,0,
				       0,1,1,1,0,
                       0,1,0,1,0,
                       1,1,0,0,1
					};
		int size = SizeOfX.find(input, 4, 5);
		assertEquals(3,size);
	}	
	
	@Test
	public void anotherComplex(){
		int[] input ={ 0,1,0,0,0,0,0,1,0,    
				       0,0,1,0,0,0,1,0,0, 
				       0,0,0,1,0,1,0,0,0,
				       0,0,0,0,1,0,0,0,0,
				       0,0,0,1,0,1,0,0,0,
				       0,0,1,0,0,0,1,0,0,
				       0,1,0,0,0,0,0,1,0,
				       0,0,0,0,0,0,0,0,0
				};
	int size = SizeOfX.find(input, 8, 9);
	assertEquals(7,size);
	}
	
	@Test
	public void shouldFindXOf5() {
	int[] matrix= {
					  0,0,0,0,0,0,0,0,0,
					  0,0,1,0,0,0,1,0,1,
					  0,0,0,1,0,1,0,1,0,
					  0,0,0,0,1,0,1,0,1,
					  0,0,0,1,0,1,0,0,0,
					  0,0,1,0,0,0,1,0,0,
					  0,0,0,0,0,0,0,0,0
	};
	assertEquals(5, SizeOfX.find(matrix,7,9));
	}
	 
	
	@Test
	public void shouldFindXOf5WithEdgeCase() {
	int[] matrix= {
					  0,0,0,0,0,0,0,0,0,
					  0,0,1,0,0,0,1,0,1,
					  0,0,0,1,0,1,0,1,0,
					  0,0,0,0,1,0,1,0,1,
					  0,0,0,1,0,1,0,0,0,
					  0,0,1,0,0,0,1,0,0,
					  1,0,0,0,0,0,0,1,0
	};
	assertEquals(5, SizeOfX.find(matrix,7,9));
	}
	
	@Test
	public void luigiCase1(){
		int[] matrix= {
				  0,0,0,0,0,0,0,0,0,
				  0,0,0,0,0,0,1,0,1,  
				  0,0,0,1,0,1,0,1,0,
				  0,0,0,0,1,0,1,0,1,
				  0,0,0,1,0,1,0,0,0,
				  0,0,1,0,0,0,1,0,0,
				  0,0,0,0,0,0,0,0,0
		};
		assertEquals(3, SizeOfX.find(matrix,7,9));
	}
	
	@Test
	public void luigiCase2(){
		int[] matrix= {
				  0,0,0,0,0,0,0,0,0,
				  0,0,1,0,0,0,0,0,1,  
				  0,0,0,1,0,1,0,1,0,
				  0,0,0,0,1,0,1,0,1,
				  0,0,0,1,0,1,0,0,0,
				  0,0,1,0,0,0,1,0,0,
				  0,0,0,0,0,0,0,0,0
		};
		assertEquals(3, SizeOfX.find(matrix,7,9));
	}
	
	@Test
	public void boundry(){
		int[] matrix= {
				  0,0,0,0,0,0,0,0,0,
				  0,0,0,0,0,0,0,0,0,  
				  0,0,0,0,0,0,0,0,0,
				  0,0,0,0,0,0,0,0,0,
				  0,0,0,0,0,0,0,0,0,
				  0,0,0,1,0,1,0,0,0,
				  0,0,0,0,1,0,0,0,0
		};
		assertEquals(0, SizeOfX.find(matrix,7,9));
	}
	
}

Daniel Sobral replied on Thu, 2013/09/12 - 1:42pm

Here's a Scala solution in linear time, though the code could be optimized to reduce the number of passes. It works in two main steps:

First, it compute the length of all directed diagonals. That is, going from up-left to bottom-right and vice versa, and from up-right to bottom-left and vice versa. The job of computing a diagonal is left to computeDiagonal, and allDirections takes care of producing all directions using it. This is done in four passes, but could be reduced to two passes (or even one pass by using a spiral movement).

Next, it compute the minimum at each position for all four matrices. At each intersection, that represents the length of the smallest of the four diagonals arriving at that point. It is halfXSizes which computes this. Since only the greatest length is of interest, instead of producing a new matrix, this could be optimized to return a single value.

Given that, the final result is a trivial matter of getting the maximum of all these values, subtracting one to get  the length of the diagonal, doubling it to account for both sides of the X, and adding one back for the center.

Here's the code:

def get(x: Int, y: Int)(s: Seq[Seq[Int]]): Option[Int] = {
  if ((s.indices contains x) && (s(x).indices contains y)) Some(s(x)(y))
  else None
}

def ul = (x: Int, y: Int) => get(x - 1, y - 1) _
def ur = (x: Int, y: Int) => get(x + 1, y - 1) _
def dl = (x: Int, y: Int) => get(x - 1, y + 1) _
def dr = (x: Int, y: Int) => get(x + 1, y + 1) _

def computeDiagonal(m: Seq[Seq[Int]],
                    at: (Int, Int) => Seq[Seq[Int]] => Option[Int],
                    reverseTraversal: Boolean) = {
  import scala.collection.mutable.ArrayBuffer
  val arr = ArrayBuffer.tabulate(m.size)(n => ArrayBuffer.fill(m(n).size)(0))
  for {
    x <- if (reverseTraversal) m.indices.reverse else m.indices 
    y <- m(x).indices
  } arr(x)(y) = m(x)(y) + at(x, y)(arr).getOrElse(0)
  arr.map(_.toIndexedSeq).toIndexedSeq
}

def allDirections(m: Seq[Seq[Int]]) = {
  val lefts = List(ul, dl) map (computeDiagonal(m, _, reverseTraversal = false))
  val rights = List(ur, dr) map (computeDiagonal(m, _, reverseTraversal = true))
  lefts ::: rights
}

def columnMins(c1: Seq[Int], c2: Seq[Int]) = 
  (c1, c2).zipped map (_ min _)

def halfXSizes(m: Seq[Seq[Int]]) = {
  val directions = allDirections(m)
  for (x <- m.indices)
  yield for (y <- m(x).indices)
        yield (directions map (_(x)(y))).min
}

def maxX(m: Seq[Seq[Int]]) =
  (halfXSizes(m).flatten.max - 1) * 2 + 1

Kamran Shamim replied on Fri, 2013/09/13 - 11:27am

Hi all. This is my contribution in Java. It seems to work:

class XGrid{
	 int[][] grid;
	 int xDim;
	 int yDim;
	 
	 XGrid() {
		 this.grid = new int [][]{
				{1,0,1},
				{0,1,0},
				{1,0,1}
		 };
	 }
	 XGrid(int[][] grid){
		 this.grid = grid;
	 }
	 
	 public int traverse() {
		 int sizeOfX = 0;
		 int res = 0;
		 setDims();
		 
		 for (int yIter = 1; yIter < yDim-1; yIter++){
			 if (res>yDim-yIter) break;
			 for (int xIter = 1; xIter < xDim-1; xIter++){
				 if (res>xDim-xIter) break;
				 if (grid[yIter][xIter] == 1){
					 sizeOfX = scanAround (yIter,xIter,0);
					 res = (sizeOfX > res?sizeOfX:res);
				 }	 
			 }
		 }
		 res = (res==0?0:(res*2)+1);
		 return res;
	 }
	 
	 private int scanAround(int y,int x,int size){
		 boolean cont = true;
		 int dim = size + 1;
		 while (cont && dimWithinBounds(x,y,dim)) {
			 if (grid[y-dim][x-dim] == 1 &&
				 grid[y-dim][x+dim] == 1 &&
				 grid[y+dim][x-dim] == 1 &&
				 grid[y+dim][x+dim] == 1){
				 dim++;
			 } else cont=false;
		 }
		 return dim-1;
	 }
	 
	 private boolean dimWithinBounds(int x,int y,int dim){
		  if (y-dim<0 ||
			 y+dim>=yDim ||
			 x-dim<0 ||
			 x+dim>=xDim) return false;
		 return true;
	 }

	 private void setDims() {
		 yDim = grid.length;
		 xDim = grid[0].length;
	 }
}
public class the_size_of_x {

	public static void main(String[] args) {
		int[][] passedGrid = {
				{1,0,1},
				{0,1,0},
				{1,0,1}
		};
		XGrid xgrid = new XGrid(passedGrid);
		int result = xgrid.traverse();
		if (result == 0) {
			System.out.println("No x found in the grid");
		} else if (result > 0){
			System.out.println("The largest x in the grid is of size:" + result);
		} else {
			System.out.println("Something didn't work");
		}
	}
}

and here are some tests:

import static org.junit.Assert.*;


import org.junit.Test;


public class XGridTest extends XGrid {

	

	

	@Test
	public void testTraverseDefault() {
		
		XGrid grid = new XGrid();
		assertEquals(3,grid.traverse());
	}
	
	
	@Test
	public void testTraverseConstructWithTwo(){
		int [][] matrix = {
				{1,0,1},
				{0,1,0}
				
		};
		XGrid grid = new XGrid (matrix);
		assertEquals(0,grid.traverse());
	}
	
	@Test
	public void testTraverseConstructWithThreeYesX(){
		int [][] matrix = {
				{1,0,1},
				{0,1,0},
				{1,0,1}
		};
		XGrid grid = new XGrid (matrix);
		assertEquals(3,grid.traverse());
	}

	@Test
	public void testTraverseConstructWithThreeNoX(){
		int [][] matrix = {
				{1,0,1},
				{0,0,0},
				{1,0,1}
		};
		XGrid grid = new XGrid (matrix);
		assertEquals(0,grid.traverse());
	}
	
	@Test
	public void testTraverseConstructWithFiveYesX(){
		int [][] matrix = {
				{0,0,0,0,0,0,0,0,0},
				{0,0,1,0,0,0,1,0,1},
				{0,0,0,1,0,1,0,1,0},
				{0,0,0,0,1,0,1,0,1},
				{0,0,0,1,0,1,0,0,0},
				{0,0,1,0,0,0,1,0,0},
				{0,0,0,0,0,0,0,0,0}
		};
		XGrid grid = new XGrid (matrix);
		assertEquals(5,grid.traverse());
	}
	
	@Test
	public void testTraverseConstructOffsetWithFiveYesX(){
		int [][] matrix = {
				{0,0,0,0,0,0,0,0,0},
				{1,0,1,0,1,0,1,0,1},
				{0,1,0,1,0,1,0,1,0},
				{0,0,1,0,1,0,1,0,1},
				{0,1,0,1,0,0,0,0,0},
				{1,0,1,0,1,0,1,0,0},
				{0,0,0,0,0,0,0,0,0}
		};
		XGrid grid = new XGrid (matrix);
		assertEquals(5,grid.traverse());
	}
	
	@Test
	public void testTraverseAsymmetricBadForTheEyesFiveYesX(){
		int [][] matrix = {
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,1,0,0,0,0,0,0,0,0,0,1,0,0,0},
				{0,0,1,0,0,0,1,0,0,0,0,1,1,0,1},
				{0,1,0,0,0,0,0,0,0,0,0,0,0,1,0},
				{0,0,0,0,0,0,0,1,0,0,0,0,1,0,1},
				{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
				{0,0,0,0,1,0,1,0,1,0,0,0,0,0,1},
				{0,0,0,0,0,1,0,0,0,1,0,0,0,1,0},
				{0,0,0,0,1,0,1,0,0,0,1,0,1,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,1,0,1,0,0},
				{0,0,0,0,0,0,0,0,0,1,0,0,0,1,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,1,0,0,0,0,1,0,0,0,1,0,0,0},
				{0,0,0,0,0,0,0,0,1,0,1,0,0,0,0},
				{0,1,0,0,0,0,0,0,0,1,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,1,0,1,0,0,0,0},
				{0,0,0,0,0,0,0,1,0,0,0,1,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
				{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
		};
		XGrid grid = new XGrid (matrix);
		assertEquals(5,grid.traverse());
	}
}

Erik Colban replied on Wed, 2013/09/18 - 2:10am

This problem can be solved using dynamic programming.

Use four int matrices of the same dimensions as the given matrix: ul, ur, dl, and dr. Initialize the four matrices with all zeros.

Initialize int s = 0.

Initialize the first row of ul and ur with the values of the first row of the given matrix. Initialize the last row of dl and dr with the values of the last row of the given matrix.

Thereafter, iterate, row by row, through all remaining the entries (i, j) of matrix. If matrix[i][j] == 1, let

  • ul[i][j] = ul[i - 1][j - 1] + 1,
  • ur[i][j] = ur[i - 1][j + 1] + 1
  • dl[i][j] = dl[i + 1][j - 1] + 1
  • dr[i][j] =dr[i +1][j + 1] +1

Let s = max(s, min( ul[i][j], ur[i][j], dl[i][j], dr[i][j])). 

After iterating through the matrix, return 2 * s - 1.

Note that there is no need to iterate through the s last rows.

Details in the code below:

public class XGrid {

    int[][] matrix;
    private int numRows;
    private int numCols;

    XGrid(int[][] grid) {
	this.matrix = grid;
	numRows = matrix.length;
	numCols = matrix[0].length;
    }

    int solve() {
	int s = 0;

	int[][] ul = new int[numRows][numCols];
	int[][] ur = new int[numRows][numCols];
	int[][] dl = new int[numRows][numCols];
	int[][] dr = new int[numRows][numCols];

	for (int col = 0; col < numCols; col++) {
	    ul[0][col] = matrix[0][col];
	    ur[0][col] = matrix[0][col];
	    dl[numRows - 1][col] = matrix[numRows - 1][col];
	    dr[numRows - 1][col] = matrix[numRows - 1][col];
	}

	for (int i = 1, j = numRows - 2; i < numRows - s; i++, j--) {
	    for (int col = 0; col < numCols; col++) {
		if (matrix[i][col] == 1) {
		    ul[i][col] = col - 1 >= 0 ? ul[i - 1][col - 1] + 1 : 1;
		    ur[i][col] = col + 1 < numCols ? ur[i - 1][col + 1] + 1 : 1;
		}
		if (matrix[j][col] == 1) {
		    dl[j][col] = col - 1 >= 0 ? dl[j + 1][col - 1] + 1 : 1;
		    dr[j][col] = col + 1 < numCols ? dr[j + 1][col + 1] + 1 : 1;
		}
		if (j <= i) {
		    s = max(s,
			    min(ul[i][col], ur[i][col], dl[i][col], dr[i][col]),
			    min(ul[j][col], ur[j][col], dl[j][col], dr[j][col]));

		}
	    }
	}

	return 2 * s - 1;
    }

    private int min(int... args) {
	int result = Integer.MAX_VALUE;
	for (int a : args) {
	    result = Math.min(a, result);
	}
	return result;
    }

    private int max(int... args) {
	int result = Integer.MIN_VALUE;
	for (int a : args) {
	    result = Math.max(a, result);
	}
	return result;
    }
}

Charles Cartwright replied on Tue, 2013/09/24 - 8:19am


Camilo Rivera replied on Mon, 2013/10/07 - 11:04pm

Tried to make a small Java solution of it and succeeded :)

Solution:

package xfinder;

public class XFinder {

	boolean[][] matrix;

	XFinder(boolean[][] matrix) {
		this.matrix = matrix;
	}

	int find() {
		int size = 0;
		for (int i = 0; i < matrix.length; i++)
			for (int j = 0; j < matrix[i].length; j++)
				while (find(i, j, size)) size++;
		return size == 0 ? -1 : size * 2 + 1;
	}

	boolean find(int x, int y, int size) {
		if (x + size >= matrix.length || x - size < 0 || y + size >= matrix[0].length || y - size < 0)
			return false;
		return matrix[x - size][y + size] && matrix[x - size][y - size] && matrix[x + size][y + size] && matrix[x + size][y - size];
	}
	
}

Usage:

package xfinder;

public class XFinderMain {

	static final int[][] MATRIX1 = new int[][] { 
		{ 1, 0, 1 },
		{ 0, 1, 0 }, 
		{ 1, 0, 1 } };
	
	static final int[][] MATRIX2 = new int[][] {
		{0,1,0,0,0,1},
		{1,1,1,0,1,1},
		{0,1,1,1,0,1},
		{1,0,1,0,1,1},
		{0,1,1,0,1,1}
	};
	
	public static void main(String[] args) {
		new XFinder(toBoolean(MATRIX1)).find();
		new XFinder(toBoolean(MATRIX2)).find();
	}
	
	static boolean[][] toBoolean(int[][] intm) {
		boolean[][] bm = new boolean[intm.length][intm[0].length];
		for (int i = 0; i < intm.length; i++) {
			for (int j = 0; j < intm[0].length; j++) {
				bm[i][j] = intm[i][j] == 1;
			}
		}
		return bm;
	}
}


Daniel Sobral replied on Tue, 2013/10/08 - 12:10am in response to: Camilo Rivera

@camilo


That won't really work. For one thing, it has an off-by-one error, since "size" is the first size that is bigger than the X. But even taking that into account, it fails because it assumes that every position satisfy all sizes smaller than the one it is presently testing. For example, try this:


    static final int[][] MATRIX2 = new int[][] {
            {1,0,1,0,0,0},
            {0,1,0,0,0,0},
            {1,0,1,0,1,0},
            {0,0,0,0,0,0},
            {0,0,0,0,0,0},
            {0,0,0,0,0,0},
            {1,0,1,0,1,0}
    };

The size is 3, your solution would give 5 if correct (off by one), but actually gives 7 because it "finds" the outer border of an X, whose interior lines are all blank.


Camilo Rivera replied on Tue, 2013/10/08 - 11:03pm in response to: Daniel Sobral

You are completely right @daniel, here's a new version of the algorithm solving the issue:

public class XFinder {

	boolean[][] matrix;

	XFinder(boolean[][] matrix) {
		this.matrix = matrix;
	}

	int find() {
		int size = 0, maxsize = 0;
		for (int i = 0; i < matrix.length; i++)
			for (int j = 0; j < matrix[i].length; j++) {
				size = -1;
				while (find(i, j, ++size))
					if (size > maxsize) maxsize = size;
			}
		return maxsize == 0 ? -1 : maxsize * 2 + 1;
	}

	boolean find(int x, int y, int size) {
		if (x + size >= matrix.length || x - size < 0 || y + size >= matrix[0].length || y - size < 0)
			return false;
		return matrix[x - size][y + size] && matrix[x - size][y - size] && matrix[x + size][y + size] && matrix[x + size][y - size];
	}
}

Paul Murray replied on Sat, 2013/11/23 - 5:08am

 Prepare a pair of arrays as wide as the matrix is wide (with a height of 1). One array will hold the length of the diagonals up to the left, the other the length up to the right.

Scan down the matrix one row at a time. for each cell that's an X, the length of the diagonal extending up from it will be one plus the previous length of the diagonal to the lef (or the right). This means you have to make two scans so as not to wipe your data as you go.

Once that is done, for each length that's an odd number, theres a potential "center of an x' at half that distance. check the other array to see if theres a diagona crossing that's at least that long.

simple, one pass, and you don't need a whole lot of storage to do it.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.