+/EE312

software design

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

Joseph RyanMore exaustive test cases40fe863

master
18.5 KiB596 linesraw
1#include <stdio.h>
2#include <stdlib.h>
3#include "MazeParams.h"
4#include "Recursion.h"
5#include <math.h>
6
7
8int maze[MATRIX_SIZE][MATRIX_SIZE];
9#define WALL (1 << 30)
10#define MARK (1 << 29)
11#define MASK (((-1) ^ WALL) ^ MARK)
12int start_col; // the starting column for the maze;
13
14void printMaze(void) {
15    unsigned r, c;
16    for (r = 0; r < MATRIX_SIZE; r += 1) {
17        for (c = 0; c < MATRIX_SIZE; c += 1) {
18            switch (maze[r][c] ) {
19            case 0:
20                putchar(' ');
21                break;
22            case 1:
23                putchar('#');
24                break;
25            case 2: // bread crumb
26                putchar('o');
27                break;
28            default: // error!
29                putchar('@');
30                break;
31            }
32        }
33        putchar('\n');
34    }
35}
36
37void printCodedMaze(void) {
38    unsigned r, c;
39    for (r = 0; r < MATRIX_SIZE; r += 1) {
40        for (c = 0; c < MATRIX_SIZE; c += 1) {
41            switch(maze[r][c] & WALL) {
42            case WALL:
43                putchar('#');
44                break;
45            case 0:
46                putchar(' ');
47                break;
48            }
49        }
50        putchar('\n');
51    }
52}
53
54enum Directions {
55    UP,
56    DOWN,
57    LEFT,
58    RIGHT
59};
60
61void interpretDir(int* prow, int* pcol, int dir) {
62    switch (dir) {
63    case UP:
64        *prow = *prow - 1;
65        break;
66    case DOWN:
67        *prow = *prow + 1;
68        break;
69    case LEFT:
70        *pcol = *pcol - 1;
71        break;
72    case RIGHT:
73        *pcol = *pcol + 1;
74        break;
75    }
76}
77
78void clearWall(int row, int col, int dir) {
79    int r = row * 2 + 1;
80    int c = col * 2 + 1;
81    interpretDir(&r, &c, dir);
82    maze[r][c] &= ~WALL;
83}
84
85void markCell(int row, int col) {
86    int r = row * 2 + 1;
87    int c = col * 2 + 1;
88
89    maze[r][c] |= MARK;
90}
91
92int isMarked(int row, int col) {
93    int r = row * 2 + 1;
94    int c = col * 2 + 1;
95
96    return (maze[r][c] & MARK);
97}
98
99
100/*
101 * return an integer that uniquely identifies each cell
102 */
103int cellID(int row, int col) {
104    int r = row * 2 + 1;
105    int c = col * 2 + 1;
106    return r * MATRIX_SIZE + c;
107}
108
109/*
110 * reverse the cellID to compute the row and col numbers
111 */
112void findCell(int cell, int* prow, int* pcol) {
113    int r = cell / MATRIX_SIZE;
114    int c = cell % MATRIX_SIZE;
115    *prow = r / 2;
116    *pcol = c / 2;
117}
118
119/*
120 * store some annotation information in a cell
121 * (the annotation must be an int less than 25 bits (i.e., smaller than 32 million)
122 */
123void annotateCell(int row, int col, int annotation) {
124    int r = row * 2 + 1;
125    int c = col * 2 + 1;
126
127    maze[r][c] &= ~MASK;
128    maze[r][c] |= annotation;
129}
130
131int annotation(int row, int col) {
132    int r = row * 2 + 1;
133    int c = col * 2 + 1;
134
135    return maze[r][c] & MASK;
136}
137
138void clearCellMark(int row, int col) {
139    int r = row * 2 + 1;
140    int c = col * 2 + 1;
141
142    maze[r][c] &= ~MARK;
143}
144
145void clearCell(int row, int col) {
146    int r = row * 2 + 1;
147    int c = col * 2 + 1;
148
149    maze[r][c] = 0;
150}
151
152void makeAllWalls(void) {
153    unsigned r, c;
154    unsigned row, col;
155    for (r = 0; r < MATRIX_SIZE; r += 1) {
156        for (c = 0; c < MATRIX_SIZE; c += 1) {
157            maze[r][c] = WALL;
158        }
159    }
160    for (row = 0; row < MAZE_SIZE; row += 1) {
161        for (col = 0; col < MAZE_SIZE; col += 1) {
162            clearCell(row, col);
163        }
164    }
165}
166
167/*
168 * this function makes a random maze with exactly one path between
169 * any two points in the maze
170 *
171 * If you're curious about the algorithm, come talk to me.  It's not very
172 * complicated (although the code might be confusing)
173 */
174void makeMaze() {
175    int num_visited = 1;
176    int first;
177    int finish_col;
178    makeAllWalls();
179    markCell(0, 0);  // mark the first cell as visited
180
181    /* add the first cell (row 0, col 0) to the linked list of visited cells */
182    first = cellID(0, 0);
183    annotateCell(0, 0, 0);
184
185    while(num_visited < MAZE_SIZE * MAZE_SIZE) {
186        int visit = rand() % num_visited;
187        int cell = first;
188        int row, col;
189        int d;
190        int nrow, ncol;
191
192        findCell(cell, &row, &col);
193        while (visit > 0) {
194            cell = annotation(row, col);
195            findCell(cell, &row, &col);
196            visit -= 1;
197        }
198        d = rand() % 4;
199        nrow = row; // row of neighbor cell
200        ncol = col; // col of neighbor cell
201        interpretDir(&nrow, &ncol, d);
202        if (nrow >= 0 && nrow < MAZE_SIZE
203                && ncol >= 0 && ncol < MAZE_SIZE
204                && !isMarked(nrow, ncol)) {
205            clearWall(row, col, d);
206            num_visited += 1;
207            markCell(nrow, ncol);
208            annotateCell(nrow, ncol, first);
209            first = cellID(nrow, ncol);
210        }
211    }
212
213    start_col = rand() % MAZE_SIZE;
214    start_col = 2 * start_col + 1;
215    maze[0][start_col] &= ~WALL;
216    finish_col = rand() % MAZE_SIZE;
217    maze[MATRIX_SIZE - 1][2 * finish_col + 1] &= ~WALL;
218}
219
220
221/*
222 * recode the maze so that all walls are exactly 1 and all
223 * other cells are exactly zero
224 */
225void recodeMaze(void) {
226    int r, c;
227    for (r = 0; r < MATRIX_SIZE; r += 1) {
228        for (c = 0; c < MATRIX_SIZE; c += 1) {
229            maze[r][c] = ((maze[r][c] & WALL) == WALL);
230        }
231    }
232}
233
234//
235// int main(void) {
236//     const int magic_number = 115530;
237//
238//     [> test min <]
239//     // int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
240//     int a[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
241//     printf("the smallest of the first 10 natural numbers is: %d\n", minIt(a, 10));
242//     printf("the smallest of the first 10 natural numbers is: %d\n", minRec1(a, 10));
243//     printf("the smallest of the first 10 natural numbers is: %d\n", minRec2(a, 10));
244//     a[3] = -1;
245//     printf("now the smallest is %d\n", minIt(a, 10));
246//     printf("now the smallest is %d\n", minRec1(a, 10));
247//     printf("now the smallest is %d\n", minRec2(a, 10));
248//
249//     [> test sqrt <]
250//     printf("the sqrt of 25 is %g\n", sqrtIt(25.0, 0, 25.0));
251//     printf("the sqrt of 26 is %g\n", sqrtIt(26.0, 0, 26.0));
252//     printf("the sqrt of 2 is %g\n", sqrtIt(2.0, 0, 2.0));
253//     printf("the sqrt of 25 is %g\n", sqrtRec(25.0, 0, 25.0));
254//     printf("the sqrt of 26 is %g\n", sqrtRec(26.0, 0, 26.0));
255//     printf("the sqrt of 2 is %g\n", sqrtRec(2.0, 0, 2.0));
256//
257//     [> test strCompare <]
258//     char* s1;
259//     char* s2;
260//     s1 = "apple";
261//     s2 = "apricot";
262//     if (strCompare(s1, s2) < 0) {
263//         printf("\"%s\" is less than \"%s\", very good\n", s1, s2);
264//     } else {
265//         printf("oops, \"%s\" should be less than \"%s\"\n", s1, s2);
266//     }
267//
268//     s1 = "Apple";
269//     s2 = "apple";
270//     if (strCompare(s1, s2) < 0) {
271//         printf("\"%s\" is less than \"%s\", very good\n", s1, s2);
272//     } else {
273//         printf("oops, \"%s\" should be less than \"%s\"\n", s1, s2);
274//     }
275//
276//     s1 = "baby boy";
277//     s2 = "banana";
278//     if (strCompare(s1, s2) < 0) {
279//         printf("\"%s\" is less than \"%s\", very good\n", s1, s2);
280//     } else {
281//         printf("oops, \"%s\" should be less than \"%s\"\n", s1, s2);
282//     }
283//
284//     s1 = "a rather silly string";
285//     s2 = "a rather silly string";
286//     if (strCompare(s1, s2) == 0) {
287//         printf("\"%s\" is equal to \"%s\", very good\n", s1, s2);
288//     } else {
289//         printf("oops, \"%s\" should be equal to \"%s\"\n", s1, s2);
290//     }
291//
292//     s1 = "12345";
293//     s2 = "12345";
294//     if (strCompare(s1, s2) == 0) {
295//         printf("\"%s\" is equal to \"%s\", very good\n", s1, s2);
296//     } else {
297//         printf("oops, \"%s\" should be equal to \"%s\"\n", s1, s2);
298//     }
299//
300//     s1 = "Numbers: 12345";
301//     s2 = "12345";
302//     if (strCompare(s1, s2) > 0) {
303//         printf("\"%s\" is greater than \"%s\", very good\n", s1, s2);
304//     } else {
305//         printf("oops, \"%s\" should be greater than \"%s\"\n", s1, s2);
306//     }
307//
308//     s1 = "Texas";
309//     s2 = "California";
310//     if (strCompare(s1, s2) > 0) {
311//         printf("\"%s\" is greater than \"%s\", very good\n", s1, s2);
312//     } else {
313//         printf("oops, \"%s\" should be greater than \"%s\"\n", s1, s2);
314//     }
315//
316//     [> test strCompare2 <]
317//     s1 = "apple";
318//     s2 = "Apricot";
319//     if (strCompare2(s1, s2) < 0) {
320//         printf("\"%s\" is less than \"%s\", very good\n", s1, s2);
321//     } else {
322//         printf("oops, \"%s\" should be less than \"%s\"\n", s1, s2);
323//     }
324//
325//     s1 = "Batman!";
326//     s2 = "bat man";
327//     if (strCompare2(s1, s2) == 0) {
328//         printf("\"%s\" is equal to \"%s\", very good\n", s1, s2);
329//     } else {
330//         printf("oops, \"%s\" should be equal to \"%s\"\n", s1, s2);
331//     }
332//
333//     s1 = "OMG, WTF?";
334//     s2 = "oh my goodness, what the heck?";
335//     if (strCompare2(s1, s2) > 0) {
336//         printf("\"%s\" is greater than \"%s\", very good\n", s1, s2);
337//     } else {
338//         printf("oops, \"%s\" should be greater than \"%s\"\n", s1, s2);
339//     }
340//
341//     [> test maze <]
342//     srand(magic_number);
343//     makeMaze();
344//     recodeMaze();
345//     printf("recursive solution to the maze\n");
346//     solveMazeRec(0, start_col);
347//     printMaze();
348//     printf("\n\n\n");
349//
350//     printf("iterative solution to the maze\n");
351//     srand(magic_number);
352//     makeMaze();
353//     recodeMaze();
354//     solveMazeIt(0, start_col);
355//     printMaze();
356//
357//
358//     [> test Martian <]
359//     Martian change1 = changeIt(15);
360//     printf("changeIt 1 should be 0d, 3n, 0p and is: %dd %dn %dp\n", change1.dodeks,
361//            change1.nicks, change1.pennies);
362//
363//     Martian change2 = changeIt(0);
364//     printf("changeIt 2 should be 0d, 0n, 0p and is: %dd %dn %dp\n", change2.dodeks,
365//            change2.nicks, change2.pennies);
366//
367//     Martian change3 = changeIt(17);
368//     printf("changeIt 3 should be 1d, 1n, 0p and is: %dd %dn %dp\n", change3.dodeks,
369//            change3.nicks, change3.pennies);
370//
371//     Martian change4 = changeIt(25);
372//     printf("changeIt 4 should be 2d, 0n, 1p and is: %dd %dn %dp\n", change4.dodeks,
373//            change4.nicks, change4.pennies);
374//
375/* A very simple and obvious test of the general form of Martian
376 * be sure and test your solution more thoroughly!!!! */
377//     change4 = changeIt(25, 5, 12);
378//     printf("changeIt 4 should be 2d, 0n, 1p and is: %dd %dn %dp\n", change4.dodeks,
379//            change4.nicks, change4.pennies);
380// }
381
382int main(void) {
383    srand(1337);
384    const int magic_number = 13017;  //<-- change value for a different set of mazes
385
386    /* test min */
387    /*int a[] = { -100, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
388    printf("the smallest of the first 10 natural numbers is: %d\n", minIt(a, 10));
389    printf("the smallest of the first 10 natural numbers is: %d\n", minRec1(a, 10));
390    printf("the smallest of the first 10 natural numbers is: %d\n", minRec2(a, 10));
391    a[3] = -1;
392    printf("now the smallest is %d\n", minIt(a, 10));
393    printf("now the smallest is %d\n", minRec1(a, 10));
394    printf("now the smallest is %d\n", minRec2(a, 10));*/
395
396    for(int array_size  = 1; array_size < 20; array_size++) {
397        for(int iteration = 0; iteration < 4; iteration++) {
398            int test_array[array_size];
399            // populate the array with random data
400            printf("Array: {");
401            for(int index = 0; index < array_size; index++) {
402                test_array[index] = rand() % 1000;
403                printf("%d, ", test_array[index]);
404            }
405            printf("\b\b  \b\b}\n");
406            // if all three functions give the same values, the solution is most likely correct
407            printf("Smallest Iter: %d\n", minIt(test_array, array_size));
408            printf("Smallest Rec1: %d\n", minRec1(test_array, array_size));
409            printf("Smallest Rec2: %d\n\n", minRec2(test_array, array_size));
410        }
411        printf("------------\n\n");
412
413    }
414
415    /* test sqrt */
416    /* printf("the sqrt of 5 is %.16g\n", sqrtIt(5.0, 0, 5.0));
417    printf("the sqrt of 0.5 is %.16g\n", sqrtIt(0.5, 0, 26.0));
418    printf("the sqrt of 1 is %.16g\n", sqrtIt(1.0, 0, 2.0));
419    printf("the sqrt of 25 is %.16g\n", sqrtRec(25.0, 4.99, 25.0));
420    printf("the sqrt of 100 is %.16g\n", sqrtRec(100.0, 0, 10.0));
421    printf("the sqrt of 2 is %.16g\n", sqrtRec(2.0, 0, 2.001));*/
422
423    // set correct precision or test won't run
424    for(double num = 0; num < 1; num += 0.05) {
425        printf("Num: %-6gSqrt It: %-20.15gSqrt Rec: %-20.15gCorrect Sqrt: %-20.15g\n",
426               num,
427               sqrtIt(num, (num / 0.97) - 0.02, (num / 4.0) + 0.75),
428               sqrtRec(num, (num / 0.97) - 0.02, (num / 4.0) + 0.75),
429               sqrt(num));
430    }
431
432    // making num too high gives segmentation fault
433    for(double num = 1; num < 50; num += 1.5) {
434        printf("Num: %-6gSqrt It: %-20.15gSqrt Rec: %-20.15gCorrect Sqrt: %-20.15g\n",
435               num,
436               sqrtIt(num, num / 7.08, (num / 0.666) - 0.5),
437               sqrtRec(num, num / 7.08, (num / 0.666) - 0.5),
438               sqrt(num));
439    }
440
441
442    /* test strCompare */
443    char* s1;
444    char* s2;
445    s1 = "apple";
446    s2 = "apricot";
447    if (strCompare(s1, s2) < 0) {
448        printf("\"%s\" is less than \"%s\", very good\n", s1, s2);
449    } else {
450        printf("oops, \"%s\" should be less than \"%s\"\n", s1, s2);
451    }
452
453    s1 = "Apple";
454    s2 = "apple";
455    if (strCompare(s1, s2) < 0) {
456        printf("\"%s\" is less than \"%s\", very good\n", s1, s2);
457    } else {
458        printf("oops, \"%s\" should be less than \"%s\"\n", s1, s2);
459    }
460
461    s1 = "baby boy";
462    s2 = "banana";
463    if (strCompare(s1, s2) < 0) {
464        printf("\"%s\" is less than \"%s\", very good\n", s1, s2);
465    } else {
466        printf("oops, \"%s\" should be less than \"%s\"\n", s1, s2);
467    }
468
469    s1 = "a rather silly string";
470    s2 = "a rather silly string";
471    if (strCompare(s1, s2) == 0) {
472        printf("\"%s\" is equal to \"%s\", very good\n", s1, s2);
473    } else {
474        printf("oops, \"%s\" should be equal to \"%s\"\n", s1, s2);
475    }
476
477    s1 = "12345";
478    s2 = "12345";
479    if (strCompare(s1, s2) == 0) {
480        printf("\"%s\" is equal to \"%s\", very good\n", s1, s2);
481    } else {
482        printf("oops, \"%s\" should be equal to \"%s\"\n", s1, s2);
483    }
484
485    s1 = "Numbers: 12345";
486    s2 = "12345";
487    if (strCompare(s1, s2) > 0) {
488        printf("\"%s\" is greater than \"%s\", very good\n", s1, s2);
489    } else {
490        printf("oops, \"%s\" should be greater than \"%s\"\n", s1, s2);
491    }
492
493    s1 = "Texas";
494    s2 = "California";
495    if (strCompare(s1, s2) > 0) {
496        printf("\"%s\" is greater than \"%s\", very good\n", s1, s2);
497    } else {
498        printf("oops, \"%s\" should be greater than \"%s\"\n", s1, s2);
499    }
500
501    /* test strCompare2 */
502    s1 = "apple";
503    s2 = "Apricot";
504    if (strCompare2(s1, s2) < 0) {
505        printf("\"%s\" is less than \"%s\", very good\n", s1, s2);
506    } else {
507        printf("oops, \"%s\" should be less than \"%s\"\n", s1, s2);
508    }
509
510    s1 = "Batman!";
511    s2 = "bat man";
512    if (strCompare2(s1, s2) == 0) {
513        printf("\"%s\" is equal to \"%s\", very good\n", s1, s2);
514    } else {
515        printf("oops, \"%s\" should be equal to \"%s\"\n", s1, s2);
516    }
517
518    s1 = "OMG, WTF?";
519    s2 = "oh my goodness, what the heck?";
520    if (strCompare2(s1, s2) > 0) {
521        printf("\"%s\" is greater than \"%s\", very good\n", s1, s2);
522    } else {
523        printf("oops, \"%s\" should be greater than \"%s\"\n", s1, s2);
524    }
525
526    /* test maze */
527    for(int i = 0; i < 20; i++) {
528        printf("Maze %d:\n", i);
529        srand(magic_number + i);
530        makeMaze();
531        recodeMaze();
532        printMaze();
533        printf("Recursive solution:\n");
534        solveMazeRec(0, start_col);
535        printMaze();
536        printf("\n\n---------------------------------\n");
537    }
538
539    /*printf("iterative solution to the maze\n");
540    srand(magic_number);
541    makeMaze();
542    recodeMaze();
543    solveMazeIt(0, start_col);
544    printMaze();*/
545
546
547    /* test Martian */
548    /*Martian change1 = change(15);
549    printf("change 1 should be 0d, 3n, 0p and is: %dd %dn %dp\n", change1.dodeks, change1.nicks, change1.pennies);
550
551    Martian change2 = change(0);
552    printf("change 2 should be 0d, 0n, 0p and is: %dd %dn %dp\n", change2.dodeks, change2.nicks, change2.pennies);
553
554    Martian change3 = change(17);
555    printf("change 3 should be 1d, 1n, 0p and is: %dd %dn %dp\n", change3.dodeks, change3.nicks, change3.pennies);
556
557    Martian change4 = change(25);
558    printf("change 4 should be 2d, 0n, 1p and is: %dd %dn %dp\n", change4.dodeks, change4.nicks, change4.pennies);*/
559
560    // don't make test too exhaustive or it will become slow
561    Martian test_change;
562    for(int i = 0; i < 50; i++) {
563        test_change = change(i);
564        printf("Cents: %d\tChange: %dd %dn %dp\n", i, test_change.dodeks,
565               test_change.nicks, test_change.pennies);
566    }
567
568    /* A very simple and obvious test of the general form of Martian
569     * be sure and test your solution more thoroughly!!!!*/
570    /*change4 = change(25, 5, 12);
571    printf("change 4 should be 2d, 0n, 1p and is: %dd %dn %dp\n", change4.dodeks, change4.nicks, change4.pennies);*/
572
573    // don't make test too exhaustive or it will become very slow
574    for(int nick_val = 0; nick_val <= 15; nick_val++) {
575        for(int dodek_val = 0; dodek_val <= 15; dodek_val++) {
576            for(int i = 0; i < 20; i += 4) {
577                // printf("%d,%d,%d\n", nick_val, dodek_val, i);
578                test_change = change(i, nick_val, dodek_val);
579                printf("Cents: %d\tChange: %dd %dn %dp\n", i, test_change.dodeks,
580                       test_change.nicks, test_change.pennies);
581            }
582        }
583    }
584    printf("----------------------------\n");
585    printf("Variable Nick and Dodek values: \n");
586
587    for(int nick_val = 16; nick_val <= 35; nick_val += ((rand() % 2) + 1)) {
588        for(int dodek_val = 16; dodek_val <= 35; dodek_val += ((rand() % 2) + 1)) {
589            for(int i = 20; i < 30; i += ((rand() % 2) + 1)) {
590                test_change = change(i, nick_val, dodek_val);
591                printf("Cents: %d\tNicks: %d\tDodeks: %d\tChange: %dd %dn %dp\n", i, nick_val,
592                       dodek_val, test_change.dodeks, test_change.nicks, test_change.pennies);
593            }
594        }
595    }
596}