UNSW High Schools Programming Competition 2006: Open Round

Welcome to the UNSW High Schools Programming Competition for 2006.

The Tasks:

  1. Rank Generator (easy, 8 marks)
  2. Suburb Name Abbreviations (easy to moderate, 10 marks)
  3. Run-Length Decoding (moderate, 12 marks)
  4. World Cup Tipping Competition Calculator (moderate, 14 marks)
  5. Magic Squares (moderate to hard, 15 to 25 marks)

Task 1. Rank Generator

Available Marks: 8

Given a list of scores, in order, write a program to generate a rank for each entry. An entry's rank is just its position in the sequence, starting at 1. If there are equal values, however, each of the equal values shares the same rank. This doesn't affect subsequent ranks. For example, here is a list of scores (in descending order) with the corresponding ranks written underneath:

134 109 109  104  94  94  94  67  42
1   2eq 2eq  4    5eq 5eq 5eq 8   9
The input format has one score per line. There is no formal limit to the number of values.

You may assume that all numbers are well-formed (legal integer or real format).

Test Data

You should test your program on the following examples.

Test 1 (all valid data)

100
100
99
98.5
98.4
98.40
98.4
98.399
97.1
92
92
92
92
0.000
0
-1

Test 2 (some out of order)

1243
1234
1243
1243
1243
1234
1234
1233
1222
1211
1233
1234
1222
1211
1211
1210
-1

Marking Scheme

Task 2: Suburb Name Abbreviations

Available Marks: 10

To squeeze address information into the phone book Telstra abbreviates suburb names. Vowels carry less information than consonants, especially in the middle of words, so the (simplified) rules for reducing suburb names are

  1. Remove any vowel that occurs in the middle of a word.

  2. Remove an 'e' at the end of a word, provided it's not preceded by another vowel.

  3. Remove spaces between words.
All other characters are retained unchanged.

A vowel is defined as one of the 5 letters aeiou. Although 'y' is considered a vowel in certain contexts it is not so here.

Examples:

Suburb Abbreviation
Banksia Bnksia
Little Bay LttlBy
Glenorie Glnrie
Lane Cove LnCv
Illawong Illwng

Write a program to abbreviate suburb names this way. Names are provided, one per line. The output should be the original name, one or more spaces, and the abbreviation.

Test Data

Show the output of your program when it reads this list of Sydney suburbs (25 lines, one per initial letter of the alphabet except for X):

Alexandria
Berowra Waters
Campsie
Doonside
East Ryde
Fairfield East
Granville
Heathcote
Ingleburn
Jannali
Kirrawee
Lane Cove North
Maianbar
Neutral Bay
Old Toongabbie
Parramatta
Queenscliff
Raby
Sans Souci
Tempe
Ultimo
Vaucluse
Woolloomooloo
Yagoona
Zetland

Task 3: Run-Length Decoding

Available Marks: 12

One of the simplest data compression schemes is called run-length encoding (RLE). RLE replaces a sequence of adjacent equal values with one copy of the value, and a count of the number of times it occurred. This works well for data representing images with regions of uniform colour, for example.

For this exercise we have applied RLE to text input only, and your task is to write the decoder to restore the original data.

An RLE-encoded sequence must be distinguishable from ordinary text. To do so, a special character is reserved to indicate the start of an RLE-encoded sequence. We will use the character '#'. An occurrence of '#' in an encoded file will be legally one of two forms:

#dc
##
where d is a digit character ('0' to '9'), representing how many times the character is to be repeated, and c is the repeated character, which can be any printable character, including '#'.

The second kind, "##", represents a single literal '#' character, as a shorter alternative to the encoding "#1#".

If a '#' is followed by other than a digit or another '#', display a question mark '?'.

For example, the input text

ab#3Cde###1Fg#9hh
would be decoded as
abCCCde#Fghhhhhhhhhh

Write a program that reads RLE-encoded data from its input and writes decoded data to its output.

Test Data

Show your program's output for the following three test files. The last one is long and has lines of up to 55 characters: make sure you transfer it completely to your program. You'll know your program is working if it displays one of the classic ASCII art pictures.

Test 1

W#1el#1c#1ome#1 t#1o Prog#1co#1m#1p 2#206

Test 2

#4 #3#
#2 #2 #2###
 #3 ###2#
#2##9#
#####9#
#2 #2 #3#
#4 #3#
 #3 ##2#1#
>#4>#>#5<#2= e#2ror

Test 3

#5 #9 #4X
#4 #9 X#4 XX
#3 #9 X  #3*  X#7 #9 #5X
  #9 X  #5*  X#3 #9 #3X#5 XX
#8 #4X #7* #3X#6 #4X #9 XX
#6 XX#3 X #6*  #9X#7 #9 #2X #3X
#4 XX#6 X #4*  X#9 #9 #9 X** X
#3 X#8 XX#4 XX#5 X#4 #9 #9 X#3*X
  X#9 //#4X#7 X#4 #9 #9 #4X
 X#9 //#3 X  #9 #9 #9 XX
X#9 //#4 X #9 #9X#9X/
X#5 #3X//#4 X #9 X
X#4 X#3 X  #3 X    #5 X
X#4 X#4 X#4 X#5    X
 X#3 X#4 X#4 X#8 X  #9 #9 XX
 X#4 X#3 X#4 X#8 X#8 #9 #3X  XX
  X#4 #3X#6 X#8 X#6 #9 X  X X  X
  X#4 #9 X#9 X#5 #9 XX X  #4X
#3 X#4 #9 X#9 #8X\#5 XX#3 XX  X
#4 XX#3 #9 XX#5 #9 X#5 X#4 X  XX
#6 XX#3 #9 #4X#3 #6X/#5 X#5 #4X
#8 #3X#4 #9 XX#3*#9 X#5 X
  #9 #4X#9X *#3 *#7 X#5 X
#6 #9 #9 *#3-* X#5 X#5 X
#5 #9 #9 *-* *#3 #3X X#5 X
#5 #9 #9 *- *#7 #3X#3 X
#4 #9 #9 *- *X #9 #3X
#4 #9 #9 *- *X  X #9 #3X
#3 #9 #9 *- *X#4 X#3 #9 XX
#3 #9 #9 *- *XX#4 X#4 #9 X
  #9 #9 *  *X* X#4 X#4 #9 X
  #9 #9 *  *#1X * X#4 X#4 #9 X
 #9 #9 *  * X**  X#3 #4X #9 X
 #9 #9 *  * X**  XX#5 X #9 X
#9 #9 *  ** X** X#5 XX #9 X
#9 #9 *  **  X*  #3X#3 X#9 X
#8 #9 *  **#4 XX#3 #4X#7 #3X
#7 #9 *  * *#6 #4X#6 X#5 X
#6 #9 *#3 * * #9 X#5 X#5 X
 #7=#7*#3 * *  #9 X#5 X#6 #8X\
#8 *#9 * *#6 /#5X#6 #8X\#6 )
#3 #5=*#9*  *#5 X#3 #9 #9 )  \  )
#5 #4=*#9 *#5 X#6 #9 \  \#3 )#5X
#9=*#9*#7 #4X#9X#9X
#2
 #9 #9 C#1U#1R#1SE Y#1O#1U, R#1ED B#1A#1R#1O#1N!

Task 4: World Cup Tipping Competition Calculator

Available Marks: 14

Even if you aren't a football fan you must know the World Cup is on. This task requires you to write a program that assigns points in a tipping competition.

