UNSW Programming Competition 1997

Preliminary Round: Advice to Competitors

At the start of the competition you should receive a copy of the description of the six tasks that the team may attempt over the available two hours. We have provided a range of tasks of varying difficulty: we expect that very few teams will be able to complete all, or even most of the tasks. Do not be discouraged if you don't get many of them done. There is no pass mark, and points are given to indicate relative difficulty. Even solving one problem is an achievement.

The computer you will use should by now contain a directory UNSWPC97 in which you will find separate directories TASKA, TASKB, and so on to TASKF (If they haven't been installed, copy and unzip the file UNSWPC97.ZIP found on your supervisor's competition disk). These directories contain test files with which to exercise your programs. In particular, files of the form TEST1.DAT, TEST2.DAT store input data for the program you will write. To establish how well your program works you need to print a copy of the program output for each of these files. Your supervisor will also ask you at the end of the time period to print program listings for each task at least partially completed.

Because you have to share a single computer you may that find the best strategy is to work on two or three tasks simultaneously (one or two people on each task). The programs should be clearly written and neatly formatted. Do not worry about fancy user interaction: all input will come from a test file. The printed copy of each test run can either be a printed text file or a screen dump.

Good luck. No doubt you will find the competition challenging, but hopefully also rewarding.

Summary of Tasks

Task key	Title	Points (basic)	Points (max)
A	Quiz Generator	5	12
B	Word Count	8	8
C	Date Conversion	10	12
D	Phrase Matching	15	20
E	Noughts & Crosses Checker	15	20
F	Investigating Chaos	12	18

Solutions

Solutions are available to most of the tasks in the preliminary round. Rather than simply making code available, each solution link leads to a page that discusses approaches to solving the task, and presents algorithms in a language-neutral form. Some solutions expressed in Basic, C or Pascal can be downloaded, but the files are encrypted with a simple rotation cipher to make you do some work to see them.

Task A: Quiz Generator

Description

A fill-in-the-blanks quiz can be produced simply by replacing strings in a block of text by underscore characters (_). Write a program to generate a numeric quiz by copying input to output replacing each digit character by an underscore.

Example

Input	Output
In 1935 the Marx Brothers made their 6th film, "A Night at the Opera", the first without the 4th Marx Brother, Zeppo.	In ____ the Marx Brothers made their _th film, "A Night at the Opera", the first without the _th Marx Brother, Zeppo.

Input

Output

In 1935 the Marx Brothers
made their 6th film,
"A Night at the Opera",
the first without the 4th
Marx Brother, Zeppo.

In ____ the Marx Brothers
made their _th film,
"A Night at the Opera",
the first without the _th
Marx Brother, Zeppo.

Extensions

The basic task is worth 5 points. Two extensions are possible for additional points:

For an additional 2 points, precede each replacement string by the next lower-case letter enclosed in parentheses, starting with (a). For example:

Input	Output
In 1935 the Marx Brothers made their 6th film, "A Night at the Opera", the first without the 4th Marx Brother, Zeppo.	In (a)____ the Marx Brothers made their (b)_th film, "A Night at the Opera", the first without the (c)_th Marx Brother, Zeppo.

Input

Output

In 1935 the Marx Brothers
made their 6th film,
"A Night at the Opera",
the first without the 4th
Marx Brother, Zeppo.

In (a)____ the Marx Brothers
made their (b)_th film,
"A Night at the Opera",
the first without the (c)_th
Marx Brother, Zeppo.

For a further 5 points, include the answers at the bottom of the quiz:

Input	Output
In 1935 the Marx Brothers made their 6th film, "A Night at the Opera", the first without the 4th Marx Brother, Zeppo.	In (a)____ the Marx Brothers made their (b)_th film, "A Night at the Opera", the first without the (c)_th Marx Brother, Zeppo. Answers: (a) 1935 (b) 6 (c) 4

Input

Output

In 1935 the Marx Brothers
made their 6th film,
"A Night at the Opera",
the first without the 4th
Marx Brother, Zeppo.

In (a)____ the Marx Brothers
made their (b)_th film,
"A Night at the Opera",
the first without the (c)_th
Marx Brother, Zeppo.
Answers:
(a) 1935
(b) 6
(c) 4

Constraints

The following limits are placed on valid input. Invalid inputs may be ignored.

Input length:	no explicit limit
Number of digit strings:	26
Maximum length of any digit string:	100 characters

Solution

Discussion here.

Task B: Word Count

Description

A word is defined as a sequence of one or more non-space characters sorrounded by spaces or the beginning or end of a line. A word need not contain letters. Write a program that counts the number of words and lines in its input.

Example

Input	Output
I sell the best brandy and sherry To make good customers merry But at times their finances Run short, as it chances, And then I feel very sad, very. -- John O'Tuomy (1706-77), innkeeper of Limerick.	`36 words on 7 lines`

