Fall 1994 Waterloo Local Contest #2

  1. Question 1 There's a Hole in the Bucket
  2. Question 2 Graph Colouring
  3. Question 3 Othello
  4. Question 4 What's an Anagram?
  5. Question 5 Run-Length Encoding

Question 1 There's a Hole in the Bucket

put caption here...

You are likely familiar with the story of Henry an Liza and the hole in the bucket. Not too many people know what happened after Henry managed to fix the hole in his bucket.

Liza, after the hole affair, was pretty upset with Henry. In an effort to get him to think, she had him fill a barrel with several different buckets. The barrel had to be filled exactly to the top by whole (or is that hole?) bucket quantities. Henry, being lazy, kept thinking about it until he could do it in the fewest buckets possible.

The Input:

The input will be a series of lines. The first line will contain a single number representing the size of the barrel in litres. The second and following lines each contain a single number representing the sizes of the available buckets, in litres.

The Output:

The output will be a single number representing the fewest buckets it takes to fill the barrel.
Sample Input A:		Sample Input B:		Sample Input C:
17			20			36
1			7			19
2			5			9
4			3			5
5			1			2
						1

Sample Output A:	Sample Output B:	Sample Output C:
4			4			4

Limits:

The barrel will never be greater than 40 litres. The pails will never be larger than the barrel, nor will there be more than 10 pails.

Question 2 Graph Colouring

Painting by Numbers...

Definition: Graph
A graph G is a finite set, V(G), of objects called ``vertices'', together with a set, E(G), of unordered pairs of distinct vertices. The elements of E(G) are called ``edges''.
Definition: Graph Colouring
A graph colouring is a finite set, C, of colours and vertex labelling function, w:V(G) -> C such that for all (u,v) in E(G), w(u) != w(v).
Definition: Chromatic Number
The chromatic number of a graph is the smallest, integer size of a set of colours that can colour that graph.

Problem:

Given a graph, output its chromatic number.

The Input:

Each graph is a list of edges separated by semi-colons ``;'', and ending with a blank edge (i.e. a double semi-colon, ``;;''. Each edge shall be a comma ``,'' separated pair of vertices, labelled by a positive integer. Any amount of white space may occur between numbers and punctuation.

Example, this is a square:

1, 2; 2, 3; 3, 4; 4, 1;;

The Output:

A single integer which is the chromatic number of the graph.

For the square above, the answer is ``2''.


Question 3 Othello

Mobility is the answer...

One of the questions during the last contest was one about Othello. This one too is about Othello. In this problem, you must find the valid moves for both black and white. This process is the basis of many Othello programs.
 abcdefgh
1........
2........
3........
4...o*...
5...*o...
6........
7........
8........
The board starts initially as above. Pieces are added, alternating between black and white, starting with black. A piece can be added on any square where there are interposing pieces of the opposite colour between that square and another of the same colour as the piece being played. No blanks can separate the pieces in question. All interposing pieces so bracketed are then changed to be the same as the colour played. Play can go on any horizontal, vertical or diagonal line. As an example, from the above starting position, black can play on squares c4, d3, f5, and e6. If we looked at white's possible moves, white could play on squares c5, d5, e3, and f4.

Input:

The input will be eight lines of eight characters, with `.' for empty squares, `*' for black, and `o' for white. With that input, decide which colour has valid moves, e.g.:
........
........
..ooo...
.*o*o*..
.ooooo..
...*....
........
........

Output:

A single line:
(Black-White)=-6
The value above (-6) is the number of black moves minus the number of white moves, as indicated.

Limits:

There will be no more than 36 possible moves for either black or white.

Question 4 What's an Anagram?

Fun with words...

Anagram -- a word or phrase formed by transposing the letters of another word or phrase.

Your task is to find all sets of anagrams that exist within a given dictionary of words. The input will be a list of words, one per line which will be incidentally sorted (being a dictionary and all...). The output shall consist of each of the sets of anagrams on a separate lines, the members separated by a single space (no trailing spaces). Please note that each set should be in alphabetical order, and all lines of sets should also be in alphabetical order. A word with no anagrams is considered a set of anagrams itself, and should be displayed with no modifications.

Input:		Output:
canter		canter centra nectar recant trance
centra		destain instead sainted stained
destain		least slate stale steal
instead		post pots stop
least		start
nectar
post
pots
recant
sainted
slate
stained
stale
start
steal
stop
trance

Limits

There will be no more than 4000 words in the list, each word in lowercase letters. The resultant sets will be no more than 128 characters long. The words will be between 4 and 15 characters long.

Question 5 Run-Length Encoding

Simple compression...

The problem:

Many data files (such as pictures) are characterised by large runs of repeated data. These files can be compressed using a technique called run-length encoding (RLE). For this problem, you will need to implement a variant of RLE.

The basic idea behind RLE is to replace, say, 20 consecutive occurrences of the character `.', with the number 20 and a single `.'. This variant allows runs to be longer than one character. For example, the sequence abcabcabcabcabc should be converted into 0503abc. The first two characters, 05, are a pair of digits specifying how many times the pattern is repeated; the next two characters, 03, are the length of the repeated pattern, and that many characters following (abc) is the pattern to be repeated, itself.

Each compression saves a certain number of characters. The digits are not to be counted in considering the length of the compressed sequence. In the example above, 12 characters were saved. Each string to be compressed will probably consist of more than one repeated pattern. For example, the string abcdabcdabcdefefefefgggggg should turn into 0304abcd0402ef0601g.

When compressing a string, always start by compressing the repeated sequence that saves the most characters first, and then compress what's left over on the left, and on the right. For example, the string aabbaabbbbaabb should be compressed as 0201a0206bbaabb and not as 0204aabb0106bbaabb or 0204aabb0202bb0202aa0202bb. If more than one such sequence exists, pick the longer one. If more than one have the same length, pick the one further to the right.

If a string has no repeating sequences, output it with no digits in front.

You will receive a number of lines of text on standard input. These lines will not contain digits. You are to compress each one as described above, and write your answer to standard output. Use one line of output for each line of input.

Sample Input:

abcdabcdabcdefefefefgggggg
aabbaabbbbaabb
bananananas fors fors
aaaaa a a aaaaaa
aaaaa a a aaaa

Sample Output:

0304abcd0402ef0601g
0201a0206bbaabb
ba0402nas0205 fors
0401a0302a 0601a
0501a0302 a0301a

Philip Chong
pchong@calum.csclub.uwaterloo.ca
http://csclub.uwaterloo.ca/u/pchong