CMSC 246 Systems Programming
Spring 2021

Assignment #2
Due: March 3 before 11:59:59pm EST

Part 1: Read a file into an array (10%)
Write a program that reads a file that contains 10 integers on exactly 10 separate lines into an array of length 10. To read the file use either a pipe or redirected input so you program will read the file from stdin. Then use fgets to read each line (a la SHOUTj.c) then use the atoi function to convert the string you read into an integer. Do not use scanf. If you have issues with either fgets or atoi, read the man page, e.g.,ß man 3 atoi. atoi is defined in stdlib.h. You may assume that the input file is perfect. (You will need to create the file.)

After reading from the file, print out the array in reverse order (along with the array index). For instance an input file might be: 
    1
    3
    5
    -7
    9
    8
    6
    4
    2
    0
in which case the output would be 
    9 0
    8 2
    7 4
    6 6
    5 8
    4 9
    3 -7
    2 5
    1 3
    0 1
Part 2: IS THE ARRAY SORTED? (10%)
Write a function sorted(int n, int arr[n]) that returns true/false depending on whether the given array is sorted.
Adapt you program from part 1 to use this new function so that after printing the last element of the array the program prints 
    the array is [NOT] sorted
Part 3: Random Walks (60%)
Write a (separate) program that takes a random walk on an NxN grid. The walker should do the following:
  1. Walk on a 10x10 grid
  2. Start at the position 5, 5
  3. Never move to a position it has occupied previously
  4. Never move off the grid
  5. Determine the set of legal moves from the current position. Legal moves are one space, either up, down, right or left AND that do not violate either of the preceding conditions.
  6. Choose a move to make randomly from among the legal moves.
  7. Print each move made on a single line. This may be as simple as "23 [3,2]" which would mean that on move 23 the walker was in position 3,2
  8. Return the number of steps it takes before the walker gets to a point of having no legal moves.
For instance, suppose that the sequence of moves is (s int he table indicates start, you could use 0 instead): 
  s [5,5]
  1 [6,5]
  2 [7,5]
  3 [7,6]
  4 [7,7]
  5 [6,7]
  6 [5,7]
  7 [5,6]
  8 [6,6]
Then at this point there are no remaining legal moves since the walker has already been to every position possible from [6,6]. Hence, program (or function) should return 8. In fact 8 moves is the shortest walk possible (on a 10x10 board) given the rules above.

Part 4: Random Walk statistics (20%)
Adapt the random walk program from part 3 so it can record the number of steps taken before exhaustion. (The principle adaptation will be to comment out the code that prints the move by move table and to add a line to print the number of moves taken before getting stuck. Thus the entire output of the program after these adaptions might be 12 or in the case of the above table, 8.) Further adapt the program so that the grid size can be varied. The best way to do this would be to have your progam accept two command line parameters, the width and height of the grid. It is OK to vary the grid size by slighlty altering the program and recompiling. However, if you take this approach, "slight" should mean changing no more than 5 characters in the program. Then:
  1. Collect the number of moves before exhaustion for 100 trials of a 10x10 grid (You may modify your program to add a loop to get it to doo 100 trials.
  2. Compute and report the mean and standard deviation of these trials
  3. Collect the number of moves before exhaustion for 100 trials of a 20x20 grid when starting at position 10,10
  4. Compute and report the mean and standard deviation.
  5. Write a brief report (to be included in the README) (max 1 paragraph) with your interpretation of this data. For instance, your interpretation might discuss a topic like: "how many moves you expect from even bigger (or smaller) boards" or "how rule changes would affect the walker" or even "how many moves it takes for a random walker to have been in every position, given that revisiting positions is allowed". You might find you answers are improved by testing with other board sizes

Scripting in Linux

Once done, you will need to show some sample runs for parts 1, 2, and 3. In order to record the runs, you can use the Linux command script.
To use script
  1. Go to your directory containing your assignment 1 programs directory and enter the command: script SESSION
    where SESSION is some meaningful name
  2. You will get your command prompt back.
  3. Run each of the above programs as you normally would.
  4. Once done, enter the command: exit
  5. This will end your script session. If you now look a the contents of the session file, you will see that the entire interaction has been recorded in it (as a script!).

What to submit:

Collect together is a single directory (assume that this directory is /home/YOU/cs246/a2) all of the following: