import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.io.File;
import java.io.FileNotFoundException;

/**
 * @author Eric Durant <durant@msoe.edu>
 * Created on November 17, 2011
 * Last updated November 17, 2011
 * Java sample solutions for Op 2011
  */
public class Op2011 {
	/**
	 * Console menu allowing selection of any of the 9 demo solutions
	 * @param args (unused)
	 */
	public static void main(String[] args)
	{
		boolean done = false;
        while(!done)
        {
        	System.out.println("Op 2011 Demo Program");
        	System.out.println("1. Law of cosines");
        	System.out.println("2. Crossword helper");
        	System.out.println("3. Length of rope");
        	System.out.println("4. Euclidean algorithm");
        	System.out.println("5. Newton's method");
        	System.out.println("6. Sudoku predicate");
        	System.out.println("7. Sudoku potential moves");
        	System.out.println("8. Image processing");
        	System.out.println("9. Degrees of separation");
        	System.out.println("0. Exit");

            int choice = -1; // invalid
            while (choice > 9 || choice < 0)
            {
            	if (sc.hasNextInt()) {
            		choice = sc.nextInt();
            		sc.nextLine(); // dump CR from stream
            	} else
            		sc.next(); // discard non-int token
            }

            switch(choice)
            {
                case 1: prob1(); break;
                case 2: prob2(); break;
                case 3: prob3(); break;
                case 4: prob4(); break;
                case 5: prob5(); break;
                case 6: prob6(); break;
                case 7: prob7(); break;
				case 8: prob8(); break;
                case 9: prob9(); break;
                case 0: done = true; break;
            }
        }
	}
	
	/**
	 * Problem 1. Law of cosines (10 Points)
	 */
	public static void prob1() {
		/* Write a program that asks the user for the length of 2 sides of a triangle and the angle between them
		 * in degrees (not radians).  Your program will calculate and output the length of the other side using
		 * the law of cosines, c^2 = a^2 + b^2 – 2 ab cos gamma, where a and b are the 2 input sides,
		 * gamma is the angle between them, and c is the third side.
		 */
		final double a = inputDouble("Side a? ");
		final double b = inputDouble("Side b? ");
		final double gammaDegrees = inputDouble("Angle gamma (degrees)? ");
		final boolean valid = a > 0 && b > 0;
		if (valid) {
			final double c = Math.sqrt(a*a+b*b-2*a*b*Math.cos(gammaDegrees/180*Math.PI));
			System.out.println("The other side is " + c + '.');
		} else {
			System.err.println("Those values don't describe a valid triangle.");
		}
	}
	
	/**
	 * Problem 2. Crossword helper (10 Points)
	 */
	public static void prob2() {
		/* Write a program that generates simple clues in the form of “n-letter word that begins with ‘x’”
		 * after the user enters a word.  For example, if the user enters “Crossword” your program would
		 * output “9-letter word that begins with ‘C’”.  Case is not important, but be sure to handle
		 * the error when the user enters a blank word by displaying the message “must have at least 1
		 * letter” and/or making the user enter another word.  That is the only error you need to handle.
 		 */
		//final String word = inputLine("Enter a word: ");
		System.out.print("Enter a word: ");
		final String word = sc.nextLine();
		
		if(word.isEmpty()) {
			System.err.println("must have at least 1 letter");
		} else {
			System.out.println(((Integer)word.length()).toString() + "-letter that begins with '" + word.charAt(0) + '\'');
		}
	}
	
	/**
	 * Problem 3. Length of rope (10 Points)
	 */
	public static void prob3() {
		/* A thin rope is wrapped around some small pegs.  The user will type in the number of pegs
		 * followed by their (x,y) coordinates and your program will output the length of the rope.  
		 * You must prompt the user so they know which value they are to enter (e.g., “Number of pegs?”, 
		 * “Y value for peg 3?”). If they enter 0 pegs or a negative number, print an error message
		 * such as “Invalid number of pegs.”  You may assume the user enters only real numbers for the
		 * positions and only integers for the number of pegs.  Note that if there is only 1 peg the
		 * length of the rope is 0. 
		 */
		
		final int n = inputUnsignedInt("Input number of pegs: ");
		if (n < 1) {
			System.err.println("Invalid number of pegs.");
		} else {
			double length = 0, xPrev = Double.NaN, yPrev = Double.NaN;
			for (int peg = 1; peg <= n; ++peg) {
				final double x = inputDouble("X value for peg " + peg + "? ");
				final double y = inputDouble("Y value for peg " + peg + "? ");
				if (peg > 1) {
					length += Math.sqrt((x-xPrev)*(x-xPrev)+(y-yPrev)*(y-yPrev));
				}
				xPrev = x;
				yPrev = y;
			}
			System.out.println("The length of the rope is " + length + '.');
		}
	}

