/**
 *	This program finds a provided 'waldo' 2d array in a provided 'image' 2d array
 *
 *	@author Zach VanDuyn
 *
 *	CS1121, Fall 2010
 *	Lab Section 4
 */

public class HW3 {

	public static void main (String[] args)
	{
		String input =  "dsleigheijasldkjfweifijl\nabcdefgWwZZZW1lkijejfifj\nhijklmnZAaZaZ2invnn,ie#v\nopqrstuZZLlZZ3ivhbiensli\nvwxyz12ZdZDdZ4qiur74nn9Z\n3456789oZZoOZ5bvifj(838,\nke8784jflkav88hj3jf838jv\n*%jie*^djfkei88738*)jeij\n";
		String wal = "Ww...W1\n.Aa.a.2\n..Ll..3\n.d.Dd.4\no..oO.5\n";

		char[][] img = convert(input);
		char[][] waldo = convert(wal);

		int[] res = findWaldo(img, waldo);
		for(int i=0; i<res.length;i++) System.out.print(res[i]+",");
	}
	/**
	 *	This method accepts a large image represented by a
	 *	two dimensional array of characters, and another
	 *	smaller image (Waldo). It returns pairs of row and
	 *	column indices of the upper left corner of Waldo in
	 *	the large image as successive two value pairs in the
	 *	2-element array. If Waldo does not appear in the image,
	 *	it returns null.
	 *
	 *	@param image A 2d array of characters (what we are searching through)
	 *	@param waldo A 2d array of characters (searching for this array in 'image')
	 *
	 * 	@return null - if 'waldo' is not found in 'image'
	 * 	@return zachsArray - returns array of locations that waldo is found
	 */
	public static int[] findWaldo(char [][] image, char [][] waldo)
	{

		int[] zachsArray;
		zachsArray = new int[((image[0].length*image.length)*2)];
		int store = 0;
		//for each row in image
		for(int a = 0; a < image.length; a++)
		{
			int row = a;

			//for each character in this row
			for(int b = 0; b < image[0].length; b++)
			{
				int column = b;
				boolean found = false;
				//for each row of waldo
				for(int c = 0; c < waldo.length; c++)
				{
					//for each character of this row
					for(int d = 0; d < waldo[0].length; d++)
					{
						if(column < image[row].length && (image[row][column] == waldo[c][d] || waldo[c][d] == '.'))
						{
							column++;
							if(d == waldo[0].length-1)
								found = true;
						}
						else
						{
							d = waldo[0].length;
							c = waldo.length;
						}

					}//end of each character of this row

				}//end of each row of waldo
				if(found)
				{
					zachsArray[store] = a;
					store++;
					zachsArray[store] = b;
					store++;
				}



			}//end of each character in this row

		}// end of each row in image
		if(store == 0)
			return null;
		int[] toReturn = new int[store];
		for(int i=0; i<store; i++){
			toReturn[i]=zachsArray[i];
		}
		return toReturn;
	}//end of findWaldo

	public static char[][] convert(String array)
	{
		int x = array.indexOf('\n');
		int y = array.length()/x;
		char[][] result = new char[x][y];

		for(int i = 0; i < y; i++)
		{
			result[i] = array.substring(0, array.indexOf('\n')).toCharArray();
			System.out.println(array.substring(0, array.indexOf('\n')));
			array = array.substring(array.indexOf('\n') + 1);
		}

		return result;
	}
}//end of HW3