Programming Fundamentals

• This page contains extra challenge exercises for week 07.
• These exercises are not compulsory, nor do they provide any marks in the course.
• These exercises are intended for students that want more challenge in the course.
• You cannot submit any of these exercises, however autotests are available for them (Command included at bottom of each exercise).

You are given an array of odd length n, where n < 20,000. All the integers but one will have a duplicate in the array. Your task is to find the integer in the array with no duplicate.

Examples

dcc odd_one_out.c -o odd_one_out
./odd_one_out
How many numbers will you enter? 9
2 93 2 4 24 26 93 24 26
The odd one out is: 4
./odd_one_out
How many numbers will you enter? 10
You must pick an odd number!

Everyone is welcome to attempt this challenge! This is doable with concepts within the scope of COMP1511. However, those may not be optimal in either speed or memory usage.

The real challenge is to use the XOR bitwise operator, which is outside of the scope of COMP1511. This will be much faster and memory efficient and after scanning in all the numbers, finding the odd one out can be done using only a single loop. This is for students who are keen to learn new concepts and challenge their current understanding.

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

1511 autotest odd_one_out

Write a program called count_file_lines.c that takes in a file name from the terminal and prints out the number of lines in that file

Creating a file

At this point in the course, you have created C files for all your exercises. Text editors such as VSCode are capable of handling any type of file containing text. We are going to open a new file with VSCode that we will access in our C program. Run the following command:

code text_file.txt

Now, put whatever text you want inside of this file. For our example, we will use:

We're no strangers to love
You know the rules and so do I
A full commitment's what I'm thinking of
You wouldn't get this from any other guy

Opening a File

The first important thing to do is make sure you have #include <stdio.h> in your program. From here, you can include the line:

FILE *file = fopen("text_file.txt", "r");

On the left-hand side, we are creating a variable file that is a pointer to a FILE. You do not need to understand what FILE is, just know that it is the type of data that file wants to point at.

On the right-hand side, we are calling a function fopen(). This function takes in the name of the file that we want to read as well as the "mode" to access the file. There are many modes to access the file in, however, we are using "r" as this corresponds to "read" since we want to read the file in our case.

As an overview, this line of code is creating a pointer to the file we just created, which we can now access in our C program!

Reading from a file

Now, reading a line from the file is almost identical to how we read lines from the terminal.

First, we create an array of characters to read the line into:

char line[MAX_SIZE];

Then we can use fgets() in a very similar manner:

fgets(line, MAX_SIZE, file);

The difference in fgets() here is that we have replaced stdin with file. In simple terms, fgets() will take input from whatever place the third parameter points to. In the case of stdin it will take input from the terminal and in the case of file, it will take input from the file we specified.

We can now print out the contents of line like so:

printf("%s", line);

And we should receive this in the terminal:

We're no strangers to love

If we were to call fgets() in exactly the same way as before, it will then scan the next line of the file which we could print out.

Run the commands below and compile the C file optained to see how the text file can be printed.

Download file_example.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/24T1/activities/count_file_lines/example_file_io/file_example.c .

Download text_file.txt here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/24T1/activities/count_file_lines/example_file_io/text_file.txt .

Back to the program

Now that we understand files, we can continue. In this exercise, you are to write code in count_file_lines.c that takes a file name as input and prints out how many lines are in that file.

You will need to make your own files to test this as none will be provided. Some examples are provided below, you can assume that the files provided will have the correct number of lines seen in the output.

Examples

dcc count_file_lines.c -o count_file_lines
./count_file_lines
super_secret_file.txt
'super_secret_file.txt' contains 7893 lines.
./count_file_lines
meaning_of_life.txt
'meaning_of_life.txt' contains 42 lines.
./count_file_lines
count_file_lines.c
'count_file_lines.c' contains 34 lines.

</stdio.h>

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

1511 autotest count_file_lines

Write a C program crack_substitution.c which decrypts text encrypted by an unknown substitution 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.

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. You may read it all before printing the decryption.

Examples

dcc crack_substitution.c -o crack_substitution
./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

Assumptions/Restrictions/Clarifications

• You may assume the filename given on the first line of input is at most 1000 characters.
• 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.

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

1511 autotest crack_substitution