CSCI1510 Computer Principles and C Programming, Spring 2018-2019 Department of Computer Science and Engineering, The Chinese University of Hong Kong
Assignment 6: Rush Hour
Due: 23:59, Tue 30 Apr 2019 Full marks: 100
Introduction
The objective of this assignment is to practice strings, pointers, and structures. You will implement a sliding block puzzle game called Rush Hour, which is played on a grid with at most 10 cars on it. The cars are aligned either vertically or horizontally in the grid and occupy two or three tiles. There is an exit hole on the right side of the grid. The goal of the puzzle is to move the cars forward or backward (but not change direction) so that a designated car (called Car 0) moves to the exit hole. Figure 1(a) shows an example puzzle configuration, in which Cars 0, 1, 6, and 7 are horizontal and can move left or right, and Cars 2, 3, 4, and 5 are vertical and can move up or down. Moving Car 1 to the right by one tile yields the state in Figure 1(b). Continuing to move the cars carefully, you can yield the solved state as in Figure 1(c) where Car 0 reaches the exit hole on the right.
########
#11…2#
#3..4.2#
#3004.2.
#3..4..#
#5…66#
#5.777.#
########
(a) Initial
(b) Move Car 1
(c) Solved
…
########
#.11..2#
#3..4.2#
#3004.2.
#3..4..#
#5…66#
#5.777.#
########
########
#311…#
#3…..#
#3….00
#5..4.2#
#5664.2#
#7774.2#
########
Figure 1: An Example Rush Hour Configuration and its Solved State
Program Specification
You need to define a structure type called RushHour, and use the type to implement a few functions to model the game play.
Structure Type RushHour
The structure type RushHour is defined as follows:
typedef struct rushhour {
char grid[8][10];
int totalSteps;
} RushHour;
char grid[8][10];
The Rush Hour puzzle is represented by an array of strings. Each string is an array of char with a null character. Therefore, grid is a two-dimensional array of char. Each string grid[𝑖] stores the contents in row 𝑖 of the grid. E.g., for the configuration in Figure 1(a), grid[0] is “########”, grid[1] is “#11…2#”, grid[2] is “#3..4.2#”, etc. The last row of the grid is grid[7]. All characters in the strings are either ‘#’ (border), ‘.’ (empty), or digits ‘0’–‘9’ (cars). All the strings are of length 8. To provide storage for the null character ‘\0’ and other usage, the size of grid would be 8×10.
Copyright © 2019 CSE, CUHK Page 1 of 6
CSCI1510 Computer Principles and C Programming, Spring 2018-2019 Department of Computer Science and Engineering, The Chinese University of Hong Kong
int totalSteps;
The total number of steps that a player has moved during puzzle play. Note that moving a car by, say, two tiles, is counted as two steps.
Required Functions
Your program must contain the following functions. These functions must be called somewhere in your program. You must not modify the prototypes of all these functions. You can design extra functions if you find necessary.
RushHour createPuzzle(const char *fname);
This function creates a RushHour structure and initializes it by reading a data file with file name fname. The structure is returned after initialization. You can assume that the data file always consists of eight lines of data; each line contains eight symbols of either ‘#’ (border), ‘.’ (empty), or digits ‘0’– ‘9’ (cars). The first line is grid[0]; the second line is grid[1]; etc. The exit hole is always at the 8th character of grid[3], that is, grid[3][7]. (You do not have to handle situations where the data file does not conform to this format.) You are provided some sample data files in Blackboard for your reference.
If the data file cannot be opened successfully, this member function should print “File not found! Program exit.” and then terminate the program by calling exit(1). Remember to also initialize the member totalSteps as 0.
Hint: if you use fgets() to read a line of data, the newline symbol (‘\n’) may be included into the string. You may need to remove the newline manually.
void printPuzzle(const RushHour rh);
Prints out the Rush Hour puzzle rh and the number of steps that the player has used. The following is an example output of printPuzzle().
########
#311..2#
#3….2#
#300..2.
#5..4..#
#5664..#
#7774..#
########
Steps: 10
bool findCarPos(const RushHour rh, int car, int *row, int *col);
Finds the position of the parameter car in the puzzle rh. The position of a vertical car is its topmost tile. The position of a horizontal car is its leftmost tile. The row and column indices of the found position are assigned to the targets of pointer parameters row and col respectively, and the function returns true. E.g., finding Car 2 in Figure 1(a) would write 1 to the target of row and 6 to the target of col, because Car 2 appears at row 1, column 6. In case car cannot be found in the grid (e.g., there is no Car 8 in Figure 1(a)), the function should not update the targets of row and col and should return false.
Copyright © 2019 CSE, CUHK Page 2 of 6
CSCI1510 Computer Principles and C Programming, Spring 2018-2019 Department of Computer Science and Engineering, The Chinese University of Hong Kong
bool moveCar(RushHour *rh, int car, int step);
Performs the action of moving the parameter car by step tiles in the puzzle targeted by the pointer rh. A positive value for step means moving down (for vertical car) or right (for horizontal car); a negative value means moving up (for vertical car) or left (for horizontal car). E.g., in Figure 1(a), moving Car 6 left by three tiles has a step of -3. A move is valid only if all the followings are satisfied:
The parameter rh is not NULL.
The parameter car exists in the grid.
The parameter step is non-zero. (Moving a car by 0 tile is meaningless.)
There is enough space to allow the car to move by step tiles, without blocked by other cars or
the border. (E.g., in Figure 1(a), Car 6 cannot move left by four tiles (-4 steps), as it would be blocked by Car 5.)
If the move is valid, then the contents of grid and member totalSteps have to be updated accordingly and the function returns true. Otherwise, no updates are needed and the function simply returns false.
Hint: first, find the position of car (with the help of findCarPos()). Then determine which one of the four cases the move is: move left, move right, move up, move down. Implement the cases one by one. For each case, check whether the move is blocked or not. If not, update the car to the new position.
bool hasSolvedPuzzle(const RushHour rh);
Returns true if Car 0 touches the exit hole in the puzzle rh; returns false otherwise.
Program Flow
Your main program declares a structure variable from RushHour and call the above required functions
to implement the following program flow.
1. The program prompts the user to enter a data file name. Then create a RushHour structure using the input data file. You can assume that the file name contains no space characters (e.g., cannot be “ab cd.txt”) and has a string length of at most 499.
2. Prompt the user to make a move. You can assume that the user always enters two integers, denoting the car and the steps of the move respectively. (Positive step means moving down/right; negative step means moving up/left.)
3. In case the input is not a valid move (see definition in the moveCar() function above), the program prints a warning message and goes back to Step 2. Otherwise, move the car accordingly.
4. If the puzzle is not yet solved after the move, go back to Step 2.
5. Once the puzzle is solved, print the solved puzzle and the message “Congrats! You finished in 𝑋
steps.”, where 𝑋 is the number of steps used.
Some Points to Note
You cannot declare any global variables in your program.
Remember to #include
type and the exit() function.
All the required functions above should not contain any scanf() statements. Instead, you use
scanf() in main() or your other functions only.
Copyright © 2019 CSE, CUHK Page 3 of 6
CSCI1510 Computer Principles and C Programming, Spring 2018-2019 Department of Computer Science and Engineering, The Chinese University of Hong Kong
All the required functions above should not contain any printf() statements except createPuzzle() (for printing “File not found!…”) and printPuzzle() (for printing the grid).
You are recommended to finish the required functions first before writing the program flow. When you write the required functions, test each of them individually one by one. The required functions will be graded separately, so you should not mix the functionalities of the functions.
Sample Run
In the following sample run, the blue text is user input and the other text is the program printout. You can try the provided sample program for other input. Your program output should be exactly the same as the sample program (same text, symbols, letter case, spacings, etc.). Note that there is a space after the ‘:’ in the program printout.
Enter data file: 1.txt ########
#11…2#
#3..4.2#
#3004.2.
#3..4..#
#5…66#
#5.777.#
########
Steps: 0
Make a move: 1 4 Invalid. Try again! Make a move: 1 1 ########
#.11..2#
#3..4.2#
#3004.2.
#3..4..#
#5…66#
#5.777.#
########
Steps: 1
Make a move: 3 -2 Invalid. Try again! Make a move: 3 -1 ########
#311..2#
#3..4.2#
#3004.2.
#…4..#
#5…66#
#5.777.#
########
Steps: 2
Make a move: 5 -1
Copyright © 2019 CSE, CUHK Page 4 of 6
CSCI1510 Computer Principles and C Programming, Spring 2018-2019 Department of Computer Science and Engineering, The Chinese University of Hong Kong
########
#311..2#
#3..4.2#
#3004.2.
#5..4..#
#5…66#
#..777.#
########
Steps: 3
Make a move: 7 -2 ########
#311..2#
#3..4.2#
#3004.2.
#5..4..#
#5…66#
#777…#
########
Steps: 5
Make a move: 6 -3 ########
#311..2#
#3..4.2#
#3004.2.
#5..4..#
#566…#
#777…#
########
Steps: 8
Make a move: 4 2 ########
#311..2#
#3….2#
#300..2.
#5..4..#
#5664..#
#7774..#
########
Steps: 10
Make a move: 2 3 ########
#311…#
#3…..#
#300….
#5..4.2#
#5664.2#
#7774.2#
########
Steps: 13
Make a move: 0 4
Copyright © 2019 CSE, CUHK Page 5 of 6
CSCI1510 Computer Principles and C Programming, Spring 2018-2019 Department of Computer Science and Engineering, The Chinese University of Hong Kong
########
#311…#
#3…..#
#3….00
#5..4.2#
#5664.2#
#7774.2#
########
Steps: 17
Congrats! You finished in 17 steps.
Submission and Marking
Your program file name should be rushhour.c. Submit the file in Blackboard (https://blackboard.cuhk.edu.hk/).
Insert your name, student ID, and e-mail as comments at the beginning of your source file.
You can submit your assignment multiple times. Only the latest submission counts.
Your program should be free of compilation errors and warnings.
Your program should include suitable comments as documentation.
Do NOT plagiarize. Sending your work to others is subjected to the same penalty as the copier.
Copyright © 2019 CSE, CUHK Page 6 of 6