Practice Assignment

(randwalk.c)

Information

  1. For this practice assignment you will write a program that performs a "random walk" over a 2-dimensional grid (8x8 array). You start in the top/left of the array (array[0][0]) and choose a random direction to travel: UP, DOWN, RIGHT, or LEFT.

    Here are a few examples showing 3 successful random walks: 

    
 A B C D . . I J
 . . . E F G H K
 . . . . . N M L
 . . . . . O R S
 . . . . . P Q T
 . . . . X W V U
 . . . . Y Z . .
 . . . . . . . .

    
 A . . . . . . .
 B . . . . . . .
 C . . . . . . .
 D . . . . . . .
 E . . . O P . Z
 F . . . N Q R Y
 G . . . M T S X
 H I J K L U V W

    
 A . . . . . . .
 B . . . . . . .
 C D . . . . . .
 . E . . . Y Z .
 . F . . . X W .
 . G H . . . V U
 . J I . O P Q T
 . K L M N . R S

    Here are a few examples showing 3 unsuccessful random walks: 

    
 A B . . . . . .
 D C . . . . . .
 E J I . . . . .
 F G H . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .

    
 A H I J . . . .
 B G . K . . . .
 C F . L . . . .
 D E N M . . . .
 . . O . . . . .
 . . P Q R . . .
 . X Y T S . . .
 . W V U . . . .

    
 A . E F G . . .
 B C D . H . . .
 . . K J I . . .
 . M L U T . . .
 . N . R S . . .
 . O P Q . . . .
 . . . . . . . .
 . . . . . . . .

    This is the prototype of the function that the driver will call: 

    void random_walk(int showall);
    The showall parameter is a boolean (integer) that tells the function if it should show every board (each new character placement) or just show the final board (like the boards above). If showall is 0 (false), then you will only show the final board. If it is non-zero (true), you will show every board. You can see all of the boards for the first example here: all-sample1.txt. Notice that there is an extra blank line printed after the board when all boards are printed.

    Having the ability to show all of the boards is necessary to debug your programs. Otherwise, you won't know which step is producing incorrect results.

    This is the command line to compile it: 

    gcc -O -Werror -Wall -Wextra -ansi -pedantic main.c randwalk.c PRNG.c -o randwalk
    Here is a simple driver file: (main.c, HTML Text) The program requires 2 command line parameters:

    1. The first parameter is an integer, either 0 or non-zero. This controls whether or not you should print every board or just the final board. A zero means just print the final board and any other integer means print all boards.
    2. The second parameter is an unsigned (0 or positive) integer that will be used as the seed to the PRNG. This allows you to reproduce walks when developing the program.

    Examples: (The text from the semi-colon on is just for descriptive purposes) 

    randwalk 0 123    ; Just show final board, seed is 123
randwalk 1 123    ; Show all boards, seed is 123
randwalk 1        ; Show all boards, seed is time(NULL) this is random
randwalk          ; Just show final board, seed is time(NULL) this is random
    See the driver to see how it works.

    Random number generator files (put these in the same directory as your C file)

    2. Sample output files:

    Final boardAll boards
    out-sc12.txt out-sc12a.txt
    out-se22.txt out-se22a.txt
    out-si213.txt out-si213a.txt
    out-ss1.txt out-ss1a.txt

    The seemingly cryptic file names actually reflect what's in the file as well as the command line arguments used to create them. All of the files start with out-s. The first character after that prefix is one of c e i s:

    The number in the filename is the seed used for the PRNG. This will allow you to reproduce these boards.

    If the letter a follows the seed, it means that all of the boards are in the file. If no letter a follows, the file contains just the final board.

    So, to generate the first file on the first line: 

    randwalk 0 12
    To generate the second file on the first line: 
    randwalk 1 12
    This file contains 36 test cases: allfiles.zip. The reason there are so many tests is because there are many cases you need to be able to handle and these represent most (if not all) of the cases. There are actually only 13 tests, but there are two files for each test: one file that just contains the final board, and another file that contains all of the boards for the test.

    This file contains the output from all 36 test cases: output-all.txt.

    There is also a stress test here, which you shouldn't test until you've passed all of the above tests. It basically does 500 runs (seeding 1 to 500) and puts the output into a file: stress.txt.

    There are batch files (Windows) and bash scripts (Linux and Mac) that will help you to automate the running of all of the tests:

    You need to remove the .txt extension on these files for them to work. All of the files are also in allfiles.zip.

    Update:

    Here's another stress driver: HTML    Text

    Run it like this: 

    randwalk 0 -100
    And the output: stress2.txt 
    







  




