Machine Problem 4, due Apr 14

Assignment:

A popular screensaver from the past used to plot an animated "worm" on the the screen. If you constrain yourself to the ASCII display of the Hawk, this such a worm might look like the following:

        * * *
            *   *
            *   *
            * * *

Here, we have spaced the cells so that the x coordinate is always even in order to make the x and y spacing look uniform when characters are about twice as high as they are wide.

In each generation of the animation:

• The asterisk that has been on the screen the longest is replaced with a space.

• The current direction of worm motion is changed if
  • A random draw with a probability of 1 in 5 determines that it is time for a direction change.
  • The worm would run off the edge of the screen if it continued in the current direction; in this case, a new current direction that allows continued growth, if possible.
  • The worm would run into itself if it continued in the current direction; again, a direction is selected that permits continued growth, if possible.
• If growth in the current direction is possible, a new asterisk is plotted. Otherwise, the program terminates.

The worm starts out 10 asterisks long somewhere on the screen. Since a new asterisk is added to grow the worm each time an asterisk is removed, the worm stays 10 asterisks long until the program terminates.

Randomness:

Software cannot generate truly random numbers without help from hardware, since the whole point of our programming environment is to produce programs that produce deterministic output -- that is, given the program and the input, the output is completely determined.

What we can do is generate pseudo-random numbers -- they seem random, but in fact, they are not. It is very difficult to write a good pseudorandom number generator, and it is worth noting that many widely used pseudorandom number generators are not very good. Here is one that is adequate for many purposes (but not good enough for security-critical applications):

        /* Park and Miller's Minimal Standard Pseudorandom Number Generator */

        #define A 16807       /* = 0x41A7 */
        #define M 2147483647  /* = 0x7FFFFFFF */
        #define Q M/A         /* = 127773 = 0x1F31D */
        #define R M%A         /* = 2836 = 0xB14 */

        int seed; /* the value used to create successive random numbers */
                  /* at all times, (0 < seed < M) */

        setseed( int i )
        /* sets the seed for random number generation */
        {
                if ((i < 1) || (i >= M)) error();
                seed = i;
        }

        int random()
        /* advance the seed through the pseudorandom sequence
           and the next value from the sequence */
        {
                int t = A * (seed % Q) - R * (seed / Q);
                if (t > 0) {
                        seed = t;
                } else {
                        seed = t + M;
                }
                /* seed = (A * seed) % M is equivalent! */
                return seed;
        }

Requirements:

• Your source file must be titled with mp4.a and your name. Failure to follow this requirement will result in your assignment being ignored. We, the instructor and teaching assistants, will not engage in detective work to determine who to credit with an assignment.

• You must use the on-line coursework submission tools, as you did form MP1, submitting the file mp3.a for the course c_060 in the submission directory mp4.

• Your code must be well formatted and readable. This means approprite use of tabs and other forms of whitespace andappropriate names for labels that are suggestive of the program structure. Use subtitles to divide up the major subsystems of your solution within your source file.

• Your code must be well commented. This is not merely a matter of writing lots of comments, but a matter of comments that motivate and explain the code. Comments that merely restate what each instruction does are bad.

• Your code must make appropriate use of subroutines, where any and all activation records and parameters must be clearly documented, and where subroutines should be clearly set off from each other by appropriate comments and or subtitles.

• You will need to use several global variables and most likely a global array to keep track of the coordinates of the asterisks making up the current worm.

Grading

As mentioned above, the assignment number mp4 and your name must appear on the title of the listing. In addition, the file name of the file you submit must be mp4.a. No upper case, no alternatives.

• If your output is correct and your program runs without error and terminates norally, you will earn 2.5 points.

• An additional 2.5 points depend on the structure of your code. Demerits of up to 1/2 point will be assessed for irregular or nonstandard indenting, for excessive or inadequate white space, for poor choice of identifiers (such things as labels), inappropriate use of subroutines, and for disorderly code.

Notes

If you ask for help debugging your code, your code must be well commented. We will not look at "naked" assembly code with no comments to suggest what it is intended to do, and when we find poor comments or discrepancies between the comments and the code, we may ask you to fix those before we look at the code in any detail. Of course, if you ask for help with the comments themselves, we will be glad to offer suggestions.