/*  James P. McEldoon
 *  CS 221
 */

import java.util.Random;

public class ArrayProblems
{

	/**
     * determine if one array of ints is a permutation of another
     * @param listA != null
     * @param listB != null
     * @return true if listB is a permutation of listA, false otherwise
     * 		Counts the occurences of each element in each array.
     *		If the number of occurences is the same for each element in the array then returns true
	*/
	public static boolean isPermutation(int[] listA, int[] listB)
	{
		assert (listA != null && listB != null) : "Violation of precondition: isPermutation";
		int cntA;	//count of element n in array A
		int cntB;   //count of element n in array B
		int number; //element n in array A at position i
		boolean permutation = true;
		if(listA.length!=listB.length){  //If arrays are not the same length return false
				permutation=false;
		}

		if(permutation){
			for(int i=0; i<listA.length; i++){
				cntA=0;
				cntB=0;
				number = listA[i];
				for(int j=0;j<listA.length;j++){
					if(number == listA[j])
							cntA++;
					if(number == listB[j])
							cntB++;
				}
				if(cntA!=cntB){
					permutation = false;
					break;
				}//if
			}
		}//if permutaion

		return permutation;
	}

	/**
	 * determine if there is a majority element in an array of ints
	 * @param list != null
	 * @return  an index of the value of the majority element if it exists.
	 * If a majority element does not exist return -1.
	*/
	public static int findMajority(int[] list)
	{
		assert ( list != null ) : "Violation of precondition: findMajority";
		int cnt;	//count the number of occurences of element n in array
		int j, i;

		for( i=0;i<list.length;i++){
			cnt=0;
			for(j=0;j<list.length;j++){
				if(list[i] == list[j])  //looking for all occurences of element n
					cnt++;
			}
			if(cnt>list.length/2){
				return j-1;
			}
			if(i>list.length/2){
				return -1;
			}
		}//for
		return -1;
	}


	/**
	 * return a shuffled version of an array of ints
	 * @param original != null
	 * @return a shuffled version of original. Original is not altered by this
	 * method. Each possible permutation of original has a roughly uniform chance
	 * of being returned.
	*/
	public static int[] shuffle(int[] original)
	{	assert original != null : "Violation of precondition: shuffle";
		int newPosition;
		long time = System.currentTimeMillis();
		Random generator = new Random(time);
		int [] a = new int[original.length];
		System.arraycopy( original, 0, a, 0, original.length );

		for(int i=0; i<a.length; i++)
		{
			newPosition = generator.nextInt( original.length );
			swap(original, i, newPosition);
		}

	 	return a;
	}
	/**
	  * Swaps position of two array elements
	  * @param the array and the index of the elements to swap
	*/
	private static void swap(int[] original, int oldIndex, int newIndex )
	{
		int temp;
		temp = original[newIndex];
		original[newIndex]=original[oldIndex];
		original[oldIndex]=temp;
	}


	/**
	 * determine if the elements of an array are non decreasing starting at index 0
	 * pre: list != null, list.length > 0
     * post: return true if the elements of an array are non decreasing, false otherwise
     * @param list the array to check
     * @return true if the elements of an array are non decreasing, false otherwise
	*/
	public static boolean nonDecreasing(int[] list)
	{	assert (list != null) && (list.length > 0) : "Violation of precondition: maxSum";

		for(int i=0; i<list.length-1; i++)
		{
			if(list[i+1] < list[i] )
				return false;
		}
		return true;
	}
    /**
	 * prints the elements of the list
	 * @param the array to print
	*/
    public static void printList(int [] list)
	{
		if(debug){
			System.out.print("\t{");
			for(int i=0; i<list.length; i++)
			{
				System.out.print(list[i] + ", ");
			}
			System.out.print("\b\b}\n");
		}
	}

