Repetition Structures - Counting Squares

One of the advantages of using computer programs is that we can easily implement repetitive tasks. Structures such as for, while, and do-while allow us to repeat a block of instructions as many times as needed. These structures are also referred to as repetition structures.

Algorithms are one of the fundamental concepts in Computer Science. Given a small set of instructions and the basic programming structures, we can solve many problems. In this laboratory experience, you will practice the creation of algorithms simulating a robot that must explore a space using a set of very limited instructions.

Objectives:

1. Design algorithms using sequential, decision and repetition structures.
2. Analyze the number of steps of the proposed algorithms and try to minimize them.
3. Practice invoking the methods of an object.

This laboratory experience is an adaptation of http://nifty.stanford.edu/2015/tychonievich-sherriff-layer-counting-squares/ .

Pre-Lab:

Before arriving to the laboratory you should have:

1. Reviewed the basic decision and repetition structures for C++.
2. Reviewed the creation of objects and how to invoke their methods.
3. Studied the concepts and instructions for the laboratory session.
4. Taken the Pre-Lab quiz, available in Moodle.

Counting Squares

In this laboratory experience, we will be programming a robot that has been placed in a grid of square rooms. Each one of the four walls in each room can have a door. Only the walls of adjoining rooms have doors. The walls that make up the grid's exterior do not have doors.

Figure 1. The robot is in the room on the upper left of the 36 room grid.

The only commands the robot understands are:

1. Verify if there is a door on the wall to the north (N), south (S), east (E), or west (W) of the room where it currently is.
2. Move to the room that is located towards the north (N), south (S), east (E), or west (W) of the current room.
3. Create variables and assign them values.
4. Carry out basic operations for sum, subtraction, multiplication and division.
5. Use decision and repetition structures.
6. Display the results on the screen.

Objects and Methods

The following is the main function of a basic program like the one you will be creating. During the laboratory experience you only need to program the main function (within the main.cpp file). The rest of the files contain functions that implement the functionality of the instructions the robot understands.

int main(int argc, char *argv[]) {
    QApplication   a(argc, argv);

    // Create the grid and the robot
    MainGameWindow *w = new MainGameWindow(Mode::RECT_RANDOM);
    w->show();

    // Show the word "Start"
    w->display("Start");

    // Move the robot towards the west while possible,
    // counting the number of steps the robot moves

    int ctr = 0;
    while (w->canMove('W')) {
        w->moveRobot('W');
        ctr = ctr + 1;
    }

    // Display the total steps taken by the robot
    w->display("Total: " + QString::number(ctr));

    return a.exec();
}

Figure 2 Example of the main Function.

In the example we are creating a robot within the grid that only knows how to check if there is a door towards the west and (if there is one), walk towards that direction. Let us see the function, line by line.

The first line creates the only object you should create, an object of the MainGameWindow class. The parameter Mode::SQUARE_TOP_LEFT specifies that the grid will be square and that the robot will start in the upper left corner. Other options for the parameter are RECT_TOP_LEFT, RECT_RANDOM and PYRAMID_RANDOM.

MainGameWindow *w = new MainGameWindow(Mode::SQUARE_TOP_LEFT);

The following shows the object w.

w->show();

The void display(QString) method displays short messages on the screen. For example:

w->display("Start");

shows the word "Start" before the robot starts to move. The code that follows:

int ctr = 0;
while ( w->canMove('W') ) {
    w->moveRobot('W');
    ctr = ctr + 1;
}

illustrates the use of the bool canMove(char) and void moveRobot(char) methods:

• bool canMove(char) - accepts as a parameter one of the following letters: 'N', 'S', 'E' or 'W' and returns true if a door exists in that direction from the room where the robot is currently found.
• void moveRobot(char) - accepts as a parameter one of the letters 'N', 'S', 'E' or 'W' and moves the robot to the next room that is found in that direction.

In the example, the code is trying to move the robot as many times as it can towards the west (W), and counting the number of rooms in that direction.

Suppose that the robot starts in the upper-left corner of a square grid. It would need to pass through each and every room in order to know how many squares the grid contains. True False The robot does not need to pass through each and every room. It only needs to find the height or width of the square, then square that to obtain the number of rooms.

Suppose that the robot starts in the upper-left corner of a rectangular grid of height h and width w. Suppose that robot must visit N rooms to determine the total number of rooms in the grid. How would that compare to M, the number of visited rooms to determine the total number of rooms in a rectangle whose height and width are 2h and 2w. It must visit approximately 4 times more rooms for the second case, i.e. M = N * 4 It must visit approximately h*w additional rooms for the second case, i.e. M = N + h*w It must visit approximately h*w times more rooms for the second case, i.e. M = N _ h_w It must visit approximately h + w additional rooms for the second case, i.e. M = N + h + w To determine the height and width of the original rectangle the robot needs to visit approximately h + w rooms. To determine the height and width of the second rectangle the robot needs to visit approximately 2h + 2w rooms. Thus, M = N + h + w.