Scoring

The task is worth 8 points.

Constraints

Input will always be a properly formed text file. To assist in counting words and lines on the screen, in every test file there will not be any blank or empty lines following the very last word. Lines containing only blank characters or no characters can occur earlier in the text, however. You should not be concerned about this.

Solution

Discussion here.

Task C: Date Conversion

Description

For some purposes it is useful to store dates in the form YYYY/DDD, where YYYY is the year and DDD is an integer representing the number of days since the beginning of the year. Some accounting systems work this way, as do astronomical dates (with times as a fraction of the day!).

Write a program that accepts any number of dates in the above format, one per line, and prints each one followed by the date in the more familiar Day Monthname Year form. The list is terminated by a zero year.

Example

Input	Output
1997/1 2000/60 1985/366 1985/365 0000/0	1997/1 1 January 1997 2000/60 29 February 2000 1985/366 Date out of range 1985/365 31 December 1985

Scoring

The basic task is worth 10 points. The number of days in each month should be defined in one place in the program; judges will deduct points if numbers are scattered throughout the program listing.

Extension

An additional 2 points will be awarded for the correct handling of all four-digit leap years, not just those between 1901 and 2099. It is a little-known that years that are a multiple of 100 (the last year of each century) are not leap years unless they are also a multiple of 400. Thus

Input	Output
1900/60 2400/366 2100/60 0000/0	1900/60 1 March 1900 2400/366 31 December 2400 2100/60 1 March 2100

Constraints

Only inputs consisting of two integers separated by a / are required to be processed. All test files meet this requirement. Note that if the day number is incorrect, processing continues as usual after the program displays the "Date out of range" message.

Solution

Discussion here.

Task D: Phrase Matching

Description

You're probably familiar with word game that goes like this: given a key word, find as many other words as you can that can be made up from the letters of the key word. The letter at each position in the key word can be used only once. For example, a new word can only have two Ns if there were at least two Ns in the key word.

Write a program that reads a key word or phrase followed by other words or phrases, and determines whether each phrase can be obtained from the letters of the key phrase in the manner described above. The spaces between words of the key phrase are significant and are matched like letters. The number of phrases to be tested will be provided on the first line of input, and every phrase is on a separate line.

The program's output consists of the key phrase on one line, then each following phrase and its classification in capitals (YES or NO) on one line. You may assume that the phrase will consist only of lower case letters and spaces.

Examples

Single word:

Input	Output
7 determination nation mine mines rare tram note tram note	determination nation YES mine YES mines NO rare NO tram YES note YES tram note NO

Phrase with two words:

Input	Output
5 fawlty towers rats fat towels two fat flys watery fowls flowery twits	fawlty towers rats YES fat towels YES two fat flys NO watery fowls YES flowery twits NO

Scoring

The basic task is worth 15 points.

Extension

An additional 5 points will be awarded if the program detects a duplicate phrase, reporting DUP instead of YES or NO. For example,

Input	Output
6 sprightly lass light pass salty git light pass haggis light haggis	sprightly lass light pass YES salty git NO light pass DUP haggis NO light YES haggis DUP

Constraints

There will be no more than 100 phrases to test, and each phrase (including the key phrase) will consist of no more than 60 characters. Processing may (optionally) terminate on encountering an invalid input line.

Solution

Discussion here.

Task E: Noughts & Crosses Checker

Description

The game of Noughts & Crosses (also known in North America as Tic-Tac-Toe) is played by two people on a 3x3 grid. One player places noughts (0) at any unoccupied place on the grid and the other places crosses (X), players taking turns. The winner is the first to produce three of their symbols in a straight line, either horizontally, vertically or diagonally. A draw results when neither player has won and there are no more blank spaces. In this version of the game assume that either player may have started.

Write a program that reads in a picture of a Noughts and Crosses board, then classifies the result of the game, if a result has been obtained. Possible responses are

X wins
0 wins
Draw
Incomplete

Examples

Input	Output
X \| 0 \| ----------- X \| X \| 0 ----------- 0 \| 0 \| X	X wins

Input	Output
X \| 0 \| ----------- X \| 0 \| X ----------- 0 \| 0 \| X	0 wins

Input	Output
X \| 0 \| X ----------- 0 \| X \| X ----------- 0 \| X \| 0	Draw

Input	Output
0 \| \| ---------- \| 0 \| X ----------- 0 \| \| X	Incomplete

Scoring

The basic task is worth 15 points.

Extension

Up to an additional 5 points will be awarded if the program can also detect an impossible board position, such as

Wrong number of X or 0 symbols (say 3 Xs but only one 0)
More than one winner

Constraints

