COMP281 2021-2022 – 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.
28 Feb 2022
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
https://sam.csc.liv.ac.uk/COMP/CW_Submissions.pl
Only the file submitted through this link will be marked.
• The deadline for this assignment submission is Monday 14-Mar-2022 at 12: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 1090
Title: Sorted count of the unique words in a piece of text.
Description
Write a program that reads in some 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 word is of at most 30 characters in length) in ASCII (which
may include some punctuation characters that must be removed). This input text will contain at most 300 unique words
(each of which may appear several times in the input text). 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 characters), filter any non-alpha
characters from the words, and store them. A count of the number of times each word is found in the text should be
maintained, to be output at the end of the processing.
The output should be an alphabetically sorted series of words, composed of lowercase characters. Each unique word
(along with its associated count) should be output. Write your own sort routine (do not use a library or third party
function).
Think carefully about the memory efficiency of your code in order to achieve the highest marks for your solution. It
would be very inefficient use of memory to always create an array of 300 31-byte strings irrespective of the size of the
input text, so although you may wish to create an array to hold up to 300 items, you should malloc the storage for the
individual strings as you need them, storing a pointer to them into the appropriate array element. Additional marks will
be awarded for the use of a structure for the word string and frequency count, and for the use of malloc and pointers.
Input
A number of lines of text (each of 100 characters at most, featuring 0 or more words of at most 20 characters each).
Output
An alphabetically sorted list of search words and their frequency counts. Each line of the output should be in the
following format: a unique word from the input text, followed by a space, a “=>” string another space, and then an
integer count of how many times that word was found in the text.
Sample Input
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
all => 2
and => 14
arms => 1
as => 2
awhile => 1
back => 1
bandersnatch => 1
beamish => 1
beware => 2
bird => 1
bite => 1
blade => 1
borogoves => 2
boy => 1
brillig => 2
burbled => 1
by => 1
callay => 1
callooh => 1
came => 2
catch => 1
chortled => 1
claws => 1
come => 1
day => 1
dead => 1
did => 2
eyes => 1
flame => 1
foe => 1
frabjous => 1
frumious => 1
galumphing => 1
gimble => 2
gyre => 2
hand => 1
hast => 1
he => 7
head => 1
his => 2
in => 6
it => 2
its => 1
jabberwock => 4
jaws => 1
joy => 1
jubjub => 1
left => 1
long => 1
manxome => 1
mimsy => 2
mome => 2
my => 3
o => 1
of => 1
one => 2
outgrabe => 2
raths => 2
rested => 1
shun => 1
slain => 1
slithy => 2
snickersnack => 1
so => 1
son => 1
sought => 1
stood => 2
sword => 1
that => 2
the => 20
thou => 1
thought => 2
through => 3
time => 1
to => 1
took => 1
toves => 2
tree => 1
tulgey => 1
tumtum => 1
twas => 2
two => 2
uffish => 1
vorpal => 2
wabe => 2
went => 2
were => 2
whiffling => 1
with => 2
wood => 1
HINTS
It is easier to compare two strings if they are converted to the same case (uppercase or 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 is called 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 could start by writing a program to read the input text and write out each word as it creates it from the input stream.
You might find the string library function strtok() useful for this. When you can successfully do this, the next stage
is to store each word in a data structure in your program.
You could use an array of pointers, each of which point to a structure that holds both a string and an integer count of the
number of occurrences of the string.