import java.util.*; import java.io.File; import java.io.FileNotFoundException; /** * @author Eric Durant * Created on November 6, 2015 * Last updated NA * Java sample solutions for Op 2015 */ public class Op2015 { /** * 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 2015 Demo Program"); System.out.println("1. Tip and split calculator"); System.out.println("2. Matching numbers"); System.out.println("3. Only one vowel"); System.out.println("4. Third largest"); System.out.println("5. Arithmetic-geometric mean"); System.out.println("6. Juggler sequence"); System.out.println("7. Partition into three triangular numbers"); System.out.println("8. Exchange rate arbitrage"); System.out.println("9. You scratch my back, I don’t scratch yours"); 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. Tip and split calculator (10 Points) */ private static void prob1() { /* * Write a calculator program that equally splits a restaurant bill between a given number of friends after adding a specified tip percentage. You can ignore rounding to the nearest cent since the purpose of the calculator is to give a very good approximation, not to be precisely accurate. But, you must display the amount in a standard dollars and cents format. Your calculator will prompt for the pre-tip total, the tip rate, and the number in the party; it will return the cost per person. For example, for a pre-tip total of $20.31, a tip of 18%, and a party size of 3, the exact answer is $7.9886, but you must display it as either $7.98 or $7.99 depending on how you chose to handle the rounding. * • You must give a meaningful prompt when asking for each piece of information. * • Don’t forget to account for the percentage being an additional number of hundredths. For example, if the user enters 10.5 for the percentage, multiply the input dollar amount by 1.105. */ final double preTipTotal = inputDouble("Pre-tip total ($)? "); final double tipRate = inputDouble("Tip Rate (%)? "); final int numberInParty = inputUnsignedInt("Number in party? "); final double cost = preTipTotal * (1+tipRate/100) / numberInParty; System.out.printf("The cost per person is $%.2f.\n", cost); } /** * Problem 2. Matching numbers (10 Points) */ private static void prob2() { /* * Write a program that allows the user to enter a series of positive integers; the program will report its result and end when 0 or a negative integer is entered. The program will report how many times the user entered the first positive integer. So, the program will report 0 if and only if the first integer entered is 0 or negative. For example, input of 5 8 5 2 5 0 gives output of 3, input of 9 -1 gives output of 1, and input of -7 gives output of 0. */ int count = 0; int currentInt; int firstInt = -1; // invalid do { currentInt = inputInt("Next integer? "); if (count == 0 && currentInt > 0) firstInt = currentInt; if (firstInt > 0 && currentInt == firstInt) ++count; } while(currentInt > 0); System.out.printf("Count of first positive integer is %d.\n", count); } /** * Problem 3. Only one vowel (10 Points) */ private static void prob3() { /* * Write a program that allows the user to enter a word. You may assume the word is entered in lowercase and contains only letters. Indicate whether the word contains 1 unique vowel, even if that vowel is repeated. Vowels are defined as ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’. For example, “cat” and “goto” each contain 1 unique vowel, but “enlarge” does not and neither does “sh”. You output will be either * • “The word contains 1 unique vowel.” or * • “The word does not contain 1 unique vowel.” */ final Character[] vowels = {'a', 'e', 'i', 'o', 'u'}; final String word = inputLine("Input word to test: "); Character vowelSeen = null; boolean duplicatedVowel = false; for(char c: word.toCharArray()) { if (Arrays.asList(vowels).contains(c)) { if (vowelSeen == null) vowelSeen = c; else if (!vowelSeen.equals(c)) { duplicatedVowel = true; break; // for } } } final boolean oneVowel = (vowelSeen != null) && !duplicatedVowel; System.out.println("The word " + (oneVowel?"contains":"does not contain") + " 1 unique vowel."); } /** * Problem 4. Third largest (20 Points) */ private static void prob4() { /* * Write a program that asks the user to enter a sequence of 10 floating point numbers. After the user enters the third through final numbers, display the third largest number from among all those entered so far. Duplicates count as unique places in the order. For example, if the first 5 numbers are -5.3, 3.7, -5.3, 4.8, 3.7, then the first 3 outputs are -5.3, -5.3, and 3.7. */ final float[] largest = {Float.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY, Float.NEGATIVE_INFINITY}; int count = 10; for(Integer i = 1; i<=count; ++i) { float next = inputFloat("Number " + i.toString() + ": "); for (int rp = largest.length-1; rp >= 0; --rp) { if (next > largest[rp]) { for (int lp = 0; lp < rp; ++lp) largest[lp] = largest[lp+1]; largest[rp] = next; break; // for rp } } if (i >= 3) System.out.printf("The 3rd largest so far is %g.\n", largest[0]); } } /** * Problem 5. Arithmetic-geometric mean (20 Points) */ private static void prob5() { /* * Write a program that calculates and displays the arithmetic-geometric mean of two positive, floating point numbers, a_1 and b_1. The arithmetic-geometric mean is the value to which the following series converges as n grows large… * a_(n+1)=(a_n+b_n)/2 * b_(n+1)=√(a_n b_n ) * You should stop and report a_{n+1} as the result as soon as it is within 0.01 of a_n after an iteration. Note that this is an “absolute error,” not a “relative error.” Do not run the iteration further as that computational effort will be considered wasted and will cause your solution to be rejected by the judges. */ double a = inputDouble("a: "), b = inputDouble("b: "); boolean terminate; do { double a_new = (a + b) / 2; b /*_new*/ = Math.sqrt(a * b); terminate = Math.abs(a_new - a) <= 0.01; a = a_new; //b = b_new; } while (!terminate); System.out.printf("The arithmetic-geometric mean is %g.\n", a); } /** * Problem 6. Juggler sequence (20 Points) */ private static void prob6() { /* * Calculate a juggler sequence, which is a series of positive integers, given a positive integer starting value. The next integer is always found by raising the integer to an exponent (resulting in a floating point intermediate result) and then rounding down. The exponent is 0.5 (square root) if the integer is even, otherwise the exponent is 1.5. The series terminates immediately after 1 is reached and reported. * You must use an integer type such as int to hold the values of the series. Using a floating point type such as double, even if you round correctly, will give incorrect results since floating point types have precision greater than 1 for large values and thus cannot represent very large integers accurately. * There is one important error case that your program must handle. In some cases the number will reach or try to exceed the maximum integer value that can be represented (such as Integer.MAX_VALUE in Java or INT_MAX from in C++). When this happens, after reporting all numbers in the sequence up to the value that was too large, you should report “Series went too high.” And end your program. * As a test case, you may want to try starting at 48443, which will result in the value going too high regardless of what intrinsic integer type you use. */ int value = inputUnsignedInt("Starting int? "); while (value > 1) { double nextDouble = (value%2 == 0) ? Math.sqrt(value) : Math.pow(value, 1.5); if (nextDouble > Integer.MAX_VALUE) { System.out.println("Series went too high."); break; // while } value = (int)nextDouble; // truncate System.out.print(Integer.toString(value) + ' '); } } /** * Problem 7. Partition into three triangular numbers (40 Points) */ private static void prob7() { /* * Triangular numbers count the number of objects in a triangle of a given edge length. Any triangular number can be found using T_n=(n(n+1))/2. Note that T0 = 0 is a valid triangular number. * [FIGURE] Figure Source: Wikipedia, CC BY-SA 3.0 Melchoir * It has been proven that any positive integer can be “partitioned” into 3 triangular numbers that yield the original integer when summed; in some cases there are many possible ways to partition a positive integer. * Your program will input a positive integer from the user and express it as a sum of 3 triangular numbers. * Hints: * * There are often many valid partitions and it is only necessary that you be able to find one for any given number. * * There may not exist a valid 3-way partition that includes the largest triangular number less than or equal to the given number, but this is a reasonable place to start your search. * * Triangular numbers may be repeated in the partition. * * 0 is a valid triangular number. * Examples: * * 1 can be partitioned as 1 0 0 or 0 1 0, or 0 0 1. * * 6 can be partitioned as 6 0 0 and 3 3 0, plus their permutations. * * 20 cannot be put into a partition including 15, which is the largest triangular number not larger than 20. But, 10 10 0 is a valid partition of 20. * * 30 can be partitioned numerous ways including 28 1 1, 21 6 3, 15 15 0, and 10 10 10. */ int N = inputUnsignedInt("N to partition: "); boolean solutionFound = false; // The following algorithm iterates from the largest down for the first 2 numbers in the partition and determines success when the residual is triangular. // Correct functioning of the following algorithm relies on the fact that a partition exists. // If a partition did not exist, the inner assertion would fail since we would try to iterate the search below the minimum possible value. // Efficiency note: It would be much more computationally efficient to construct the previous triangular numbers by keeping track of the side length, but that would make the required storage slightly greater or would require lookup/calculation of the triangular numbers during summation (but that's much cheaper). // Note: Inputting 0 and triangular numbers are important test cases. Also, testing a number like 9 that has a maximal partition into exactly 2 non-trivial factors (6+3+0) is an important test case. // Note: "20" is an important test case since that is the lowest number for which a greedy approach fails // Should also try some large numbers. int p[] = new int[3]; // partition under consideration int remainder[] = new int[p.length-1]; for (p[0] = maxTriangularLe(N); !solutionFound; ) { //System.out.printf("Trying p[0] == %d... ", p[0]); // debug remainder[0] = N-p[0]; for (p[1] = maxTriangularLe(remainder[0]); !solutionFound; ) { //System.out.printf("Trying p[1] == %d... ", p[1]); // debug remainder[1] = remainder[0]-p[1]; if (remainder[1]==maxTriangularLe(remainder[1])) { p[2] = remainder[1]; solutionFound = true; break; // for p[1], prevent searching to next p[1] } else { // !solutionFound if (p[1] == 0) break; // tried smallest p[1], so go to next p[0] else p[1] = maxTriangularLe(p[1] - 1); } } if (!solutionFound) // Except for N=0, p[0] should never reach 0 for correct implementation p[0] = maxTriangularLe(p[0]-1); // can't do in for loop since update happens before check } assert solutionFound; // The theory guarantees a solution exists. Also, the implementation ensures this is true on termination. Any implementation errors are likely to be caught by invalid calls to maxTriangularLe() System.out.printf("A valid partition of %d is %d + %d + %d.\n", N, p[0], p[1], p[2]); } private static int maxTriangularLe(int N) { assert N >= 0; int n = (int)(Math.sqrt(2*N+0.25) - 0.5); // intentional truncation, applying quadratic formula, positive branch cut return n * (n+1) / 2; } /** * Problem 8. Exchange rate arbitrage (40 Points) */ private static void prob8() throws FileNotFoundException { /* * Write a program that finds the best “triangular arbitrage” opportunity in currency conversions from and back to US dollars (USD). Read in a table of conversion factors for 8 major currencies. A file with the data below is provided to help you with testing, but the judges will test your program with other files. * AUD CAD CNY EUR GBP HKD JPY USD * AUD 1 0.952153 4.582447 0.634103 0.463361 5.576225 86.331528 0.720900 * CAD 1.065123 1 4.940244 0.680883 0.495708 5.984590 91.643933 0.765404 * CNY 0.218892 0.207801 1 0.140663 0.101551 1.209804 19.139644 0.157307 * EUR 1.546365 1.456471 7.093427 1 0.750966 8.592669 135.297375 1.124500 * GBP 2.125315 2.003891 9.778921 1.377917 1 11.708705 184.226658 1.532600 * HKD 0.178693 0.166534 0.818408 0.116518 0.083673 1 15.725514 0.129032 * JPY 0.011635 0.010769 0.053581 0.007419 0.005480 0.064916 1 0.008336 * USD 1.387155 1.306500 6.357000 0.889284 0.652486 7.750000 119.968000 1 * The rows represent the source currency and the columns represent the destination currency. For example, the value at the lower left shows that 1 USD yields 1.387155 AUD (Australian dollars). * A triangular arbitrage is done by converting USD to currency X, then currency X to currency Y, and finally currency Y back to USD. For example, if X is JPY and Y is EUR, we could do the following: * • Start with 1 USD * • Convert it to 119.968 JPY * • Convert each JPY to 0.007419 EUR, giving 0.890042592 EUR * • Convert each EUR to 1.1245 USD giving 1.000852894704 USD. * If $1,000,000 were converted this way the profit would be $852.89. High speed automated trading algorithms often take advantage of short-lived opportunities such as these. * Your program will * • Read in a tab-and-newline delimited currency conversion matrix that contains just the numbers in the same order as presented above for the 8 currencies (sample file on website). The currencies will not change and will always be presented in the order shown. * • Consider the profit for all combinations of triangular arbitrage starting from USD through 2 other currencies. You will not consider the cases where X=Y and/or X=USD and/or Y=USD and will therefore never use the diagonal elements, which all equal to 1 in the sample matrix. * • Report the maximum arbitrage opportunity as profit on $1,000,000. So, if the example above represents the maximum profit, report, “Converting $1,000,000 to JPY, then to EUR, and finally back to USD yields a profit of $852.89.” * • The maximum profit can be negative. This can happen if the rates have fees embedded. Banks use this to claim that they are not charging currency conversion fees when in fact they adjust their rates to and from foreign currencies to include profit in each direction. */ final String[] currLbl = {"AUD", "CAD", "CNY", "EUR", "GBP", "HKD", "JPY", "USD"}; final int SIZE = currLbl.length; // number of currencies final String filename = inputLine("Filename [e.g., p8a.txt]: "); final double[][] matrix = readDoubleArray(filename, SIZE); final int LOCAL = SIZE-1; // the local currency is the last one, 0-based final double investment = 1e6; double maxProfit = -Double.MAX_VALUE; int xy[] = {-1, -1}; // indexes of arbitrage currencies for max profit, initially invalid for (int xIdx = 0; xIdx < SIZE; ++xIdx) { if (xIdx == LOCAL) continue; for (int yIdx = 0; yIdx < SIZE; ++yIdx) { if (yIdx == LOCAL || yIdx == xIdx) continue; double profit = investment * (matrix[LOCAL][xIdx] * matrix[xIdx][yIdx] * matrix[yIdx][LOCAL] - 1); if (profit > maxProfit) { maxProfit = profit; xy[0] = xIdx; xy[1] = yIdx; System.out.printf("New best opportunity found: %s -> %s -> %s -> %s yields $%.2f on $%.2f investment.\n", currLbl[LOCAL], currLbl[xy[0]], currLbl[xy[1]], currLbl[LOCAL], profit, investment); } } } } /** * Problem 9. You scratch my back, I don’t scratch yours (40 Points) */ private enum BirdType {SUCKER, CHEAT, GRUDGER}; private static BirdType getType(int s, int c, int g, int i) { assert 0 <= i && i < (s+c+g) : "Bird index out of bounds"; return (i < s) ? BirdType.SUCKER : (i < s+c ? BirdType.CHEAT : BirdType.GRUDGER); } private static String genList(double[] list, int begin, int end) { // generate string representation on [begin,end) StringBuilder sb = new StringBuilder(); for(int idx = begin; idx < end; ++idx) { sb.append(list[idx]); sb.append(' '); } return sb.toString(); } private static void prob9() { /* Write a program that simulates a population of birds and their ability to accumulate resources (food, health, etc.) that help them to be successful at reproducing. Unfortunately these birds are plagued by a parasite that attaches to their backs in a hard to reach spot. While a bird has no way on its own to rid itself of a parasite, the birds are resourceful and have learned that they can easily knock parasites off of each other. It does take a bit of work (depleting one’s resources) to do so, however, and some of the birds would rather not bear that cost. There are 3 types of birds. • Suckers: Suckers will help any fellow feathered friend who asks for their assistance in removing a parasite. If all the birds in a population are suckers, everyone is happy since they can always get their parasites removed by the first bird they ask. • Cheats: Cheats never help other birds remove their parasites. A population that consisted of only cheats would suffer since no parasites would ever get removed, but in a population of mostly suckers with a few cheats, the cheats greatly benefit since they pretty much always get their parasites removed on the first try but never expend resources to remove a parasite themselves. • Grudgers: The grudgers have caught on to the cheats. They start off by helping any bird who asks for help, but if they ask for help and are turned down, they never forget who cheated them. If that cheat ever asks the same grudger for help, the grudger turns him down. A population of just grudgers, or a population of suckers and grudgers without any cheats, always has everyone helping everyone else. In a population of just grudgers and cheats, the grudgers soon learn who the cheats are, resulting in the cheats never getting help but the grudgers getting help as long as they are lucky enough to ask another grudger. In your computer model, the user will be asked to input several parameters that will control your simulation: • Non-negative integers */ final int s = inputInt("s = number of suckers, from 0 to 20? "); final int c = inputInt("c = number of cheats, from 0 to 20? "); final int g = inputInt("g = number of grudgers, from 0 to 20? "); /* • Positive, floating point values */ final double i = inputDouble("i = initial resources that each bird has? "); final double r = inputDouble("r = cost to a bird of helping another bird remove its parasite? "); final double p = inputDouble("p = cost to an infected bird of finding a random bird to ask to remove its parasite? "); /* • Positive integers */ final int t = inputInt("t = number of times a bird will ask to have its parasite removed before giving up and accepting an additional resource cost of 100×p? "); final int N = inputInt("N = number of rounds to simulate? "); /* Once the user enters all the parameters, you will first ensure that there are at least 2 birds in the population. If there are fewer than 2 birds, report the problem to the user and quit. */ final int scg = s+c+g; // total number of birds if (scg < 2) { System.out.println("There are fewer than 2 birds, so I'm reporting the problem and quitting per the spec."); return; } /* Then, you will conduct N rounds of simulation, keeping track of the resources that each bird has. You’ll also need to keep track of which birds each grudger is grudging against. Note that resources for some or all birds might become negative. That is okay for this simulation. In each round, you will iterate through all the birds (suckers, then cheats, then grudgers). Each bird will get infected by a parasite and then try up to t times to ask a random other bird to remove the parasite. Be careful that you don’t have a bird try to remove its own parasite since that is not allowed! The random bird is selected “with replacement” meaning that the same other bird may be asked multiple times for help by the same parasitized bird in a single round. Each time the bird asks for help it incurs a cost p and if it finds a bird to help it that bird incurs a cost r. If the bird still has its parasite after t attempts it gives up, lives with the parasite, and incurs an additional cost of 100×p. */ double[] resources = new double[scg]; for(int j = 0; j < scg; ++j) resources[j] = i; // initial resources for each bird boolean grudging[][] = new boolean[g][scg]; // 1st index is who is doing the grudging; 2nd is who is begrudged; default of false is what is intended java.util.Random myGenerator = new java.util.Random(); for(int round = 0; round < N; ++round) { for(int bird = 0; bird < scg; ++bird) { for(int TRY = 0; TRY < t; ++TRY) { int potentialAlly = myGenerator.nextInt(scg - 1); if (potentialAlly >= bird) ++potentialAlly; // select at random, but never self BirdType paType = getType(s,c,g,potentialAlly); resources[bird] -= p; boolean helped = false; switch(paType) { case SUCKER: helped = true; break; case CHEAT: helped = false; break; case GRUDGER: helped = !grudging[potentialAlly-(s+c)][bird]; // base is grudger start break; } if(!helped && getType(s,c,g,bird) == BirdType.GRUDGER) // if the potential ally just picked the wrong bird to mess with... grudging[bird-(s+c)][potentialAlly] = true; if(helped) { resources[potentialAlly] -= r; break; // stop asking for help once you're healed } else if (TRY == t-1) resources[bird] -= 100*p; // live with the parasite for this round despite the immense pain } } } /* After all the rounds are completed, provide the following report to the user, substituting the results from your simulation. • There were 10 suckers and they ended up with average resources of 13.43. The resource values were: • There were 5 cheats and they ended up with average resources of 4.87. The resource values were: • There were 20 grudgers and they ended up with average resources of 13.79. The resource values were: */ double sAve = 0, cAve = 0, gAve = 0; for(int idx = 0 ; idx < s ; ++idx) sAve += resources[idx]; for(int idx = s ; idx < s+c; ++idx) cAve += resources[idx]; for(int idx = s+c; idx < scg; ++idx) gAve += resources[idx]; sAve /= s; cAve /= c; gAve /= g; System.out.printf("There were %d suckers and they ended up with average resources of %g. The resource values were: %s\n", s, sAve, genList(resources, 0 , s )); System.out.printf("There were %d cheats and they ended up with average resources of %g. The resource values were: %s\n", c, cAve, genList(resources, s , s+c)); System.out.printf("There were %d grudgers and they ended up with average resources of %g. The resource values were: %s\n", g, gAve, genList(resources, s+c, scg)); // System.out.println("The final grudging matrix (not required) is:"); dumpBooleanArray(grudging); } private static void dumpBooleanArray(boolean[][] b) { for(int r = 0; r < b.length; ++r) { for(int c = 0; c < b[r].length; ++c) { System.out.print(b[r][c]?'1':'0'); System.out.print(' '); } System.out.println(); } } /**Read a NxN array from a file. * Assumes properly formatted file. * @param fn the name of the file to read from * @param N side length of array in file * @return the NxN array */ private static double[][] readDoubleArray(String fn, int N) throws FileNotFoundException { Scanner sc = null; double[][] result = null; //try { sc = new Scanner(new File(fn)); //} catch (FileNotFoundException e) { // System.out.printf("File not found: [%s].\n", fn); //} assert N >= 0; if (sc != null) { result = new double[N][N]; boolean success = true; for(int row = 0; row < N && success; ++row) { for(int col = 0; col < N; ++col) { if (sc.hasNextDouble()) { result[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 result; } /** * prompt for int, skipping any invalid preamble * @param prompt prompt to display * @return the entered int */ private 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 */ private static int inputUnsignedInt(String prompt) { System.out.print(prompt); int result = -1; while (result < 0) { while (!sc.hasNextInt()) sc.next(); // discard non-int token result = sc.nextInt(); } sc.nextLine(); // dump CR from stream return result; } /** * prompt for a float, skipping any invalid preamble * @param prompt prompt to display * @return the entered float */ private static float inputFloat(String prompt) { System.out.print(prompt); while (!sc.hasNextFloat()) sc.next(); // discard non-matching token float retVal = sc.nextFloat(); 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 */ private 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; } private static String inputLine(String prompt) // Simple prompt for a line of text { System.out.print(prompt); String result; // 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 { result = sc.nextLine(); result = result.trim(); } while (result.length() == 0); return result; } private final static Scanner sc = new Scanner(System.in); }