+/EE312

software design

git clone https://git.julia.blue/+/EE312

Joseph RyanFix sqrt(0)1c126f3

master
17.3 KiB535 linesraw
1/*
2 * Project6.c
3 * Recursion
4 * Fall 2017
5 * Joseph Ryan
6 * jbr2558
7 */
8
9
10#include <stdio.h>
11#include <stdint.h>
12#include <limits.h>
13#include <float.h>
14#include "MazeParams.h"
15#include "Recursion.h"
16
17#define MIN(X,Y) (X<Y?X:Y)
18
19/* return the smallest of the elements in array x[]
20 * there are n elements in x[] (x[0].. x[n-1])
21 */
22int minIt(int x[], int n) {
23    int min = INT_MAX;
24    for(int i = 0; i < n; ++i) {
25        min = MIN(x[i], min);
26    }
27    return min;
28}
29
30/* return the smallest of the elements in array x[]
31 * there are n elements in x[] (x[0].. x[n-1])
32 * solve the problem recursively and
33 * use an "n-1" type of decomposition
34 */
35int minRec1(int x[], int n) {
36    if(n == 0) {
37        return x[0];
38    }
39    return MIN(x[n - 1], minRec1(x, n - 1));
40}
41
42/*
43 * return the smallest of the elements in array x[]
44 * there are n elements in x[] (x[0].. x[n-1])
45 * n may be either odd or even
46 * solve the problem recursively and
47 * use an "n / 2" type of decomposition
48 */
49int minRec2(int x[], int n) {
50    if(n <= 1) {
51        return x[0];
52    }
53    int half = n / 2;
54    int first = minRec2(x, half);
55    int last = minRec2(x + half, half + n % 2);
56    return MIN(first, last);
57}
58
59
60/*
61 * calculate and return the square root of x.
62 * The other two parameters are estimates of the square root.
63 * low_guess is smaller than the actual square root, and high_guess
64 * is larger than the actual square root.
65 * Searching for the square root can be done much like searching
66 * for a name in a phone book.
67 *
68 * Since you can't calculate a square root exactly, for this problem
69 * you're required to calculate the answer to 15 decimal digits of
70 * accuracy.
71 */
72double sqrtIt(double x, double low_guess, double high_guess) {
73    double half = 1;
74    while(high_guess - low_guess > 1e-15) {
75        half = (low_guess + high_guess) / 2;
76        if(half * half > x) {
77            high_guess = half;
78        } else {
79            low_guess = half;
80        }
81    }
82    return half;
83}
84
85/*
86 * calculate and return the square root of x.
87 * The other two parameters are estimates of the square root.
88 * low_guess is smaller than the actual square root, and high_guess
89 * is larger than the actual square root.
90 * Searching for the square root can be done much like searching
91 * for a name in a phone book.
92 *
93 * Since you can't calculate a square root exactly, for this problem
94 * you're required to calculate the answer to 15 decimal digits of
95 * accuracy.
96 */
97double sqrtRec(double x, double low_guess, double high_guess) {
98    if(high_guess < 0){
99        return 0;
100    }
101    double half = (low_guess + high_guess) / 2;
102    if(high_guess - low_guess > 1e-15) {
103        if(half * half > x) {
104            high_guess = half;
105        } else {
106            low_guess = half;
107        }
108        return sqrtRec(x, low_guess, high_guess);
109    }
110    return half;
111}
112
113
114/*
115 * using only recursion, write a string comparison function
116 * return -1 if str1 is less than str2
117 * return 0 if the two strings are equal
118 * return +1 if str1 is greater than str2
119 * when comparing strings, use the ASCII value to compare each character
120 * (i.e., that means 'A' is less than 'a' since it's ASCII value is smaller)
121 * The string str1 is less than str2 if either
122 * str1[0] < str2[0]
123 * or there exists a k such that str1[k] < str2[k] and
124 *   for all j < k str1[j] == str2[j]
125 *   and k is less than the length of str1 and str2
126 */
127
128int strCompare(char* str1, char* str2) {
129    char a = str1[0], b = str2[0];
130    if(!a && !b) {
131        return 0;
132    }
133    if(!b || a > b) {
134        return 1;
135    }
136    if(!a || b > a) {
137        return -1;
138    }
139    return strCompare(++str1, ++str2);
140}
141
142/*
143 * if c is not a letter return -1
144 * if c is a letter, return the position of c in the alphabet
145 * where 'A' (and 'a') are position 1 and 'Z' (and 'z') are position 26
146 *
147 * This code is rather ugly as I'm exploiting some detailed knowledge of the ASCII table
148 */
149int whatLetter(char c) {
150    if (c < 'A') {
151        return -1;
152    }
153    if (c > 'z') {
154        return -1;
155    }
156    if (c > 'Z' && c < 'a') {
157        return -1;
158    }
159    return c & ~32 - 64;
160}
161
162/*
163 * same as before, only this time
164 * ignore anything that is not a letter
165 * ignore the case (upper case, lower case)
166 * So, strCompare2("Hello", "hello") should return 0 (they're the same)
167 * strCompare2("The plane!", "theater") should return 1 since "theplane" is larger than "theater"
168 * once again, you can only use recursion, no loops
169 */
170int strCompare2(char* str1, char* str2) {
171    char a = whatLetter(*str1), b = whatLetter(*str2);
172    if(!*str1 && !*str2) {
173        return 0;
174    }
175    if(a == -1) {
176        return strCompare2(++str1, str2);
177    }
178    if(b == -1) {
179        return strCompare2(str1, ++str2);
180    }
181    if(a > b) {
182        return 1;
183    }
184    if(b > a) {
185        return -1;
186    }
187    return strCompare2(++str1, ++str2);
188}
189
190
191
192/*
193 * the two dimensional array maze[MATRIX_SIZE][MATRIX_SIZE] contains a maze
194 * Each square is (initially) either a 1 or a zero.  Each 1 represents a wall
195 * (you cannot walk through walls, so you can't go into any square where the
196 * value is 1).  Each 0 represents an open space.
197 *
198 * Write an recursive solution to find your way out of the maze
199 * Your starting point is at row and col. (params to this function)
200 * Your exit point is somewhere in the last row (which is: MATRIX_SIZE - 1)
201 *
202 * There is a relatively easy recursive solution to this problem, the trick is
203 * to think of the solution in the following terms:
204 *   "In which direction(s) can I go and find a way out of this maze?"
205 * In some cases, you may find yourself in a spot in the maze that there's
206 * no way out (at least, not without backtracking). In that case, you'd return "false"
207 * since the maze has no solution. In most cases, there's one or more ways out
208 * from where you are now. Your key question is simply, "what is the first step I need to take"
209 *
210 * If you considered going "north", and you had a function that could tell you whether
211 * it was possible to get out of the maze starting at the square to the north of your
212 * current position, then you could use this function to determine if you can get out by
213 * going north first. Similarly, you could consider going south, east or west, and (recursively)
214 * determine if the maze can be solved from any of those locations.
215 *
216 * With that hint, the base case should be pretty obvious.  In fact,
217 * I'd suggest you consider the possibility that the base case is "Yup, I'm already at
218 * the exit!"
219 *
220 * There is one tricky part to this decomposition.  You need to make certain
221 * that the problem is getting smaller.  The "bigness" or "smallness" of this
222 * problem is the number of squares that have not yet been tested.  Each time
223 * you test an adjacent square (making a recursive call to decide if there is a
224 * path to the exit through that square), you'll be reducing  the number of squares
225 * that have not yet been tested.  Eventually, you must have tested all the
226 * squares and so you'll have to have found a way to the exit.
227 *
228 * The easy way to deal with the tricky part is to leave "bread crumbs" behind.
229 * Before you recursively check any (or all) of your neighbors to see if you
230 * can find the exit from there -- drop a bread crumb in your current square.
231 * Then, don't ever check to see if you can find the exit using a square
232 * with a breadcrumb in it (backtracking into that square would be silly).
233 *
234 * If you're trying to see if you can find an exit from some square, and all
235 * the adjacent squares are either walls, or have bread crumbs in them, then
236 * you already know the answer -- "you can't get to the exit from here".
237 * Pick up your bread crumb and return false.
238 *
239 * You can set the value of the current square to "2" to indicate that a bread
240 * crumb has been dropped.  Set the square back to 0 when you want to pick
241 * the bread crumb back up.
242 * be sure not to change any of the squares that are 1 (the walls).
243 *
244 * for partial credit, you can leave all your bread crumbs on the floor.
245 * for full credit, you must pick up all the bread crumbs EXCEPT those
246 * along a path to the exit.
247 */
248
249int solveMazeRec(int row, int col) {
250    if(row >= MATRIX_SIZE || row < 0 || col >= MATRIX_SIZE || col < 0) {
251        return 0;
252    }
253    if(maze[row][col]) {
254        return 0;
255    }
256    maze[row][col] = 2;
257    if(row == MATRIX_SIZE - 1) {
258        return 1;
259    }
260    if(solveMazeRec(row + 1, col) || solveMazeRec(row, col + 1)
261            || solveMazeRec(row - 1, col) || solveMazeRec(row, col - 1)) {
262        return 1;
263    }
264    maze[row][col] = 0;
265    return 0;
266}
267
268
269/**********************
270 * adjacentCell and isOK are functions provided to help you write
271 * solveMazeIt()
272 */
273
274/*
275 * OK, we're currently at maze[row][col] and we're considering moving
276 * in direction dir.
277 * Set trow and tcol (local variables inside the calling function)
278 * to the row and column that we would move to IF we moved in
279 * that direction
280 *
281 * For example, there are two good ways to use this function.
282 * 1. to actually move one step in a direction use:
283 *       adjacentCell(row, col, dir, &row, &col);
284 *    That will set row and col to new values.  The new values will
285 *    be one square away from the old values.
286 *
287 * 2. to set trow and tcol to a square that is adjacent to row and col use:
288 *       adjacentCell(row, col, dir, &trow, &tcol);
289 *    That will not change row and col, but will change trow and tcol.
290 *    This is useful if you aren't sure if you can actually move in this
291 *    direction yet (e.g., maze[trow][tcol] may be a wall!).  So, you set
292 *    trow and tcol, and then check to see if it's OK to move there
293 */
294void adjacentCell(int row, int col, int dir, int* trow, int* tcol) {
295    *trow = row;
296    *tcol = col;
297    switch(dir) {
298    case 0: // UP
299        *trow = *trow - 1;
300        break;
301    case 1: // RIGHT
302        *tcol = *tcol + 1;
303        break;
304    case 2: // DOWN
305        *trow = *trow + 1;
306        break;
307    case 3: // LEFT
308        *tcol = *tcol - 1;
309        break;
310    }
311}
312
313
314/*
315 * return false if there is a wall in the square for row and col
316 * return true if it's not a wall.
317 */
318int isOK(int row, int col) {
319    return (row > 0 && row < MATRIX_SIZE
320            && col > 0 && col < MATRIX_SIZE
321            && maze[row][col] != 1);
322}
323
324/*
325 * return the value of the direction that is one turn to the right
326 */
327int turnRight(int dir) {
328    return (dir + 1) % 4;
329}
330
331/*
332 * return the value of the direction that is one turn to the left
333 */
334int turnLeft(int dir) {
335    return (dir + 3) % 4;
336}
337
338/*
339 * the two dimensional array maze[MATRIX_SIZE][MATRIX_SIZE] contains a maze
340 * Each square is (initially) either a 1 or a zero.  Each 1 represents a wall
341 * (you cannot walk through walls, so you can't go into any square where the value
342 * is 1).  Each 0 represents an open space.
343 *
344 * write an iterative solution to find your way out of the maze
345 * Your starting point is at row and col. (params to this function)
346 * Your exit point is somewhere in the last row (which is: MATRIX_SIZE - 1)
347 * The maze can be solved by following the right hand wall.  In fact, there
348 * is exactly one path between any two points in the maze (well, between any two
349 * points that are not walls).
350 *
351 * The algorithm is not too bad, although it is certainly not trivial
352 * Initially, you'll be headed DOWN (direction 2)
353 * Each iteration do one of the following.  Note that only one of two cases
354 * can possibly apply (the properties of the maze guarantee that).
355 *    case 1: you can move in the current direction
356 *       In this case, you should take one step in the current direction
357 *       and then turn right.
358 *    case 2: you cannot move in the current direction
359 *       If there's a wall directly in front of you, then to follow the right
360 *       hand wall, you'd need to turn left (placing your hand on the wall that
361 *       used to be directly in front of you).  So, if you discover this case
362 *       then turn left.  Don't move, just turn left.
363 * If you were walking down a straight corridor (with walls on both sides)
364 * then you'd alternate case 1 and case 2.  On the first iteration, you'd
365 * take a step, and then turn right (case 1).  This causes you to walk
366 * one position down the hallway but then turn to face the wall.
367 * On the next iteration, you'll be facing the wall, so you can't walk
368 * forward and therefore (case 2) you'll turn left.  On the third iteration
369 * you'll be able to walk down the hallway again.
370 *
371 * If you follow those two cases, then you'll eventually find your way out
372 * of the maze.  To confirm that you're making it out, leave a "bread crumb"
373 * behind each square along the path to the exit.
374 * For partial credit, place a bread crumb in every square you visit.
375 * For full credit, pick up all the breadcrumbs when you backtrack.
376 * Backtracking is when you go back to a square you've already been before.
377 * If the square you're about to step into has a breadcrumb, then pick up
378 * the bread crumb in the square you're at now.
379 * You indicate "bread crumbs" by setting the square equal to "2"
380 */
381void solveMazeIt(int row, int col) {
382    int dir = 2; // 0 is up, 1 is right, 2 is down, 3 is left.
383    int trow, tcol;
384    maze[row][col] = 2; // drop a bread crumb in the starting square
385    while (row < MATRIX_SIZE - 1) {
386        maze[row][col] = 2;
387        adjacentCell(row, col, dir, &trow, &tcol);
388        if(isOK(trow, tcol)) {
389            if(maze[trow][tcol] == 2) {
390                maze[row][col] = 0;
391            }
392            adjacentCell(row, col, dir, &row, &col);
393            dir = turnRight(dir);
394        } else {
395            dir = turnLeft(dir);
396        }
397    }
398}
399
400int countCoins(Martian m) {
401    return m.pennies + m.nicks + m.dodeks;
402}
403
404Martian minMartian(Martian a, Martian b) {
405    if(countCoins(a) > countCoins(b)) {
406        return b;
407    }
408    return a;
409}
410
411/*
412 * using recursion, with no loops or globals, write a function that calculates the optimal
413 * (fewest total coins) change for a given amount of money. Return a Martian struct that indicates
414 * this optimal collection of coins.
415 */
416Martian change(int cents) {
417    return change(cents, 5, 12);
418}
419
420/*
421 * Same as before, except the more general version where the coins have values
422 * a cents and b cents, with a and b being algebraic. For the original problem,
423 * a is the constant 5 (nick_value = 5 cents) and b is the constant 12
424 * (dodek_value = 12 cents).
425 * If you've really mastered thinking recursively, then this version of the
426 * martian change problem is just as easy as the concrete version
427 */
428Martian change(int cents, int nick_val, int dodek_val) {
429    if(!cents) {
430        struct Martian m;
431        m.pennies = 0;
432        m.nicks = 0;
433        m.dodeks = 0;
434        return m;
435    }
436    struct Martian temp;
437    struct Martian m;
438    temp.dodeks = INT_MAX;
439    temp.nicks = INT_MAX;
440    temp.pennies = INT_MAX;
441    m.dodeks = INT_MAX;
442    m.nicks = INT_MAX;
443    m.pennies = INT_MAX;
444    if(cents >= dodek_val && dodek_val) {
445        m = change(cents - dodek_val, nick_val, dodek_val);
446        ++m.dodeks;
447    }
448    temp = minMartian(m, temp);
449    if(cents >= nick_val && nick_val) {
450        m = change(cents - nick_val, nick_val, dodek_val);
451        ++m.nicks;
452    }
453    temp = minMartian(m, temp);
454    if(cents >= 1) {
455        m = change(cents - 1, nick_val, dodek_val);
456        ++m.pennies;
457    }
458    return minMartian(m, temp);
459}
460
461/*
462 * without using recursion, solve the Martian change problem described above.
463 * it's not too bad for the specific case of nick_value = 5 and dodek_value = 12
464 */
465Martian changeIt(int cents) {
466    return changeIt(cents, 5, 12);
467}
468
469int ternaryInc(int arr[]) {
470    int i = 0;
471    while(arr[i] == 2) {
472        ++i;
473    }
474    int num = i;
475    ++arr[i];
476    while(i > 0) {
477        arr[--i] = 0;
478    }
479    return num + 1;
480}
481
482/*
483 * However, I don't have a solution for the general case. In fact, I consider
484 * the general problem to "challenging" (i.e, an exercise in futility).
485 * But, if you like banging your head against the wall for zero credit
486 * this is the problem for you!
487 */
488Martian changeIt(int cents, int nick_value, int dodek_value) {
489    int num = 1;
490    int arr[10];
491    for(int i = 0; i < 10; ++i) {
492        arr[i] = 0;
493    }
494    while(cents) {
495        // for(int i = 0; i < num; ++i) {
496        //     printf("%d ", arr[i]);
497        // }
498        // printf("\n");
499        int temp = ternaryInc(arr);
500        num = temp > num ? temp : num;
501        int sum = 0;
502        for(int j = 0; j < num; ++j) {
503            if(arr[j] == 0) {
504                ++sum;
505            } else if(arr[j] == 1) {
506                sum += nick_value;
507            } else if(arr[j] == 2) {
508                sum += dodek_value;
509            }
510        }
511
512        if(sum == cents) {
513            break;
514        }
515        if(num == 9) {
516            break;
517        }
518    }
519    Martian m;
520    m.pennies = 0;
521    m.nicks = 0;
522    m.dodeks = 0;
523    for(int i = 0; i < num; ++i) {
524        if(arr[i] == 0) {
525            ++m.pennies;
526        }
527        if(arr[i] == 1) {
528            ++m.nicks;
529        }
530        if(arr[i] == 2) {
531            ++m.dodeks;
532        }
533    }
534    return m;
535}