The input will consist of five lines as shown in the examples. The three rows of the grid are the first, third and fifth lines of the input. The three columns are the second, sixth and tenth character positions on these lines. Upper case X is used to represent a cross and zero (0) is used to represent a nought. An unused position contains a space character.

Error checking may be limited to verifying that the nine grid positions contain one of the three legal characters (X, 0 or space). The characters in the positions marking out the grid lines and spacing can be ignored. Processing should terminate on encountering an invalid input line.

Solution

Discussion here.

Task F: Investigating Chaos

Important Note: This task may look more complicated than it really is. While the basic programming task is not very difficult, to understand what is required you should try to follow the (rather long) description.

Description

Some dynamic systems act in an orderly and predictable way. Others, like the weather or the stock market, exhibit unpredictable and ultimately chaotic behaviour. Chaos theory is the study of simple mathematical equations that model such behaviour.

Many of the equations that produce chaos are iterative formulae. In an iterative formula the value of an expression is used as a parameter for the next evaluation of the expression, as for example,

p' = p + 1

If we start with p=1 and keep replacing p by p' then this generates the sequence

1, 2, 3, 4, 5, ....

The formula that you will investigate is slightly more complicated:

p' = p + k * p * (1-p)

The parameter k has an important influence on the sequence of p-values, which normally starts at p = 0.3. If k is small, between 0.5 and 1.5, then the sequence of p-values quickly converges to 1. For example, when k = 1 the sequence is

0.3, 0.51, 0.76, 0.942, 0.997, 1, 1, 1, ...

When k is 2.2, the sequence alternates between the two values 0.746 and 1.1628. When k is 2.5 the sequence cycles through four different values. Such repeated values in the sequence are called attractors. When k is greater than 2.55 the sequence becomes quite unpredictable, producing apparently random values in the range 0.5 to 1.4. What's more, very slight changes to the starting value produce a very different-looking sequence. This is an indication of chaos.

If you were to try many values of k between, say, 2.4 and 2.9, and plot each of the sequences (apart from the first few values) on a graph with k on the X axis and p on the Y axis, you would get a picture something like this: [Chaos 100] (Unfortunately you won't have time to produce pictures like this under competition conditions.) The branching shown is where two attractors becomes four, then eight. Soon the chaotic region appears, with curious internal structure. Some other time you might like to experiment further.

Now for the task itself.

Write a program that shows the first few iterations of the above formula for a particular k. The program input consists of the value of k and the initial value of p, both real numbers, and the number of iterations to be displayed (a positive integer). Successive values of p should be printed, five per line. Display real numbers with 4 decimal places.

Examples

Input	Output
1.5 0.3 15	k = 1.5 15 iterations 0.3000 0.6150 0.9702 1.0136 0.9929 1.0035 0.9983 1.0009 0.9996 1.0002 0.9999 1.0001 1.0000 1.0000 1.0000 1.0000

Input	Output
2.5 0.3 40	k = 2.5 40 iterations 0.3000 0.8250 1.1859 0.6347 1.2143 0.5637 1.1785 0.6525 1.2194 0.5507 1.1692 0.6745 1.2234 0.5402 1.1612 0.6934 1.2249 0.5362 1.1579 0.7007 1.2250 0.5359 1.1577 0.7013 1.2250 0.5359 1.1577 0.7012 1.2250 0.5359 1.1577 0.7012 1.2250 0.5359 1.1577 0.7012

Input

Output

2.5 0.3 40

k = 2.5  40 iterations
    0.3000
    0.8250    1.1859    0.6347    1.2143    0.5637
    1.1785    0.6525    1.2194    0.5507    1.1692
    0.6745    1.2234    0.5402    1.1612    0.6934
    1.2249    0.5362    1.1579    0.7007    1.2250
    0.5359    1.1577    0.7013    1.2250    0.5359
    1.1577    0.7012    1.2250    0.5359    1.1577
    0.7012    1.2250    0.5359    1.1577    0.7012

Constraints

When k is greater than 3, the sequence rapidly diverges to an attractor of minus infinity, resulting in floating point overflow. Your program should reject k values outside the range 0 to 3, and initial p values outside the range 0 to 1.

Extension

The basic task is worth 12 points. For an additional 6 points, modify the program to identify the attractors in the sequence. To do this, you must determine if a value occurs earlier in the sequence. Because of the inaccuracy of floating-point arithmetic, two numbers are considered equal if they differ by only a small amount, say 0.001. For example,

Input	Output
2.5 0.3 40	(output as above, followed by) 4 attractors: 1.2250 0.5359 1.1577 0.7012

You may assume that there are no more than 8 attractors. If no attractors can be found in the last 16 iterations, display "Chaos" instead.

Solution

Discussion here.

Reference

The background for this task was taken from the book

Becker, K and M Dörfler (1989). Dynamic Systems and Fractals, Cambridge Univ Press.