Practical 1
Due Date/Time
11:59pm, Sunday, April 7th, 2019
Background
When encoding messages one simple option is a substitution cipher. A substitution cipher replaces certain letters of the alphabet with other letters. For example, for each B in a message, a cipher may instead write Q and so on and so forth for the other letters of the alphabet. Unfortunately, a much more classic cipher was used last year, so this year I have produced a completely contrived one!!
Here is the logic. It is a variation on the idea, that you replace A with Z, B with Y, C with X and so on through the alphabet. In essence the first letter becomes the last letter. To make this arbitrarily annoying to program, I have decided to instead of just reversing from A to Z, the program should be able to arbitrarily shuffle from any start point to any end point. For example:
If I swap from C to F, all C’s becomes F’s, all D’s become E’s, all E’s become D’s, all F’s become C’s. All other letters remain unchanged.
Now, fortunately Unix has a function that will greatly simplify this process called translate (shortened to tr).
If given a few parameters, translate can perform an arbitrary cipher. For example:
tr ‘[abc]’ ‘[123]’
Will simply turn all a’s into 1’s, all b’s into 2’s and all c’s into 3’s.
Translate also has a neat hyphen syntax for translating consecutive characters.
tr ‘[a-m]’ ‘[A-M]’
… will convert the first 13 letters of the alphabet (a-m) from lower case to upper case! This won’t be particularly useful for this practical (or maybe it will?). However translate is essential for those who don’t want to lose their minds.
Task 1 (40 Marks)
Write a shell script called create_pattern.sh (the name must be EXACTLY correct) that takes two switches as parameters. The idea is that create_pattern will output a string suitable for translation that looks something like this:
tr ‘[ABC]’ ‘[CBA]’
The switches are defined as follows:
• -u: Where present (can be absent) will apply the rule to only UPPER CASE LETTERS
• -s: Will be followed by two parameters, both integers representing the first and last letter
(INCLUSIVE) which will be involved (and thus all the letters in between) where A=1 and Z=26 (whether upper or lower case).
If it is still not clear, here is an example:
• ./create_pattern -u -s 5 7
Will produce:
• tr ‘[EFG]’ ‘[GFE]’
If it is still not clear, here is an example: • ./create_pattern -s 15 19
Will produce:
• tr ‘[opqrs]’ ‘[srqpo]’
Please don’t do the opposite. I can’t be bothered writing two marking scripts • tr ‘[srqpo]’ ‘[opqrs]’
WARNING
There is a very stupid way to do this practical. You could write a giant if-else statement for each possible pair of input numbers. That said, given there are ~650 legal combinations… I mean, why would you do this? It will not be met with… happiness (by that I mean good marks or… marks).
Task 2 (20 Marks)
Create a second script called encode that takes the same two switches (and again allows any ordering). This script must read its input from stdin (line by line until eof is met) and each line will be encoded and written to standard out. It will perform this task by calling the first script to create the pattern and using that pattern in a call to tr. Do not assume the search path to your first script includes the current directory! (that is you should invoke the current script with a path starting: ./).
Task 3 (40 Marks)
Create a second script called decode that takes two parameters. The first parameter is the name of a file with an encoded message. The second file contains the same message unencoded. The goal is to determine what encoding was used to ‘encode’ the message and print out the two numbers corresponding to the start and end of the reversal string.
For example, if the unencoded message was: • cab driver
And the encoded message was: • bdc ariver
The expected return would be: •14
OR
• 14-u
If the encoding was upper case. There will be only one encoding on the sample text.
Note that the test cases will all be unambiguous (for example above, the answer must be 1-4) as ‘e’ in driver remains unaltered. It is possible for a mid-alphabet message that there are multiple solutions. The test cases will be selected to avoid this.
The simplest solution to this problem is brute force, by using the create_pattern.sh function to simply go through possible translations. This is fine. If you want to do it another way feel free (I encourage this). It should be possible to generate a much faster solution this way.
Detailed Submission Instructions
The handin key for this exercise is: prac1. The following SVN commands will enable you to make a repository for this assignment. Please note the following:
• Perform these steps in the order written once only!
• Replace a#######, where it appears in the commands, with YOUR student id.
• Some commands are long — they must be typed on one line.
Use the Unix “cd” command to change to the place where you want your exercise directory to be stored, then type these commands:
svn mkdir –parents -m “spc prac start” https://version- control.adelaide.edu.au/svn/a#######/2019/s1/spc/prac1
(creates this directory in your svn tree)
svn co https://version-control.adelaide.edu.au/svn/a#######/2019/s1/spc/prac1 . (checks out a working copy in your directory) You can now begin work.
You can add a file to the repository by typing the commands:
svn add NAME-OF-FILE
svn commit -m “REASON-FOR-THE-COMMIT”
where “reason-for-the-commit” should be some brief text that explains why you changed the code since the last commit. Note that you only need to add a file once — after that, SVN will “know” it is in the repository. You are now ready to commence working on the exercise.
Make sure you commit your files frequently, in case you have an accident. The University’s SVN repository is very reliable and is backed up regularly — your computer probably is not… Regular submission is also a good defence against plagiarism by others, since the submissions are dated. We will test the behaviour of your scripts using an automated tester. The tester is thorough and will find places where your scripts do not work correctly. If it finds an error, it will offer a (vague) hint. To encourage you to test your own work, the tester will not be fully available in the first few days before the exercise deadline.
The websubmission system (found here: https://cs.adelaide.edu.au/services/websubmission/) will award up to 75 marks automatically. We will manually check the code for style and commenting. Note that we reserve the right to deduct marks if your code does anything egregious or games the system to obtain marks.
Note again: all your files must be carefully commented to explain the logic of your code.