CSE2303 / CSE2304 Prac #0 semester 1, 2000

A final version of prac#0 is here: [/~dwa/CSE2303/prac0.ps](postscript).
It is strongly based on the following...

Rough Draft, Practical #0, week 1, semester 1, 28 February - 3 March, 2000

http://www.csse.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/2000/prac00.html

The point of this (unmarked) prac' is to increase your familiarity with the Linux / Unix operating system, particularly editing, compiling and running C-programs. You must do it!

A friend of mine likes to do the word puzzle in The Age,
e.g. The Age, 11/9/'99:

H	E	R
L	O	T
B	A	T

The point of the puzzle is to form as many words as possible, each of four letters or more, from the given letters; each letter can only be used once and the centre letter must be used in every word. The "jewel" is the 9-letter word (or words), and it is particularly satisfying to be able to drop it in casual conversation. Let's get some computer help! For this exercise we are only interested in words using all of the letters.

The main task for this practical is to write a C-program, `permute', which takes a string of characters as a command-line parameter, e.g. `permute HERLOTBAT', and prints all permutations of the string, one per line. (Beware, there are a lot, so start with short strings.)
There is an example program using command-line parameters [click here] and a C program to permute a fixed string [click here].
NB. Your program must be able to permute any string of any length.

The Unix program `spell' produces an alpbetically ordered list of those words from the input that spell believes to be incorrect. It can read from `standard input', e.g. typing

spell                        -- i.e. run the spell program
camputer                     -- this is
computer                     -- data
control_D                    -- i.e. end of input data

gives the output:

camputer

(The control_D key combination, often written `^D', indicates end-of-input from the keyboard.)
spell more commonly reads from a file, e.g. `spell input_file'.

I/O-redirection can be used to connect standard-input (<) or standard-output (>) of any program to files, e.g. `spell input_file > output_file' leaves the output of spell in the file called `output_file'.

The Unix program `sort' does what its name suggests, e.g. `sort unsorted_file > sorted_file'.

The Unix program `uniq' removes duplicate lines from a sorted file.

A pipe connects two or more programs together. e.g. `permute HERLOTBAT | sort | uniq > perms' runs permute, sorts its output, and removes duplicates, leaving the result in the file `perms'. The pipe operator is the vertical bar `|'.

The Unix program `diff' compares two files and shows which lines need to be changed to convert the first file into the second file. It produces a list of the edit commands needed to make this change. After each command any affected lines from the first file are shown preceded by `<'. Any affected lines from file two are shown preceded by >'. Therefore if we have:

file_1:  camputer         file_2:  camputer
         computer

the output of `diff file_1 file_2' is

2d1
< computer

i.e. go to line 2 of file one and delete one line; the line happens to be `computer', a valid word.

Use the manual command, `man', e.g. `man spell' and `man diff', to find out more about spell and diff. What does `spell -b' do?

We are now ready to run our puzzle solver:
1. Use (your) program `permute' to write all permutations of the given letters to a file, `perms', e.g. `permute HERLOTBAT | sort | uniq > perms'

ABEHLORTT                    -- NB. no duplicates
ABEHLOTRT
 ...
TTROLHEBA

2. Run spell on the output, i.e. `spell perms > rejects'.
3. Now use `diff perms rejects' to find the valid words that are permutations of the original input string.
4. And the answer is . . . . . . . . . ?

Note that all of the separate stages above can be optionally wrapped up in a shell script so that only a single command need be typed to carry out the whole process.