Week 07 Laboratory Exercises

Objectives

processing of characters and strings
use of functions
an introduction to encryption & decryption

Preparation

Before the lab you should re-read the relevant lecture slides and their accompanying examples.

Getting Started

Remote Working Survey

In light of recent events, COMP1511 is running a survey to identify how able students are to access course resources, and what timezone they're in. This information will be used to help us prepare for the next four weeks of tutorials, and for all our upcoming assessments.

You can submit a response to this survey as many times as you would like - if you need to update your response because your situation has changed, please submit a response again. This survey will remain open until the end of term.

Please fill out the survey here!

Exercise — in pairs:
Devowelling Text

Write a C program devowel.c which reads characters from its input and writes the same characters to its output, except it does not write lower case vowels ('a', 'e','i', 'o', 'u').

Your program should stop only at the end of input.

For example:

./devowel
Are you saying 'Boo' or 'Boo-Urns'?
Ar y syng 'B' r 'B-Urns'?
In this house, we obey the laws of thermodynamics!
In ths hs, w by th lws f thrmdynmcs!

Hint: hint use getcharto read characters (don't use scanf or fgets).

Hint: you need only a single int variable. Don't use an array.

Hint: use putchar to output each character.

Hint: make sure you understand this example program which reads characters until end of input.

Hint: make sure you understand this example program which reads characters, printing them with lower case letters converted to upper case.

Hint: create a function with a prototype like this:

int is_vowel(int character);

which returns 1 the character is a lower case vowel and 0 otherwise.

Hint: To tell the program you have finished typing, you can press Ctrl+D.

New! You can run an automated code style checker using the following command:

1511 style devowel.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest devowel

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab07_devowel devowel.c

Note, even though this is a pair exercise, you both must run give from your own account before Friday 05 April 20:00 to obtain the marks for this lab exercise.

Exercise — in pairs:
Its a Case of Swapping

Write a C program swap_case.c which reads characters from its input and writes the same characters to its output with lower case letters converted to upper case and upper case letters converted to lower case.

Your program should stop only at the end of input.

For example:

dcc swap_case.c -o swap_case
./swap_case
Are you saying 'Boo' or 'Boo-Urns'?
aRE YOU SAYING 'bOO' OR 'bOO-uRNS'?
In this house, we obey the laws of thermodynamics!
iN THIS HOUSE, WE OBEY THE LAWS OF THERMODYNAMICS!
UPPER !@#$% lower
upper !@#$% LOWER

Hint: hint use getcharto read characters (don't use scanf or fgets).

Hint: you need only a single int variable. Don't use an array.

Hint: use putchar to output each character.

Hint: make sure you understand this example program which reads characters until end of input.

Hint: make sure you understand this example program which reads characters, printing them with lower case letters converted to upper case.

Hint: create a function with a prototype like this:

int swap_case(int character);

which:

returns the character in lower case if it is an upper case letter
returns the character in upper case if it is a lower case letter
returns the character unchanged otherwise

New! You can run an automated code style checker using the following command:

1511 style swap_case.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest swap_case

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab07_swap_case swap_case.c

Note, even though this is a pair exercise, you both must run give from your own account before Friday 05 April 20:00 to obtain the marks for this lab exercise.

Exercise — in pairs:
Encrypting Text with a Caesar Cipher

Write a C program caesar.c which reads characters from its input and writes the characters to its output encrypted with a Caesar cipher.

A Caesar cipher shifts each letter a certain number of positions in the alphabet.

The number of positions to shift will be given to your program as the first line of input. The next lines of input will be the actual text to be shifted.

Characters other than letters should not be encrypted.

Your program should stop only at the end of input.

Your program should contain at least one function other than main.

For example:

./caesar
1
This life well it's slipping right through my hands
Uijt mjgf xfmm ju't tmjqqjoh sjhiu uispvhi nz iboet
These days turned out nothing like I had planned
Uiftf ebzt uvsofe pvu opuijoh mjlf J ibe qmboofe

./caesar
10
abcdefghijklmnopqrstuvwxyz
klmnopqrstuvwxyzabcdefghij
ABCDEFGHIJKLMNOPQRSTUVWXYZ
KLMNOPQRSTUVWXYZABCDEFGHIJ

./caesar
-42
Control well it's slipping right through my hands
Myxdbyv govv sd'c cvszzsxq bsqrd drbyeqr wi rkxnc
These days?
Droco nkic?

Hint: You will have to read the integer for the shift amount first, which will be followed by a newline, which is not part of the message to be encrypted.

Hint: handle upper and lower case letters separately

Hint: use %

Hint: create a function with a prototype like this:

int encrypt(int character, int shift);

which returns the character shifted by the specified amount

Manually Cracking a Caesar Cipher

Here is some (New Zealand) English text that has been encrypted with a Caesar cipher.

Z uf dp drbvlg ze jfdvsfup vcjv'j tri
Nv fiuvi uzwwvivek uizebj rk kyv jrdv srij
Z befn rsflk nyrk pfl uzu reu Z nreer jtivrd kyv kilky
Jyv kyzebj pfl cfmv kyv svrty, pfl'iv jlty r urde czri

Use the program you have just written to discover the secret text?

Hint:: try different shifts until you see English.

New! You can run an automated code style checker using the following command:

1511 style caesar.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest caesar

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab07_caesar caesar.c

Note, even though this is a pair exercise, you both must run give from your own account before Friday 05 April 20:00 to obtain the marks for this lab exercise.

Exercise — in pairs:
Encrypting Text with a Substitution Cipher

Write a C program substitution.c which reads characters from its input and writes the characters to its output encrypted with a Substitution cipher.

A Substitution cipher maps each letter to another letter.

The mapping will be given to your program as the first line of input. It will contain 26 characters: an ordering of the letters 'a'..'z'. The next lines will be the text to be encrypted.

Characters other than letters should not be encrypted.

Your program should stop only at the end of input.

Your program should contain at least one function other than main.

For example:

./substitution
qwertyuiopasdfghjklzxcvbnm
I was scared of dentists and the dark
O vql leqktr gy rtfzolzl qfr zit rqka
I was scared of pretty girls and starting conversations
O vql leqktr gy hktzzn uoksl qfr lzqkzofu egfctklqzogfl

./substitution
abcdefghijklmnopqrstuvwxyz
The identity cipher!!!
The identity cipher!!!

./substitution
bcdefghijklmnopqrstuvwxyza
The Caesar cipher is a subset of the substitution cipher!
Uif Dbftbs djqifs jt b tvctfu pg uif tvctujuvujpo djqifs!

New! You can run an automated code style checker using the following command:

1511 style substitution.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest substitution

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab07_substitution substitution.c

Note, even though this is a pair exercise, you both must run give from your own account before Friday 05 April 20:00 to obtain the marks for this lab exercise.

Exercise — in pairs:
Decrypting a Substitution Cipher

Write a C program decode.c which decrypts text encrypted by substitution.c

For example:

./decode
qwertyuiopasdfghjklzxcvbnm
O vql leqktr gy rtfzolzl qfr zit rqka
I was scared of dentists and the dark
O vql leqktr gy hktzzn uoksl qfr lzqkzofu egfctklqzogfl
I was scared of pretty girls and starting conversations

./decode
abcdefghijklmnopqrstuvwxyz
The identity cipher!!!
The identity cipher!!!
./decode
bcdefghijklmnopqrstuvwxyza
Uif Dbftbs djqifs jt b tvctfu pg uif tvctujuvujpo djqifs!
The Caesar cipher is a subset of the substitution cipher!

Your program will only be tested with an appropriate cipher input - but a good programmer would check the input is present and appropriate.

Manually Cracking a Substitution Cipher

This English text was encrypted with a substitution cipher.

Di jd, vdl'ht xtqa dh O qn
Vdl rdlwk O'ss wdkith htqromu omkd ok
O fhdwqwsv xdm'k
Styk kd nv dxm rtzoetj
Wlk kiqk'j kit royythtmet om dlh dfomodmj

Vdl'ht q ndlkiyls
Kiqk qndlmkj ydh qmdkith xtta dm nv dxm
Mdx O'n q mdzts nqrt htjdlhetyls
O jkqhk q eiqom xoki nv kidluik

Kqsa oj eitqf, nv rqhsomu
Xitm vdl'ht yttsomu houik qk idnt
O xqmmq nqat vdl ndzt xoki edmyortmet
O xqmmq wt xoki vdl qsdmt

What was the original text?

Hint: use frequency_analysis.c on the encrypted text and compare the frequencies to English letter frequencies and then try your guesses with decode.c

New! You can run an automated code style checker using the following command:

1511 style decode.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest decode

When you are finished working on this exercise, you and your lab partner must both submit your work by running give:

give cs1511 lab07_decode decode.c

Note, even though this is a pair exercise, you both must run give from your own account before Friday 05 April 20:00 to obtain the marks for this lab exercise.

Challenge Exercise — individual:
Working Out the Letter Frequencies of Text

Write a C program frequency_analysis.c which reads characters from its input until end of input.

It should then print the occurrence frequency for each of the 26 letters 'a'..'z'.

The frequency should be printed as a decimal value and an absolute number in exactly the format below.

Note upper and lower case letters are counted together.

For example:

./frequency_analysis
Hello and goodbye.

'a' 0.066667 1
'b' 0.066667 1
'c' 0.000000 0
'd' 0.133333 2
'e' 0.133333 2
'f' 0.000000 0
'g' 0.066667 1
'h' 0.066667 1
'i' 0.000000 0
'j' 0.000000 0
'k' 0.000000 0
'l' 0.133333 2
'm' 0.000000 0
'n' 0.066667 1
'o' 0.200000 3
'p' 0.000000 0
'q' 0.000000 0
'r' 0.000000 0
's' 0.000000 0
't' 0.000000 0
'u' 0.000000 0
'v' 0.000000 0
'w' 0.000000 0
'x' 0.000000 0
'y' 0.066667 1
'z' 0.000000 0
./frequency_analysis
Hey! Hey! Hey!
I don't like walking around this old and empty house
So hold my hand, I'll walk with you my dear

'a' 0.072289 6
'b' 0.000000 0
'c' 0.000000 0
'd' 0.084337 7
'e' 0.084337 7
'f' 0.000000 0
'g' 0.012048 1
'h' 0.096386 8
'i' 0.072289 6
'j' 0.000000 0
'k' 0.036145 3
'l' 0.084337 7
'm' 0.036145 3
'n' 0.060241 5
'o' 0.084337 7
'p' 0.012048 1
'q' 0.000000 0
'r' 0.024096 2
's' 0.036145 3
't' 0.048193 4
'u' 0.036145 3
'v' 0.000000 0
'w' 0.036145 3
'x' 0.000000 0
'y' 0.084337 7
'z' 0.000000 0

Hint: hint use getchar to read characters (don't use scanf or fgets).

Hint: make sure you understand this example program which reads characters until end of input.

Hint: use an array to store counts of each letter.

Hint: make sure you understand this example program which counts integers from the range 0..99.

New! You can run an automated code style checker using the following command:

1511 style frequency_analysis.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest frequency_analysis

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab07_frequency_analysis frequency_analysis.c

You must run give before Friday 05 April 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Challenge Exercise — individual:
Cracking A Caesar Cipher

Write a C program crack_caesar.c which decrypts text encrypted by an unknown Caesar cipher.

Your program should make no assumptions about the language of the original text - don't assume its English. However, you can assume the English alphabet ('a'..'z').

Your program will be given as a first line of input the name of a file containing a large amount of unencrypted text in the same language as the encrypted text.

For example for example your program might be given this file containing 188k characters of English text (wikipedia sentences from here)

Your program will be given the encrypted text on the next lines of input. It should print its decryption.

For example, here is some English text encrypted with a Caesar cipher with an unknown shift:

Kyzj zj fli crjk xffuspv
Z yrkv kf wvvc kyv cfmv svknvve lj uzv
Slk zk'j fmvi
Aljk yvri kyzj reu kyve Z'cc xf
Pfl xrmv dv dfiv kf czmv wfi
Dfiv kyre pfl'cc vmvi befn

So for example:

./crack_caesar
wiki_sentences.txt
Kyzj zj fli crjk xffuspv
Z yrkv kf wvvc kyv cfmv svknvve lj uzv
Slk zk'j fmvi
Aljk yvri kyzj reu kyve Z'cc xf
Pfl xrmv dv dfiv kf czmv wfi
Dfiv kyre pfl'cc vmvi befn

This is our last goodbye
I hate to feel the love between us die
But it's over
Just hear this and then I'll go
You gave me more to live for
More than you'll ever know

You may assume the filename given on the first line of input is at most 1000 characters.

You may assume the encrypted text of stdin contains at most 10000 characters.

You may assume the unencrypted example text in the file contains at most 250000 characters.

Hint: use fopen to open the file and fgetc to read the file. These won't be covered in lectures, so read this example program to see how to use this functions to read a file.

Hint: read all the encrypted text into an array, then decrypt it.

New! You can run an automated code style checker using the following command:

1511 style crack_caesar.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest crack_caesar

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab07_crack_caesar crack_caesar.c

You must run give before Friday 05 April 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Extra-hard challenge: Cracking A Substitution Cipher (individual - attempt if you dare)

Write a C program crack_substitution.c which decrypts text encrypted by an unknown s cipher.

Your program should make no assumptions about the language of the original text - don't assume its English. In other words don't hard code English properties into your program, extract the statistical properties from the sample plain text. However, you can assume the English alphabet ('a'..'z').

Your program will be given as its first line of input the name of a file containing a large amount of unencrypted text in the same language as the encrypted text.

Your program will be given the encrypted text on the next lines. You may read it all before printing the decryption.

For example:

./crack_substitution
wiki_sentences.txt
M'ka paat dra qegbu, ueta md xbb
Rxu vw fxya teq
Umxvetup, ogmbbmxtd, mt Oab-Xmg teq
Red psvvag tmlrdp, vmu Jsbw
Qrat wes xtu M qaga negakag qmbu
Dra fgxzw uxwp, fmdw bmlrdp
Dra qxw wes'u cbxw qmdr va bmya x frmbu
Qmbb wes pdmbb beka va
Qrat M'v te betlag westl xtu oaxsdmnsb?
Qmbb wes pdmbb beka va
Qrat M'ka led tedrmtl osd vw xfrmtl pesb?
M yteq wes qmbb, M yteq wes qmbb
M yteq drxd wes qmbb
Qmbb wes pdmbb beka va qrat M'v te betlag oaxsdmnsb?
M'ka paat dra qegbu, bmd md sc
Xp vw pdxla teq
Frxbbatlmtl xtlabp mt x taq xla teq
Red psvvag uxwp, gefy t gebb
Dra qxw wes cbxw neg va xd wesg preq
Xtu xbb dra qxwp, M led de yteq
Wesg cgaddw nxfa xtu abafdgmf pesb

I've seen the world, done it all
Had my cake now
Diamonds, brilliant, in Bel-Air now
Hot summer nights, mid July
When you and I were forever wild
The crazy days, city lights
The way you'd play with me like a child
Will you still love me
When I'm no longer young and beautiful?
Will you still love me
When I've got nothing but my aching soul?
I know you will, I know you will
I know that you will
Will you still love me when I'm no longer beautiful?
I've seen the world, lit it up
As my stage now
Challenging angels in a new age now
Hot summer days, rock n roll
The way you play for me at your show
And all the ways, I got to know
Your pretty face and electric soul

You may assume the encrypted text on stdin contains at most 10000 characters.

You may assume the unencrypted example text in the file contains at most 250000 characters.

Hint: you will need to look at the probabilities of sequences of 2 or perhaps 3 letters occurring or perhaps the probabilities of words.

Hint: use fopen to open the file and fgetc to read the file. These won't be covered in lectures, so read this example program to see how to use this functions to read a file.

An autotest is available to help you test your program but because this is a difficult problem it is possible very good attempts at the problem won't pass the autotests.

New! You can run an automated code style checker using the following command:

1511 style crack_substitution.c

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest crack_substitution

When you are finished working on this exercise, you must submit your work by running give:

give cs1511 lab07_crack_substitution crack_substitution.c

You must run give before Friday 05 April 20:00 to obtain the marks for this lab exercise. Note that this is an individual exercise, the work you submit with give must be entirely your own.

Submission

When you are finished each exercises make sure you submit your work by running give.

You can run give multiple times. Only your last submission will be marked.

Don't submit any exercises you haven't attempted.

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember you have until Week 7 Sunday 20:00 to submit your work.

You cannot obtain marks by e-mailing lab work to tutors or lecturers.

You check the files you have submitted here

Automarking will be run by the lecturer several days after the submission deadline for the test, using test cases that you haven't seen: different to the test cases autotest runs for you.

(Hint: do your own testing as well as running autotest)

After automarking is run by the lecturer you can view it here the resulting mark will also be available via via give's web interface

Lab Marks

When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine:

1511 classrun -sturec