UNSW High Schools Programming Competition 2012: Open Round
- You have 2 hours.
- Submissions after the deadline will be marked as LATE and will not be marked unless prior arrangements have been made.
- You may solve the tasks in any order.
- Tasks are of differing value and difficulty.
- You may submit multiple times for each task. Only your most recent submission will be marked.
- You are reminded that only genuine output from a working program and the program text itself is to be pasted into the submission boxes, unless otherwise explicitly stated. Hand-crafted output will result in the team's disqualification.
- Good luck and have fun!
The Tasks:
Junior task: Plurals (easy, 10 marks)
Task 1. Two out of Three Ain't Bad (easy, 7 marks)
Task 2. Pangrams (easy to moderate, 9 marks)
Task 3. Luhn Algorithm (easy to moderate, 11 marks)
Task 4. The Clacks (moderate, 14 marks)
Task 5. Filomino (moderate to hard, 19 marks)
Junior Task. Plurals
Available Marks: 10
How many times has a computer told you something using phrases like these?
|
3 item(s) in your basket 1 message(s) in your inbox 0 day(s) to go |
That's just lazy programming: the system knows exactly whether you have no items, one item or many items, so why can't it use the right words, like any five-year-old can?
To counter this insidious attitude of "Oh it's too much trouble, the user can work it out," this task produces the appropriate phrase based on quantity, assuming the noun isn't one of a number that form irregular plurals (leave that for another time).
Given a non-negative integer quantity Q and a word, the correct phrase to print is either
- "no" and the plural of the word, if Q is zero;
- "one" and the singular of the word, if Q is 1; or
- the quantity as a decimal integer and the plural of the word, otherwise.
To form the plural of a word, use the following rules that cover common cases:
- If the word ends in "s", "x", "z", "ch" or "sh", append "es";
- if the word ends in "o" preceded by a consonant (that is, not "a", "e", "i", "o", "u" or "y" in this context), append "es";
- if the word ends in "y" preceded by a consonant, remove the "y" and append "ies";
- if the word ends in "fe" preceded by a letter other than another "f", remove the "fe" and append "ves";
- if the word ends in "f" preceded by a letter other than another "f", remove the "f" and append "ves"; or
- append "s" otherwise.
Write a program that reads a quantity and word from each line of input, separated by a space, and displays the appropriate phrase according to the rules above. The first input line contains the number of test cases that follow, which is a maximum of 30. Quantities are less than 10000 and no word is longer than 20 characters. Words are strictly in lower case.
Example
Input:
5 6 ferry 0 potato 1 camera 2 knife 243 box |
6 ferries no potatoes one camera 2 knives 243 boxes |
Test Data
You should test your program on the following data:27 1 caterpillar 101 dalmation 9999 cat 5 bee 0 computer 4 compass 2 bus 0 ibis 8 lynx 15 axe 15 ax 15 adze 4 waltz 7 church 3 wish 12 bath 8 potato 3 toe 6 embryo 6 kangaroo 5 whisky 3 kidney 52 handcuff 2 giraffe 3 dwarf 9 wife 4 handkerchief |
Note: if you can't manage to read the test cases from an input file, for part marks run your program separately for at least three different scenarios. Be careful to paste only legitimate, unedited output into the submission box.
Task 1. Two out of Three Ain't Bad
Available Marks: 7
Consider the following product of fractions:
Write a program that determines the largest value of k for which Pk > 0.666667000...
If you are only able to use single precision arithmetic, then for 4 marks you are permitted to use the limiting value 0.6667000... instead.
Task 2. Pangrams
Available Marks: 9
A pangram is a phrase that contains at least one instance of each of the 26 letters of the alphabet, ignoring differences between upper and lower case. The quick brown fox jumps over the lazy dog is probably the most well-known pangram, but with advent of computer processing many more have been devised.
Write a program that processes a file containing up to 50 phrases, one per line,
each up to 120 characters in length. The first line contains the number of phrases.
The program should display each phrase, and on the next line, indented so we can see it easily, either:
Pangram (if it is), or
Not a pangram, does not contain: xyz (where xyz are all the letters not present in the phrase, in alphabetic order)
Example
Input:
4 the quick brown fox jumps over the lazy possum Many-wived Jack laughs at probes of sex quiz. CHEEKY JUVENILE DELINQUENTS BLAME LAX PARENTAL CONTROLS FOR WANTON VANDALIZING pangram |
Output:
the quick brown fox jumps over the lazy possum Not a pangram, does not contain: dg Many-wived Jack laughs at probes of sex quiz. Pangram CHEEKY JUVENILE DELINQUENTS BLAME LAX PARENTAL CONTROLS FOR WANTON VANDALIZING Pangram pangram Not a pangram, does not contain: bcdefhijkloqstuvwxyz |
Test Data
You should test your program on the following data:15 jackdaws love my big sphinx of quartz Five or six big jet planes zoom quickly by the tower. PR flacks quiz gym: TV DJ box when? Amazingly few discotheques provide jukeboxes. Six big juicy steaks sizzled in a pan as five workers left the quarry. UNSW Computing Progcomp A quart jar of oil mixed with zinc oxide makes very bright paint. He wrote deftly and quickly, amazing us with his expertise and his unabashed love of letters. Portez ce vieux whisky au juge blond qui fume. (French: Take this old whiskey to the blond judge who smokes) Five hexing wizard bots jump quickly. B, C, F, G, H, I, J, K, M, P, Q, U, V, W, X, Y, and Z are letters. The job requires extra pluck and zeal from every staff member. Six calligraphers, justly amazed, watch kids busily cutting quills with their favourite penknives. |
Task 3. Luhn Algorithm
Available Marks: 11
The algorithm devised by Hans Peter Luhn in 1954 to determine whether sequences of digits have (probably) been typed without error is still used to this day for things like credit card number validation. It works like this: to validate a sequence of digits (each in the range 0 to 9) that has been suitably encoded,
- Counting from the right, add the digits in odd positions (last, third last, etc).
- Double each digit in an even position. If the result is greater than 9, add the two digits together. Add the resulting even-position values.
- Add the odd and even sums. If the overall sum is not a multiple of 10, the sequence is invalid.
For example, if the encoded sequence is 71368054, the calculation gives a final sum of 30,
which is indeed a multiple of 10 (even positions are shaded):
However if, say, the adjacent digits 6 and 8 were accidentally swapped, the sum is no longer
divisible by 10:
The Luhn algorithm can be used to add a check digit to an account number so that common typing errors can be detected. The check digit, when determined, is appended to the original number so it's in an odd position and won't be doubled. You can use this fact to devise a way of generating the full Luhn code.
Your Task
Write a program that can either validate a number that has been encoded for Luhn validation, or generate the Luhn code for a digit sequence. Each line of input contains either a V (for validate) or E (for encode), a space, then a string of up to 20 digits. Leading zeros are ordinary digits. The number of data lines is on the first line of the input.
If the action is validate, display the number and then either the string " is valid" or the string " is INVALID" as appropriate. If the action is encode, display the encoded value, with is the original number with the calculated check digit appended to it, followed by the word " encoded".
Example
Input:5 V 00000 V 71368054 V 0071368056 E 7136805 E 123456789 |
Output:
00000 is valid. 71368054 is valid. 0071368056 is INVALID. 71368054 encoded 1234567897 encoded |
Marking Scheme
6 marks for correct validation and 5 for correct encoding.
Test Data
Test your program on the following data:20 V 123 V 1234 V 4444444 V 987654321 V 1357924680 V 13579246805 V 13572946805 V 93450345330 V 09345034533 V 30934503453 V 32049509345969205438 E 123 E 9999 E 76543 E 893563 E 21388462 E 034234273 E 20394284834 E 9837982348977317 E 9823423894798723444 |
Task 4. The Clacks
Available Marks: 14
Terry Pratchett's novel Going Postal features a sempahore-based communication system called "The Clacks". It consists of a series of towers each with eight shuttered lamps in a 2 by 4 array. Each lamp can be shuttered (light off) or unshuttered (light on), and the patterns of lights can carry information.
Pratchett didn't elaborate on the design of the coding system, but to avoid ambiguity on dark and stormy nights certain combinations are not used. For example, if the top row of lights was on and the rest were off, the receiver couldn't be sure which row was showing since they can't see the tower itself. The rules (so far as this task is concerned) are these:
- Each of the four rows must have at least one light on.
- Each of the two columns must have at least one light on.
- The all-lights-on configuration is a special LOCKOUT code that causes communication to shut down (a similar idea was exploited in the novel by a group of hackers who called themselves The Smoking Gnu).
If you analyse the situation you will find that 78 valid codes (light combinations) are available to carry a data symbol each (34 less 2 prohibited by the second rule and one by the third). The codes are assigned consistently and progressively, that is, with the top row changing first and then the second row and so on, but you'll have to work out what the algorithm is from the example below. The encoded symbols are, in order, upper-case letters, lower-case letters, decimal digits, a space and these 15 punctuation characters
!"$%&'()*,-.:?@
A message sent by the Clacks system is given by a list of 8-character sequences, each representing a symbol encoded by the 4 rows of shutter pairs, from top to bottom. The symbol X indicates a shutter (light OFF) and a dot indicates a light that's ON. Each code is on a separate line, and the message is preceded by the number of symbols in the message (maximum 100).
For example, the following data represents the encoded message Clacks!, use it to deduce the coding scheme.
7 X..XX.X. ..X..X.X X.X.X..X ..X.X..X .XX..X.X .XX....X ..X..X.. |
Write a program that decodes a message sent on the Clacks communication system. If your program encounters an invalid combination it should emit a # character and continue decoding, and if it sees the LOCKOUT code it must display the message so far, then display LOCKOUT and stop.
Test Data
You should test your program on the following three data sets. If your program is working the results will make sense. Resist the temptation to edit the output. Part marks are awarded for reasonable attempts, and fraud will result in disqualification.
Test 1
|
Test 2
|
Test 3
|
Task 5. Fillomino
Available Marks: 19
Fillomino is a logic puzzle developed by the Japanese Nikoli puzzle magazine. It is played on a square grid of some fixed but arbitrary size. In the completed puzzle the cells are grouped into polyminos, or connected regions of various size (number of cells). Cells in a region are adjacent horizontally or vertically (ignore diagonals), and every cell in a region contains the size of that region. To keep the size representation to a single digit, regions cannot be larger than 9 cells.
An important requirement is that regions of the same size cannot be adjacent, or they would combine to form a larger region.
The starting point is an incomplete puzzle with some cell values filled in. For the version of the puzzle used in this task, at least one cell of each region is provided.
Example
| Starting position | Completed puzzle | |
|---|---|---|
 |
 |
Write a program that can solve a Fillomino puzzle by filling in appropriate numbers in the empty squares.
The input consists of the grid size on the first line, followed by each row of the grid.
Each cell is either a digit or a dot, and cells are separated horizontally by a space.
The maximum grid size is 9.
Thus the sample input above looks like this:
5 3 . . . . 2 . . . . 3 5 . 5 4 . 1 . . . . 6 . . 1 |
R5C1 R2C2...
Test Data
You should test your program on the following three data sets, which are of varying degrees of difficulty. Part marks are given if your program can partly solve some puzzles, as simple heuristics will work in certain limited circumstances. All puzzles can be solved without backtracking.Once again, only unedited output from your program is acceptable.
| Test 1 | Test 2 | Test 3 | ||
|---|---|---|---|---|
4 . 2 . . 1 . 3 . 2 . 4 . 1 . . 3 |
5 4 . . . . 1 . 2 3 . . 4 5 . . . 6 1 5 3 . . 6 3 . |
8 7 . 8 . . . . 8 . . 1 4 . . . . 1 . . 4 8 5 . 5 7 7 . 3 . 6 3 . . . . 3 . . 4 . . 2 . 6 . . 3 3 3 1 5 . . 6 6 . 2 . . 5 6 . . . |