University of Toronto
CSC148S--Introduction to Computer Science, Spring 1996
Solutions to Assignment 2

Question 1: Specifications

A well-formed rectangular array is a two dimensional array of black and white squares with the following properties:

1. The corners of the array are black.

2. There are no two adjacent white squares along any border of the array.

3. There is no block of white squares anywhere in the array.

4. There is exactly one white square on a border of the array that has an arrow pointing into it. (This is called the entrance of the maze.)

Another correct solution is to include the following additional property:

5. There is at least one white square on the border of the array besides the entrance. (These are called exits of the maze.)

These two solutions are different. For example, the figure below is a well-formed rectangular maze according to the first definition, but not according the second definition.

A solution equivalent to the first solution was obtained by a student. It consists of condition 4 and the following condition:

6. If a layer of white squares is put around the outside of the array, then the resulting array does not contain a block of white squares.

A completely different solution was obtained by another student.

If a row of the array starts with a white square, that row must contain exactly one black square.

If a row of the array starts with a black square, that row cannot contain two adjacent white squares followed by a black square.

Yet another student had the following solution, which is also very concise.

1''. The array must have at least 2 rows and at least 3 columns.

2''. In the second row of the array (from the top), the second square (from the left) must differ in colour from the squares before and after it in the row.

Question 3: Ambiguity

1. Consider the following input file:

1 3
2 1
100*

Both of the following output messages are consistent with the output specifications.

Line 3 contains a character that is not a bit.
Line 3 does not consist of the correct number of bits.

2. Add the following sentence to the output specifications to eliminate ambiguity: If two or more error messages apply to to the first occurrence of an error within the file, report the first of these in the list on page 2 of the assignment.

Question 5: Data Structure

A maze is represented by a two dimensional boolean array M plus two integers entranceX and entranceY denoting the horizontal and vertical position of the entrance. Element (1,1) of the array represents the lower left corner square of the maze. This is to match the assignment handout and it also makes displaying the maze on the screen slightly easier.

It would be better style to put both the array and the entrance coordinates of a maze in a record and to declare a formal type (e.g. ``mazeType"). This isn't done, however, because Turing dynamic arrays cannot be members of a record. Instead, the entrance coordinates must be passed as separate parameters to the various routines.

The array element false denotes a black (solid) square and true denotes a white square (a ``space'').

Question 6: User's Guide

Brief User Guide (not written for a 10 year old!):

This program allows the user to edit a maze by progressing through several different stages. Once a stage is completed, a user cannot move back to an earlier stage.

Informative messages are displayed at the top of the screen.

Stage 1: Specifying the height and width of the maze.

The user is prompted for the height and width of the maze. These must be positive integers and cannot be too large for the screen being used. The prompts will be repeated if the user responds with invalid values.

Stage 2: Specifying the elements of the maze.

The elements of the maze are initially all black. The user may flip any element from black to white by clicking on it with the mouse. Clicking again will flip it back. There are no checks at this stage, so the user may create an ill-formed rectangular maze.

This stage is completed when the user clicks on the ``Done" button.

Stage 3: Specifying the entrance of the maze.

The user may specify one entrance by clicking on a maze element. The designated element will be coloured green. The entrance may be changed simply by clicking on a different element. There are no checks at this stage so any element (or none at all) can be chosen as an entrance.

This stage is completed when the user clicks on the ``Exit" button.

Stage 4: Checking the maze.

After specifying an entrance, the maze is checked and the user is informed whether the maze is well-formed or not.

Stage 5: Outputting the file.

The user is asked to name the file the maze will be written to. The maze is then output to this file.

Limitations/Interesting details:

1. The size of the maze created depends on the screen size. The dimensions are dictated by the interface module.
2. The user cannot go back to an earlier stage.
3. An entrance is displayed as green whether it is a space or a solid. It would be more informative to use different colours.
4. The default entrance is (0,0) which is not a legal maze coordinate.

• About this document ...