In the competition, each participant (we'll call them a "tipper") predicts the final score for a particular match. A prediction is represented by two non-negative integers: how many goals the first identified team will score, and how many goals the second team will score. When the final score is known, points are awarded to each participant depending on how accurate their prediction was.

The points system varies according to whether or not a draw is predicted (equal number of goals for each side).

If a draw is predicted...

Final result points awarded
Draw occurred 5
Score was exact +1 (so total = 6)
Draw did not occur 1
Goal difference is 1 or –1 +1 (so total = 2)

The "goal difference" is the difference between the number of goals scored by the first and second team. It's 0 for a draw.

For example, if a tipper predicts 1-1, the following points would be awarded:

Final score points awarded
1-1 6
0-0 5
0-1 2
4-2 1
2-3 2

If a win is predicted for one team...

Final result points awarded
Win 3
Predicted goal difference differs from the actual goal difference by 1 or less +1 (so total = 4)
Predicted goal difference is correct +1 (so total = 5)
Exact score +1 (so total = 6)
Loss 0
Draw 0
Draw, but predicted goal difference = 1 or –1 +1 (so total = 1)

For example, if a tipper predicts 1-2 the following points would be awarded:

Final score points awarded
1-2 (correct score) 6
0-1 (correct goal difference) 5
2-4 (goal diff incorrect by 1) 4
0-3 (right team won) 3
1-0 (wrong team won) 0
1-1 (draw, 1 pt for goal diff = 1) 1

Your Task

Write a program that awards point to each tipper. The first line of input is number of tippers. The second line of input is the final score. The remaining input consists of the tipper's name (one word only) followed by a space and their tip. All scores and tips are two integers separated by a dash.

The output should be the name of each tipper followed by the number of points awarded according to the scoring system described above.

Tests

Show the output of your program for each of the following three tests.

Test 1: Australia v Japan

4
3-1
Marcus 1-2
Steve 2-1
Mei-Cheng 3-1
Geoff 2-2

Test 2: Tunisia v Saudi Arabia

7
2-2
Janet 1-0
Jimmy 0-2
Tao 1-1
Alex 4-1
Rui 2-2
Isan 3-4
Keith 0-0

Test 3: Angola v Portugal

10
0-1
Me 0-0
You 0-1
Him 1-0
Her 1-1
Them 1-2
Those 2-1
It 9-9
Another 1-10
Others 3-1
TheRest 99-100

Task 5: Magic Squares

Available Marks: 15 to 25

A magic square of order n is an array of the integers from 1 to n2 arranged in an n by n square. Each number is used exactly once. What makes the squares "magic" is that the sum of each row, column and the two diagonals is the same.

Magic squares exist for all orders except 2. For example, an order-3 magic square is shown below. Its row, column and diagonal sum is 15.

8 1 6
3 5 7
4 9 2

Basic Task: 15 marks

Your task is to verify whether an array of n by n integers is a magic square. The input starts with the value of n on a line by itself, then n lines each containing n positive integers separated by spaces (there may be leading and/or trailing spaces too).

For example, the magic square above could be represented as

3
8 1 6
3 5 7
4 9 2

You should be able to handle any magic square up to order 9.

The program's output is one of the following statements:

Extension: additional 10 marks

Note: this section is likely to be a tie-breaker for the top few teams. It is not expected that many (or possibly any) will produce a complete solution in the time available.

Just as Sudoko puzzles are solved by inferring the contents of empty cells based on the rules of the game, magic squares with missing numbers can be completed using the rules above.

Given an incomplete magic square, with * symbols where the missing numbers are, modify your program to generate the missing values. Only one solution is required in the event that more than one exists.

The input format is the same as above apart from the use of the missing number symbol. If the input contains one or more missing numbers, output the complete magic square. Assume that if the input contains an incomplete magic square none of the error cases will arise.

Test Data

Tests 1 to 3 are for the basic task; tests 4 and 5 are for the extension. Only paste these results if you have attempted the extension.

Judges will be looking very carefully at your program to confirm that it can generate the indicated output. If possible, the code will be compiled and executed. If irregularities are detected, no score is awarded for this task and the team may also be disqualified from the competition.

Test 1 (Dürer, 1514)

4
16  3  2 13
 5 10 11  8
 9  6  7 12
 4 15 14  1

Test 2

5
 1  9 12 20 23
17 25  3  6 14
 8 11 19 22  5
24  2  9 13 16
15 18 21  4  7

Test 3

9
 9 34 62 12 37 65 24 49 77
15 40 68 27 52 80  3 28 56
21 46 74  6 31 59 18 43 71
35 63  7 38 66 10 50 78 22
41 69 13 53 81 25 29 57  2
47 75 19 32 60  4 44 72 16
61  8 36 64 11 39 76 23 51
67 14 42 79 26 54 55  1 30
73 20 48 58  5 33 70 17 45

Test 4 (extension)

5
 *  7 23 19  *
18 14  *  6 22
10  * 17 13  4
12  3  * 25  *
24  * 11  *  8

Test 5 (extension)

7
 1  8  * 25 35 39  *  
 * 41 44  2  * 17 28
11 21 24  * 37 43  * 
 *  *  4 14  * 26 30 
20 23  * 40 46  * 10 
49  3 13 16  * 34 38  
27  * 42  *  5  9 15