MUIC Homework 2 System Skill: Vertical Histogram, ToInt, Entab/Detab Utility, Game of life and Unscramble
Homework 2 System Skill
This assignment will give you practice on basic C programming. You will implement a few C programs, test them thoroughly, and hand them in. To work on Tasks 4 and 5, you will need a few starter files.
Collaboration
We interpret collaboration very liberally. You may work with other students. However, each student must write up and hand in his or her assignment separately. Let us repeat: You need to write your own code. You must not look at or copy someone else’s code. You need to write up answers to written problems individually. The fact that you can recreate the solution from memory will be taken as proof that you actually understood it, and you may actually be interviewed about your answers. Be sure to indicate who you have worked with (refer to the hand-in instructions).
Hand-in Instructions
To submit this assignment, please follow the steps below:
- Zip up all the scripts and name it a2.zip i.e.
zip a2.zip vert_hist.c roman.c tabutil.c life_engine.c unscramble.c
- LogontoCanvas,gotoassignment2submissionpageandsubmityourzipfilethere. If you collaborate with another student, include in your zip file a README file indicating your collaborators and the extent to which you work together.
Homework 2 System Skill
Task 1: Vertical Histogram (15 points)
You will write a program that prints a histogram of frequencies of letters in the English alphabet. The input will come from stdin. Your program should downcase all input letters and ignore symbols besides a to z. The output is a histogram rendered vertically. Please make sure you must support reading multiple lines if you pipe the input from a file using the cat command. Code and Compilation: Your code will be one standalone file called vert_hist.c. Use the following command to generate an executable vert_hist. Your code must compile clean with this command. gcc -Wall -W -pedantic -o vert_hist vert_hist.c Example: Below is an example assuming vert_hist has been compiled and lives in the current directory. Each * represents a count of 1. echo This Is a TeST--Hello, MississippI. Yippie | ./vert_hist
abcdefghijklmnopqrstuvwxyz
Hint: Learn about the function getchar. Furthermore, you can use cat and pipe to test this program.Forexample,thecommand“cat poem.txt | ./vert_hist”willreadpoem.txtandsend it to the stdin of your program.
Hint #2: A few functions in ctypes.h will prove to be useful. For example, what does tolower do? How about isalpha? Use the man command to find out.
Task 2: ToInt (5 points)
Inthistask,youwillwriteafunctionint toInt(char* Roman)thattakesinacharacterarraythatis formatted in Roman Numeral and convert this to an integer. You must also write the main function that takes the into from the stdin using scanf to test your code. Code and Compilation: Your code will be one standalone file called roman.c. Use the following command to generate an executable roman. Your code must compile clean with this command. gcc -Wall -W -pedantic -o roman roman.c
Hint: The similar functions and library from Task 1 will be useful here as well.
Task 3: Entab/Detab Utility (10 points)
The tab character ('\t') is both useful and annoying. You will write a program, called tabutil.c, with the following features:
• tabutil -d
Task 4: Game of Life (25 points)
In this problem, you will be implementing Conway’s Game of Life. Back in 1970, British Mathematician J. H. Conway created the Game of Life, a simulation of a population of lifeforms over generations. The simulation takes place on a 2-dimensional grid. We provide a description of the Game of Life below.
For many of you, this is your very first time programming in C. For this reason, we have done the design work for you, providing function prototypes, each of the function skeletons, and ample comments to help you get started.
The Game of Life The Game of Life takes place on a 2-dimensional grid. Each grid cell can house zero or one organism. The game starts with an arbitrary initial grid—that is, some cells are inhabited and some are empty. Cells that are occupied are alive; the other cells are dead. From this initial grid, the next generation of population is obtained by the following rules: • a cell has 8 neighbors, those cells that immediately surround it vertically, horizontally, and diagonally (on both diagonals). • Ifacellisaliveandhas2or3liveneighbors,itwillremainaliveinthenextgeneration. • Ifacellisaliveandhasfewerthan2liveneighbors,itwilldieofloneliness. • Ifacellisaliveandhas4ormoreliveneighbors,itwilldieofsuffocation. • Ifacellisdeadandhasexactly3liveneighbors,aneworganismwillbeborninthatcell.Otherwise, it remains dead in the next generation. • Importantly: All births and deaths take place at exactly the same time. That is to say, all the cells’ neighbors are counted simultaneously, based on the current generation, before the next generation is produced. This means, for example, that it is possible for a new cell to be born out of current live neighbors that will be dead in the next generation. In the original game, the rules assume an infinite grid in all directions. However, we can only store a finite-sized grid, so what to do with cells that are beyond our finite grid? For this problem, treat any cell that isn’t on the finite grid as dead. To gain a better understanding of the game, you can find a simulator at http://pmav.eu/stuff/ javascript-game-of-life-v3.1.1/. Use this to ensure that you understand the rules and to deter- mine whether or not your implementation is working correctly.
Your Task
We have prepared for you the following files:
• life_engine.c-thefilecontainingfunctionstubsthatyouwillcomplete,thoughsomefunc- tions have already been written for you.
• life_engine.h - the header file (that you will not modify) corresponding to functions and datatypes used in the simulation. Even though you aren’t changing this file, you should look through it.
• life_driver.c-the“driver”codethatwillmakeuseofyourfunctionsinrunningagameoflife simulation.Oncecompiled(seebelow),yourunitaslife
Task 5: Unscramble (25 points)
You will write a program that takes in 2 files: a dictionary file and a file listing jumbled words. Your binary will be called unscramble and will be run using
unscramble
nwae: wean anew wane eslyep: sleepy rpeoims: semipro imposer promise ettniner: renitent ahicryrhe: hierarchy dica: acid cadi caid dobol: blood nyegtr: gentry cukklen: knuckle warllc: NO MATCHES addej: jaded baltoc: cobalt mycall: calmly dufil: fluid preko: poker ... lines omitted .. milit: limit pudmy: dumpy hucnah: haunch genjal: jangle (When a word doesn’t unscramble to any dictionary word, you’ll say “NO MATCHES” as shown in the example above.) Logistics: Your code should follow good programming style. This includes writing each logical unit of code in a self-contained function that is not too long. We’re a little impatient: On the sample input, we are willing to wait only up to around 3 seconds on Hamachi. The sample files can be found in the handout directory (see the beginning of this handout). Code and Compilation: Your code will be one standalone file called unscramble.c. Use the following command to generate an executable unscramble. Your code must compile clean with this command. gcc -Wall -W -pedantic -o unscramble unscramble.c
ASSUMPTIONS: For ease, you can assume that no words are longer than 50 letters and the dictionary file contains no more than 500,000 words. TIPS: You should observe that a word s unscrambles to a dictionary word w if when you sort the letters of s lexicographically and similarly sort the letters of w , they result in the same sequence of letters. For example, sorted("eslyep") is eelpsy, which is the same as sorted("sleepy"). Furthermore, it is easy to sort an array (or a string—i.e., an array of characters) using the built-in function qsort
