package solution;

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

import javax.swing.JFileChooser;
import javax.swing.filechooser.FileNameExtensionFilter;

/**
 * @author Eric Durant <durant@msoe.edu>
 * Created on November 14, 2013
 * Last updated November 19, 2013
 * Java sample solutions for Op 2013
  */
public class Op2013 {
    /**
     * Console menu allowing selection of any of the 9 demo solutions
     * @param args (unused)
     * @throws FileNotFoundException 
     */
    public static void main(String[] args)
    {
        boolean done = false;
        while(!done)
        {
            System.out.println("Op 2013 Demo Program");
            System.out.println("1. Parallel resistance");
            System.out.println("2. Scrabble score");
            System.out.println("3. Bertrand's ballot theorem");
            System.out.println("4. Anagrams");
            System.out.println("5. Angle between clock hands");
            System.out.println("6. Text histogram");
            System.out.println("7. Bertrand's ballot theorem simulation");
            System.out.println("8. Spin ice");
            System.out.println("9. Dispatching cabs");
            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
            }

            try {
                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;
                }
            } catch (FileNotFoundException e) {
                System.err.println("Op Demo returned to main menu due to FileNotFound exception: " + e.getMessage());
            }
        }
    }
    
    /**
     * Problem 1. Parallel resistance (10 Points)
     */
    public static void prob1() {
        /*
         * Calculate the “parallel resistance” of three loads (1st 3 inputs from user) placed across a “voltage source” (4th and final input from user).
         * For example, the voltage source might be a battery and the loads might be an LED (light source), computer processor, and camera.
         * Ohm’s law tells us that the electrical current (proportional to electrons per second) flowing through a load is equal to the voltage divided
         * by the resistance, or I = V/R. These quantities are given in units of amperes (A), volts (V), and ohms ($\Omega$), respectively.
         * For example, if we have a 5 V battery and an LED with resistance of 1000 $\Omega$, the resulting current through the LED is 5/1000 V/ $\Omega$ = 0.005 A.
         * 
         * In our example, all 3 devices are placed with their ends touching the ends of the voltage source since they each require the voltage it provides.
         * In this case, the voltage source is providing the calculated current to each of the 3 devices,
         * thus we can add the 3 device currents to get the current out of the voltage source.
         * Now that we have the total current, we can solve for the parallel resistance again using Ohm’s law: Itotal = V/Rparallel.
         * 
         * For example, if the user tells us the resistances are 500, 1000, and 2500 \Omega, and the voltage is 5 V, the currents would be
         * 0.01, 0.005, and 0.002 A. Adding the currents together, we get a total of 0.017 A.
         * Then, we can solve for the resistance as seen from the voltage source by solving the equation for R: R = V / I = 5 V / 0.017 A = 294.12 \Omega.
         * 
         * Note: There is a shortcut to this problem that allows you to ignore the input voltage. You may use it, but are not required to do so.
         */
        final double R1 = inputDouble("R1? ");
        final double R2 = inputDouble("R2? ");
        final double R3 = inputDouble("R3? ");
        final double V  = inputDouble("V ? ");
        
        final double[] I = { V/R1, V/R2, V/R3 };
        double I_tot = 0;
        for (double i : I) I_tot += i;
        
        System.out.printf("The parallel resistance is %g.\n", V/I_tot);
    }
    
    /**
     * Problem 2. Scrabble score (10 Points)
     */
    public static void prob2() {
        /*
         * Ask the user to input a word and calculate its Scrabble score.
         * The user may use any mix of uppercase and lowercase, but case is not significant in your calculation.
         * You may assume that the user enters only letters. The values of the letters are given below:
         * •    1 point: A, E, I, L, N, O, R, S, T, U
         * •    2 points: D, G
         * •    3 points: B, C, M, P
         * •    4 points: F, H, V, W, Y
         * •    5 points: K
         * •    8 points: J, X
         * •    10 points: Q, Z
         */
        //                    A B C D E F G H I J K L M N O P Q  R S T U V W X Y Z
        final int[] points = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};
        final String word = inputLine("Enter a word: ");
        int score = 0;
        for (char c: word.toCharArray()) score += points[Character.toUpperCase(c)-'A'];
        System.out.printf("The word [%s] is worth %d points.\n", word, score);
    }
    
    /**
     * Problem 3. Bertrand's ballot theorem (10 Points)
     */
    public static void prob3() {
        /*
         * Bertrand’s ballot theorem calculates the probability that the ultimate winner of a 2-candidate election is ahead after each individual vote is cast
         * (so, they must receive the first vote; we are ignoring ties).
         * Given that candidate A is the ultimate winner and receives p votes and candidate B receives q votes, the probability is:
         * (p-q)/(p+q)
         * Ask the user to input p and q and calculate the probability. Assume the user enters positive integers.
         * Your answer should take the form of “Candidate B, who received 13 out of 20 votes, had a 0.3 chance of being ahead throughout the election.”
         * This example is for p = 7 and q = 13. Your sentence should begin with which ever candidate received more votes.
         */
        final int p = inputUnsignedInt("Candidate A votes? ");
        final int q = inputUnsignedInt("Candidate B votes? ");
        final int s = p+q;
        final double prob = (p-q)/(double)s; // It is given that there is a first vote, therefore we ignore s==0 case
        final boolean aWon = prob >= 0; // ignoring ties per spec.
        System.out.printf("Candidate %c, who received %d out of %d votes, had a %g chance of being ahead throughout the election.\n",
                           aWon?'A':'B',              aWon?p:q, s,              aWon?prob:-prob);
    }

    /**
     * Problem 4. Anagrams (20 Points)
     */
    public static void prob4() {
        /*
         * Ask the user to input 2 words. Ignore case. Assume the user enters only letters.
         * Report whether the words are anagrams of each other, that is, whether they contain the identical number of each letter.
         * Note that the words must be of exactly the same length in order to possibly be anagrams.
         */
        final String word1 = inputLine("Enter a first word: ");
        final String word2 = inputLine("Enter another word: ");
        if (word1.length() != word2.length())
            System.out.println("The words are of different lengths, so they cannot be anagrams."); // not necessary to point this out as long as program reports not anagrams
        else
        {
            final int[] bucket = new int['Z'-'A'+1];
            for (char c: word1.toCharArray()) ++bucket[Character.toUpperCase(c)-'A']; // Specification REQUIRES ignoring case
            for (char c: word2.toCharArray()) --bucket[Character.toUpperCase(c)-'A'];
            // buckets will all be at 0 if they're anagrams
            boolean anagram = true;
            for (int b: bucket) {
                if (b != 0) {
                    anagram = false;
                    break;
                }
            }
            System.out.println("The truth value of the words being anagrams is: " + Boolean.toString(anagram));
        }
    }
    
    /**
     * Problem 5. Angle between clock hands (20 Points)
     */
    public static void prob5() {
        /* Ask the user for the hour and minute and display the resulting angle between the hands of a clock.
         * Assume that the hour is correctly entered as an integer between 1 and 12 and that
         * the minute is correctly entered as a real number between 0 and 60.
         * The angle must be presented as a value between 0 and 180 degrees inclusive.
         */
        final int h = inputUnsignedInt("Hour? ");
        final double m = inputDouble("Minute? ");
        
        double degrees  = Math.abs(60*h-11*m)/2; // 0-360
        if (degrees > 180)
            degrees = 360-degrees; // ensure on 0-180
        
        System.out.println("The angle is " + degrees + " degrees.");
    }
    
    /**
     * Problem 6. Text histogram (20 Points)
     */
    public static void prob6() {
        /*
         * A histogram is a graph that shows the number of values in each of a series of bins.
         * It is a useful tool for showing where values are most popular.
         * A histogram is computed by dividing the number line up into a series of bins of the same size and counting the number of values in each bin’s range.
         * For the sequence of data: 3 6 1 1 2 3 4 5 1 3 6 2 9 4 2 3 4 6 6 7 and bins starting at 0 with a width of 2, the following histogram would result:
         * 0 - 1    ***
         * 2 - 3    *******
         * 4 - 5    ****
         * 6 - 7    *****
         * 8 - 9    *
         * 
         * This result is correct because there are 3 values in the range 0 to 1, 7 in the range 2 to 3, …,  and 1 in the range 8-9.
         * 
         * Write a program that inputs from the user:
         * •    a starting bin location (for the example above this is 0),
         * •    the bin width (for the example above this is 2),
         * •    and all the values on a single line, separated by spaces.
         * Compute and plot the histogram in a format similar to the example above. You may assume that all the data are integers.
         * If the starting location is greater than the minimum of the data, respond as if the user entered the minimum for the starting location. 
         */
            
        int left = inputInt("Starting bin location: "); // below code assumes this is not greater than the minimum
        final int width = inputInt("Bin width: ");
        final Scanner data = new Scanner(inputLine("All the values on a single line, separated by spaces: "));
        final List<Integer> li = new ArrayList<Integer>();
        while (data.hasNextInt())
            li.add(data.nextInt());
        data.close();
        final int min = Collections.min(li), max = Collections.max(li);
        if (left > min) left = min;
        final int totalWidth = max-left+1;
        final int binCount = totalWidth / width + ((totalWidth % width > 0) ? 1 : 0);
        final int[] bin = new int[binCount];
        for(int i : li) ++bin[(i-left) / width];
        for(int i = 0; i < bin.length; ++i) {
            char[] stars = new char[bin[i]];
            Arrays.fill(stars , '*'); // There are more efficient ways, but probably no simpler ways because of limitations on int, etc.
            System.out.printf("%d - %d %s\n", left+(i*width), left+(i+1)*width-1, new String(stars));
        }
    }

    /**
     * Problem 7. Bertrand’s ballot theorem simulation (40 Points)
     */
    public static void prob7()
    {
        /*
         * Write a program to simulate a large number of elections to confirm whether Bertrand’s ballot theorem (see problem 3) is approximately correct.
         * You will ask the user for 3 inputs, and you may assume they are all valid:
         * •    The number of voters (an integer from 1 to 1000)
         * •    The probability that each voter will vote for candidate A (between 0 and 1)
         * •    The number of elections to simulate (an integer from 1 to 1000)
         * 
         * For each election, you must determine whether the ultimate winner was always ahead, starting with the first vote.
         * Thus, if A receives the 1st vote, but falls behind or reaches parity at any point as votes are tallied (regardless of whether A wins),
         * the election counts in the “not always ahead” category.
         * Note that it is possible and okay that A and B each win some elections where they are always ahead.
         * 
         * After running all the elections (at least far enough to categorize them),
         * you will divide the “always ahead” election count by the total election count and summarize the relevant facts for the user similarly to the following:
         * “In 1000 simulated elections each with 100 voters, where candidate A received each vote with probability 0.65, the winner was always ahead 0.287 of the time.”
         * 
         * Note: This is solving a similar, but different problem, than Bertrand’s theorem.
         * Results may differ greatly for small electorates.
         * While Bertrand’s theorem applies to exact numbers of votes, this problem concerns the probability of receiving each vote.
         * 
         * Note: Your program will need random numbers to solve this. See the end of this document for information on how to generate these.
         */
        
        final int numberVoters = inputUnsignedInt("Number of voters (integer from 1 to 1000): ");
        final double probabilityA = inputDouble("Probability that each voter will vote for candidate A (between 0 and 1): ");
        final int numberElections = inputUnsignedInt("Number of elections to simulate (integer from 1 to 1000): ");
        
        final java.util.Random myGenerator = new java.util.Random();
        
        int countAlwaysAhead = 0;
        for (int election = 0; election < numberElections; ++election) {
            final int[] votes = new int[2]; // votes for A and B
            // first voter is special case
            final boolean aAlwaysLeading = myGenerator.nextDouble() < probabilityA; // abort election if this would be about to change
            int vote = aAlwaysLeading ? 0 : 1;
            ++votes[vote];
            boolean alwaysLeading = true;
            for(int voter = 1; voter < numberVoters; ++voter) {
                vote = myGenerator.nextDouble() < probabilityA ? 0 : 1;
                ++votes[vote];
                if (aAlwaysLeading != votes[0] > votes[1] || votes[0] == votes[1]) { // if the wrong candidate just pulled ahead or into a tie; handling of terminal ties unimportant per problem spec.
                    alwaysLeading = false;
                    break; // end this election
                }
            }
            if (alwaysLeading) ++countAlwaysAhead;
        }       
        System.out.printf("In %d simulated elections each with %d voters, where candidate A received each vote with probability %g, the winner was always ahead %g of the time.\n",
                numberElections, numberVoters, probabilityA, (double)countAlwaysAhead/numberElections);
    }
    
    /**
     * Problem 8. Spin ice (40 Points)
     * @throws FileNotFoundException 
     */
    public static void prob8() throws FileNotFoundException
    {
        /*
         * A “spin ice” is a substance similar to a crystalline solid in that its atoms are locked in fixed, regular positions.
         * Each vertex (intersection of a horizontal line with a vertical line) in the diagram represents an atom.
         * Each atom can have one of two spin states (it is convenient to think of it as spinning either up or down,
         * but spin is actually a quantum mechanical property that doesn’t have such a physical interpretation).
         * Usually the spins are balanced around alternating spaces between the atoms (indicated by gray squares;
         * note they always occur where the sum of the row and column numbers is odd).
         * Balanced means that there equal numbers of inward pointing spins (spins on the bottom pointing up and spins on the top pointing down)
         * as outward pointing spins. Note also that spins never point at any of the white squares (gaps between atoms).
         * Sometimes spins are reversed from a balanced pattern, however, such as the 4 spins marked by dark gray triangles.
         * Note that the space at r3c4 (row 3, column 4), marked N, is out of balance since 3 spins are pointing in and 1 spin is pointing out.
         * Similarly, the space at r5c6, marked S, is out of balance with 1 spin pointing in and 3 pointing out.
         * The N and S represent the north and south poles of a microscopic magnet. There is also a north pole at r1c2.
         * Note that there are more north poles than south poles!
         * This actually happens in certain spin ices, although it is not something that normally makes sense
         * when we think of normal magnets where north and south poles always come in pairs.
         * 
         * The spins in the diagram can be represented by the following array.
         * The gray spins in the diagram are marked by bold-italic text and break the checkerboard pattern of 0s and 1s.
         * Note that there is one more row and one more column in the atom spin array than there is in the array of spaces between atoms;
         * atom [0,0] with its spin is at the upper left side of space [0,0], atom [8,8] with its spin is at the lower right of space [7,7].
         * 
         * You must write a program that inputs an array of 1s and 0s as shown from a user-specified file.
         * You may assume it is always a 9×9 array as illustrated and that there are 9 lines each containing 9 characters;
         * there are no row or column labels in the file. Your program will do the following:
         * 
         *    c012345678
         * r0: 101000101
         * r1: 010001010
         * r2: 101010101
         * r3: 010101010
         * r4: 101011101
         * r5: 010101110
         * r6: 101010101
         * r7: 010101010
         * r8: 101010101
         * 
         * •    Find the locations of all the contained N and S poles and report them. In this case, you would report, “N at [1,2][3,4]. S at [5,6].”
         *      The precise formatting isn’t critical as long as the meaning is clear.
         * •    Report whether the net polarity is N or S and how strong it is. In the example, there are 2 Ns and 1 S, so the net polarity is 1 N.
         *      So, in this case you would report “Net polarity: 1 N”, but in some situations you might report “Net polarity: 2 S”, “Net polarity: 0”, etc.
         *
         * Note: you may assume that no spaces have 4 arrows pointing to or away from them.
         * That represents a spin configuration that is physically impossible.
         */

        final int spins[][] = readSpins();
        
        /*      
         * Note: Competitors do NOT need to make this check. This section checks that an input file represents a physically realizable configuration,   
         * that is, one with no spaces that have 4 arrows pointing to or away from them. If this section identifies an invalid file, than that file
         * should NOT be used to determine whether student programs are correct.
         */
        boolean success = true; // if we fail at any point, we report the error and break out
        for (int row = 0; row < spins.length-1 && success; ++row) { // iterating over spaces, so one less than spins/atoms
            for (int col = 1-row%2; col < spins[0].length-1; col+=2) { // row+col must be odd
                final int T = spins[row  ][col]+spins[row  ][col+1], // # up from top
                          B = spins[row+1][col]+spins[row+1][col+1]; // # up from bottom
                final int inward = B - T;
                if (inward == 2 || inward == -2) {
                    System.out.printf("Invalid spin state found at space [%d,%d].", row, col);
                    success = false;
                    break;
                }
            }
        }
        
        /*
         * •    Find the locations of all the contained N and S poles and report them. In this case, you would report, “N at [1,2][3,4]. S at [5,6].”
         *      The precise formatting isn’t critical as long as the meaning is clear.
         */
        if (success) {
            for (int row = 0; row < spins.length-1; ++row) { // iterating over spaces, so one less than spins/atoms
                for (int col = 1-row%2; col < spins[0].length-1; col+=2) { // row+col must be odd
                    final int T = spins[row  ][col]+spins[row  ][col+1], // # up from top
                              B = spins[row+1][col]+spins[row+1][col+1]; // # up from bottom
                    final int inward = B - T;
                    if (inward != 0) {
                        System.out.print(pole(inward));
                        System.out.println(" at [" + row + ',' + col + ']');
                    }
                }
            }
        }

        /*
         * •    Report whether the net polarity is N or S and how strong it is.
         *      In the example, there are 2 Ns and 1 S, so the net polarity is 1 N.
         *      So, in this case you would report “Net polarity: 1 N”, but in some situations you might report “Net polarity: 2 S”, “Net polarity: 0”, etc.
         */
        if (success) {
            /* I expect student solutions to take the easy route and simply sum the results they found in the previous section.
             * However, I implement a different approach here, partially as a cross-check on the validity of the algorithm.
             * I use just the border values to calculate the net polarity; internal disturbances don't affect the net polarity
             * Note that in the example data there are 2 more spins pointing in than out (the difference will always be an even number).
             * Note that the spins at [0,0] and [8,8] are ignored since they do not cross the boundary of any of the gray squares.
             */

            int inward = 0; // net inward arrows
            for (int col = 0; col < spins[0].length-1; ++col) { // indexes across bottom (including LL); +1 to get top (including UR)
                inward += (spins[spins.length-1][col] == 1 ? 1 : -1)  // bottoms pointing up are in 
                        + (spins[0][col+1]            == 0 ? 1 : -1); // tops pointing down are in
            }
            for (int row = 1; row < spins.length-1; ++row) { // indexes down sides, neglecting top & bottom rows, which are already taken care of
                inward += ((spins[row][0                ] == row                      %2) ? -1 :  1)  // lefts up are out (S, neg) on odd rows
                        + ((spins[row][spins[0].length-1] == ((row+spins[0].length)-1)%2) ?  1 : -1); // rights down are out when row+col is even
            }
            assert inward % 2 == 0 : inward; // there is a logic error if inward isn't even
            System.out.print("Net polarity: " + Integer.toString(Math.abs(inward)/2) + ' '); // abs first to ensure rounding towards 0
            if (inward != 0) System.out.print(pole(inward));
            System.out.println();
        }
    }
    
    private static char pole(int inward) { // assumes inward != 0
        return inward>0 ? 'N' : 'S';
    }
    
    private static int SIZE = 9; // specified as constant for problem
    /**
     * Ask user to select file (beware: dialog is sometimes raised in background).
     * This function is given to the competitors, but they may modify it if they desire a different representation.
     * @return 2-D array of spins of size SIZE x SIZE
     * @throws FileNotFoundException if the picked file is not found when we attempt to open it
     */
    private static int[][] readSpins() throws FileNotFoundException {
        JFileChooser chooser = new JFileChooser();
        chooser.setFileFilter(new FileNameExtensionFilter("Text files", "txt"));
        if(chooser.showOpenDialog(null) != JFileChooser.APPROVE_OPTION) {
            throw new IllegalArgumentException("User did not select a file");
        }
        // Open the specified file
        final Scanner fsc = new Scanner(chooser.getSelectedFile()); // throws FileNotFoundException
        // Read the file, assuming it is properly formatted; may throw runtime exceptions for formatting errors
        final int[][] spins = new int[SIZE][SIZE];
        for (int row = 0; row < spins.length; ++row) {
            final String line = fsc.nextLine();
            assert line.length() == spins[row].length;
            for (int col = 0; col < spins[row].length; ++col) {
                spins[row][col] = (line.charAt(col) == '0') ? 0 : 1;
            }
        }
        fsc.close();
        return spins;
    }
    
    /**
     * Problem 9. Dispatching cabs (40 Points)
     */
    public static void prob9() {
        /* You are given two data files (samples are available on the contest website).
         * Cabs.txt contains the location of available cabs at the beginning of the day.
         * Each cab has a sequential ID number beginning with 0.
         * Passengers.txt contains the location of passengers in the order that they call for a cab.
         * The passenger names in order are ‘A’, ‘B’, ‘C’, etc.; there are at most 26 passengers.
         * For the purposes of this problem, people take very long cab rides; once a cab is used, it is never available again.
         * Write a program that, given names of files containing cab locations and passengers, assigns the closest cab to each passenger and dispatches
         * it as the calls come in; your program will output a list of cabs and passengers (for example, “Cab 3 dispatched to passenger N.”).
         * If there are more passengers than cabs, stop after all cabs are dispatched.
         * Since the cabs need to travel streets that form a grid pattern with only right angles, “distance” between two points is defined as
         * the distance in the x direction plus the distance in the y direction (no square roots or trigonometry are involved).
         */
        
        // Prompt user, or set PATH to where you keep your data files.
        String PATH = "C:\\Users\\durant\\Desktop\\op2013\\data\\";
        
        final double[][] cabs = readArray(PATH + "p9-cabs.txt");
        final double[][] passengers = readArray(PATH + "p9-passengers.txt");
                
        for (int passId = 0; passId < Math.min(passengers.length, cabs.length); ++passId) {
            double minDistance = Double.MAX_VALUE;
            int cabMinIdx = -1; // invalid
            
            for (int thisCab = 0; thisCab < cabs.length; ++thisCab) {
                double distance = Math.abs(passengers[passId][0]-cabs[thisCab][0])
                                + Math.abs(passengers[passId][1]-cabs[thisCab][1]);
                if (distance < minDistance) {
                    minDistance = distance;
                    cabMinIdx = thisCab;
                }
            }
            
            assert cabMinIdx >= 0 : cabMinIdx;
            
            System.out.printf("Cab %d dispatched to passenger %c at city-block distance %g.\n",
                    cabMinIdx, 'A'+passId, minDistance);
            
            cabs[cabMinIdx][0] = cabs[cabMinIdx][1] = Double.MAX_VALUE;
        }
    }
    /**Read a Nx2 array from a file. Assumes properly formatted file.
     * @param fn the name of the file to read from
     * @return the Nx2 array (N is determined from file)
     */
    private static double[][] readArray(String fn) {
        Scanner sc = null;
        double[][] retval = null;
        try {
            sc = new Scanner(new File(fn));
        } catch (FileNotFoundException e) {
            System.out.printf("File not found: [%s].\n", fn);
        }
        if (sc != null) {
            final int N = sc.nextInt();
            
            retval = new double[N][2];
            
            boolean success = true;
            
            for(int row = 0; row < N && success; ++row) {
                for(int col = 0; col < 2; ++col) {
                    if (sc.hasNextDouble()) {
                        retval[row][col] = sc.nextDouble();
                    }
                    else {
                        success = false;
                        break;
                    }
                }
            }
            
            if(!success) {
                System.out.printf("Fewer than the expected number of elements found in [%s].\n", fn);
            }
            
            sc.close();
        }
        return retval;
    }
    
    /**
     * 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
        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
        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 bit 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);
}