    /**
	 * Checks the rows of a 2D int array or SUDOKU board
	 * @param the 2D int or SUDOKU board
	 * @return  0 if row is valid for solved row
	 *			1 if row contains invalid element
	 *			2 if row repeat element
	 *			3 if row is incomplete but valid
	 *   calls isPermutation()
	 *   calls probleFound() if not valid solved row
	*/
	public static int rowCheck(int [][] board)
	{
        int row=0; 		//count of rows, max 9 rows for Sudoku board
        int result=0;   //result to return
        final int[] validNumbers = {1,2,3,4,5,6,7,8,9}; //valid numbers for Sudoku board
        												//will be used in isPermutation()

		while((result==0 || result==3) && row<9){
			if(!isPermutation(validNumbers, board[row])){
				debugMess("Problem found row Check");
				printList(board[row]);
				result = problemFound(board[row]);
			}
			else{
				debugMess("Valid");
				printList(board[row]);
			}
			row++;
		}
		return result;

	}
	/**
	 * Checks the columns of a 2D int array or SUDOKU board
	 * @param the 2D int or SUDOKU board, result
	 * @return  0 if column is valid for solved row
	 *			1 if column contains invalid element
	 *			2 if column repeat element
	 *			3 if column is incomplete but valid
	 *	 First step is to transfer the elements of a column into a tempArray
	 *	 tempArray is then checked
	 *   calls isPermutation()
	 *   calls probleFound() if not valid solved row
	*/
	private static int colCheck(int [][] board, int result)
	{
		int col=0;	//count of columns, max 9 columns for Sudoku board
        final int[] validNumbers = {1,2,3,4,5,6,7,8,9}; //valid numbers for Sudoku board
        												//will be used in isPermutation()

		while((result==0 || result==3) && col<9){
			int[] tempArray = new int[9];
			for (int i=0; i<9;i++){//transpose array
				tempArray[i]=board[i][col];
			}
			if(!isPermutation(validNumbers, tempArray)){
				debugMess("Problem with col Check");
				printList(tempArray);
				result = problemFound(tempArray);
			}
			else{
				debugMess("Valid");
				printList(tempArray);
			}
			col++;
		}
		return result;
	}

	/**
	 * Checks the columns of a 2D int array or SUDOKU board
	 * @param the 2D int or SUDOKU board, result
	 * @return  0 if column is valid for solved row
	 *			1 if column contains invalid element
	 *			2 if column repeat element
	 *			3 if column is incomplete but valid
	 *	 First step is to transfer the elements each of the nine 3 by 3 sub regions into a tempArray
	 *	 tempArray is then checked
	 *   calls isPermutation()
	 *   calls probleFound() if not valid solved row
	*/
   public static int subBoxCheck(int [][] board)
   {
		int[] tempArray = new int[9];
		int cnt=0, indexRow, indexCol;
		int row, col, result=0;
		final int[] validNumbers = {1,2,3,4,5,6,7,8,9};

	subBoxLoop:    	for(indexRow = 0; indexRow<=6; indexRow+=3){
						for(indexCol = 0; indexCol<=6; indexCol+=3){
							for( row=0; row<3; row++){
								for( col=0; col<3; col++){
									tempArray[cnt] = board[(row+indexRow)][(col+indexCol)];
									cnt++;
									if(cnt==9){
										if(!isPermutation(validNumbers, tempArray)){
											debugMess("Problem in subBox");
											printList(tempArray);
											result = problemFound(tempArray);
											if(result!=3){
												break subBoxLoop;//force break. invalid
											}
										}
										else{
											debugMess("Valid");
											printList(tempArray);
										}
										cnt=0;
									}//if cnt
								}//for col
							}//for row
						}//indexCol
					}//indexRow
		return result;
	}//class
	/**
	 * Called if row, column, or sub box is not valid
	 * @param the row, column or sub box as a 9 element array
	 * @return  1 if column contains invalid element
	 *			2 if column repeat element
	 *			3 if column is incomplete but valid
	 *	 First step is to transfer the elements each of the nine 3 by 3 sub regions into a tempArray
	 *	 tempArray is then checked
	 *   calls isPermutation()
	 *   calls probleFound() if not valid solved row
	*/
 private static int problemFound(int [] problemArray)
 {
	int result=3;
	int [] doubleNumber = new int[10];

	for(int i=0; i<9; i++){//check for invalid number
	 	if(problemArray[i]<0 || problemArray[i]>9){ //0 is valid for incomplet board
			 result=1;
	 	}
 	}

 	if(result==3){
		for(int i=0; i<9; i++){
			if(problemArray[i]>0)
				doubleNumber[problemArray[i]]++;
			if(doubleNumber[problemArray[i]]>1){
				result=2;
			}
		}
		//System.out.println("problemFound result = " + result);

	}
	return result;
 }
   /**
	 * determine the status of a sudoku puzzle board. 0s represent open spaces.
	 *  pre: board != null, board.length = 9, board is a square matrix.
	 *  post: return 0 if the board is solved,
	 * 1 if it is incorrent due to an invalid digit,
	 * 2 if it is incorrect due to a duplicate digit in a row, col, or sub region
	 * 3 if it is a valid in progress board
	 * @param board the sudoku board
	 * @return an int based on the status of the board
	 */
	public static int sudokuStatus(int[][] board){
		assert (board != null) && board.length == 9 && isSquare(board): "Violation of precondition: sudokuStatus";
		int result;

		debugMess("Row Check");
		result = rowCheck(board);

		if(result==0 || result==3){
			debugMess("Col Check");
			result = colCheck(board, result);
		}

		if(result==0 || result ==3){
			debugMess("SubBox Check");
			result = subBoxCheck(board);
		}

		return result;
	}
	/**
	 * Used for debuging
	 * @param Message string
	 */
	private static void debugMess(String m)
	{
		if(debug){
			System.out.println(m);
		}
	}

