CSCI 1510
Fundamental Computing with C Tutorial 11: Assignment 6
Yue Wang
yuewang@cse.cuhk.edu.hk
1
Outline
• Part 1: Basic Requirement
• Part 2: Problem Introduction • Part 3: Detail Implementation • Part 4: Suggestions
2
Part 1: Basic Requirement
• Due: 23:59, Tue 30 Apr 2019
• Fullmarks:100
• Submit the single source file ‘rushhour.c’
• Do not modify any required function prototypes
• Includepersonalinfo,suitablecomments,and make sure your program is: free of compilation errors and warnings
• Do NOT plagiarize!
3
Outline
• Part 1: Basic Requirement
• Part 2: Problem Introduction • Part 3: Detail Implementation • Part 4: Suggestions
4
Part 2: Problem Introduction • A sliding block puzzle gram: Rush Hour
– Watch this similar game video for better understanding (https://www.youtube.com/watch?v=PUEuticqXpI)
• The task is to move Car 0 into the exit hole
Exit hole
5
Rush Hour game
• The grid size: 8 * 8, where ‘#’ denotes the border and ‘.’ denotes the emply tile.
• There are at most 10 cars (denoted as 0-9, no two cars has the same index notation)
• Each car is placed either vertically or horizontally and occupy two or three tiles
• Each car can move forward or backward along their original placement direction
• There are 8 cars in the grid (0-7)
• Car 0, 1, 6, 7 can only move left or right
• Car 2, 3, 4, 5 can only move up and down
• We always assume that Car 0 is horizontally placed at line 3 (where the rightmost is the exit hole )
6
Outline
• Part 1: Basic Requirement
• Part 2: Problem Introduction • Part 3: Detail Implementation • Part 4: Suggestions
7
Part 3: Detail Implementation • How to represent the grid?
– grid[8][10]: 8 rows of strings
• The first row (grid[0]) and last row (grid[7]) are “########”
• For each string in each row, the length is always 8. Since string has the null character ‘\0’ at the end, the least length would be 9.
– totalSteps: recording the number of tiles that have be moved
• Note that moving a car by, say, two tiles, is counted as two steps
8
Required functions
• You have to implement your program using these five required functions. (important!)
• You are allowed to write extra functions
9
RushHour createPuzzle(const char *fname)
• Create a new RushHour structure and initialize it by reading a data file named as “fname”.
– For a RushHour structure, you need to initialize its grid and totalSteps into 0;
• fname refers to a txt file with string length less than 499. When debugging in Visual Studio, the file should be put at the same directory of the source code:
10
•
RushHour createPuzzle(const char *fname) How read this file into the grid[8][10]?
– File I/O in C
If the data file cannot be opened successfully
– print “File not found! Program exit.”
– terminate the program by calling exit(1) (need to include
•
void printPuzzle(const RushHour rh)
• Print the grid and the steps as the following:
– printf(“%s\n”, rh.grid[i]);
Do not forget to print the steps!
12
•
bool findCarPos(const RushHour rh, int car, int *row, int *col)
Find the position of the car and store it into the row and col (this is why they are passed as pointer)
– row and col: range from 0 to 7 (0 and 7 are borders)
– car: if you compare the car in the grid, you need to convert it to char:
•
How to define the position of a car?
– The position of a vertical car is its topmost tile.
– The position of a horizontal car is its leftmost tile
0 1 2 3 4 5 6 7
• The position of car 0: (3, 2)
• The position of car 4: (2, 4)
• The position of car 7: ?
13
bool moveCar(RushHour *rh, int car, int step)
• You need to move the car with step, if that move is valid, update the rh->grid and rh->totalSteps (this is why RushHour is passed as pointer) and return true. If invalid, return false and no changes to RushHour rh.
• Step can be positive or negative
– Positive : moving down (for vertical car) or right (for horizontal car);
– Negative value: moving up (for vertical car) or left (for horizontal car).
14
•
bool moveCar(RushHour *rh, int car, int step) How to check whether the move is valid or not?
– rh is not NULL
– car exists in the grid
– stepisnon-zeroand|step|<=5
– There is enough space to allow the car to move by step tiles (without blocked by other cars or the border)
The space for the right move of Car 7 is only 1, thus cannot be move by 2 tiles!
15
bool moveCar(RushHour *rh, int car, int step) • How to update the rh for conducting the move?
(if the move is valid)
1. Find the position of the car (use findCarPos())
2. Determine the moving direction (left, right, up, down?)
• Decided by step and the placement direction of car in the grid
3. For the chosen direction, conduct the move
• Usual you need to know the length of the car (2 or 3)
• An example for a right move
16
bool hasSolvedPuzzle(const RushHour rh)
• Returns true if Car 0 touches the exit hole in the puzzle rh; returns false otherwise.
17
Overall game flow (pseudo code)
int main() {
Ask the user to input the file name (a.k.a. fname); RushHour puzzle = createPuzzle(fname); printPuzzle(puzzle);
while (!hasSolvedPuzzle(puzzle)) {
Ask the user to input the car and step;
bool validMove = moveCar(&puzzle, car, step); if (!validMove) {
print the invalid prompts; else {
printPuzzle(puzzle);
} }
print the congrats prompt with the total steps;
return 0; }
// findCarPos can be used in the moveCar function
}
18
Outline
• Part 1: Basic Requirement
• Part 2: Problem Introduction • Part 3: Detail Implementation • Part 4: Suggestions
19
Part 4: Suggestions
• Do not declare any global variables
• All required function should not contain any scanf statements and printf statements
– except createPuzzle() (for printing “File not found!...”) and printPuzzle() (for printing the grid)
• Here is how I am going to grade your codes:
1. Check some basic requirement (personal info,
comments, any compilation warnings or errors)
2. Verify each of required function (by copying it into
my testing code)
3. Testing your code with test cases (at least two will be chosen from the provided puzzle configurations)
20
Part 4: Suggestions • Before submitting your code
– Check whether each of your required function are correctly implemented without any changes to the function prototypes
– Run your code according to the case in the specification file step by step. Make sure your output is the same
– Choose at least two other puzzle configurations and play the game until the end
21
Thanks!
22