	/**
	 * Problem 4. Euclidean algorithm (20 Points)
	 */
	public static void prob4() {
		/* You will prompt the user for 2 positive integers (you may assume they’re entered correctly)
		 * and then calculate and display their greatest common divisor (GCD), which is the largest integer
		 * that divides them both without leaving a remainder.  You must implement and use the “Euclidean
		 * algorithm” to calculate the GCD; you may want to write a function to do this.
		 * 
		 * Example of GCD:  6 is the GCD of 408 and 906 since (a) it evenly divides both numbers
		 * (408 = 6 × 68 and 906 = 6 × 151) and (b) it is the greatest/largest number to do so.
		 * 
		 * The Euclidean algorithm is an efficient way to find the GCD of 2 integers.  Here are its steps:
		 * 1.	Start with the 2 numbers, a and b.
		 * 2.	If either a or b is 0, the other number is the GCD and you’re finished.
		 * 3.	Replace the larger number with its remainder when divided by the smaller number.  This can be calculated using the % operator in Java and C++.
		 * 4.	Go to step 2.
		 * 
		 * Example of the Euclidean algorithm for a = 408 and b = 906:
		 * •	b is larger, so it is replaced with b%a = 906%408.  So, b becomes 90 (906 = 2 × 408 + 90).
		 * •	a is larger, so it is replaced with a%b = 408%90. So, a becomes 48 (408 = 4 × 90 + 48).
		 * •	b is larger, so it is replaced with b%a = 90%48.  So, b becomes 42.
		 * •	a is larger, so it is replaced with a%b = 48%42.  So, a becomes 6.
		 * •	b is larger, so it is replaced with b%a = 42%6.  So, b becomes 0.
		 * •	One of the numbers (b) is now 0, so the other number (a) is the answer (6).
 		 */
		int a = inputUnsignedInt("a? ");
		int b = inputUnsignedInt("b? ");
		if (b >= a && a != 0) {
			b %= a;
		}
		assert b <= a : b;
		do {
			if (b != 0) {
				a %= b;
			}
			if (a == 0) {
				break; // do
			} else {
				b %= a;
			}
		} while (b != 0);
		System.out.println("The GCD is " + Math.max(a, b) + '.');
	}
	
	/**
	 * Problem 5. Newton’s method (20 Points)
	 */
	public static void prob5() {
		/* Newton’s method is an algorithm for finding where a function reaches 0.
		 * It works by starting with a guess of an x value and calculating f(x).
		 * Since x is only a guess, f(x) != 0.  The algorithm calculates y = f(x) and
		 * the slope of the function at the point (x,y).  In calculus, this slope
		 * is called the first derivative and it is also a function that varies with x;
		 * it is symbolized f’(x).  Newton’s method makes use of f(x) (how close we are
		 * to the goal of 0) and f’(x) (how quickly and in which direction the function
		 * is sloping at x) to make a new guess x for the value where the function reaches 0:
		 *   x := x – f(x) / f’(x)
		 * := means that x is assigned a new value.  This is just = (the assignment operator)
		 * in Java or C++, but := is used to make clear that this is not an algebraic equation
		 * stating 2 quantities are equivalent.
		 * 
		 * Specifically, you will work with
		 * y = f(x) =   a6 x^6 +   a5 x^5 +   a4 x^4 +   a3 x^3 +   a2 x^2 + a1 x + a0
		 *    f’(x) = 6 a6 x^5 + 5 a5 x^4 + 4 a4 x^3 + 3 a3 x^2 + 2 a2 x   + a1
		 * where a6 = -0.09, a5 = 1.6108, a4 = -10.9167, a3 = 34.7625, a2 = -52.0433, a1 = 31.1767, and a0 = -4.
		 * These values are exact – do not round them or remove any digits.  They should be constants in your program
		 * that can be easily changed.  Here is a plot of the function and its derivative (local slope): [see handout]
		 * 
		 * Your program will ask the user for the initial guess of x and then run Newton’s algorithm several
		 * times to find a more accurate value of x where f(x) reaches 0.  You will keep finding a better
		 * value until the absolute value of y is less than 0.001.  You must output the guess x after each
		 * iteration.  For example, if the user enters a guess of 5, your program must refine the guess since
		 * f(5) = 0.6760.  It would ultimately find something near f(4.8782) = -0.00025. 
		 */
		final double[] a = new double[] {-4, 31.1767, -52.0433, 34.7625, -10.9167, 1.6108, -0.09};
		double x = inputDouble("Initial guess of x value at 0-crossing? ");
		final double tol = 0.001;
		System.out.println("Initial position: f(" + x + ") = " + f(a, x)); // initial value does NOT need to be output
		while (Math.abs(f(a, x)) > tol) {
			x -= f(a, x) / df(a, x); // univariate Newton iteration
			System.out.println("Refined zero: f(" + x + ") = " + f(a, x)); // output after each step is required
		}
	}
	