    private static boolean debug;
	public static void main(String[] args)
	{
		if(args.length==0){
			debug=false;
		}
		else{
			debug=true;
			debugMess("Debug messages enabled with arg[0] != null");
		}
		int result;


		//test 1
		int[] a = {1, 2, 3};
		int[] b = {2, 1, 3};
		if ( isPermutation(a,b) )
			System.out.println("passed test 1");
		else
			System.out.println("failed test 1");
		printList(a);
		printList(b);


		//test 2
		b = new int[]{2, 1, 3, 3};
		int[] c = {2, 1, 2, 3 };
		if ( !isPermutation(a,b) )
			System.out.println("passed test 2");
		else
			System.out.println("failed test 2");
		printList(a);
		printList(b);

		//test 3
		if( findMajority(b) == -1 )
			System.out.println("passed test 3");
		else
			System.out.println("failed test 3");
		printList(b);

		//test 4
		b[0] = 3;
		result = findMajority(b);
		if( result == 0 || result == 2 || result == 3 )
			System.out.println("passed test 4");
		else
			System.out.println("failed test 4 "+ result);
		printList(b);

		//test 5
		int[][] sBoard = { {7, 0, 1, 8, 0, 0, 9, 0, 0},
						   {0, 3, 0, 4, 0, 0, 6, 5, 0},
						   {9, 0, 0, 0, 5, 0, 3, 0, 0},
						   {0, 2, 0, 1, 0, 0, 4, 0, 0},
						   {3, 0, 0, 0, 8, 0, 0, 0, 5},
						   {0, 0, 4, 0, 0, 5, 0, 7, 0},
						   {0, 0, 5, 0, 2, 0, 0, 0, 3},
						   {0, 1, 3, 0, 0, 6, 0, 4, 0},
						   {0, 0, 9, 0, 0, 8, 5, 0, 2}};
		result = sudokuStatus(sBoard);
		if( result == 3)
			System.out.println("passed test 5");
		else
			System.out.println("failed test 5");


		//test 6
		b = new int[] {2, 5, 5, 5, 3, 6, 7};
		a = shuffle(b);
		if( isPermutation(a,b) )
			System.out.println("passed test 6");
		else
			System.out.println("failed test 6");
		printList(a);
		printList(b);

		//test 7
		b = new int[]{0};
		if( nonDecreasing(b))
			System.out.println("passed test 7");
		else
			System.out.println("failed test 7");
		printList(b);


		//test 8
		sBoard[8][7] = 4;
		result = sudokuStatus(sBoard);
		if( result == 2)  //change to 2, there is a duplicate in a column
			System.out.println("passed test 8");
		else{
			System.out.println("failed test 8");
			debug = true;
			System.out.println("result = " + result);
			for(int i=0; i<9; i++){
				printList(sBoard[i]);
			}
			debug = false;
		}

		//test 9
		sBoard[8][7] = 1;
		result = sudokuStatus(sBoard);
		if( result == 3)
			System.out.println("passed test 9");
		else
			System.out.println("failed test 9");

		//test 10
		sBoard = new int[][] { {7, 5, 1, 8, 6, 3, 9, 2, 4},
							   {8, 3, 2, 4, 1, 9, 6, 5, 7},
							   {9, 4, 6, 7, 5, 2, 3, 8, 1},
							   {5, 2, 8, 1, 9, 7, 4, 3, 6},
							   {3, 6, 7, 2, 8, 4, 1, 9, 5},
							   {1, 9, 4, 6, 3, 5, 2, 7, 8},
							   {4, 8, 5, 9, 2, 1, 7, 6, 3},
							   {2, 1, 3, 5, 7, 6, 8, 4, 9},
							   {6, 7, 9, 3, 4, 8, 5, 1, 2}};
		result = sudokuStatus(sBoard);
		if( result == 0)
			System.out.println("passed test 10");
		else
			System.out.println("failed test 10");

		//test 11
		b = new int[] {0, 0, 0};
		if( nonDecreasing(b))
			System.out.println("passed test 11");
		else
			System.out.println("failed test 11 nonDecreasing");
		printList(b);


		//test 12
		b = new int[] {0, 2, 4};
		if( nonDecreasing(b))
			System.out.println("passed test 12");
		else
			System.out.println("failed test 12 nonDecreasing");
		printList(b);

		//test 13
		b = new int[] {0, 0, 1, 1, 2, 2, 3, 4, 1000};
		if( nonDecreasing(b))
			System.out.println("passed test 13");
		else
			System.out.println("failed test 13 nonDecreasing");
		printList(b);

		//test 14
		b = new int[] {0, 0, 1, 0, 1, 1,};
		if( !nonDecreasing(b))
			System.out.println("passed test 14");
		else
			System.out.println("failed test 14 nonDecreasing");
		printList(b);

		//test 15
		b = new int[] {0, 2, 1};
		if( !nonDecreasing(b))
			System.out.println("passed test 15");
		else
			System.out.println("failed test 15 nonDecreasing");
		printList(b);

		//test 16
		sBoard = new int[][] { {7, 5, 1, 8, 6, 3, 9, 2, 4},
							   {8, 10, 2, 4, 1, 9, 6, 5, 7},
							   {9, 4, 6, 7, 5, 2, 3, 8, 1},
							   {5, 2, 8, 1, 9, 7, 4, 3, 6},
							   {3, 6, 7, 2, 8, 4, 1, 9, 5},
							   {1, 9, 4, 6, 3, 5, 2, 7, 8},
							   {4, 8, 5, 9, 2, 1, 7, 6, 3},
							   {2, 1, 3, 5, 7, 6, 8, 4, 9},
							   {6, 7, 9, 3, 4, 8, 5, 1, 2}};
		result = sudokuStatus(sBoard);
		if( result == 1)
			System.out.println("passed test 16");
		else
	        System.out.println("failed test 16");

	    //test 17
		sBoard = new int[][] { {7, 5, 1, 8, 6, 3, 9, 2, 4},
							   {8, 2, 2, 4, 1, 9, 6, 5, 7},
							   {9, 4, 6, 7, 5, 2, 3, 8, 1},
							   {5, 2, 8, 1, 9, 7, 4, 3, 6},
							   {3, 6, 7, 2, 8, 4, 1, 9, 5},
							   {1, 9, 4, 6, 3, 5, 2, 7, 8},
							   {4, 8, 5, 9, 2, 1, 7, 6, 3},
							   {2, 1, 3, 5, 7, 6, 8, 4, 9},
							   {6, 7, 9, 3, 4, 8, 5, 1, 2}};
		result = sudokuStatus(sBoard);
		if( result == 2)
			System.out.println("passed test 17");
		else
			System.out.println("failed test 17");

		//System.out.println("result = " + result);

		//test 18
		sBoard = new int[][] { {7, 5, 1, 8, 6, 3, 9, 2, 4},
							   {8, 4, 2, 4, 1, 9, 6, 5, 7},
							   {9, 4, 6, 7, 5, 2, 3, 8, 1},
							   {5, 2, 8, 1, 9, 7, 4, 3, 6},
							   {3, 6, 7, 2, 8, 4, 1, 9, 5},
							   {1, 9, 4, 6, 3, 5, 2, 7, 8},
							   {4, 8, 5, 9, 2, 1, 7, 6, 3},
							   {2, 1, 3, 5, 7, 6, 8, 4, 9},
							   {6, 7, 9, 3, 4, 8, 5, 1, 2}};
		result = sudokuStatus(sBoard);
		if( result == 2)
			System.out.println("passed test 18");
		else
			System.out.println("failed test 18");
		//System.out.println("result = " + result);

		//test 19
		sBoard = new int[][] { {7, 5, 1, 8, 6, 3, 9, 2, 4},
							   {8, 4, 2, -4, 1, 9, 6, 5, 7},
							   {9, 4, 6, 7, 5, 2, 3, 8, 1},
							   {5, 2, 8, 1, 9, 7, 4, 3, 6},
							   {3, 6, 7, 2, 8, 4, 1, 9, 5},
							   {1, 9, 4, 6, 3, 5, 2, 7, 8},
							   {4, 8, 5, 9, 2, 1, 7, 6, 3},
							   {2, 1, 3, 5, 7, 6, 8, 4, 9},
							   {6, 7, 9, 3, 4, 8, 5, 1, 2}};
		result = sudokuStatus(sBoard);
		if( result == 1)
			System.out.println("passed test 19");
		else
			System.out.println("failed test 19");
		//System.out.println("result = " + result);

		//test 20
		sBoard =  new int[][]{ {7, 0, 1, 8, 0, 0, 9, 0, 0},
						   {0, 3, 0, 4, 4, 0, 6, 5, 0},
						   {9, 0, 0, 0, 5, 0, 3, 0, 0},
						   {0, 2, 0, 1, 0, 0, 4, 0, 0},
						   {3, 0, 0, 0, 8, 0, 0, 0, 5},
						   {0, 0, 4, 0, 0, 5, 0, 7, 0},
						   {0, 0, 5, 0, 2, 0, 0, 0, 3},
						   {0, 1, 3, 0, 0, 6, 0, 4, 0},
						   {0, 0, 9, 0, 0, 8, 5, 0, 2}};
		result = sudokuStatus(sBoard);
		if( result == 2)
			System.out.println("passed test 21");
		else
			System.out.println("failed test 21");

		//test 21
		sBoard =  new int[][]{ {7, 0, 1, 8, 0, 0, 9, 0, 0},
						   {0, 3, 0, 4, 0, 0, 6, 5, 0},
						   {9, 0, 0, 4, 5, 0, 3, 0, 0},
						   {0, 2, 0, 1, 0, 0, 4, 0, 0},
						   {3, 0, 0, 0, 8, 0, 0, 0, 5},
						   {0, 0, 4, 0, 0, 5, 0, 7, 0},
						   {0, 0, 5, 0, 2, 0, 0, 0, 3},
						   {0, 1, 3, 0, 0, 6, 0, 4, 0},
						   {0, 0, 9, 0, 0, 8, 5, 0, 2}};
		result = sudokuStatus(sBoard);
		if( result == 2)
			System.out.println("passed test 21");
		else
			System.out.println("failed test 21");


}// end main


	/* pre: mat != null
	   post: return true if mat is a square matrix, false otherwise
	*/
	private static boolean isSquare(int[][] mat)
	{	assert mat != null : "Violation of precondition: isSquare";

		final int numRows = mat.length;
		int row = 0;
		boolean square = true;
		while( square && row < numRows )
		{	square = ( mat[row] != null) && (mat[row].length == numRows);
			row++;
		}
		return square;
	}


	/* pre: mat != null, valid != null
	   post: return true if all elements in mat are one of the characters in valid
	*/
	private static boolean onlyContains(char[][] mat, char[] valid)
	{	assert mat != null && valid != null : "Violation of precondition: onlyContains";

		int row = 0;
		int col;
		boolean correct = true;
		while( correct && row < mat.length)
		{	col = 0;
			while(correct && col < mat[row].length)
			{	correct = contains(valid, mat[row][col]);
				col++;
			}
			row++;
		}
		return correct;
	}


	/* pre: list != null
	   post: return true if c is in list
	*/
	private static boolean contains(char[] list, char c)
	{	assert ( list != null ) : "Violation of precondition: contains";

		boolean found = false;
		int index = 0;
		while( !found && index < list.length)
		{	found = list[index] == c;
			index++;
		}
		return found;
	}


	/* pre: mat != null, mat.length > 0
	 * post: return true if mat is rectangular
	 */
	private static boolean isRectangular(int[][] mat)
	{	assert (mat != null) && (mat.length > 0) : "Violation of precondition: isRectangular";

		boolean correct = true;
		final int numCols = mat[0].length;
		int row = 0;
		while( correct && row < mat.length)
		{	correct = (mat[row] != null) && (mat[row].length == numCols);
			row++;
		}
		return correct;
	}

}