COMP281 2020-2021 – Assignment 2
• In the following, you will find the problems that constitute Assignment 2. They will be also available
on the online judging (OJ) system available at https://student.csc.liv.ac.uk/JudgeOnline
• You need to write a C program (not C++ or C#) that solves each problem – it must read the input, as
specified in the problem description then print the solution to the given problem for that input.
o Note that code is “correct” only if it correctly implements a solution to the problem stated
in the assignment, not "if online judge accepts it".
o That is, even if OJ accepts your code, it could be wrong. Read the problems carefully.
• Input is read from the standard input, in the same way that you read input from the keyboard as shown
in lectures (e.g., using scanf). Output is also printed to the standard output, as you have seen (e.g.,
using printf).
• When you are satisfied that your C programs work correctly, you must submit them through the
departmental submission system.
o Even if the program is not correct, still submit whatever you have! You can still earn points if
certain parts of the code are done right.
• You must also include a brief report describing your solutions to the problems. This should be
maximum two sides of A4 paper and should give a description of how each of your solutions works.
This should include describing the algorithm used to reach the solution, describing your use of any C
language features (that were not discussed in lectures) and identifying any resources that you have
used to help you solve the problems.
• This assignment is worth 50% of the total mark for COMP281.
o Both problems are weighted equally.
o For each problem, you can earn a total of 50 points
§ 25 points for “Functionality and Correctness” awarded for programs that correctly
solve the problem for all test cases.
§ 20 points for “Programming style, use of comments, indentation and identifiers”
awarded depending on the style, comments and efficiency of the solution
§ 5 points for the quality and depth of the accompanying report
o The final grade results from normalising the earned points to a scale of 100.
o See separate “comp281-detailed-marking-guidelines.pdf” for more details.
Submission Instructions
• Create a folder, and name it using your Student ID and User ID, e.g. 201234567_sgpj6 • In the folder, there should be 3 files:
o 1 report file, in PDF format. Name it with your Student ID and User ID, e.g.
201234567_sgpj6.pdf
o 2 source code files. Name each using the Problem Number, e.g. 1006.c
§ In your source code, include your Student Info and Problem Info, e.g.:
/*
* Student ID: 201234567
* Student Name: Phil Jimmieson
* Email: phil.jimmieson@student.liverpool.ac.uk
*
* User: sgpj6
*
* Problem ID: 1006
* RunID: 22456
* Result: Accepted
*/
§ The OJ provides a RunID, which is different from the Problem ID.
§ The Result is one of the following: Accepted, Wrong Answer, Presentation Error, Time
Limit Exceeded, Memory Limit Exceeded, Output Limit Exceeded, Runtime Error,
Compile Error.
• Compress the folder into a single zip file, and name it as, e.g. 201234567_sgpj6.zip
o Use the standard (pkzip) zip file format:
https://en.wikipedia.org/wiki/Zip_%28file_format%29
which is supported by winzip, winrar, etc. on Windows/Mac OS X, and 'zip' on Linux
o Test your zip file before submitting.
• Submit this zip file using the departmental submission system at
http://www.csc.liv.ac.uk/cgi-bin/submit.pl
Only the file submitted through this link will be marked.
• The deadline for this assignment submission is 18-Mar-2021 at 17:00
• Penalties for late submission apply in accordance with departmental policy as set out in the student
handbook, which can be found at: http://intranet.csc.liv.ac.uk/student/ug-handbook.pdf
1. Problem 1086
Title: Run Length Encoding of ASCII Art
Description
In the very early days of computing, images were produced using ASCII characters. Such ASCII Art was very popular
and, since storage was limited, simple techniques were developed to compress such images. One such simple
technique of lossless compression was Run Length Encoding. This scans an input image for runs (sequences) of 2 or
more identical values, and replaces them with two such characters followed by an INT string representing a count of
the number of characters, and terminated by a * e.g.
A line from a piece of ASCII Art image as follows:
,,,,,,]F 8,
which is composed of 6 commas, a closed square bracket, a capital F, 48 spaces an eight and a comma, would be
represented as:
,,6*]F 48*8,
Write a program to accept as input either the letter "C" or the letter "E" followed by a carriage return. Each subsequent
line of input data until EOF contains image data.
If the initial input was "C" this represents "compress", and the lines of input text represent an ASCII Art image.
Process this input to compress it using the rules specified above, and output the compressed version.
If the initial input was "E" this represents "expand", and the lines of input text represent a compressed ASCII Art
image. Process this input and expand it using the rules referred to above. Print out this uncompressed ASCII Art
image.
You can test your program by compressing an ASCII Art image, saving the output to a file, editing the file to add E as
the first line, then feeding this back into your program to effectively reproduce the original ASCII Art image. If your
program is working correctly then the original image and your compressed then decompressed version should be
identical.
Input
Either an ASCII art file with a C on the first line (this will be compressed using RLE)
or
A compressed ASCII art file with an E on the first line (this will be expanded).
Output
After compressing an input file, all runs of two or more of any character should be replaced by two of the character, an
integer count and a star.
After expanding an input file, all previously compressed sequences should be replaced by the original character runs.
Sample Input
C
#####
####### #**#!!###
#**#!!!!## #****#!!!!#
#****###!!!# #*****#!!!!#
#*******#!!!# #******#!!!!#
#*********#!###!*!*!*#!!!!!# --
#!*!*!*!*!*!#!##########!!!!# /_
###########!##!!!!!!!!!!#!!!# //__
###!!!!!!!!!!!#!!!!!!!!!!!!!#!!!####/// \ \ ##!#!!!!!!!!!!!#!!!!!!!!!!!!!!!#!!!!!!!#
_\ ##!!#!!!!!!!!!!!#!!!!!!!!!!!######!!!!!!!*#
\\ ##!!#!!!!!!!!!!!!#!!!!####### #!!!!!!***#
___\\#!!!###################***** #...!!*****#
/ \#!!!.# ***** # *** #....*******#
#*....# *** # #.......*****#
#**.....## ***** ##........!!****#
#!........## *******#########......#...!!!!!*#
#!...........#######.*****...............#.#..!!!!**#
#*.....##.............#..#...............#...#.!!****#
#*....#.#............#....#............##......!*****#
#*.......##.......###......###........#.......!!!****#
#*.........#######......!!....########.......!!!!!***#
#!!!.................!!!!!!!!.............!!!*******#
#!!!!............!!!!!!!!!!!!!!!!!!!!!!!!!!!******#
#*******!!!!!!!!!!!!!!!!!!!!!!!!!!!!***!!!!*****#
#******!!!!!!!!!!!!!!!!!!!!!!!!!********!!****#
##*****!!!!!!!!!!!!!!!!!!!!!#*************###
##****!!!!!!!!!!!!!!!!!!!!!###******####
####!!!!!!!!!!!!!!!!!!!!!!!!######!#
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*#
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!***##
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!******#
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*******#
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*****#
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!**#
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!##
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*##
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!***#
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!####!!!!!!****##
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!###****##!!!!******##
#!!!!!!!!!!!!!!!!!!!!!!!!!!!!!##**!!*****#!!!********#
#!!!!!!!!#!!!!!!!!!!!#!!!!!!!#***!!!!***!!!!**********#
#!!!!!!!!!!#!!!!!!!!!#!!!!!!!#****!!!!!*!!!!!!!!!!*****#
#!!!!!!!!!!!#!!!!!!!#!!!!!!!#*!!***!!!!!!!!!!!!!!!!!***#
#!!!!!!!!!!!!#!!!!!!#!!!!!!#*!!!!!*!!!!!!!!!!!!!!!*****#
#!!!!!!!!!!!!#!!!!!!#!!!!!#***!!!!!!!!!!!!!!!!!********#
#!!!!!!!!!!!!!#!!!!!!#!!!!!#****!!!!!!!!!!!!!!**********#
#!!!!!!!!!!!!!#!!!!!!#!!!!!#*****!!!!!!!!!!!!!!*********#
#!!!!!!!!!!!!!#!!!!!!#!!!!!#***!!!!!!!!!!!!!!!!!********##
##!!!!!!!!!!!!!#!!!!!!#!!!!!#*!!!!!!!!!!!!!!!!!!!!!*****#!*##
#!#!!!!!!!!######!!!!!!#!!!!!#**!!!!!!!!!!#########!!!!*#!!**##
#!#!#!!!!!!#!!!!!!!!!!!!#!!!!!#***!!!!!####******!!!#######!!**#
#!#!!##!!!!#!!!!!!!!!!!############*!!!#********!!!!!!!!!!!!!!!**#
#!#!!#!#!!#!!!#!!!!!!!#!!!!!!!!!!!!!!!#***********!!!!!!!!!!!!!!!#
#!#!!!#!#!#!!#!!!!!!!#!!!!#!!!!#!!!!!#**********!!!!!!!!!!!!!!!**#
#!!#!!!#!##!!#!!!!!!#!!!!#!!!!#!!!!!!#************!!!!!!!!!!****#
######### ##########!!!!#!!!!#!!!!!!#**********!!!!!!!!!!!!***#
#################************!!!!!!!!!!**#
#**********!!!!!#########
###############
Sample Output
32*##5*
18*##7* 6*#**2*#!!2*##3*
17*#**2*#!!4*##2* 3*#**4*#!!4*#
16*#**4*##3*!!3*# 2*#**5*#!!4*#
16*#**7*#!!3*# #**6*#!!4*#
16*#**9*#!##3*!*!*!*#!!5*# 8*--2*
16*#!*!*!*!*!*!#!##10*!!4*# 6*/_
16*##11*!##2*!!10*#!!3*# 5*//2*__2*
13*##3*!!11*#!!13*#!!3*##4*//3* 2*\
3*\ 7*##2*!#!!11*#!!15*#!!7*#
3*_\ 4*##2*!!2*#!!11*#!!11*##6*!!7**#
4*\\2* 2*##2*!!2*#!!12*#!!4*##7* 5*#!!6***3*#
2*__3*\\2*#!!3*##19***5* 7*#..3*!!2***5*#
/ 3*\#!!3*.# 7***5* # 5***3* 8*#..4***7*#
5*#*..4*# 8***3* 3*# 14*#..7***5*#
4*#**2*..5*##2* 10***5* 10*##2*..8*!!2***4*#
4*#!..8*##2* 7***7*##9*..6*#..3*!!5**#
3*#!..11*##7*.**5*..15*#.#..2*!!4***2*#
2*#*..5*##2*..13*#..2*#..15*#..3*#.!!2***4*#
2*#*..4*#.#..12*#..4*#..12*##2*..6*!**5*#
2*#*..7*##2*..7*##3*..6*##3*..8*#..7*!!3***4*#
2*#*..9*##7*..6*!!2*..4*##8*..7*!!5***3*#
3*#!!3*..17*!!8*..13*!!3***7*#
4*#!!4*..12*!!27***6*#
5*#**7*!!28***3*!!4***5*#
6*#**6*!!25***8*!!2***4*#
7*##2***5*!!21*#**13*##3*
9*##2***4*!!21*##3***6*##4*
11*##4*!!24*##6*!#
15*#!!30**#
15*#!!29***3*##2*
14*#!!29***6*#
13*#!!29***7*#
12*#!!32***5*#
11*#!!35***2*#
10*#!!39*##2*
9*#!!41**##2*
8*#!!43***3*#
8*#!!33*##4*!!6***4*##2*
7*#!!31*##3***4*##2*!!4***6*##2*
7*#!!29*##2***2*!!2***5*#!!3***8*#
7*#!!8*#!!11*#!!7*#**3*!!4***3*!!4***10*#
6*#!!10*#!!9*#!!7*#**4*!!5**!!10***5*#
6*#!!11*#!!7*#!!7*#*!!2***3*!!17***3*#
6*#!!12*#!!6*#!!6*#*!!5**!!15***5*#
6*#!!12*#!!6*#!!5*#**3*!!17***8*#
5*#!!13*#!!6*#!!5*#**4*!!14***10*#
5*#!!13*#!!6*#!!5*#**5*!!14***9*#
5*#!!13*#!!6*#!!5*#**3*!!17***8*##2*
4*##2*!!13*#!!6*#!!5*#*!!21***5*#!*##2*
3*#!#!!8*##6*!!6*#!!5*#**2*!!10*##9*!!4**#!!2***2*##2*
2*#!#!#!!6*#!!12*#!!5*#**3*!!5*##4***6*!!3*##7*!!2***2*#
#!#!!2*##2*!!4*#!!11*##12**!!3*#**8*!!15***2*#
#!#!!2*#!#!!2*#!!3*#!!7*#!!15*#**11*!!15*#
#!#!!3*#!#!#!!2*#!!7*#!!4*#!!4*#!!5*#**10*!!15***2*#
#!!2*#!!3*#!##2*!!2*#!!6*#!!4*#!!4*#!!6*#**12*!!10***4*#
2*##9* ##10*!!4*#!!4*#!!6*#**10*!!12***3*#
22*##17***12*!!10***2*#
38*#**10*!!5*##9*
39*##15*
Hint
You'll need to use a mono-spaced font to view the art correctly (proportionally spaced fonts distort the layouts).
Use scanf to retrieve individual characters from the standard input and process them as you read them in (no need to
store them in arrays).
You can convert a digit char to an int value (i.e. '1' => 1, '2' => 2 etc) using:
intValue = ((int) inputChar) - 48;
2. Problem 1088
Title: Matching Word Count
Description
Write a program that accepts as input an ASCII string (a word) of max length 20 characters. This
word is the search term that your program will use. It should then read in the remaining input text
(e.g. a poem), which features a series of lines (each of no more than 100 characters in length)
comprising zero or more words (each of at most 20 characters) in ASCII (which may include some
punctuation characters that must be removed). Your C program should process that text into a series
of individual words (i.e. strings separated from one another by space, comma or full-stop), filter any
non-alphabetic characters from the words, and compare them with the search word. A count of the
number of times the search word is found in the text should be maintained, and printed out at the end
of the processing.
The output should be the search word, along with a count of how many times that word was found in
the text.
Input
A word of at most 20 characters on a line on its own, followed by a number of lines of text (each of 100
characters at most, featuring 0 or more words of at most 20 characters each)
Output
The search word, followed by a “=>” string and then an integer count of how many times that word was
found in the text.
Sample Input
jabberWock
The Jabberwock
Twas brillig, and the slithy toves
Did gyre and gimble in the wabe:
All mimsy were the borogoves,
And the mome raths outgrabe.
Beware the Jabberwock, my son!
The jaws that bite, the claws that catch!
Beware the Jubjub bird, and shun
The frumious Bandersnatch!
He took his vorpal sword in hand;
Long time the manxome foe he sought
So rested he by the Tumtum tree
And stood awhile in thought.
And, as in uffish thought he stood,
The Jabberwock, with eyes of flame,
Came whiffling through the tulgey wood,
And burbled as it came!
One, two! One, two! And through and through
The vorpal blade went snicker-snack!
He left it dead, and with its head
He went galumphing back.
And hast thou slain the Jabberwock?
Come to my arms, my beamish boy!
O frabjous day! Callooh! Callay!
He chortled in his joy.
Twas brillig, and the slithy toves
Did gyre and gimble in the wabe:
All mimsy were the borogoves,
And the mome raths outgrabe.
Sample Output
jabberWock=>4
HINTS
It is easier to compare two strings if they are converted to uppercase (or to lowercase) first.
Your program needs to process text until an EOF is encountered (indicating the end of the text). When testing
your program yourself (not via online judge), it is difficult to generate an EOF on some platforms. It is simpler
to prepare your test input data in a text file, and then pipe that data into your program using “<” e.g. if your
program has been compiled into the a.out file then:
./a.out < sourcetext.txt
will send the contents of sourcetext.txt into your program, and when all the contents of that file have been
processed, your program will receive an EOF on the input stream.
You might find the string library function strtok() useful to solve this problem.