Notes:


    


    

  1. The driver handles the details of seeding the PRNG. You must NOT do that, or you will
  not get the correct output.
    2. 

    

  2. After displaying the board you will print out how many steps were completed. On a
  successful walk (all 26 characters were placed) you'll display this:

    All 26 steps were completed.  

    
If you can't complete the walk, you must display something like this:

    Only completed 22 steps.

    


  3. You'll notice there are extra blank lines printed when printing all of the boards.
  Look at the sample outputs to see how to format them.
    4. 

    


  4. The board should be a 2-dimensional array (8x8) of char. All of the elements must
  be initialized to just a period.
    5. 

    

  5. The only system header file that you should need is stdio.h (for printf).
  
    

  6. Your code is basically in a loop (do..while) that repeatedly calls the RandomInt 
  function similar to this:

    int direction = RandomInt(0, 3);

    
  
  There are 4 possible directions: UP, DOWN, RIGHT, and LEFT. You must use this enumeration
  in your file:

    typedef enum DIRECTION {dirUP, dirDOWN, dirRIGHT, dirLEFT} DIRECTION;

    

  This will essentially give the enumerators the values 0 to 3. It's very important
  that you order the enumerators like this. If you use other values for those directions, you will not get
  the correct output because of the PRNG.

    
  
  7. If you generate a random move that leads to a spot on the board that is already
    taken, or the random move leads you off of the board,
     you just call the RandomInt function again.
    8. 
   
    


  8. There are two ways the program ends:
  
    
  
      
    
    1. You successfully placed the last character (Z) on a spot. 
      (See the first 3 examples at the top of this page.)
      2. 
    
    2. The last character that was placed is surrounded on all 4 sides by other characters
      or an off-the-board location. (See the second 3 examples at the top of this page.)
      3. 
  
    


    



Hints and advice:


  This is by far the most complex practice. However, you have all of the C knowledge
    required. You just need to apply good coding practices.
  


    
  
  1. Think! - You should spend at least 20 minutes thinking about how you are going
    to structure your solution. Don't start writing code until you can sketch out the
    entire process. This leads to the next point.
  
    
  
  2. Helper functions - You'll need several helper functions. If you try to do
    all of the work in one or two functions, you will fail. Even if you were able to
    do that, your code will most likely be a mess that no one would ever want to work with.
    
    
    There are two important helper functions. The first is for determining the next move based on
    the current position. The second is to determine if a particular character is surrounded.
    If the last character placed is surrounded so that another character cannot be placed,
    the program must end. You should call this second helper function before attempting to
    place another character. If you don't, you may find yourself in an infinite loop looking
    for an open spot that doesn't exist.
  
    3. 
  
    
  
  3. Don't hard-code values - Even though you are only expected to support an 8x8 array, you
    shouldn't hard-code those numbers anywhere. Use a #define. This will make it trivial
    for you to change to a 10x10, or 20x20, or whatever size you want. In fact, you should
    allow both the number of rows and the number of columns to change, something like this:

    #define BOARD_SIZE_ROWS 8
#define BOARD_SIZE_COLS 8

    

    That is the proper way to write code.
    4. 
  
    





  




Additional features:


