UNSW High Schools Programming Competition 2009: Open Round

Welcome to the UNSW High Schools Programming Competition for 2009.

The Tasks:

Junior task: Two-Up (easy, 10 marks)

  1. Digital Extraction (easy, 7 marks)
  2. Title Case (easy to moderate, 9 marks)
  3. Day of the Week (easy to moderate, 10 marks)
  4. Product Codes (easy to moderate, 13 marks)
  5. Trampolines (moderate to hard, 21 marks)

Junior Task. Two-Up

Available Marks: 10

The traditional Australian gambling game of two-up can legally be played only on Anzac Day each year. Its rules are simple, especially in the limited form described here. One person, the Spinner, bets Heads (H) or Tails (T). He or she then throws two pennies up in the air. If the pennies land with one head showing and one tail showing, the result is called ODDS and the Spinner throws again. Otherwise the Spinner wins if the pennies (now both Heads or both Tails) match the bet they made, and loses otherwise.

If five ODDS are thrown in a row, the Spinner loses too.

Write a program that scores this version of two-up. The input consists of several lines, each representing a throw, preceded by the number of throws. Each throw consists of a bet (H or T) followed by the result of the throw (two symbols, each H or T). The three letters are separated by a space.

The program should repeat the input and show the result of the throw on the same line. The result can be WIN, LOSE, ODDS or LOSE: 5 ODDS.

Example

Input:
9
T T H
T T T
H T T
H T H
H H T
H H T
H T H
H T H
T H H

Output:

T T H ODDS
T T T WIN
H T T LOSE
H T H ODDS
H H T ODDS
H H T ODDS
H T H ODDS
H T H LOSE: 5 ODDS
T H H LOSE

You can assume each line of input is a valid throw. Bets will only change after a win or loss.

Test Data

You should test your program on the following data.
16
H H T
H T H
H H H
H T T
T H T
T H T
T T H
T H T
T T H
T T T
H T H
H T H
H H T
H H T
H T T
T H H

Marking Scheme

Task 1. Digital Extraction

Available Marks: 7

I bet you get annoyed at websites that refuse to accept a credit card number, account number or phone number that contains spaces or hyphens, even though these separators make it easier to remember and accurately type the value.

Write a program that is smart enough to ignore all the non-digits in a string, displaying only the digits. If there are no digits, say so.

Your program should be able to process many sets of data, though you will get some marks if it correctly handles the first one. The first row of input is the number of strings, followed by one string per line. There may be as many as 20 strings and each string may be up to 60 characters long. Each line of output should consist of the input string, an equals sign and the extracted digits (or the "no digits" message if applicable).

Example

Input:
4
123   456
[7854-8954-8942]
#!)A*%#O&*&%
(02) 9900-6795

Output:

123   456=123456
[7854-8954-8942]=785489548942
#!)A*%#O&*&%=no digits
(02) 9900-6795=0299006795

Test Data

You should test your program on the following data.
10
78-3044/ 2678543
123456789
no.666<<<
00489;78954.22

------4------
l33t n00b
twenty-seven
809582098350298902l8450230958098223422393850298059809243O52.
he110 sa1l0r

Marking Scheme

Task 2. Title Case

Available Marks: 9

A string written in title case has Every Word Capitalised (except sometimes for trivial ones). Phrases that name things, like people, places and creative works are usually written in title case. This task comes in two versions, a basic one and a more difficult but improved version.

Write a program that reads in strings, one per line, and displays each string with title case, except that existing capital letters are retained (for example, to stop NSW becoming Nsw). A word is defined as a sequence of letters surrounded by non-letters or the start or end of the string. All characters are normal printable text characters (7-bit ASCII).

Hint: A lower case letter should be converted to the corresponding upper case letter only when preceded by a non-letter or the start of the string. Every other character is unchanged.

The input is preceded by a line indicating the number of strings to be converted. Each string is a maximum of 60 characters long.

Example 1

Input:
5
the cat sat on the mat
the university of new south wales, sydney NSW 2052
2001, a space odyssey (Stanley Kubrick, 1968)
o'dwyer, fleetwood-smith and d'silva
"a clockwork orange (stanley kubrick, 1970)"

Output:

