/*
 * Saddle.java
 * Written by: Dominic Wroblewski
 * First written: 16/11/09
 * Last updated: 17/11/09
 */



/*

 Algorithm for program:

 *	Get grid size from user input
 *	Create new 2D array using inputted grid size
 *	Find least value in each row
 *	Find max value in each column
 *	Find largest value in the row minima
 *	Find smallest value in the column maximums
 *	If largest value in row minima is same as smallest in coloumn maxima then theres a saddle point
 *	Output location of saddle point
 *	Output number of iterations taken using the count variable

 */



import sheffield.*;

public class Saddle {
	public static void main(String[] args) {

		// Creating a new instance of EasyReader
		EasyReader keyboard = new EasyReader();

		System.out.println();

		// Getting the grid size from user input
		final int gridSize = keyboard.readInt("Enter the grid size: ");

		System.out.println();

		// Creating a new grid with the grid size entered by user
		int[][] grid = new int[gridSize][gridSize];

		// Initialising some values
		boolean foundSaddlePoint = false;
		int maximaLocation = 0;
		int minimaLocation = 0;

		// Creating the count, used for counting how many iterations have been made by the program
		int count = 0;

		do {
			// Populating the grid with random numbers generated by the program
			for (int i=0; i<gridSize; i++){
				for (int j=0; j<gridSize; j++){
					// Creating the random number between 0 and 9 and storing into the grid
					int randomNumber = (int)(Math.random() * 9);
					grid[i][j]=randomNumber;
				}
			}

			// Producing an output of the grid to the user
			for (int[] row : grid) {
				for (int col : row)
					System.out.print(col+"  ");
				System.out.println();
			}

			System.out.println();

			// Find the minimum value in each row

			int[] lowestInRows = new int[grid.length];

			for (int i = 0; i<grid.length; i++) {
				lowestInRows[i] = grid[i][0];
				for (int j=0; j<grid[i].length; j++) {
					if ((lowestInRows[i]) > (grid[i][j])) {
						lowestInRows[i] = grid[i][j];
					}
				}
			}


			// Find the maximum value in each column

			int[] maxInColumns = new int[grid.length];

			for (int j=0; j<gridSize; j++) {
				maxInColumns[j] = grid[0][j];
				for (int i=0; i<gridSize; i++) {
					if (maxInColumns[j] < grid[i][j]) {
						maxInColumns[j] = grid[i][j];
					}
				}
			}


			// Find largest value in row minima


			int largestMinima = lowestInRows[0];

			for (int i=0; i<gridSize; i++) {
				if (lowestInRows[i] >= largestMinima) {
					largestMinima = lowestInRows[i];
					minimaLocation = i;
				}
			}


			// Find the smallest value in the column maxima


			int smallestMaxima = maxInColumns[0];

			for (int i=0; i<gridSize; i++) {
				if (maxInColumns[i] <= smallestMaxima) {
					smallestMaxima = maxInColumns[i];
					maximaLocation = i;
				}
			}

			// Adding 1 to the count for the counter of the number of iterations
			count++;

			// If a saddle point is made, then exit the DO WHILE loop
			if (smallestMaxima == largestMinima) {
				foundSaddlePoint = true;
			}

		} while (!foundSaddlePoint);

		// Outputting the location of the saddle point
		System.out.println("There is a saddle point at ("+minimaLocation+","+maximaLocation+")");

		// Outputting the number of iterations the program ran before finding a saddle point
		System.out.println("It took "+count+" iterations to find one");
		System.out.println();

	}
}