	private static double f(double[] a, double x) { // Horner's method
		double y = a[a.length-1];
		for (int idx = a.length-2; idx >= 0; --idx) {
			y *= x;
			y += a[idx];
		}
		return y;
	}
	
	private static double df(double[] a, double x) { // f' by Horner's method
		double y = (a.length-1) * a[a.length-1];
		for (int idx = a.length-2; idx >= 1; --idx) {
			y *= x;
			y += idx * a[idx];
		}
		return y;
	}
	
	/**
	 * Problem 6. Sudoku predicate (20 Points)
	 */
	public static void prob6() {
		/* Write a function (and a program to use it) that determines whether a particular number can be placed
		 * in a particular square on a Sudoku board.  Sudoku is a game played on a 9×9 grid where you start with
		 * several cells containing numbers 1 through 9, which are the only valid numbers in the game.  The goal
		 * is to fill the entire grid so that in any row and any column each number 1 through 9 appears exactly
		 * once.  Also, the 9×9 board is divided like a tic-tac-toe board into 9 3×3 subregions, and each
		 * subregion must contain each number exactly once.  It may be helpful to see this article for an
		 * illustration: http://en.wikipedia.org/wiki/Sudoku
		 * 
		 * Your function does not implement any Sudoku strategy; it just checks whether the 3 basic rules are
		 * satisfied for a new move that the player is trying to make.  You can assume that the board does not 
		 * violate any of the 3 rules before the move is made.  Your function takes 4 arguments:
		 * •	a 9×9 array of int (created in Java with int[][] A = new int[9][9]; for example).
		 *		You will have to decide how to represent empty squares.  You might use 0 since that is not one of the 9 valid moves.
		 * •	A row number from 0 to 8
		 * •	A column number from 0 to 8
		 * •	A move to try to make in the given row and column, a number from 1 through 9.
		 * 
		 * Your function returns the boolean (bool in C++) true if the move would not violate any of the 3 rules and false otherwise.
		 * You also must write a test program that prompts the user for a row, column, and move to try.
		 * If the row and column is already filled, report the error, otherwise call the function and use the result
		 * to tell the user whether that move violates the rules.  Declare an array representing the following board
		 * and use it for testing: [see handout]
		 * Rows and columns are numbered from the upper left starting at (0,0).  We can see that the square at (0,0)
		 * is empty and it cannot contain 8, 5, 1, or 7 because of the column rule; 2, 7, 8, or 4 because of the
		 * row rule; or 2, 8, 6, 5, 4, 7 because of the subregion rule.  So, if the user tries to put an 8 there,
		 * your function will return false.  But, since the number 3 does not violate any of these rules, your
		 * function would return true. (Note that this does not mean that 3 is the correct move in the solved puzzle,
		 * but just that it is a move that meets the rules; that is all you need to check.)
		 */
		int row = inputUnsignedInt("row? ");
		int col = inputUnsignedInt("col? ");
		int move = inputUnsignedInt("move? ");
		System.out.println("Truth value of that being a valid move:" + sudokuCheck(board, row, col, move));

	}
	 private static final int[][] board =
	 {	{0, 0, 2, 0, 7, 8, 4, 0, 0},
		{8, 6, 0, 0, 4, 5, 1, 0, 0},
		{5, 4, 7, 2, 9, 1, 6, 0, 0},
		{1, 0, 8, 0, 0, 6, 0, 4, 0},
		{7, 5, 6, 0, 0, 0, 2, 0, 0},
		{0, 9, 4, 1, 5, 0, 0, 0, 0},
		{0, 0, 0, 8, 0, 0, 0, 0, 0},
		{0, 0, 5, 0, 6, 4, 0, 0, 1},
		{0, 2, 1, 0, 0, 0, 0, 6, 0}
	};
	private static final int sudokuRoot = 3;
	private static final int sudokuSize = sudokuRoot*sudokuRoot;
	private static boolean sudokuCheck(int[][] board, int row, int col, int move) {
		assert board.length == sudokuSize : board;
		assert board[0].length == sudokuSize: board; // not a complete check of size, could be jagged
		boolean validMove =	(sudokuSize >= move) && (move >= 1) // 1-based
						&&	(sudokuSize > row)	&& (row >= 0) // 0-based
						&&	(sudokuSize > col)	&& (col >= 0)
						&&	(board[row][col] == 0); // empty space?
		
		if (validMove) { // row check
			for(int c = 0; c < sudokuSize; ++c) {
				//if (c == col) { // not actually needed since we verified the putative move is to an empty spot
				//	continue;
				//} else
				if (board[row][c] == move) {
					validMove = false; // proposed move already made in this row
					break;
				}
			}
		}
		if (validMove) { // col check
			for(int r = 0; r < sudokuSize; ++r) {
				if (board[r][col] == move) {
					validMove = false;
					break;
				}
			}
		}
		if (validMove) { // subregion check
			row = (row / sudokuRoot) * sudokuRoot; // find subregion origin
			col = (col / sudokuRoot) * sudokuRoot; // destructive, must come last 
			for (int r = 0; validMove && r < sudokuRoot; ++r) {
				for (int c = 0; c < sudokuRoot; ++c) {
					if (board[row+r][col+c] == move) {
						validMove = false;
						break; // for c						
					}
				}
			}
		}
		return validMove;
	}

