001package algs11; 002 003import java.util.Arrays; 004import stdlib.*; 005 006/** 007 * This is a skeleton file for your homework. Edit the sections marked TODO. You 008 * may also edit the function "main" to test your code. 009 * 010 * You must not change the declaration of any method. This will be true of every 011 * skeleton file I give you. 012 * 013 * For example, you will get zero points if you change the line 014 * <pre> 015 * public static double minValue (double[] list) { 016 * </pre> 017 * to something like 018 * <pre> 019 * public static void minValue (double[] list) { 020 * </pre> 021 * or 022 * <pre> 023 * public static double minValue (double[] list, int i) { 024 * </pre> 025 * 026 * Each of the functions below is meant to be SELF CONTAINED. This means that 027 * you should use no other functions or classes. You should not use any HashSets 028 * or ArrayLists, or anything else! In addition, each of your functions should go 029 * through the argument array at most once. The only exception to this 030 * removeDuplicates, which is allowed to call numUnique and then go through the 031 * array once after that. 032 */ 033public class MyFirstHomeworkFor402 { 034 035 /** 036 * minValue returns the minimum value in an array of doubles. You can assume 037 * the array is nonempty and has no duplicates. Your solution must go 038 * through the array exactly once. Your solution must not call any other 039 * functions. Here are some examples (using "==" informally): 040 * 041 * <pre> 042 * -7 == minValue (new double[] { -7 }) 043 * 1 == minValue (new double[] { 1, 7, 8, 11 }) 044 * -7 == minValue (new double[] { 1, -4, -7, 7, 8, 11 }) 045 * -13 == minValue (new double[] { -13, -4, -7, 7, 8, 11 }) 046 * -13 == minValue (new double[] { 1, -4, -7, 7, 8, 11, -13 }) 047 * </pre> 048 */ 049 public static double minValue (double[] list) { 050 return StdRandom.uniform (); //TODO: fix this 051 } 052 053 /** 054 * minPosition returns the position of the minimum value in an array of 055 * doubles. The first position in an array is 0 and the last is the 056 * array.length-1. 057 * 058 * You can assume the array is nonempty and has no duplicates. Your solution 059 * must go through the array exactly once. Your solution must not call any 060 * other functions. Here are some examples (using "==" informally): 061 * 062 * <pre> 063 * 0 == minPosition(new double[] { -7 }) 064 * 2 == minPosition(new double[] { 1, -4, -7, 7, 8, 11 }) 065 * 0 == minPosition(new double[] { -13, -4, -7, 7, 8, 11 }) 066 * 6 == minPosition(new double[] { 1, -4, -7, 7, 8, 11, -9 }) 067 * </pre> 068 */ 069 public static int minPosition (double[] list) { 070 return StdRandom.uniform (100); //TODO: fix this 071 } 072 073 /** 074 * distanceBetweenMinAndMax returns difference between the minPosition and 075 * the maxPosition in an array of doubles. 076 * 077 * You can assume the array is nonempty and has no duplicates. Your solution 078 * must go through the array exactly once. Your solution must not call any 079 * other functions. Here are some examples (using "==" informally): 080 * 081 * <pre> 082 * 0 == distanceBetweenMinAndMax(new double[] { -7 }) // -7,-7 are the min and max 083 * 3 == distanceBetweenMinAndMax(new double[] { 1, -4, -7, 7, 8, 11 }), // -7,11 084 * 5 == distanceBetweenMinAndMax(new double[] { -13, -4, -7, 7, 8, 11 }) // -13,11 085 * 1 == distanceBetweenMinAndMax(new double[] { 1, -4, -7, 7, 8, 11, -9 }) // -9,11 086 * </pre> 087 */ 088 public static int distanceBetweenMinAndMax (double[] list) { 089 return StdRandom.uniform (100); //TODO: fix this 090 } 091 092 /** 093 * allSame returns true if all of the elements in list have the same value. 094 * allSame returns false if any two elements in list have different values. 095 * The array may be empty and it may contain duplicate values. 096 * 097 * Your solution should contain at most one loop. You may not use recursion. 098 * Your solution must not call any other functions. 099 * Here are some examples (using "==" informally): 100 * 101 * <pre> 102 * true == allSame(new double[] { }) 103 * true == allSame(new double[] { 11 }) 104 * true == allSame(new double[] { 11, 11, 11, 11 }) 105 * false == allSame(new double[] { 11, 11, 11, 22 }) 106 * false == allSame(new double[] { 11, 11, 22, 11 }) 107 * true == allSame(new double[] { 22, 22, 22, 22 }) 108 * </pre> 109 */ 110 public static boolean allSame (double[] list) { 111 return StdRandom.bernoulli(); //TODO: fix this 112 } 113 114 /** 115 * numUnique returns the number of unique values in an array of doubles. 116 * The array may be empty and it may contain duplicate values. 117 * Unlike the previous questions, you can assume the array is sorted. 118 * 119 * Your solution should contain at most one loop. You may not use recursion. 120 * Your solution must not call any other functions. 121 * Here are some examples (using "==" informally): 122 * 123 * <pre> 124 * 0 == numUnique(new double[] { }) 125 * 1 == numUnique(new double[] { 11 }) 126 * 1 == numUnique(new double[] { 11, 11, 11, 11 }) 127 * 8 == numUnique(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 }) 128 * 8 == numUnique(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 }) 129 * </pre> 130 */ 131 public static int numUnique (double[] list) { 132 return StdRandom.uniform (100); //TODO: fix this 133 } 134 135 /** 136 * removeDuplicates returns a new array containing the unique values in the 137 * array. There should not be any extra space in the array --- there should 138 * be exactly one space for each unique element (Hint: numUnique tells you 139 * how big the array should be). You may assume that the list is sorted, as 140 * you did for numUnique. 141 * 142 * Your solution may call numUnique, but should not call any other 143 * functions. After the call to numUnique, you must go through the array 144 * exactly one more time. Here are some examples (using "==" informally): 145 * 146 * <pre> 147 * new double[] { } 148 * == removeDuplicates(new double[] { }) 149 * new double[] { 11 } 150 * == removeDuplicates(new double[] { 11 }) 151 * == removeDuplicates(new double[] { 11, 11, 11, 11 }) 152 * new double[] { 11, 22, 33, 44, 55, 66, 77, 88 } 153 * == removeDuplicates(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 }) 154 * == removeDuplicates(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 }) 155 * </pre> 156 */ 157 public static double[] removeDuplicates (double[] list) { 158 return null; // TODO: fix this 159 } 160 161 /** 162 * A test program, using private helper functions. See below. 163 * To make typing tests a little easier, I've written a function to convert strings to arrays. See below. 164 */ 165 public static void main (String[] args) { 166 // for minValue: array must be nonempty with unique elements 167 testMinValue (11, "11"); 168 testMinValue (-11, "-11"); 169 testMinValue (9, "9 11 21 31 41"); 170 testMinValue (9, "11 9 21 31 41"); 171 testMinValue (9, "11 21 9 31 41"); 172 testMinValue (9, "11 21 31 9 41"); 173 testMinValue (9, "11 21 31 41 9"); 174 testMinValue (-99, "-99 -11 -21 -31 -41"); 175 testMinValue (-99, "-11 -99 -21 -31 -41"); 176 testMinValue (-99, "-11 -21 -99 -31 -41"); 177 testMinValue (-99, "-11 -21 -31 -99 -41"); 178 testMinValue (-99, "-11 -21 -31 -41 -99"); 179 testMinValue (-7, "1 -4 -7 7 8 11 9 -5"); 180 testMinValue (-0.5, "0.2 -0.5 -0.1"); 181 182 // for minPosition: array must be nonempty with unique elements 183 testMinPosition (0, "11"); 184 testMinPosition (0, "-11"); 185 testMinPosition (0, "9 11 21 31 41"); 186 testMinPosition (1, "11 9 21 31 41"); 187 testMinPosition (2, "11 21 9 31 41"); 188 testMinPosition (3, "11 21 31 9 41"); 189 testMinPosition (4, "11 21 31 41 9"); 190 testMinPosition (0, "-99 -11 -21 -31 -41"); 191 testMinPosition (1, "-11 -99 -21 -31 -41"); 192 testMinPosition (2, "-11 -21 -99 -31 -41"); 193 testMinPosition (3, "-11 -21 -31 -99 -41"); 194 testMinPosition (4, "-11 -21 -31 -41 -99"); 195 testMinPosition (2, "1 -4 -7 7 8 11 9 -5"); 196 testMinPosition (1, "0.2 -0.5 -0.1"); 197 198 // for distanceBetweenMinAndMax: array must be nonempty with unique elements 199 testDistanceBetweenMinAndMax (0, "11"); 200 testDistanceBetweenMinAndMax (0, "-11"); 201 testDistanceBetweenMinAndMax (4, "9 11 21 31 41"); 202 testDistanceBetweenMinAndMax (3, "11 9 21 31 41"); 203 testDistanceBetweenMinAndMax (2, "11 21 9 31 41"); 204 testDistanceBetweenMinAndMax (1, "11 21 31 9 41"); 205 testDistanceBetweenMinAndMax (1, "11 21 31 41 9"); 206 testDistanceBetweenMinAndMax (4, "9 -11 -21 -31 -41"); 207 testDistanceBetweenMinAndMax (3, "-11 9 -21 -31 -41"); 208 testDistanceBetweenMinAndMax (2, "-11 -21 9 -31 -41"); 209 testDistanceBetweenMinAndMax (1, "-11 -21 -31 9 -41"); 210 testDistanceBetweenMinAndMax (1, "-11 -21 -31 -41 9"); 211 testDistanceBetweenMinAndMax (3, "1 -4 -7 7 8 11 9 -5"); 212 testDistanceBetweenMinAndMax (3, "0.1 -0.4 -0.7 0.7 0.8 1.1 0.9 -0.5"); 213 214 // for numUnique: array must be sorted 215 testNumUnique (0, ""); 216 testNumUnique (1, "11"); 217 testNumUnique (1, "11 11 11 11"); 218 testNumUnique (4, "11 21 31 41"); 219 testNumUnique (4, "11 11 11 21 31 31 31 31 41"); 220 testNumUnique (4, "11 21 21 21 31 41 41 41 41"); 221 testNumUnique (4, "11 11 21 21 21 31 31 41 41 41 41"); 222 testNumUnique (8, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81"); 223 testNumUnique (8, "11 21 31 41 41 41 41 41 51 51 61 71 81"); 224 testNumUnique (7, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71"); 225 testNumUnique (7, "11 21 31 41 41 41 41 41 51 51 61 71"); 226 testNumUnique (8, "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11"); 227 228 // for removeDuplicates: array must be sorted 229 testRemoveDuplicates ("", ""); 230 testRemoveDuplicates ("11", "11"); 231 testRemoveDuplicates ("11", "11 11 11 11"); 232 testRemoveDuplicates ("11 21 31 41", "11 21 31 41"); 233 testRemoveDuplicates ("11 21 31 41", "11 11 11 21 31 31 31 31 41"); 234 testRemoveDuplicates ("11 21 31 41", "11 21 21 21 31 41 41 41 41"); 235 testRemoveDuplicates ("11 21 31 41", "11 11 21 21 21 31 31 41 41 41 41"); 236 testRemoveDuplicates ("11 21 31 41 51 61 71 81", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81"); 237 testRemoveDuplicates ("11 21 31 41 51 61 71 81", "11 21 31 41 41 41 41 41 51 51 61 71 81"); 238 testRemoveDuplicates ("11 21 31 41 51 61 71", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71"); 239 testRemoveDuplicates ("11 21 31 41 51 61 71", "11 21 31 41 41 41 41 41 51 51 61 71"); 240 testRemoveDuplicates ("-81 -71 -61 -51 -41 -31 -21 -11", "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11"); 241 StdOut.println ("Finished tests"); 242 } 243 244 /* Test functions --- lot's of similar code! */ 245 private static void testMinValue (double expected, String list) { 246 double[] aList = doublesFromString (list); 247 double actual = minValue (aList); 248 if (! Arrays.equals (aList, doublesFromString (list))) { 249 StdOut.format ("Failed minValue([%s]): Array modified\n", list); 250 } 251 if (expected != actual) { 252 StdOut.format ("Failed minValue([%s]): Expecting (%.1f) Actual (%.1f)\n", list, expected, actual); 253 } 254 } 255 private static void testMinPosition (int expected, String list) { 256 double[] aList = doublesFromString (list); 257 int actual = minPosition (aList); 258 if (! Arrays.equals (aList, doublesFromString (list))) { 259 StdOut.format ("Failed minPosition([%s]): Array modified\n", list); 260 } 261 if (expected != actual) { 262 StdOut.format ("Failed minPosition([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual); 263 } 264 } 265 private static void testDistanceBetweenMinAndMax (int expected, String list) { 266 double[] aList = doublesFromString (list); 267 int actual = distanceBetweenMinAndMax (aList); 268 if (! Arrays.equals (aList, doublesFromString (list))) { 269 StdOut.format ("Failed distanceBetweenMinAndMax([%s]): Array modified\n", list); 270 } 271 if (expected != actual) { 272 StdOut.format ("Failed distanceBetweenMinAndMax([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual); 273 } 274 } 275 private static void testNumUnique (int expected, String list) { 276 double[] aList = doublesFromString (list); 277 int actual = numUnique (aList); 278 if (! Arrays.equals (aList, doublesFromString (list))) { 279 StdOut.format ("Failed numUnique([%s]): Array modified\n", list); 280 } 281 if (expected != actual) { 282 StdOut.format ("Failed numUnique([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual); 283 } 284 } 285 private static void testRemoveDuplicates (String expected, String list) { 286 double[] aList = doublesFromString (list); 287 double[] actual = removeDuplicates (aList); 288 if (! Arrays.equals (aList, doublesFromString (list))) { 289 StdOut.format ("Failed removeDuplicates([%s]): Array modified\n", list); 290 } 291 double[] aExpected = doublesFromString (expected); 292 // != does not do what we want on arrays 293 if (! Arrays.equals (aExpected, actual)) { 294 StdOut.format ("Failed removeDuplicates([%s]): Expecting (%s) Actual (%s)\n", list, Arrays.toString (aExpected), Arrays.toString (actual)); 295 } 296 } 297 298 299 /* A utility function to create an array of doubles from a string. */ 300 // The string should include a list of numbers, separated by single spaces. 301 private static double[] doublesFromString (String s) { 302 if ("".equals (s)) return new double [0]; // empty array is a special case 303 String[] nums = s.split (" "); 304 double[] result = new double[nums.length]; 305 for (int i = nums.length-1; i >= 0; i--) { 306 try { 307 result[i] = Double.parseDouble (nums[i]); 308 } catch (NumberFormatException e) { 309 throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i])); 310 } 311 } 312 return result; 313 } 314}