This practice has been purposely kept simple. If you feel you are up to a bigger challenge,
here are some ideas. If you've been using good programming habits, these additional features
are not difficult at all.


    
  
  1. Dynamic sized boards - Don't hard-code the size as 8x8. Dynamically allocate the 2-dimensional board
    at runtime. You should allow the user to specify the size of the board on the 
    command line. Example of a 12x12 board:
    2. 


    
 A D E . . . . . . . . .
 B C F I J K L M N . Z Y
 . . G H . . . . O . . X
 . . . . . . . Q P . V W
 . . . . . . . R S T U .
 . . . . . . . . . . . .
 . . . . . . . . . . . .
 . . . . . . . . . . . .
 . . . . . . . . . . . .
 . . . . . . . . . . . .
 . . . . . . . . . . . .
 . . . . . . . . . . . .

        
  
    
  
  2. Non-square boards - You should be able to handle boards
    like 5x10, 10x5, 20x8, etc. The smallest rows/columns should be set to 2.
     Example of an 8x20 board:

    
 A . . F G H . . . . . . . . . . . . . .
 B C D E . I J K . . . . . . . . . . . .
 . . U T . . . L . . . . . . . . . . . .
 . . V S R Q P M . . . . . . . . . . . .
 . . W . . . O N . . . . . . . . . . . .
 . . X . . . . . . . . . . . . . . . . .
 . . Y Z . . . . . . . . . . . . . . . .
 . . . . . . . . . . . . . . . . . . . .

     

And an example with 2 rows and 24 columns:

    
 A B C F G J K L . P Q T U X Y . . . . . . . . .
 . . D E H I . M N O R S V W Z . . . . . . . . .

     

    3. 


  
    
  
  3. Starting position - Allow the first character to be placed anywhere on the board instead of always
    placing it at the top left. Example of a 9x9 board with starting position row 5, column 5:
    4. 

    
 . J I H . . . . .
 . K . G F . . . .
 . L . . E . . . .
 . M N C D . . . .
 . P O B A . . . .
 . Q . . . . . . .
 S R . . . . . . .
 T W X Y Z . . . .
 U V . . . . . . .

    

  
    
  
  4. Length of the walk - Instead of hard-coding the length to 26 characters, 
    allow more or less. With more than 26, it's a little weird because you have to know
    the order of the ASCII values. Example of an 8x8 with 30 moves instead of 26:
    5. 

    
 A B . . . X Y Z
 D C . U V W \ [
 E F G T . . ] ^
 J I H S . e f _
 K L Q R . d c `
 . M P . . . b a
 . N O . . . . .
 . . . . . . . .

    
Another strategy to having more than 26 characters is to start over at A after
you place Z on the board. Yet another strategy would be to switch to lowercase characters
after the uppercase characters have been exhausted. Of course, using numbers instead
of letters will allow the most flexibility, at the cost of more code to format the
output, as well as possibly having to use ints instead of chars in the 2D array.

    

Example of a 5x5 board with a limit of only 10 moves:

    
 A B C D .
 . . . E .
 I H G F .
 J . . . .
 . . . . .

    

  
    
  
  5. Diagonal moves - In addition to the 4 moves (UP, DOWN, RIGHT, LEFT), allow
    diagonal moves. This gives a maximum of 8 moves instead of just 4. With this in mind,
    rename the directions to North, South, East, West, NorthEast, SouthEast, SouthWest,
    and NorthWest:

    
 NW  N  NE
  W  ·  E
 SW  S  SE

    

and a possible enumeration:


    typedef enum DIRECTION {dirN, dirS, dirE, dirW, dirNE, dirSE, dirSW, dirNW} DIRECTION;

    

Here's a sample walk:

    
 A . . . . . . . . .
 . B . . . . . . . .
 . C E . . . . . . .
 . . D F . . . . . .
 . . . G . . . . . .
 . . . . H . . . . .
 . . . R S I . . Z .
 . . Q T J K . . Y .
 . . P . U M L X . .
 . . . O N V W . . .

    

    6.