	/**
	 * Problem 7. Sudoku potential moves (40 Points)
	 */
	public static void prob7()
	{
		/* You should complete problem 6 before working on this problem.
		 * You may work on this problem before your problem 6 is graded, but be aware that any errors
		 * in your solution to 6 will probably prevent you from solving this problem.
		 * But, since you must implement 6 in a function, it should be easy to copy and paste any
		 * corrections you make to 6 over to your working area for this problem.
		 * 
		 * Write a program that uses your function from 6 and a new function that you will write for this problem.
		 * The new function takes 3 arguments (the same as the first 3 from the solution to problem 6) and returns
		 * an array of int of length 0 to 9 containing all the valid moves for the given square (In C++ you may also
		 * want to pass an argument by reference to receive the size of the array.).  Call your function written in
		 * 6 to determine whether a move is valid.
		 * 
		 * The main program you write for this problem will define the 9×9 board as in problem 7 and then call
		 * your new function for every empty square.  Depending on the size of the returned array, print one of
		 * the following sentences, filling in (x,y) and move values according to the data:
		 * •	“There are 0 valid moves for square (x,y), so the board is invalid.”
		 * 		[This shouldn’t happen because you’re promised a valid board, but checking may be helpful in debugging your code.]
		 * •	“There is 1 valid move for square (x,y) and it is N.  You should make this move.”
		 * •	“There are multiple valid moves for square (x,y) and they are N O P Q.”
		 * 		[Note: example for 4 possibilities; there may be anywhere from 2 to 9.]
		 */
		for (int row = 0; row < sudokuSize; ++row) {
			for (int col = 0; col < sudokuSize; ++col) {
				if (board[row][col] == 0) {
					int[] moves = sudokuEnumerate(board, row, col);
					if (moves.length == 0) {
						System.err.println("There are 0 valid moves for square ("+row+","+col+"), so the board is invalid.");
					} else if (moves.length == 1) {
						System.out.println("There is 1 valid move for square ("+row+","+col+") and it is "+moves[0]+".  You should make this move.");
					} else { // more than 1 move
						System.out.print("There are multiple valid moves for square ("+row+","+col+") and they are");
						for(int move : moves) {
							System.out.print(" " + move);
						}
						System.out.println();
					}
				}
			}
		}		
	}
	
