// Arup Guha
// 4/24/2016
// Solution to 2015 AP CS A Free Response Question 1: Two Dimensional Array Diversity

import java.util.*;

public class Array2D {

	public static void main(String[] args) {

		Random r = new Random();

		// Test our method five times.
		for (int test =0; test<5; test++) {

			// Generate and print a 2d array.
			int[][] nums = getRandomArray(4, 5, r, 10+test*5);
			System.out.println("Here is the array generated:");
			print2D(nums);

			// Test row sums.
			int[] rows = rowSums(nums);
			System.out.println("Here are the row sums:");
			print1D(rows);

			// Test isDiverse method.
			System.out.println("Results of diversity: "+isDiverse(nums)+" "+isDiverseV2(nums)+" "+isDiverseV3(nums));
		}
	}

	public static int arraySum(int[] arr) {

		int sum = 0;

		// Just go through the whole array and add each item into sum.
		for (int i=0; i<arr.length; i++)
			sum += arr[i];
		return sum;
	}

	public static int[] rowSums(int[][] arr2D) {

		int[] res = new int[arr2D.length];

		// Now, for each row in arr2D, call arraySum and store its answer.
		for (int i=0; i<arr2D.length; i++)
			res[i] = arraySum(arr2D[i]);

		// Return the array that stores all the row sums.
		return res;
	}

	public static boolean isDiverse(int[][] arr2D) {

		// First, get the row sums.
		int[] sums = rowSums(arr2D);

		// If we sort the row sums, then values in this array that
		// are equal will become adjacent.
		Arrays.sort(sums);

		// So, here, I can just look for equality between adjacent values.
		for (int i=0; i<sums.length-1; i++)
			if (sums[i] == sums[i+1])
				return false;

		// If we make it here, it's a diverse array.
		return true;
	}

	public static boolean isDiverseV2(int[][] arr2D) {

		// First, get the row sums.
		int[] sums = rowSums(arr2D);

		// Old fashioned way - try each pair of row sums for equality.
		for (int i=0; i<sums.length; i++)
			for (int j=i+1; j<sums.length; j++)
				if (sums[i] == sums[j])
					return false;

		// If we get here, we're good.
		return true;
	}

	public static boolean isDiverseV3(int[][] arr2D) {

		// First, get the row sums.
		int[] sums = rowSums(arr2D);

		// HashSets are very quick at keeping track of whether or not they contain an element.
		HashSet<Integer> vals = new HashSet<Integer>();

		// So go through all row sums, if one value is already in the set, it's not a diverse array.
		// Otherwise, we add the value into the set.
		for (int i=0; i<sums.length; i++) {
			if (vals.contains(sums[i]))
				return false;
			else
				vals.add(sums[i]);
		}

		// If we get here, we've made it.
		return true;
	}

	// So we can see what's in our array.
	public static void print2D(int[][] arr2D) {
		for (int i=0; i<arr2D.length; i++)
			print1D(arr2D[i]);
	}

	// Prints out a 1D array.
	public static void print1D(int[] arr) {
		for (int i=0; i<arr.length; i++)
			System.out.printf("%5d", arr[i]);
		System.out.println();
	}

	// Returns a random array of size numRows x numCols with all elements in the range [1, max].
	public static int[][] getRandomArray(int numRows, int numCols, Random r, int max) {
		int[][] res = new int[numRows][numCols];
		for (int i=0; i<res.length; i++)
			for (int j=0; j<res[i].length; j++)
				res[i][j] = r.nextInt(max) + 1;
		return res;
	}
}