+/EE312
software design
git clone https://git.julia.blue/+/EE312
40fe863
master
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 ) { 15unsigned r ,c ; 16for (r = 0 ;r < MATRIX_SIZE ;r += 1 ) { 17for (c = 0 ;c < MATRIX_SIZE ;c += 1 ) { 18switch (maze [r ][c ] ) { 19case 0 : 20putchar (' ' ); 21break ; 22case 1 : 23putchar ('#' ); 24break ; 25case 2 :// bread crumb 26putchar ('o' ); 27break ; 28default :// error! 29putchar ('@' ); 30break ; 31 } 32 } 33putchar ('\n' ); 34 } 35} 36 37void printCodedMaze (void ) { 38unsigned r ,c ; 39for (r = 0 ;r < MATRIX_SIZE ;r += 1 ) { 40for (c = 0 ;c < MATRIX_SIZE ;c += 1 ) { 41switch (maze [r ][c ]& WALL ) { 42case WALL : 43putchar ('#' ); 44break ; 45case 0 : 46putchar (' ' ); 47break ; 48 } 49 } 50putchar ('\n' ); 51 } 52} 53 54enum Directions { 55UP , 56DOWN , 57LEFT , 58RIGHT 59}; 60 61void interpretDir (int * prow ,int * pcol ,int dir ) { 62switch (dir ) { 63case UP : 64* prow = * prow - 1 ; 65break ; 66case DOWN : 67* prow = * prow + 1 ; 68break ; 69case LEFT : 70* pcol = * pcol - 1 ; 71break ; 72case RIGHT : 73* pcol = * pcol + 1 ; 74break ; 75 } 76} 77 78void clearWall (int row ,int col ,int dir ) { 79int r = row * 2 + 1 ; 80int c = col * 2 + 1 ; 81interpretDir (& r ,& c ,dir ); 82maze [r ][c ] &= ~WALL ; 83} 84 85void markCell (int row ,int col ) { 86int r = row * 2 + 1 ; 87int c = col * 2 + 1 ; 88 89maze [r ][c ] |=MARK ; 90} 91 92int isMarked (int row ,int col ) { 93int r = row * 2 + 1 ; 94int c = col * 2 + 1 ; 95 96return (maze [r ][c ]& MARK ); 97} 98 99 100/* 101* return an integer that uniquely identifies each cell 102*/ 103int cellID (int row ,int col ) { 104int r = row * 2 + 1 ; 105int c = col * 2 + 1 ; 106return 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 ) { 113int r = cell /MATRIX_SIZE ; 114int 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 ) { 124int r = row * 2 + 1 ; 125int c = col * 2 + 1 ; 126 127maze [r ][c ] &= ~MASK ; 128maze [r ][c ] |=annotation ; 129} 130 131int annotation (int row ,int col ) { 132int r = row * 2 + 1 ; 133int c = col * 2 + 1 ; 134 135return maze [r ][c ]& MASK ; 136} 137 138void clearCellMark (int row ,int col ) { 139int r = row * 2 + 1 ; 140int c = col * 2 + 1 ; 141 142maze [r ][c ] &= ~MARK ; 143} 144 145void clearCell (int row ,int col ) { 146int r = row * 2 + 1 ; 147int c = col * 2 + 1 ; 148 149maze [r ][c ]= 0 ; 150} 151 152void makeAllWalls (void ) { 153unsigned r ,c ; 154unsigned row ,col ; 155for (r = 0 ;r < MATRIX_SIZE ;r += 1 ) { 156for (c = 0 ;c < MATRIX_SIZE ;c += 1 ) { 157maze [r ][c ]= WALL ; 158 } 159 } 160for (row = 0 ;row < MAZE_SIZE ;row += 1 ) { 161for (col = 0 ;col < MAZE_SIZE ;col += 1 ) { 162clearCell (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 () { 175int num_visited = 1 ; 176int first ; 177int finish_col ; 178makeAllWalls (); 179markCell (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 */ 182first = cellID (0 ,0 ); 183annotateCell (0 ,0 ,0 ); 184 185while (num_visited < MAZE_SIZE * MAZE_SIZE ) { 186int visit = rand () %num_visited ; 187int cell = first ; 188int row ,col ; 189int d ; 190int nrow ,ncol ; 191 192findCell (cell ,& row ,& col ); 193while (visit > 0 ) { 194cell = annotation (row ,col ); 195findCell (cell ,& row ,& col ); 196visit -= 1 ; 197 } 198d = rand () %4 ; 199nrow = row ;// row of neighbor cell 200ncol = col ;// col of neighbor cell 201interpretDir (& nrow ,& ncol ,d ); 202if (nrow >=0 && nrow < MAZE_SIZE 203&& ncol >=0 && ncol < MAZE_SIZE 204&& !isMarked (nrow ,ncol )) { 205clearWall (row ,col ,d ); 206num_visited += 1 ; 207markCell (nrow ,ncol ); 208annotateCell (nrow ,ncol ,first ); 209first = cellID (nrow ,ncol ); 210 } 211 } 212 213start_col = rand () %MAZE_SIZE ; 214start_col = 2 * start_col + 1 ; 215maze [0 ][start_col ] &= ~WALL ; 216finish_col = rand () %MAZE_SIZE ; 217maze [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 ) { 226int r ,c ; 227for (r = 0 ;r < MATRIX_SIZE ;r += 1 ) { 228for (c = 0 ;c < MATRIX_SIZE ;c += 1 ) { 229maze [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 ) { 383srand (1337 ); 384const 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 }; 388printf("the smallest of the first 10 natural numbers is: %d\n", minIt(a, 10)); 389printf("the smallest of the first 10 natural numbers is: %d\n", minRec1(a, 10)); 390printf("the smallest of the first 10 natural numbers is: %d\n", minRec2(a, 10)); 391a[3] = -1; 392printf("now the smallest is %d\n", minIt(a, 10)); 393printf("now the smallest is %d\n", minRec1(a, 10)); 394printf("now the smallest is %d\n", minRec2(a, 10));*/ 395 396for (int array_size = 1 ;array_size < 20 ;array_size ++ ) { 397for (int iteration = 0 ;iteration < 4 ;iteration ++ ) { 398int test_array [array_size ]; 399// populate the array with random data 400printf ("Array: {" ); 401for (int index = 0 ;index < array_size ;index ++ ) { 402test_array [index ]= rand () %1000 ; 403printf ("%d, " ,test_array [index ]); 404 } 405printf ("\b\b \b\b}\n" ); 406// if all three functions give the same values, the solution is most likely correct 407printf ("Smallest Iter: %d\n" ,minIt (test_array ,array_size )); 408printf ("Smallest Rec1: %d\n" ,minRec1 (test_array ,array_size )); 409printf ("Smallest Rec2: %d\n\n" ,minRec2 (test_array ,array_size )); 410 } 411printf ("------------\n\n" ); 412 413 } 414 415/* test sqrt */ 416/* printf("the sqrt of 5 is %.16g\n", sqrtIt(5.0, 0, 5.0)); 417printf("the sqrt of 0.5 is %.16g\n", sqrtIt(0.5, 0, 26.0)); 418printf("the sqrt of 1 is %.16g\n", sqrtIt(1.0, 0, 2.0)); 419printf("the sqrt of 25 is %.16g\n", sqrtRec(25.0, 4.99, 25.0)); 420printf("the sqrt of 100 is %.16g\n", sqrtRec(100.0, 0, 10.0)); 421printf("the sqrt of 2 is %.16g\n", sqrtRec(2.0, 0, 2.001));*/ 422 423// set correct precision or test won't run 424for (double num = 0 ;num < 1 ;num += 0.05 ) { 425printf ("Num: %-6gSqrt It: %-20.15gSqrt Rec: %-20.15gCorrect Sqrt: %-20.15g\n" , 426num , 427sqrtIt (num , (num /0.97 )- 0.02 , (num /4.0 )+ 0.75 ), 428sqrtRec (num , (num /0.97 )- 0.02 , (num /4.0 )+ 0.75 ), 429sqrt (num )); 430 } 431 432// making num too high gives segmentation fault 433for (double num = 1 ;num < 50 ;num += 1.5 ) { 434printf ("Num: %-6gSqrt It: %-20.15gSqrt Rec: %-20.15gCorrect Sqrt: %-20.15g\n" , 435num , 436sqrtIt (num ,num /7.08 , (num /0.666 )- 0.5 ), 437sqrtRec (num ,num /7.08 , (num /0.666 )- 0.5 ), 438sqrt (num )); 439 } 440 441 442/* test strCompare */ 443char * s1 ; 444char * s2 ; 445s1 = "apple" ; 446s2 = "apricot" ; 447if (strCompare (s1 ,s2 )< 0 ) { 448printf ("\"%s\" is less than \"%s\", very good\n" ,s1 ,s2 ); 449 }else { 450printf ("oops, \"%s\" should be less than \"%s\"\n" ,s1 ,s2 ); 451 } 452 453s1 = "Apple" ; 454s2 = "apple" ; 455if (strCompare (s1 ,s2 )< 0 ) { 456printf ("\"%s\" is less than \"%s\", very good\n" ,s1 ,s2 ); 457 }else { 458printf ("oops, \"%s\" should be less than \"%s\"\n" ,s1 ,s2 ); 459 } 460 461s1 = "baby boy" ; 462s2 = "banana" ; 463if (strCompare (s1 ,s2 )< 0 ) { 464printf ("\"%s\" is less than \"%s\", very good\n" ,s1 ,s2 ); 465 }else { 466printf ("oops, \"%s\" should be less than \"%s\"\n" ,s1 ,s2 ); 467 } 468 469s1 = "a rather silly string" ; 470s2 = "a rather silly string" ; 471if (strCompare (s1 ,s2 )== 0 ) { 472printf ("\"%s\" is equal to \"%s\", very good\n" ,s1 ,s2 ); 473 }else { 474printf ("oops, \"%s\" should be equal to \"%s\"\n" ,s1 ,s2 ); 475 } 476 477s1 = "12345" ; 478s2 = "12345" ; 479if (strCompare (s1 ,s2 )== 0 ) { 480printf ("\"%s\" is equal to \"%s\", very good\n" ,s1 ,s2 ); 481 }else { 482printf ("oops, \"%s\" should be equal to \"%s\"\n" ,s1 ,s2 ); 483 } 484 485s1 = "Numbers: 12345" ; 486s2 = "12345" ; 487if (strCompare (s1 ,s2 )> 0 ) { 488printf ("\"%s\" is greater than \"%s\", very good\n" ,s1 ,s2 ); 489 }else { 490printf ("oops, \"%s\" should be greater than \"%s\"\n" ,s1 ,s2 ); 491 } 492 493s1 = "Texas" ; 494s2 = "California" ; 495if (strCompare (s1 ,s2 )> 0 ) { 496printf ("\"%s\" is greater than \"%s\", very good\n" ,s1 ,s2 ); 497 }else { 498printf ("oops, \"%s\" should be greater than \"%s\"\n" ,s1 ,s2 ); 499 } 500 501/* test strCompare2 */ 502s1 = "apple" ; 503s2 = "Apricot" ; 504if (strCompare2 (s1 ,s2 )< 0 ) { 505printf ("\"%s\" is less than \"%s\", very good\n" ,s1 ,s2 ); 506 }else { 507printf ("oops, \"%s\" should be less than \"%s\"\n" ,s1 ,s2 ); 508 } 509 510s1 = "Batman!" ; 511s2 = "bat man" ; 512if (strCompare2 (s1 ,s2 )== 0 ) { 513printf ("\"%s\" is equal to \"%s\", very good\n" ,s1 ,s2 ); 514 }else { 515printf ("oops, \"%s\" should be equal to \"%s\"\n" ,s1 ,s2 ); 516 } 517 518s1 = "OMG, WTF?" ; 519s2 = "oh my goodness, what the heck?" ; 520if (strCompare2 (s1 ,s2 )> 0 ) { 521printf ("\"%s\" is greater than \"%s\", very good\n" ,s1 ,s2 ); 522 }else { 523printf ("oops, \"%s\" should be greater than \"%s\"\n" ,s1 ,s2 ); 524 } 525 526/* test maze */ 527for (int i = 0 ;i < 20 ;i ++ ) { 528printf ("Maze %d:\n" ,i ); 529srand (magic_number + i ); 530makeMaze (); 531recodeMaze (); 532printMaze (); 533printf ("Recursive solution:\n" ); 534solveMazeRec (0 ,start_col ); 535printMaze (); 536printf ("\n\n---------------------------------\n" ); 537 } 538 539/*printf("iterative solution to the maze\n"); 540srand(magic_number); 541makeMaze(); 542recodeMaze(); 543solveMazeIt(0, start_col); 544printMaze();*/ 545 546 547/* test Martian */ 548/*Martian change1 = change(15); 549printf("change 1 should be 0d, 3n, 0p and is: %dd %dn %dp\n", change1.dodeks, change1.nicks, change1.pennies); 550 551Martian change2 = change(0); 552printf("change 2 should be 0d, 0n, 0p and is: %dd %dn %dp\n", change2.dodeks, change2.nicks, change2.pennies); 553 554Martian change3 = change(17); 555printf("change 3 should be 1d, 1n, 0p and is: %dd %dn %dp\n", change3.dodeks, change3.nicks, change3.pennies); 556 557Martian change4 = change(25); 558printf("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 561Martian test_change ; 562for (int i = 0 ;i < 50 ;i ++ ) { 563test_change = change (i ); 564printf ("Cents: %d\tChange: %dd %dn %dp\n" ,i ,test_change .dodeks , 565test_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); 571printf("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 574for (int nick_val = 0 ;nick_val <=15 ;nick_val ++ ) { 575for (int dodek_val = 0 ;dodek_val <=15 ;dodek_val ++ ) { 576for (int i = 0 ;i < 20 ;i += 4 ) { 577// printf("%d,%d,%d\n", nick_val, dodek_val, i); 578test_change = change (i ,nick_val ,dodek_val ); 579printf ("Cents: %d\tChange: %dd %dn %dp\n" ,i ,test_change .dodeks , 580test_change .nicks ,test_change .pennies ); 581 } 582 } 583 } 584printf ("----------------------------\n" ); 585printf ("Variable Nick and Dodek values: \n" ); 586 587for (int nick_val = 16 ;nick_val <=35 ;nick_val += ((rand () %2 )+ 1 )) { 588for (int dodek_val = 16 ;dodek_val <=35 ;dodek_val += ((rand () %2 )+ 1 )) { 589for (int i = 20 ;i < 30 ;i += ((rand () %2 )+ 1 )) { 590test_change = change (i ,nick_val ,dodek_val ); 591printf ("Cents: %d\tNicks: %d\tDodeks: %d\tChange: %dd %dn %dp\n" ,i ,nick_val , 592dodek_val ,test_change .dodeks ,test_change .nicks ,test_change .pennies ); 593 } 594 } 595 } 596}