More Recursion in C

Due 11:55pm on Wednesday, February 12, 2020.

Exercise 1: Solving a Maze in C

This exercise involves solving a maze, i.e., finding a path from start to finish without going through walls. This lab is an exercise in recursion as well as 2-D matrices whose maximum size is known.

You will implement a simple recursive method for solving a maze, a java version of which is available here (adapted from here, see under "Recursive algorithm"). We will modify/adapt it for a C implementation. A starter file for your C program is available (ex1.c). Instead of calling the method generateMaze(), the C program reads in the maze from the standard input. Our main() function reads in the maze, initializes the three matrices maze, wasHere and correctPath, then calls recursiveSolve(), and finally prints the maze with the path identified.

Assume the width and height of the maze are provided at run time, but the size of the maze will not exceed 100x100, so storage for the 2-D maze is provided by a fixed-size 100x100 array. At runtime, however, only part of the array is actually used, for a total of height * width entries.

The maze itself will be read from standard input. First its width and height will be present in the input (in that order), followed by the maze, one row at a time. A '*' character represents a wall, and the space character ' ' represents open space through which one can move (i.e., a corridor). One point in the maze will have an 'S' to indicate "start", and one point will have an 'F' to indicate "finish".

Your task is to use the recursive algorithm to find the path, and indicate the path on the maze using the '.' character, and print the maze with the path on the standard output.

For example, for the following 10-column X 5-row maze as the input:

10
5
****S  ***
*   ** ***
***    **F
*** ***** 
***       

The expected output is:

****S..***
*   **.***
***....**F
***.*****.
***.......

You can assume that the maze is solvable, i.e., a path exists from start to finish. Also, assume that if multiple paths exist, you only need to display the one path found by the algorithm implemented by java program linked to above (it stops after finding one path).

Use the template provided (ex1.c). Complete the code, compile and run on inputs of your choice, and also make sure it runs correctly on the sample inputs provided.

Here are some explanations and useful tips:

• Typically, a 2-D matrix is thought of as having the row as its first index, and column as the second one: matrix[row][col]. This is called row-major order, i.e., the information is stored one entire row at a time, and within each row, successive columns appear adjacent in memory. Since the x-coordinate corresponds to columns, and the y-coordinate corresponds to rows, the correct way to access the elements of the maze is maze[y][x].
• There is no built-in Boolean type in C. There is Boolean emulation available if you include <stdbool.h>. It basically defines the "bool" type (ultimately as an unsigned integer), and "true" as 1 and "false" as 0. Or, as the template does, you could skip <stdbool.h>, and simply declare Boolean variables as "int", and define "true" to be 1 and "false" to be 0 (see the definitions near the top). Everything else works the same as for Booleans.
• You can read the width and height from the first two lines of the input using scanf("%d%d", ...). However, note that scanf() will leave the newline after second number in the input stream. So, a subsequent call to any C input function to read the actual maze will read this newline character first. You can either be sure to ignore this newline character, or use the scanf() call to explicitly eat the newline after reading the height, as done in the template.
• There are multiple ways for reading in the maze.
  • The recommended way is to read an entire row at a time using fgets(tempString, width+2, stdin). The +2 is needed to read the newline at the end of each row, plus one space for the string terminator; while these last two values will not be entered into the maze, they still need to be read and then discarded. Accordingly, tempString itself must have been declared to be of size MAX+2 characters. After reading an entire row, you can iterate through it column-by-column (by varying x), and assigning the values into the corresponding maze row.
  • An alternative method is to read in the maze one character at a time, using getchar() or scanf("%c", ...). However, we do not recommend these methods at this time because they are not compatible with the assembly programming environment we will be studying shortly. You will be asked to re-do this exercise in assembly language so, to preserve compatibility, please follow the fgets() approach.

  The template provided uses the preferred fgets() approach.

Exercise 2: Matrix Multiplication

Write a program to multiple two MxM matrices. If the two input matrices are A[M][M] and B[M][M], and the result of multiplication is C[M][M], the elements of C are given by:

