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}