CS1101C Practical Exam

Session 3 (1400 - 1545 hours)

Aragon's Walk

The name of your C program file must be called walk.c, files with any other name will not be marked.

The deadline for this lab is Wednesday 13 April 2005, 15:45 hours. Strictly no submissions will be accepted after the deadline.

Background

Aragon is protecting Frodo with the precious Ring! Frodo is hiding inside a group of trees, and Aragon's job is to patrol the group of trees by walking clockwise around it.

The entire area is an 8 x 8 board, where an empty square is marked by a full-stop, a tree is marked by a letter X, and Aragon is marked by the character @. The following is an example of an initial layout:

........
........
....X...
..@XXX..
....X...
........
........
........

Coordinates

We assume that each square is given by the coordinates (r,c) where r is the row number and c is the column number. The top left hand corner has coordinates (0,0) and the top right hand corner has coordinates (0,7).

Patrol

Aragon will walk around the entire block of trees until he returns back to his original square. Aragon can only move in one of the four directions: up, down, left, and right. The following shows an example of how Aragon will patrol a block of trees.

........
........
....X...
..@XXX..
....X...
........
........
........

........
........
..@.X...
...XXX..
....X...
........
........
........

........
........
...@X...
...XXX..
....X...
........
........
........

........
...@....
....X...
...XXX..
....X...
........
........
........

........
....@...
....X...
...XXX..
....X...
........
........
........

........
.....@..
....X...
...XXX..
....X...
........
........
........

........
........
....X@..
...XXX..
....X...
........
........
........

........
........
....X.@.
...XXX..
....X...
........
........
........

........
........
....X...
...XXX@.
....X...
........
........
........

........
........
....X...
...XXX..
....X.@.
........
........
........

........
........
....X...
...XXX..
....X@..
........
........
........

........
........
....X...
...XXX..
....X...
.....@..
........
........

........
........
....X...
...XXX..
....X...
....@...
........
........

........
........
....X...
...XXX..
....X...
...@....
........
........

........
........
....X...
...XXX..
...@X...
........
........
........

........
........
....X...
...XXX..
..@.X...
........
........
........

........
........
....X...
..@XXX..
....X...
........
........
........

Movement

For simplicity, we assume that Aragon always starts with a tree on his right, and he always starts facing upwards. The initial position of Aragon is not fixed.

The following pseudocode is given to help you to ensure that Aragon patrols the trees correctly. It shows the decision that Aragon will make depending on the trees around him. Note that turning left or right keeps Aragon on the same square; only the direction he faces is changed.

if there is a tree in front and there is a tree on the right
    turn left
else if there is a tree on the right
    go forward one square
else
    turn right
    go forward one square

Objective

The objective of your program is to read in a text file containing the initial layout of Aragon and the trees. You will print the initial layout, then show Aragon's movements by printing the coordinates of the squares he walks on. Aragon keeps walking until he returns to his original square.

Text File

To simply matters, the layout is stored in a text file called walk1.txt containing only integers. The following is a sample text file.

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 2 1 1 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

We use 0 to indicate an empty square, 1 to indicate a tree, and 2 to indicate Aragon. The locations of the trees and Aragon vary from file to file. You may assume that none of the trees will be placed at the board's edges, e.g. there will be no trees at row 0, column 0, row 7, and column 7.

For simplicity, we assume that Aragon always starts with a tree on his right, and he always starts facing upwards. The initial position of Aragon is not fixed.

You can find other text files (walk2.txt) in your practical exam account.

We will test your program with other text files.

Sample Run

The following shows a sample run when using the file walk1.txt as shown above. Print the initial layout, the list of squares that Aragon walks on (including the original square), and the total number of moves (not including turning left or right) that Aragon makes.

Follow the sample run exactly or you will not get any marks for the test cases. The UNIX prompt is shown by the $ sign.

$ gcc -Wall walk.c -o walk
$ ./walk
........
........
....X...
..@XXX..
....X...
........
........
........
(3,2)
(2,2)
(2,3)
(1,3)
(1,4)
(1,5)
(2,5)
(2,6)
(3,6)
(4,6)
(4,5)
(5,5)
(5,4)
(5,3)
(4,3)
(4,2)
(3,2)
Moves: 16
$

Remember to submit your program using the submit walk.c command, and check your submission using the check command.

All the best!

UNIX commands

Some useful UNIX commands (in case you forgot what you did in Lab 0):

  1. “dir”: lists all the files in the directory.
  2. “cp a.txt b.txt”: copies a.txt to b.txt.
  3. “mv a.txt b.txt”: moves / renames a.txt to b.txt.
  4. “cat a.txt”: shows the contents of a.txt.