	private static int[] sudokuEnumerate(int[][] board, int row, int col) {
		int valid[] = new int[sudokuSize]; // alloc max, correct not yet known
		int count = 0;
		for(int move = 1; move <= sudokuSize; ++move) {
			if (sudokuCheck(board, row, col, move)) {
				valid[count++] = move;
			}
		}
		int retVal[] = new int[count]; // alloc correct
		java.lang.System.arraycopy(valid, 0, retVal, 0, count);
		return retVal;
	}
	/*
	// alternate approach using "frequency" algorithm
	private static int[] sudokuEnumerate(int[][] board, int row, int col) {
		List<boolean> valid = new ArrayList<boolean>(sudokuSize); // capacity, not size
		for(int move = 1; move <= sudokuSize; ++move) {
			valid.add(sudokuCheck(board, row, col, move));
		}
		int[] moves = new int[java.util.Collections.frequency(valid, true)];
		for(int idx = 0, move = 1; idx != moves.length && move <= sudokuSize; ++move) {
			if(valid.get(move-1)) {
				moves[idx++] = move;
			}
		}
		return moves;
	}
	*/
	
	/**
	 * Problem 8. Image Processing (40 points)
	 * Find and label the contiguous elements of a monochrome image.
	 * @author Dr. Welch 2006; Dr. Durant tweaks 11/2009
	 */
	public static void prob8()
	{
		// Set-up for file input
		Scanner freader = null;
		while (freader == null) {
			try {
				freader = new Scanner(new File(inputLine("Image filename (e.g., 'image1.txt'): ")));
			} catch (FileNotFoundException e) {
				System.err.println("Sorry, that file wasn't found, please try again.");
			}
		}
			
		// Read the data
		final int rows = freader.nextInt();
		final int cols = freader.nextInt();
		freader.nextLine(); // skip \n
		
		// Initialize data
		List<StringBuffer> data = new ArrayList<StringBuffer>();
		for (int i = 0; i < rows; ++i) {
			data.add(new StringBuffer(freader.nextLine()));
		}
		
		// Begin scan
		char code = 'A';
		for (int r = 0; r < rows; ++r) {
			// The first column is different
			if (r != 0) {
				// Look only if pixel
				if (data.get(r).charAt(0) == '*') {
					// Look above
					if (data.get(r-1).charAt(0) != ' ') {
						data.get(r).setCharAt(0, data.get(r-1).charAt(0));
					}
					// Look above-right
					else if (data.get(r-1).charAt(1) != ' ') {
						data.get(r).setCharAt(0, data.get(r-1).charAt(1));
					}
					else {
						data.get(r).setCharAt(0, code);
						++code;
					}
				}
			}
			for (int c = 1; c < cols; ++c) {
				// Look only if pixel
				if (data.get(r).charAt(c) == '*') {
					
					char left = data.get(r).charAt(c-1);
					// If first row only look left
					if (r == 0) {
						// Look left
						if (left != ' ') {
							data.get(r).setCharAt(c, left);							
						}							
					}
					else {
						// Get info
						char above_left = data.get(r-1).charAt(c-1);
						char above = data.get(r-1).charAt(c);
						char above_right = ' ';
						
						if (c != cols-1) above_right = data.get(r-1).charAt(c+1);
						// Look left
						if (left != ' ') {
							data.get(r).setCharAt(c, left);							
						}
						// Look above-left
						else if (above_left != ' ') {
							data.get(r).setCharAt(c, above_left);
						}
						// Look above
						else if (above != ' ') {
							data.get(r).setCharAt(c, above);
						}
						// Look above-right
						else if (above_right != ' ') {
							data.get(r).setCharAt(c, above_right);
						}
						else {
							data.get(r).setCharAt(c, code);
							++code;
						}
						// Check for merge: left or above-left with above-right
						if (((left != ' ') || (above_left != ' ')) &&
						     (above_right != ' ') && (data.get(r).charAt(c) != above_right)) {
							prob8_merge(data,data.get(r).charAt(c), above_right);
						}
					}
				}					
			}
		}
		for (StringBuffer row : data) {
			for (int c = 0; c < row.length(); ++c) {
				System.out.print(row.charAt(c));
			}
			System.out.println();
		}
	}
	
	/**
	 * Helper method to merge two classifications. Substitute area1 for area2 throughout the image
	 * @param data collection of image lines
	 * @param area1 value for both classifiers
	 * @param area2 classifier to replace
	 */
	private static void prob8_merge(List<StringBuffer> data, char area1, char area2) {

		// Loop through each row and column substituting area1 for area2
		for (StringBuffer row : data) {
			for (int c = 0; c < row.length(); ++c) {
				if (row.charAt(c) == area2) row.setCharAt(c, area1);
			}
		}
	}