The Cat Sat On The Mat
The University Of New South Wales, Sydney NSW 2052
2001, A Space Odyssey (Stanley Kubrick, 1968)
O'Dwyer, Fleetwood-Smith And D'Silva
"A Clockwork Orange (Stanley Kubrick, 1970)"

Improved Version

To get full marks, your program should also accept a "stop list" of words, one per line, that are only capitalised if they are the first word in the string. Stop words are in lower case, and only match words completely in lower case. The first line of input will have two numbers, the first is the number of stop words and the second is the number of strings. Then follows the stop words (in alphabetic order) and the strings to be converted.

Example 2

Input:
3 2
a
on
the
the cat sat on the mat
"mutiny on the bounty"

Output:

The Cat Sat on the Mat
"Mutiny on the Bounty"

Test Data

You should run your program using the following data. The first one tests the basic version, the second tests the improved version.

Test 1

9
pack my box with five dozen liquor jugs
cigar? toss it in a can, it is so tragic (palindrome)
it's a mad mad mad mad world
a
20th century frog
new york, NY, USA
[{!@#$%^&*(x)_+-=:";'y,.z/?~`|}]
1234567890
abc.Abc.ABc.ABC.aBC.aBc

Test 2

36 12
a
am
an
and
as
at
be
but
by
do
for
from
had
has
have
if
in
into
is
it
its
of
on
or
s
so
t
th
than
that
the
this
to
was
what
with
a few rolling stones' songs:
you can't always get what you want
(here comes your) 19th nervous breakdown
ain't too proud to beg
live with me
ALL CAPITAL LETTERS
a "Title Case" title
no pet so tragic as a cigar to step on (another palindrome)
a man, a plan, a canal: Panama! (yet another palindrome)
full circle, a TV series presented by michael palin-drome (sorry)
###a###a###a###
was.was.Was.WAs.WAS.wAS.wAs

Marking Scheme

Task 3. Day of the Week

Available Marks: 10

One of the peculiarities of the calendar is that the day of the week for any date since 15 October 1582 can be determined using only a few steps of arithmetic. The formula devised by Christian Zeller (1822-1899) is known as Zeller's Congruence. One form of the formula is

w = (d + [2.6m – 0.2] + Y + [Y/4] + 5C + [C/4] ) mod 7
where

Values inside square brackets [...] are truncated to integer, and mod is the modulus or remainder operator.
For example, [3.75] = 3, [11] = 11, 9 mod 7 = 2 and 42 mod 7 = 0.

Example: Australia Day this year, 2009-01-26. Here d = 26, m = 11, Y = 8, C = 20 (use previous year for Jan/Feb, in this case 2008). Calculate

w = (26 + [2.6×11 – 0.2] + 8 + [2] + 5×20 + [5]) mod 7

= (26 + [28.4] + 8 + 2 + 100 + 5) mod 7 = 1
which is Monday.

Write a program that reads any number of dates, calculates the day of the week for each using Zeller's Congruence and displays its name. Dates are in ISO 8601 format (yyyy-mm-dd). Part marks will be given for correctly calculating the day of the week for the first test date given below, regardless of how you enter the date into the program. If your programming language provides calendar functions you may only use them for validating dates, not for the day-of-the-week calculations.

For full marks you will need to identify invalid dates such as 2009-06-31, but you may assume that the input consists of three non-negative integers separated by hyphens and the year is valid.

The first line of input contains the number of dates. There may be up to 20 dates.

Example

Input:
4
2009-06-12
1792-02-29
1992-09-31
2001-09-11

Output:

2009-06-12 is a Friday
1792-02-29 is a Wednesday
1992-09-31 is not a valid date
2001-09-11 is a Tuesday

Test Data

You should test your program on the following data.
13
1945-08-15
2009-12-31
2010-01-01
1582-10-15
2008-02-28
1770-05-29
2009-02-29
1861-07-14
1855-12-03
2100-02-29
1616-04-23
2050-03-31
2009-13-13

Marking Scheme

Task 4. Product Codes

Available Marks: 13

Product codes are 13-digit numbers written below (and encoded by) bar codes on most products sold around the world. Parts of the numeric code carry various kinds of information, like manufacturer and country of origin. For example, all book codes start with 978 or 979, and Australian products apart from books start with 93. To help detect errors if the code ever needs to be typed by hand, such as when a product won't scan at the checkout, the rightmost digit is uniquely chosen such that all valid codes satisfy this nifty rule:

The sum of the digits in odd positions, plus three times the sum of the digits in even positions, is a multiple of 10.
Positions are conventionally counted from the right, which is an odd position.

A consequence of the rule is that mis-typing a single digit, or (with a few exceptions) swapping adjacent digits of a valid code always produces an invalid code, so these kinds of error can be detected.

For example, the validity of the code pictured is demonstrated by this diagram:

Write a program that reads what are supposed to be product codes, one per line, and responds with a copy of the input, a space and either

You may assume that each line of input contains only digits, and the first line contains the number of codes to be processed (a maximum of 20).

Example

Input (these are all based on the above example):
6
9780091835132
9780091853132
9780031835132
978009183513
97800918351
97800918351399

Output:

9780091835132 is valid
9780091853132 is INVALID
9780031835132 is INVALID
978009183513 full code is 9780091835132
97800918351 has the wrong length
97800918351399 has the wrong length

(The first invalid code swapped the adjacent 3 and 5, while the second replaced the second 9 by a 3.)

Test Data

You should test your program on the following data.
17
9312650441905
9300643881051
9329538001220
8850539180252
9781864364386
4902030309351
8373610005133
0123456789876
1234567898765
930064838101
978086840862
400638133363
978097511941
12345678901234
98765432109
9876543210
9

Marking Scheme

Task 5. Trampolines

Available Marks: 21

You have climbed through the corner window of a rectangular room filled with trampolines in a fixed grid. The trampolines have varying elasticity, and can propel you an integer number of positions horizontally or vertically. Starting at the top left corner (shown in yellow in the example), you want to reach the exit at the bottom right corner (the green square labelled 0) with the smallest number of jumps.

You must follow these rules:

  1. You must jump exactly the number of squares indicated by the elasticity of the trampoline you just jumped on.
  2. You can't jump diagonally.
  3. You can't bounce off a wall or jump out of the room.
  4. You can only jump on each trampoline at most once.

We refer to trampoline positions as row:column, with rows and columns counting from 1. Starting at 1:1, there are 5 different paths through the sample room, the shortest requiring 5 jumps:

1:1 1:2 1:3 3:3 3:1 3:4
1:1 2:1 2:3 3:3 3:1 3:4
1:1 2:1 2:3 1:3 3:3 3:1 3:4
1:1 1:2 2:2 2:4 2:1 2:3 3:3 3:1 3:4
1:1 1:2 2:2 2:4 2:1 2:3 1:3 3:3 3:1 3:4

Write a program that reads the layout of a room and displays one or more paths from 1:1 to the exit, one per line in the format above. For full marks the program's output should be

Part marks are available if the program finds some or all valid paths.

The input consists of a line containing the number of rows and columns separated by a space, then the elasticity of the trampolines in each row, one row per line, with one space between each cell value (trampoline elasticity). The room has a maximum of 8 rows and 8 columns. Elasticity values are positive integers less than the longer dimension of the room (so they are never more than 7). The exit square is always the last cell in the last row, and has value 0.

Sample data:

3 4
1 1 2 1
2 2 1 3
3 1 2 0

Test Data

You should test your program on each of the three sets of data below. At least one solution exists in every case.

Test 1

3 3
1 2 1
2 1 2
2 1 0

Test 2

4 5
3 4 2 3 2
2 1 3 2 1
1 3 2 1 4
2 3 1 2 0

Test 3

Caution: this room has a large number of paths. We don't want to see them all, just count them and, if possible, show the optimal solutions.
8 8
2 4 2 4 1 3 2 6
1 3 5 2 4 3 6 1
6 5 1 7 4 6 4 2
7 3 2 5 3 1 7 1
2 7 6 2 3 4 3 6
3 3 3 3 3 3 3 3
7 4 3 2 1 4 4 5
1 1 4 3 3 2 1 0

Marking Scheme

Acknowledgment

Adapted from the 2003 Southern African ACM Collegiate Programming Competition.