CMPT 111: Assignment #8
Draft 1
Arrays
Lab session: Week of Nov 21-25
Due date: Nov 25, 2011, 8:00pm
Notes:
This assignment is individual work. You may discuss the questions and problems with anyone, but the work you hand in for this assignment should be your own work.
Hand in your work using Moodle. The tutorial exercise in Week 3 shows you how to do this. After you upload something, check that it really is on Moodle. If your file is too big, Moodle will silently reject it, and the marker will see an empty file.
Every file you submit to Moodle must have an appropriate file extension, reflecting the type of the file. See Files and file types from the first tutorial if you are unsure about this requirement. If you submit a file with no file type, or with the wrong file type, the marker may not even try to open it, and you'll get 0 for that question.
Please submit cpp files only for your source code! Do not submit whole projects! Projects will not be graded. You can find your cpp files in <workspace>/<project>/src
Question 0 (0 marks)
Please go to https://evaluation.usask.ca to fill out the course evaluation for this course. It will only take you about 5 minutes, and is of immense value to your instructors. The evaluations help us determine what we are doing right, and what we are doing wrong.
You will not be able to fill in this evaluation prior to Monday Nov 21.
Question 1 (16 marks)
This is a multipart question. Do the parts in order; we are guiding you through the process of creating an interesting (at least we think it's interesting) piece of software, and if you do the parts out of order then you may get mixed up. This program will read in a representation of an ASCII art image, decode it the representation, and allow the user to display the image in a few different ways.
Background: ASCII Art
ASCII art is an image representation that uses plain text characters to "draw" an image in a text window; that is, rather than using color (or grayscale) pixels as the basis of the image, it uses text characters. For example:
\\\\\\\\|/////\
\\\\\\\\\|//////\
\\\\\\\\I////////\
\\\\\\\I//////////\
\IIIIII\I\//////////\
/****/*\////////////\
/****/***\////////////\
/****/*****|////////////|
J$$$$$$$$$$$$$$$******\////////////|
J$$***************$$$$$***|///////////
$$**********************$$L. \\\\\\\\\/
.$***************************$$L
.J$$$$$$$$$************************$L
.J$$*********$$$$$$$$$$$***************$$
J$$$***********************$$$$$$$$*********$
$$**********************************$$$$$$$***$
$*****************************************$$$$$
$********$$$$$$*************************$***$$
$******$$$$$$$$$$$$$$$$$$$$************$*****$$
$**$$$$ $$$$$$$$$$$$$$$$$ $$$$$$$$****$******$
~~ $$$ %%$$$$$$$%% $$$$$$$$$$$$$$****$
$$$ %% $$$ %% $$$$$$$$$$$$$$*#$$*$
$$$ $$$ $$$$$$$$$$$$$$*#****$
$$$$$ $$$$$ $$$$$$$$$$$$$*#*****$
$&&$$$$$$$$$$$$$$$$$$$$$$$$$$%**##*****$
$&&&&&$$$$$$$$$$$$$$$$$$$$$$$%**#******$
$&&&&&&&$$$$$$$$$$$$$$$$$$$$$$#########$ ---< Where's the KA-BOOM!
$&&&&&&&&&&% ~T$$$$$$$$$$$$$$T~********$ There was suppose to
$&&&&&&&&T' OOOOOOOOOOOO********$ be an earth-shattering
OOOOOOOOOOOOOOOO KA-BOOM!!!
OOOOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOOOO by: Mark Stahlsmith
OOO/OOOOOOOOOOOOO/OOOOOO
Background: RLE
Runlength encoding (RLE) is a simple method for image compression. That is, it is an algorithm that can be used to reduce the amount of space that is required to store an image in a file. It is the primary method employed by the .bmp image file format that used to be commonly used on Windows-based computers.
The algorithm compresses an image by identifying "runs" of "pixels" that are identical, and instead of storing every pixel separately it will store a number indicating how many of the pixel there are in the run, followed by the value of the pixel. For example, the string of text (each character in the string is a "pixel") "AAAAABBBBBBCCCCCDEFFFFFFFFFAAAAA" would be runlength encoded as "5A6B5C1D1E9F5A". The runlength encoded string can then be decoded by the following algorithm:
while not done
{
read in a number, N
read in a character, c
add N duplicates of c to the image
}
In this assignment we are going to give you ASCII art that has already been runlength encoded, and by doing the assignment questions, you will decode it into a two-dimensional array of characters. You will then print out the ASCII art in several different ways, as chosen by the user of your program.
For example, consider the text "11+8.2+8.2+8.11+". This is not arithmetic! It represents 11 '+' followed by 8 '.' followed by 2 '+' etc. If we use the decoding algorithm above to ddecode the text into a 4 row by 10 column ascii art image then your two-dimensional array will have the following characters in it:
++++++++++
+........+
+........+
+........+
++++++++++
The runlength encoding that we will use in this assignment will add a single colon (':') between the number of times to repeat a character for the run, and the character to repeat; this will allow our ASCII art to have digits in it, if required. So, instead of using the string "11+8.2+8.2+8.11+" as a runlength encoding for your program, we will use "11:+8:.2:+8:.2:+8:.11:+".
Outline
You are going to start your program by writing the functions that will print out the contents of a two-dimensional array of characters in parts 1 through 4. Part 1 will give you a function that can be used to verify that your ASCII art decoder is functioning correctly; parts 2 through 4 are just variations of part 1 that will be used to display the ASCII art in different ways.
Once your display functions are complete, you can write the function for decoding ASCII art and you will have the ability to test it. In part 5 you are asked to write the function that will input the decoded ASCII art via the console, and decode it into a two-dimensional array of characters.
In part 6 you are asked to complete your program: the program will read in a piece of encoded ASCII art, decoded it, and then display it right-side up, upside down, backwards, and upside down and backwards.
Part 1
a)
Start by writing a single function that will have as input (through parameters): a single two-dimensional array that is 80 rows by 80 columns; an integer, R, indicating the number of rows that are being used in the array; and an integer, C, indicating the number of columns that are being used in the array.
This function has no return value.
This function will print out R rows and C columns of the two-dimensional array to the console. Each row will be on a line by itself; so, you should print out an endline after each row.
You may call this function whatever you wish, but must identify in a comment that the function is for part 1.
b)
Create a second function called "testing" that has no input and no return value. You will be using this function to test part 1, and all other parts of this question.
In the body of this function you should declare a single two dimensional array of characters with 80 rows and 80 columns, and then initialize the array (using nested loops) so that the element at row r and column c contains the character described by the following expression: 'a' + ((r+c)%26). (Yes, this is a valid C expression for a character!)
After your array has been declared and initialized, you are to write a couple of function calls to your function from (a) to print out parts of the array; you will find it easier to read the console output of your program if you print a newline between each function call. For example, if you call your function with values of 5 and 10 for R and C, respectively, then your program will print out:
abcdefghij
bcdefghijk
cdefghijkl
defghijklm
efghijklmn
c)
Call your testing function from your main() function.
At this stage, your main() function should only contain a call to your testing function and a return statement.
Part 2
Now you will write a function like the one in part 1a, only it should display the array upsidedown.
For example, if you call this function with 5 and 10 for R and C, respectively, then your function will print out:
efghijklmn
defghijklm
cdefghijkl
bcdefghijk
abcdefghij
This is the same set of characters as in the example of part 1a, except the order of the rows is different.
The easiest way to do this is to copy your function from part 1a into a new function, and name the copy of the function something else. Change the copy of the function so that it prints out the desired portion of the array upsidedown. Identify in the comments for this function that it is for part 2.
Test your function by adding a few different calls to it, with different values of R and C, to your testing function.
Part 3
Now you will write a function like the one in part 1a, only it should display the array backwards.
For example, if you call this function with 5 and 10 for R and C, respectively, then your function will print out:
jihgfedcba
kjihgfedcb
lkjihgfedc
mlkjihgfed
nmlkjihgfe
This is the same set of characters as in the example of part 1a, except the order of the columns is different.
The easiest way to do this is to copy your function from part 1a into a new function, and name the copy of the function something else. Change the copy of the function so that it prints out the desired portion of the array backwards (i.e. mirrored left-right). Identify in the comments for this function that it is for part 3.
Test your function by adding a few different calls to it, with different values of R and C, to your testing function.
Part 4
Now you will write a function like the one in part 1a, only it should display the array upsidedown and backwards.
For example, if you call this function with 5 and 10 for R and C, respectively, then your program will print out:
nmlkjihgfe
mlkjihgfed
lkjihgfedc
kjihgfedcb
jihgfedcba
This is the same set of characters as in the example of part 1a, except the order of the rows and columns is different.
The easiest way to do this is to copy your function from part 1a into a new function, and name the copy of the function something else. Change the copy of the function so that it prints out the desired portion of the array upsidedown and backwards (i.e. mirrored left-right and upsidedown). Identify in the comments for this function that it is for part 4.
Test your function by adding a few different calls to it, with different values of R and C, to your testing function.
Part 5
For this part you will be writing the function that reads, and decodes, a runlength encoded piece of ASCII art. See the above section on runlength encoding for the format that the input through the console will have.
This function will have as input (through parameters): a single two-dimensional array that is 80 rows by 80 columns; an integer, R, indicating the number of rows in the ASCII art; and an integer, C, indicating the number of columns in the ASCII art.
The very first line of this function should be the code:
cin >> noskipws;
This will tell cin to not ignore whitespace when reading in a single character.
The very last line of this function should be the code:
cin >> skipws;
This will tell cin to start ignoring whitespace again.
Note: You will have to #include <iomanip> in your program for this to work.
You can test that your function works by creating an 80 row by 80 column two-dimensional array of characters in your main function, calling your new function with that array and an R of 5 and a C of 10, then calling your function from part 1a with an R of 5 and a C of 10. If you run your program, and copy & paste the text "11:+8:.2:+8:.2:+8:.11:+" (without the double-quotes) into your console then your program should print out the box that you see in the discussion of runlength encoding above.
Part 6 (the final step)
Now, you are going to use all of the pieces that you have assembled to complete your program that will:
Read in an encoded ASCII art image from the console, and then
Call your function from part 1a using the decoded ASCII art as input, and then
Call your function from part 2 using the decoded ASCII art as input, and then
Call your function from part 3 using the decoded ASCII art as input, and finally
Call your function from part 4 using the decoded ASCII art as input.
Please cout a couple of blank lines, or a line of minus signs between each of items 2 through 5 from the above list. Printing out this extra text will make it easier for the marker to see the parts of your output.
The following are a few text files that you can copy & paste into the console when you run your program to provide data for ASCII art; only use one image per run.
Marvin the Martian
Barnie Rubble
Homer Simpson
The format for these text files is as follows:
On the first line are two integers: R and C
On the next line is the encoded ASCII art. When unencoded this ASCII art with have R rows, and C columns.
Note: To read in the encoded ASCII art, you will need to read the values of R and C in your main() function, and then call your function from part 5 with the values of R and C that you read in.
Note2: Immediately after reading the values of R and C, but before you call your function from part 5, you must have the following two lines of code:
string flushNewline;
getline(cin, flushNewline);
Since there is an end-of-line between the value of C and the start of the encoded ASCII art, you must read the <enter> keypress at the end of the first line before calling your function from part 5. That is what these two lines of code do.
Purpose:
Learning the syntax for two-dimensional arrays.
To study a "proper" decomposition of a complex program into small, and managable, functions.
What to hand in:
Prior to handing in your source file: within Eclipse select all of the text in your source file (press control-A to select all text), and then select the "Correct Indentation" option from the "Source" menu (or press the shortcut: control-I [that's an eye, not an ell]).
Your source file for this question entitled "a8q1.cc" or "a8q1.cpp" that contains all of your code from parts 1 through 7; part marks are available, so hand in whatever you have.
A text document (word doc, rtf file, plain text) called "a8q1" (with the appropriate extension) containing the contents of the console from a run of your program that demonstrates that everything is working correctly. Pick one of the encoded ASCII art files to copy & paste to the console, and demonstrate the output of your program.
Evaluation:
0/X: Nothing submitted, or cannot open files for reading.
1 mark for identification in the files (Name, NSID, Student number, lecture and lab section)
2 marks for each of your functions from parts 1a, 2, 3, and 4.
2 marks for your complete testing function from part 1b extended to testing all of parts 1 through 4
4 marks for your decoding function for part 5
2 marks for putting it all together for part 7