	/**
	 * STL-style pair class (nested, top-level) for use in degrees of separation project
	 * @author Dr. Durant (durant@msoe.edu)
	 *
	 * @param <L> the type of the left element
	 * @param <R> the type of the right element
	 */
	private static class Pair<L, R> {
	    public final L left;
	    public final R right;
	    public Pair(final L left, final R right) {
	        this.left = left;
	        this.right = right;
	    }
	}

	/**
	 * Problem 9. Degrees of separation (40 points)
	 */
	public static void prob9() {
		// Note, there are several errors, including malformed file errors, that we do not check for.  Student may assume a valid input file
		
		Scanner fsc = null;
		try {
			fsc = new Scanner(new File(inputLine("Filename (e.g., separation1.txt): "))); // competitors may hardcode or prompt for filename, but MUST read from a file
		} catch (FileNotFoundException e) {
			System.err.println("The file was not found - will now terminate in an ugly manner.");
			System.exit(-1);
		}
		
		final int people = fsc.nextInt();
		
		List<Pair<Integer, Integer> > pair = new ArrayList<Pair<Integer, Integer> >();
		while(fsc.hasNextInt()) {
			pair.add(new Pair<Integer, Integer> (fsc.nextInt(), fsc.nextInt())); // Per the problem spec, using 0-base
		}
		
		int[][] degrees = new int[people][people];
		for (int row = 0; row < people; ++row)
			for (int col = 0; col < people; ++col)
				degrees[row][col] = 9999; // sentinel for infinity
		for (Pair<Integer, Integer> pa : pair)
			degrees[pa.left][pa.right] = degrees[pa.right][pa.left] = 1;			
		for (int person = 0; person < people; ++person)
			degrees[person][person] = 0;
		
		// using FULL until now; TRIU optimized below
		
		boolean foundShorter = true;
		while(foundShorter) {
			foundShorter = false;
			for (int row = 0; row < people; ++row)
				for (int col = 0; col < row; ++col) // TRIU only
					for (int between = 0; between < people; ++between)
						if (between != row && between != col) {
							int via = degrees[row][between] + degrees[between][col];
							if (via < degrees[row][col]) {
								degrees[row][col] = degrees[col][row] = via; // maintain FULL for simplified lookup
								foundShorter = true; // don't terminate while (complete fors regardless)
							}
						}
		}
		
		final int person1 = inputInt(String.format("Person 1 (0-%d): ", people-1)); // 0-base
		final int person2 = inputInt(String.format("Person 2 (0-%d): ", people-1));
		
		System.out.printf("The degrees of separation are %d.\n", degrees[person1][person2]);
	}

	
	/**
	 * prompt for int, skipping any invalid preamble
	 * @param prompt prompt to display
	 * @return the entered int
	 */
	public static int inputInt(String prompt)
	{
		System.out.print(prompt);
		while (!sc.hasNextInt())
			sc.next(); // discard non-int token
		//return sc.nextInt();
		int retVal = sc.nextInt();
		sc.nextLine(); // dump CR from stream
		return retVal;
	}
	/**
	 * prompt for unsigned int, skipping any invalid preamble
	 * @param prompt prompt to display
	 * @return the entered int
	 */
	public static int inputUnsignedInt(String prompt)
	{
		System.out.print(prompt);
		int retval = -1;
		while (retval < 0)
		{
			while (!sc.hasNextInt())
				sc.next(); // discard non-int token
			retval = sc.nextInt();
		}
		sc.nextLine(); // dump CR from stream
		return retval;
	}
	
	/**
	 * prompt for a double, skipping any invalid preamble
	 * @param prompt prompt to display
	 * @return the entered double
	 */
	public static double inputDouble(String prompt)
	{
		System.out.print(prompt);
		while (!sc.hasNextDouble())
			sc.next(); // discard non-matching token
		//return sc.nextDouble();
		double retVal = sc.nextDouble();
		sc.nextLine(); // dump CR from stream
		return retVal;
	}
	
	public static String inputLine(String prompt)
	// Simple prompt for a line of text
	{
		System.out.print(prompt);
		String retval;
		// Key here is to discard empty lines (including \n's left in the buffer), but we make it a more robust to whitespace...
		do {
			retval = sc.nextLine();
			retval = retval.trim();
		} while (retval.length() == 0);
		return retval;
	}
	
	private final static Scanner sc = new Scanner(System.in);
}