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 * 015 * <pre> 016 * public static double minValue (double[] list) { 017 * </pre> 018 * 019 * to something like 020 * 021 * <pre> 022 * public static void minValue (double[] list) { 023 * </pre> 024 * 025 * or 026 * 027 * <pre> 028 * public static double minValue (double[] list, int i) { 029 * </pre> 030 * 031 * Each of the functions below is meant to be SELF CONTAINED. This means that 032 * you should use no other functions or classes. You should not use any HashSets 033 * or ArrayLists, or anything else! In addition, each of your functions should 034 * go through the argument array at most once. The only exception to this 035 * removeDuplicates, which is allowed to call numUnique and then go through the 036 * array once after that. 037 */ 038public class MyFirstHomeworkFor300PartTwo { 039 040 /** 041 * allSame returns true if all of the elements in list have the same value. 042 * allSame returns false if any two elements in list have different values. The 043 * array may be empty and it may contain duplicate values. 044 * 045 * Your solution should contain at most one loop. You may not use recursion. 046 * Your solution must not call any other functions. Here are some examples 047 * (using "==" informally): 048 * 049 * <pre> 050 * true == allSame(new double[] { }) 051 * true == allSame(new double[] { 11 }) 052 * true == allSame(new double[] { 11, 11, 11, 11 }) 053 * false == allSame(new double[] { 11, 11, 11, 22 }) 054 * false == allSame(new double[] { 11, 11, 22, 11 }) 055 * true == allSame(new double[] { 22, 22, 22, 22 }) 056 * </pre> 057 */ 058 public static boolean allSame(double[] list) { 059 return StdRandom.bernoulli(); //TODO: fix this 060 } 061 062 /** 063 * numUnique returns the number of unique values in a sorted array of doubles. 064 * The array may be empty and it may contain duplicate values. Assume that the 065 * list array is sorted. 066 * 067 * Your solution should contain at most one loop. You may not use recursion. 068 * Your solution must not call any other functions. Here are some examples 069 * (using "==" informally): 070 * 071 * <pre> 072 * 0 == numUnique(new double[] { }) 073 * 1 == numUnique(new double[] { 11 }) 074 * 1 == numUnique(new double[] { 11, 11, 11, 11 }) 075 * 8 == numUnique(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 }) 076 * 8 == numUnique(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 }) 077 * </pre> 078 */ 079 public static int numUnique(double[] list) { 080 return StdRandom.uniform (100); //TODO: fix this 081 } 082 083 /** 084 * removeDuplicates returns a new array containing the unique values in the 085 * sorted argument array, in the same order that they were found in the original 086 * array. There should not be any extra space in the array --- there should be 087 * exactly one space for each unique element (Hint: numUnique tells you how big 088 * the array should be). 089 * 090 * Assume that the list array is sorted, as you did for numUnique. 091 * 092 * Your solution should contain at most one loop. You may not use recursion. 093 * Your solution must not call any other functions, except numUnique. Here are 094 * some examples (using "==" informally): 095 * 096 * <pre> 097 * new double[] { } 098 * == removeDuplicates(new double[] { }) 099 * new double[] { 11 } 100 * == removeDuplicates(new double[] { 11 }) 101 * == removeDuplicates(new double[] { 11, 11, 11, 11 }) 102 * new double[] { 11, 22, 33, 44, 55, 66, 77, 88 } 103 * == removeDuplicates(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 }) 104 * == removeDuplicates(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 }) 105 * </pre> 106 */ 107 public static double[] removeDuplicates(double[] list) { 108 int resultLength = numUnique(list); 109 double[] result = new double[resultLength]; 110 // TODO: fix this 111 return result; 112 } 113 114 /* 115 * A main function for debugging -- change the name to "main" to run it (and 116 * rename the existing main method to something else). Change the test as 117 * appropriate. 118 */ 119 public static void main2(String[] args) { 120 Trace.drawStepsOfMethod("removeDuplicates"); 121 Trace.run(); 122 testRemoveDuplicates("11 21 31 41", "11 21 31 41"); 123 testRemoveDuplicates("11 21", "11 11 21"); 124 } 125 126 /** 127 * A test program, using private helper functions. See below. To make typing 128 * tests a little easier, I've written a function to convert strings to arrays. 129 * See below. 130 */ 131 public static void main(String[] args) { 132 testAllSame(true, "11 11 11 11"); 133 testAllSame(true, "5 5 5"); 134 testAllSame(false, "11 5 11 11"); 135 testAllSame(false, "11 11 5 11"); 136 testAllSame(false, "11 11 11 5"); 137 testAllSame(false, "5 11 11 11"); 138 testAllSame(false, "11 5 5 11 11"); 139 testAllSame(false, "11 11 5 5 11"); 140 testAllSame(false, "11 11 5 11 5"); 141 testAllSame(false, "5 5 11 11 11"); 142 testAllSame(false, "11 11 11 5 5"); 143 testAllSame(true, "11"); 144 testAllSame(true, "2"); 145 testAllSame(true, ""); 146 147 // for numUnique: array must be sorted 148 testNumUnique(4, "11 21 21 21 31 41 41 41 41"); 149 testNumUnique(1, "11 11 11 11"); 150 testNumUnique(4, "11 21 31 41"); 151 testNumUnique(4, "11 11 11 21 31 31 31 31 41"); 152 testNumUnique(4, "11 11 21 21 21 31 31 41 41 41 41"); 153 testNumUnique(8, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81"); 154 testNumUnique(8, "11 21 31 41 41 41 41 41 51 51 61 71 81"); 155 testNumUnique(7, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71"); 156 testNumUnique(7, "11 21 31 41 41 41 41 41 51 51 61 71"); 157 testNumUnique(8, "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11"); 158 testNumUnique(3, "-11 -11 -11 0 0 11 11 11"); 159 testNumUnique(2, "0 11 11 11"); 160 testNumUnique(2, "-Infinity 11 11 11"); 161 testNumUnique(2, "11 11 11 Infinity"); 162 testNumUnique(1, "11 11"); 163 testNumUnique(1, "11"); 164 testNumUnique(0, ""); 165 166 // for removeDuplicates: array must be sorted 167 testRemoveDuplicates("11", "11 11 11 11"); 168 testRemoveDuplicates("11 21", "11 11 21"); 169 testRemoveDuplicates("11 21 31 41", "11 21 31 41"); 170 testRemoveDuplicates("11 21 31 41", "11 11 11 21 31 31 31 31 41"); 171 testRemoveDuplicates("11 21 31 41", "11 21 21 21 31 41 41 41 41"); 172 testRemoveDuplicates("11 21 31 41", "11 11 21 21 21 31 31 41 41 41 41"); 173 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"); 174 testRemoveDuplicates("11 21 31 41 51 61 71 81", "11 21 31 41 41 41 41 41 51 51 61 71 81"); 175 testRemoveDuplicates("11 21 31 41 51 61 71", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71"); 176 testRemoveDuplicates("11 21 31 41 51 61 71", "11 21 31 41 41 41 41 41 51 51 61 71"); 177 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"); 178 testRemoveDuplicates("-11 0 11", "-11 -11 -11 0 0 11 11 11"); 179 testRemoveDuplicates("0 11", "0 11 11 11"); 180 testRemoveDuplicates("-Infinity 11", "-Infinity 11 11 11"); 181 testRemoveDuplicates("Infinity 11", "Infinity 11 11 11"); 182 testRemoveDuplicates("11", "11 11"); 183 testRemoveDuplicates("11", "11"); 184 testRemoveDuplicates("", ""); 185 StdOut.println("Finished tests"); 186 } 187 188 private static void testAllSame(boolean expected, String list) { 189 double[] aList = doublesFromString(list); 190 boolean actual = allSame(aList); 191 if (!Arrays.equals(aList, doublesFromString(list))) { 192 StdOut.format("Failed allSame([%s]): Array modified\n", list); 193 } 194 if (expected != actual) { 195 StdOut.format("Failed allSame([%s]): Expecting (%b) Actual (%b)\n", list, expected, actual); 196 } 197 } 198 199 private static void testNumUnique(int expected, String list) { 200 double[] aList = doublesFromString(list); 201 int actual = numUnique(aList); 202 if (!Arrays.equals(aList, doublesFromString(list))) { 203 StdOut.format("Failed numUnique([%s]): Array modified\n", list); 204 } 205 if (expected != actual) { 206 StdOut.format("Failed numUnique([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual); 207 } 208 } 209 210 private static void testRemoveDuplicates(String expected, String list) { 211 double[] aList = doublesFromString(list); 212 double[] actual = removeDuplicates(aList); 213 if (!Arrays.equals(aList, doublesFromString(list))) { 214 StdOut.format("Failed removeDuplicates([%s]): Array modified\n", list); 215 } 216 double[] aExpected = doublesFromString(expected); 217 // != does not do what we want on arrays 218 if (!Arrays.equals(aExpected, actual)) { 219 StdOut.format("Failed removeDuplicates([%s]): Expecting (%s) Actual (%s)\n", list, 220 Arrays.toString(aExpected), Arrays.toString(actual)); 221 } 222 } 223 224 /* A utility function to create an array of doubles from a string. */ 225 // The string should include a list of numbers, separated by single spaces. 226 private static double[] doublesFromString(String s) { 227 if ("".equals(s)) 228 return new double[0]; // empty array is a special case 229 String[] nums = s.split(" "); 230 double[] result = new double[nums.length]; 231 for (int i = nums.length - 1; i >= 0; i--) { 232 try { 233 result[i] = Double.parseDouble(nums[i]); 234 } catch (NumberFormatException e) { 235 throw new IllegalArgumentException( 236 String.format("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i])); 237 } 238 } 239 return result; 240 } 241}