Assignment 8: Maze, Fill

Deadline

9 November 2018 (Friday), 23:59 pm

Prerequisites

• You are able to access the CS1010 programming environment.
• You are familiar with basic UNIX CLI and using terminal-based editor vim.
• You have gone through Exercise 1 and have already set up your .gitconfig.
• You are familiar with the steps of accepting, downloading, and submitting your exercise and assignment.
• You are familiar with the directory structure and the common files included in your assignment skeleton.

Learning Outcomes

• Be comfortable writing C programs that involve arithmetic operations, long, double, bool, and char types, conditional if/else statements, loops with while/for/do-while statements, arrays (including 2D arrays), strings, pointers, and dynamic memory allocation.
• {++Be able to design and implement recursive search algorithms with correct pruning to prevent repetitive or redunant work.
• Be comfortable breaking down a problem into smaller subproblems which can be resolved using functions, including reusing existing functions written for other programs (with a tweak), writing a function that calls itself, designing what should the inputs and return values/types of a function be.
• Be able to analyze the problem and come up with solutions to problems that are efficient, through eliminating redundant and repetitive work.

Setup

• Accept the assignment
• Login to one of the hosts of CS1010 programming environment
• Run:

~cs1010/get-as08

• You should see the folder as08-<github id> in your home directory with the assignment skeleton inside.

Solving The Assignments

• Edit the C files to solve the corresponding question as described below.
• You should break down the problem into smaller subproblems, and write one function for each of the subproblem to solve the problem.
• To compile and run tests with the sample inputs and outputs:

make

• A minimal set of test cases are given in the inputs and outputs subdirectory. You can use cat or less to look at the content of these test cases. You should add more test cases or edit the given ones to extensively test your programs.

Submission

When you are ready, run the following command to submit:

~cs1010/submit-as08

The C files given will be uploaded to GitHub. You can submit multiple times, but only the last submission will be graded.

Editing Your Files in Multiple Locations

You should edit your code only on the CS1010 PE hosts. If you choose to edit your code in other places, such as directly on Github or in a second location (such as your own laptop), you need to be comfortable with various git command to synchronize your code across the different locations, possibly needing to resolve synchronization conflicts.

Only the C files listed above will be submitted. You can create additional C files for testing different solutions, but eventually, you must put your solution into the corresponding C file provided as the skeleton.

Identifying Yourself

In every C file that you submit to CS1010, you need to identify yourself by writing your name and tutorial group. Marks will be deducted if you fail to do so. You need to edit the line:

@author XXXX (Group YYYY)

and change it to something like:

@author Fox Mulder

Grading

This assignment contributes towards 3% of your final grade. The total mark for this assignment is 30 marks. There are five marking criteria: design, efficiency, correctness, documentation, and style.

• Design: 2 marks. You should break down your program into smaller functions, each one performs a single coherent task or solves a well-defined subproblem. You should avoid repetitive code that can be factored out as a function. Writing everything in a single long function main or cutting-and-pasting code would likely cause you to lose marks for this criteria.
• Efficiency: See the question for the breakdown and marking criteria for efficiency.
• Correctness: The rest of the marks are allocated to correctness. Note that passing the tests does not guarantee that your code is correct. Correctness here is defined in the broad sense of using the various programming constructs in C (type, function, variable, loops, arrays, pointers, conditionals, arithmetic expressions, logical expressions) properly, not just producing the correct output and bug-free.
• Style: Marks are no longer allocated for style, but we will deduct up to 2 marks if you have a serious violation of the style guideline. Please refer to the CS1010 C Style Guide and follow the recommended guideline.
• Documentation: Marks are no longer allocated for documentation, but we will deduct up to 2 marks if you do not document the functions in your code properly. Please refer to the documentation and follow the recommended format. We have added the compilation flag -Wdocumentation to help you identify documentation errors. You need to explain the purpose of every file, function, and parameter. Logic in your code that is not obvious should be explained as well.

We reserve the right to penalize students for using banned C syntax in the assignments. In addition, each grader at his or her own discretion can penalize students for repeating mistakes / bad practices from the student's past assignments (even if it was just a warning with no marks deducted in the earlier assignments).

Question 1: Maze (15 marks)

Agent Scully woke up and found herself in the dark. She figured out that she is in a maze. She has to find her way out, if there is one!

The maze can be simplified as a $m \times n$ cells. Each cell can be of the following:

1. '#' denotes a segment of a wall. Noone can pass through the walls.
2. '.' denotes an empty space
3. '@' denotes where Scully is at currently. It is also an empty space

Anytime Scully reaches a border cell (a cell in either the top-most or bottom-most row or left-most or right-most column), she escapes the maze and can go save her partner Agent Mulder. She can only move from one empty space to another adjacent cell in one step. Two cells are adjacent if they share a common edge.

Scully took CS1010, and she got a concrete plan to seek a way out by trial and error. She follows strictly the following strategy to find a way through the maze starting from her initial position. At each time step,

1. She looks for an empty adjacent cell that has never been visited yet, in the sequence of up/right/down/left to the current cell she is at. If there is an empty adjacent cell, she moves to that cell. The cell she moves to is now visited.
2. If no empty, unvisited, adjacent cell exists, she backtracks on the path that she comes from, moving one step back, and repeat 1 again.

In this way, Scully will explore the maze in a systematic manner, with no repetitive visit of any cell more than once except when she backtracks. She will stop when successfully escaped the maze, or finds that there is no way out after backtracking all the way back to the original position. She is completely trapped within the maze and now must wait for Agent Mulder to come and free her.

Write a program maze.c, that reads from standard input. First, read two positive integers $m$ and $n$, followed by $m$ lines of $n$ characters in each line that represents the maze setup. One and only one @ will be present in the maze setup.

The program then prints, to standard output, an animation of $k$ iterations. The output should only contain $m$ rows with $n$ characters in each row, with an additional row at last. Similarly, you must use # to represent a wall, a . to represents an empty space, and @ to represent where Scully is at. After printing the maze, your program prints the number of steps that Scully has made.

You should use recursion to explore the maze and look for a way out.

Here is an example. The following is the starting position of Scully and the maze.

###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#@#.#..#..#
#...#.#.#..
###########
0

Scully firstly moves five steps up:

###########
#@#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
5

At this point, Scully is stuck since there is no more adjacent empty cell that has not been visited. Scully then backtracks:

###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#@#.#..#..#
#...#.#.#..
###########
10

Scully then moves down:

###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#@..#.#.#..
###########
11

Then right:

###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#..@#.#.#..
###########
13

Then up:

###########
#.#.....#.#
#.#####.#.#
#.#@..#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
17

Then right (two steps) and then down (two steps) and then right (two step):

###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#..@..#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
22

Then Scully moves up and left, and she is stuck again.

###########
#.#@....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
29

At this point she backtracks:

###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#..@..#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
36

Moves right, and up, and stuck again!

###########
#.#.....#@#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
41

She backtracks again,

###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#...@.#
#.#.##.#.##
#.#.#..#..#
#...#.#.#..
###########
45

This time she found her way out!

###########
#.#.....#.#
#.#####.#.#
#.#...#.#.#
#.#.#.....#
#.#.##.#.##
#.#.#..#..#
#...#.#.#.@
###########
50

It took her a total of 50 steps to exit the maze.

Animation on Screen

We have provided a few lines of code in the skeleton file. You should insert this at appropriate places:

char clear_screen[] = { 27, '[', '2', 'J',27, '[', ';', 'H', '\0'};
   :
cs1010_print_string(clear_screen);

usleep(250*1000); // you can change the interval here without affecting the correctness of the program.

Line 1 in the code above defines a special string that, when printed, will clear the screen and place the cursor on the top left corner of the terminal. Line 5 calls the system function usleep that takes in the number of microseconds. Calling usleep causes the program to pause for that amount of time. Sleeping time in input file is set to to 250ms (250000) and you can freely change the value if you wish. During grading, sleeping time in all inputs are 0.

Hint: You need to strictly follow the described strategy and sequence of exploration. Do not forget to print the initial matrix, and final matrix Your solution must take no more than $O(mn)$ time.

The grading criteria for this question is:

	Marks
Design	2
Correctness	5
Efficiency	8

Sample Run

• maze.1.in

• maze.2.in

We also included a larger maze maze.3.in for you to play with but there is no corresponding output file for this. This maze would take Scully 900 steps to find out that she is stuck in the maze!

Question 2: Fill (15 marks)

Scully is attending a drawing class today. She has already completed her work, but the teacher is not satisfied with her choice of colors and wants her to re-color some parts. She asks you, a programming genius, to help.

Scully's drawing can be simplified as a 2D array of size $m \times n$, with colors '0' to '9'. The drawing consists of several objects. Each object can be viewed as connected areas of cells of the same color. Two cells are connected if they share a common edge, i.e. a cell will have at most 4 connected cells.

Write a program, fill.c, to help Scully re-color her drawing according to her teacher's requirement. It reads from standard input two positive integers $m$ and $n$ in the first line, followed by $m$ lines of strings. Each string is of length $n$, consisting of only characters '0' to '9'. The next line is a positive integer $q$, which is the number of color changes the teacher requires. Following this, there are $q$ lines with three integers on each line: $x_i$, $y_i$, and $c_i$. It means to color the object containing pixel ($x_i$, $y_i$) to the color $c_i$. We denote the top left pixel to be $(0,0)$ and the indices increases towards the right and down.

The program shall prints to standard output, the drawing after re-coloring the objects according to the teacher's commands according to the order of the input. Note that one object can be re-colored multiple times.

You should use recursion to complete the coloring process.

Your solution must take no more than $O(mnq)$ time.

The grading criteria for this question is:

	Marks
Design	2
Correctness	5
Efficiency	8

Sample run

ooiwt@pe119:~/as08-skeleton$ cat inputs/fill.1.in
5 5
00110
00110
00000
11040
01100
2
0 3 2
4 1 3
ooiwt@pe119:~/as08-skeleton$ ./fill < inputs/fill.1.in
00220
00220
00000
33040
03300
ooiwt@pe119:~/as08-skeleton$ cat inputs/fill.2.in
5 5
11111
11111
11111
11111
11111
2
0 3 2
4 1 3
ooiwt@pe119:~/as08-skeleton$ ./fill < inputs/fill.2.in
33333
33333
33333
33333
33333