(Optional) For more discussion on matrix multiplication, you may refer to these articles on Wikipedia or Math is fun.

The first line of the input will be the value of M, which will be within the range 1 to 10. This is followed by M*M integers, one per line, for the values of the matrix A. Then another M*M integers for the values of matrix B. These values are in row-major order, i.e., first the M values of the elements of row 0, then M more values for row 1, and so on. All numbers are in base ten.

The output will be the matrix C, with each element printed within a width of 6 characters, i.e., printed using printf("%6d",...);

Use the template provided in the file ex2.c. Compile and run your program on inputs of your choice, and also make sure it runs correctly on the sample inputs provided.

Exercise 3: There was an old lady ...

In this exercise, you are to write a recursive implementation of a function nurseryrhyme() that takes a sequence of words and spins them into a story, as follows.

If the input to the function nurseryrhyme() is this sequence of strings, one per line:

cat
Imagine that! She swallowed a cat!
bird
How absurd to swallow a bird!
spider
That wriggled and jiggled and tickled inside her!
fly
Perhaps she'll die!
END

Then it prints the following output:

There was an old lady who swallowed a cat;
 She swallowed the cat to catch the bird;
  She swallowed the bird to catch the spider;
   She swallowed the spider to catch the fly;
   I don't know why she swallowed a fly - Perhaps she'll die!
  I don't know why she swallowed a spider - That wriggled and jiggled and tickled inside her!
 I don't know why she swallowed a bird - How absurd to swallow a bird!
I don't know why she swallowed a cat - Imagine that! She swallowed a cat!

Here are some notes and tips:

• As you read the name of each animal, using fgets(), it will come with a newline at the end, e.g., "cat\n", etc. It will be highly convenient to strip the newline as soon as the animal's name has been read. To do so, simply determine the length of the name using strlen(), and then replace the newline with a null character.
• The indentation level is different for each line. Each extra indent is exactly one space character. Tip: You can print n spaces without using a loop by simply using a '*' for the width parameter in the format string for printf() as follows:

  printf("%*s", n, "");

  What this does is it tells printf() to print the empty string "" using a width given by the integer before it, that is n.
• The last line of the input is "END". You can use the strcmp() function to determine when the end has been reached by comparing the string read with "END\n" (note the newline!).
• The number of animals (e.g., cat, bird, etc.) in the input will be determined at runtime, not to exceed 20. The name of each animal will not exceed 15 characters including the NULL terminator. Associated with each animal is a lyric (e.g., "Imagine that! She swallowed a cat!"), which will not exceed 60 characters in length include NULL. You will write a main() procedure that will read these strings from the input, put them into arrays and then call nurseryrhyme(). Use the code template provided in ex3.c.
• My own implementation was 41 lines of code, including blank lines, the same length as the template.

Your implementation of nurseryrhyme() must be recursive. A non-recursive implementation of the function will receive zero credit. Moreover, since this is an exercise in generating text, any mismatches, including white space errors, will be penalized. Name the file with your C code ex3.c. Test it using your own inputs, and also the sample inputs provided.

Test Inputs, Due Date and Submission Procedure

Your assignment must be submitted electronically via Sakai by 11:55pm on Wednesday, February 12, 2020. You will submit your work on Exercises 1-3, specifically, the files ex1.c, ex2.c and ex3.c.

Sample Inputs/Outputs: Sample inputs and corresponding outputs are provided under /home/montek/comp411/samples/lab5. The sequence of steps to run your program and verify its output is as follows. First, copy all the sample input and output files to your lab5 folder:

% cd ~/comp411lab/lab5
% cp /home/montek/comp411/samples/lab5/* .
% selfchecklab5

How to submit: First transfer your work back to your laptop by either using WinSCP (for Windows), or Cyberduck/FileZilla/Macfusion or terminal/shell (for Mac/Linux), as explained in Lab 1. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.

Resubmissions: You are allowed to submit a lab assignment as many times as you would like to, but only the latest submission will be considered for grading.

In case of any problems, please contact the instructor or the TAs.