Laboratory Session:

Exercise 1 - Square Grid

Suppose that the robot is currently in the upper left room (northwest) of a square space of rooms, i.e. the space contains the same number of rows and columns of rooms (like the one in Figure 1). Design an algorithm that allows the robot to compute the number of rooms that there are in the grid.

Instructions

1. Load the project CountingSquares into QtCreator. There are two ways to do this:

   • Using the virtual machine: Double click the file CountingSquares.pro located in the folder /home/eip/labs/repetitions-countingsquares of your virtual machine.
   • Downloading the project’s folder from Bitbucket: Use a terminal and write the command git clone http:/bitbucket.org/eip-uprrp/repetitions-countingsquares to download the folder repetitions-countingsquares from Bitbucket. Double click the file CountingSquares.pro located in the folder that you downloaded to your computer.

2. Configure the project. The project consists of various files. You will only write code in the file main.cpp. The rest of the files contain functions that implement the functionality of the instructions the robot can understand.

3. When writing your algorithm, you should make sure that the MainGameWindow object is created using the argument Mode::SQUARE_TOP_LEFT. Remember, the robot does not know beforehand how many rooms there are. Test your algorithm with some examples.

4. If the size of the grid is 3x3, how many rooms should the robot visit to complete your algorithm? How about 4x4? How about $n \times n$ rooms?

5. Suppose we want to minimize the amount of energy used by the robot. Can you create an algorithm that uses less steps for the same grid size?

6. Once you have finished your algorithm, and made it correct and efficient, hand it in using Deliverable 1 in Moodle. On the algorithm's header, write and explain the expression you found about the number of rooms the robot should visit to complete its task for a grid of size $n \times n$ (For example, "The robot takes 2x+5 steps, 5 to arrive at the middle and 2n to count the rest").

Exercise 2 - Rectangular Grid

Instructions

1. Suppose that now the robot is in the upper left room (northwest) of a rectangular space (not necessarily square) of rooms. Design an algorithm so the robot can compute the number of rooms in the grid.

2. To test this part of the program you should make sure the MainGameWindow object is created using the argument Mode::RECT_TOP_LEFT.

3. Once you have finished your algorithm, and made it correct and efficient, implement it in the main function. In the header of the program, write and explain the expression you found about the number of rooms the robot should visit to complete its task for a grid of size $m \times n$.

4. Hand in the main.cpp file with the code to calculate the number of rooms in a rectangular grid using Deliverable 2 in Moodle.

Exercise 3 - Rectangular Grid, Random Position

Instructions

1. Suppose that now the robot starts its task in any of the rooms in a rectangular grid (not necessarily square). Design an algorithm so the robot can compute the number of rooms there are in the grid.

2. To test this part of the program you should make sure the MainGameWindow object is created using the argument Mode::RECT_RANDOM.

3. Once you have finished your algorithm, and made it correctly and efficiently, implement it in the main function. In the header of the program, write and explain the expression you found about the number of rooms the robot should visit to complete its task for a grid of size $m \times n$. In this case, the number of rooms to visit will depend on the robot's initial position, so express the worst case, i.e. according to your algorithm, how many rooms should the robot visit if it starts in the worst room.

4. Hand in the main.cpp file with the code to calculate the number of rooms in a rectangular grid with the robot in a random position using Deliverable 3 in Moodle.

Exercise 4 - Pyramid Grid, Random Position

Instructions

1. Suppose that now the robot starts its task in any of the rooms in a grid shaped like a pyramid. Design an algorithm so the robot can compute the number of rooms there are in the grid.

2. To test this part of the program you should make sure the MainGameWindow object is created using the argument Mode::PYRAMID_RANDOM.

3. Once you have finished your algorithm, and made it correct and efficient, implement it in the main function. In the header of the program, write and explain the expression you found about the number of rooms the robot should visit to complete its task for a grid of size $m \times n$. In this case, the number of rooms to visit will depend on the robot's initial position, so express the worst case, i.e. according to your algorithm, how many rooms should the robot visit if it starts in the worst room.

4. Hand in the main.cpp file with the code to calculate the number of rooms in the pyramid with the robot in a random position using Deliverable 4 in Moodle.

Deliverables

Use the "Deliverable" links in Moodle to hand in the algorithm for Exercise 1 and the main.cpp files that contain the code you implemented in exercises 2, 3 and 4. Remember to use good programming techniques, to include the names of the programmers involved, and to document your program.

References

[1] Luther A. Tychonievich, Mark S. Sherriff, and Ryan M. Layer, http://nifty.stanford.edu/2015/tychonievich-sherriff-layer-counting-squares/