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