COMP281 2019-2020 – 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: [email protected] * * 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 11-Mar-2020 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. 1081 Title: Game of Life Description In this assignment, you will code a simulation called “Game of Life”. It is a very famous ‘game’ and the formed the basis of an entire field of simulation models called “cellular automata”. Before continuing reading this assignment, I suggest you read a bit more about Game of Life at: https://en.wikipedia.org/wiki/Conway’s_Game_of_Life or http://www.math.com/students/wonders/life/life.html (the latter also has a nice Java applet of the game that is quite fun to play with!) You should now know about the basics of game of life: it is a ‘simulation’ of cells that are ‘dead’ or ‘alive’ in discrete time steps, at every step all of the cells will get computed a new value in parallel (i.e., based on the values of the neighbours at the *previous* time step – this will require a little bit of thinking!), and the rules to determine if a cell is dead or alive are: -Any live cell with fewer than two live neighbours die, as if caused by under population. -Any live cell with two or three live neighbours lives on to the next generation. -Any live cell with more than three live neighbours dies, as if by overpopulation. -Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. You now need to write a program that reads in an initial ‘board’ configuration, and then performs a specified number of simulations. As always, try and keep your program clean, modular, and only allocate as much memory as you need (using malloc). Input The first line will specify 3 numbers: -the number of rows -the number of columns -the number of steps you need to simulate The remainder of the input file comprises the initial configuration, which will have exactly the specified number of rows and columns. Dead cells are indicated with ‘.’ while live cells are marked with ‘X’. Output As output, you will need to write the board configuration that results from the specified number of simulations, in exactly the same format as you read the input. Sample Input 6 6 20 .X…X X.X.X. X…X. X..XX. ..XX.X …X.X Sample Output …X.. ..X.X. ..X.X. …X.. …… …… 2. 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;
