UNSW High Schools Programming Competition 2013: Open Round

The Tasks:

Junior task: Digital Roots (easy, 10 marks)

Task 1. Case Mapping (easy, 7 marks)

Task 2. Safe-T-Cam (easy to moderate, 9 marks)

Task 3. Peanuts (easy to moderate, 11 marks)

Task 4. One-Time Pad (moderate, 14 marks)

Task 5. Gift Wrapping (moderate to hard, 19 marks)

Junior Task. Digital Roots

Available Marks: 10

Numerologists ascribe certain magical properties to numbers, and in turn derive numbers from words or phrases. Nonsense like this can still provide an interesting computational exercise.

The two algorithms of interest to us are:

Write a program that reads in up to 20 lines, preceded by the number of lines. For each line, if it contains only a number, calculate and display the digital root, spaces and the number. If it's a phrase, calculate the letter sum, then display the digital root, the sum and the phrase, agsin separated by spaces. Input and calculated numbers are less than a billion and phases are shorter than 100 characters.

Example

Input: 

5
123
the quick brown fox
7823438
"640 K ought to be enough for anybody". Bill Gates, 1981.
Progcomp
Output: 
6       123
4       211     the quick brown fox
8       7823438
1       406     "640 K ought to be enough for anybody". Bill Gates, 1981.
4       103     Progcomp

Test Data

You should test your program on the following data: 
14
99999
10000
7
12345678
98765432
June
UNSW Progcomp Twenty-thirteen
the second figure thrice
"Tragedy is when I cut my finger,...
Comedy is when you walk into an open sewer and die" (attributed to Mel Brooks).
the thirty-sixth triangular number, declared the number of the beast
A Clockwork Orange, Stanley Kubrick: 3*114+1=343
(114 was Kubrick's signature code, it appears in four films as CRM114 or serum 114 or C-rm114.)
Nineteen associates attacked the World Trade Center in New York and the Pentagon in Washington.

Marking Scheme

5 marks for correctly implementing the digit reduction algorithm and 5 for combining it correctly with the phrase analysis.

Task 1. Case Mapping

Available Marks: 7

Perl's regular expressions have been adopted by other systems, sometimes incompletely. Version 9.1 of the SAS enterprise database system, for example, didn't implement case mapping codes in replacement text. This task does so, but for any string.

Embedded in a string of printable ASCII characters are the following symbol sequences, that change the state of the characters that follow:

Code State change
\u The following single character is converted to upper case
\l The following single character is converted to lower case
\U All following characters are converted to upper case
\L All following characters are converted to lower case
\E Stop converting case

Rules

Write a program that reads a file of lines representing perl-style case mapping strings, preceded by the number of lines, and displays the converted lines. There can be up to 20 lines and each line can have up to 100 characters.

Example

Input: 

3
\Uunsw\E Computing
\uprogcomp \l2013\u.
T\LITLE CASE\E is also known as \L\uproper CASE\E.

Output: 

UNSW Computing
Progcomp 2013.
Title case is also known as Proper case.

Test Data

You should test your program on the following data: 
9
Mapping "\UuPpEr"\E and "\LlOWeR\E" case
\uNon-\lNested \using\lles
Nested \L\umc\uvEE\E and \Uo'l\le\la\lr\ly\E, \U\lR\Eedundant sequences.
Nested same-case: \Uab\uc\ud\uef\E and \L\lAB\lC\lDE\lF\E
Punctuation is unaffected\U:!@#$%^&*()_-+={}[]'";:,.<>/?1234567890\E
To get a \u\ precede it with either \l\u or \u\l.
\u\E is optional and can be redundant\E\E\E: \u\Uh\u\LeLLo[endofline] produces \Uh\LeLLo
Pointless repeats: \L\L\L\L\L\L\L\L\U\L\L\L\L\U\U\U\L\L\L\LX\E
Non-special sequences \t \n \e \A \$ \\

Task 2. Safe-T-Cam

Available Marks: 9

Drivers slow down briefly for marked speed cameras, but calculating average speeds between checkpoints can be a more effective way of detecting consistently speeding vehicles.

Assume there are three checkpoints numbered 1, 2 and 3, spaced along a highway with a 110km/hr speed limit. Checkpoints 1 and 2 are 133.0 km apart and checkpoints 2 and 3 are 57.5km apart. Each checkpoint has an accurate clock and reliable numberplate recognition equipment. After each vehicle passes, the time, checkpoint number and numberplate are sent to a central log.

Your task is to read the log and identify any speeding vehicles.

The data is presented as a single file with the rows in strict time order, preceded by the number of rows on the first line (up to 300). Each data item consists of three fields, separated by a space:

You can assume the supplied data uses the correct format, all times are legitimate and so on.

The program's output consists of only the rows that indicate that a vehicle's average speed has exceeded the speed limit for the section that ends at that checkpoint, along with the calculated average speed in km/hr to 1 decimal place.

The output must be in chronological order, same as the input.

Example

Input: 

7
02:12:49 1 MYTRUK
02:21:52 1 BI66BT
03:17:21 2 MYTRUK
03:22:55 2 2SLOW
03:42:18 2 BI66BT
03:55:37 3 2SLOW
04:12:58 3 BI66BT

Output: 

03:17:21 2 MYTRUK 123.7
04:12:58 3 BI66BT 112.5

Test Data

You should test your program on the following long data set: 
250
13:07:15 1 RA58EC
13:07:25 1 TS67NH
13:07:48 1 WZ11ZN
13:07:53 1 DM13OR
13:08:41 1 UM17HA
13:08:57 1 DU07WI
13:09:57 1 NF00OD
13:10:07 1 ZOOM98
13:10:32 1 AD78YQ
13:10:34 1 LM91XR
13:12:20 1 JA61RD
13:13:00 1 STQLN
13:13:06 1 VX53MY
13:13:15 1 JX64XY
13:14:14 1 ZI31OE
13:14:28 1 ZOOM99
13:15:49 1 RP75XK
13:16:23 1 UA37TY
13:18:06 1 OS61YP
13:18:17 1 LEMANS
13:18:42 1 JX33RT
13:18:54 1 VW48PU
13:19:19 1 BT73EC
13:19:24 1 YK65QD
13:19:40 1 LINFOX
13:19:58 1 PB4UGO
13:20:00 1 TB31YK
13:20:04 1 US00GP
13:21:07 1 OJ74JG
13:21:14 1 RM08PC
13:21:24 1 KN90YF
13:21:46 1 SY14LJ
13:22:04 1 CN15EE
13:22:24 1 MYBMW
13:23:01 1 QW20QT
13:23:15 1 50BER
13:24:06 1 FG43KY
13:24:23 1 THSTIG
13:24:40 1 SC77NC
13:24:52 1 PF85NJ
13:26:23 1 OP22QI
13:27:19 1 OZ26WC
13:29:03 1 GI47PC
13:29:12 1 NR80VS
13:29:14 1 UL45LZ
13:29:21 1 VZ89KR
13:29:25 1 SE21VN
13:29:53 1 EF04DY
13:30:21 1 HB06VI
13:31:08 1 H8COPS
13:31:10 1 NP84HG
13:32:27 1 XD22YM
13:32:29 1 QO43DJ
13:32:52 1 SK93IQ
13:32:59 1 XY13XS
13:33:20 1 PY43JF
13:34:46 1 TO56HT
13:35:42 1 ZX38BC
13:36:00 1 LB34KH
13:36:11 1 JQ59CG
13:36:16 1 BH59CW
13:36:20 1 VC38LK
13:36:26 1 WW54SN
13:37:00 1 RC07GN
13:37:15 1 VV60FW
13:38:53 1 IR99TT
13:39:08 1 HP10MT
13:39:52 1 RH80OK
13:40:12 1 JT50UU
13:41:20 1 NQ34LX
13:41:41 1 SS80CY
13:41:52 1 4MYHSC
13:42:05 1 OM46VU
13:42:27 1 VF31XW
13:42:47 1 PC2013
13:43:19 1 BJ13VY
13:43:45 1 HN43VZ
13:44:00 1 EI25KB
13:44:07 1 ZJ46HV
13:44:36 1 JS98BQ
13:45:14 1 EJ04YX
13:45:45 1 XP92CE
13:47:02 1 SXYCAR
13:48:09 1 KK09LY
14:08:27 2 GB72NM
14:16:11 2 VW46BL
14:18:09 2 KG06AF
14:18:09 2 TS67NH
14:19:55 2 HT70JW
14:21:52 2 STQLN
14:22:11 2 UM17HA
14:24:21 2 JX34SZ
14:25:14 2 ZOOM99
14:25:41 2 WZ11ZN
14:27:50 2 LEMANS
14:27:58 2 FS19UM
14:28:06 2 JX64XY
14:29:09 2 TK72GR
14:30:21 2 DM13OR
14:31:20 2 RM08PC
14:33:06 2 DU07WI
14:33:31 2 NF00OD
14:33:48 2 JX33RT
14:34:34 2 THSTIG
14:34:39 2 ZOOM98
14:34:41 2 TB31YK
14:35:01 2 AD78YQ
14:35:06 2 DK82BX
14:35:14 2 LINFOX
14:35:24 2 UA37TY
14:35:31 2 VX53MY
14:36:37 2 YK65QD
14:36:38 2 CN15EE
14:37:07 2 FG43KY
14:38:17 2 US00GP
14:38:39 3 GB72NM
14:38:42 2 UU91CK
14:39:26 2 QW20QT
14:39:28 2 RA58EC
14:39:31 2 JA61RD
14:39:49 2 BW74CO
14:40:28 2 MX62VO
14:40:44 2 RTFM
14:41:03 2 OS61YP
14:43:11 2 VQ11GF
14:44:09 2 50BER
14:44:54 2 OZ26WC
14:45:05 2 UL45LZ
14:45:36 2 VW48PU
14:46:00 2 EF04DY
14:46:19 2 NP84HG
14:46:20 2 OJ74JG
14:46:46 2 GI47PC
14:46:47 2 H8COPS
14:47:04 2 BT73EC
14:47:52 2 KN90YF
14:47:52 2 XD22YM
14:48:00 3 VW46BL
14:48:38 2 ZI31OE
14:49:03 2 QO43DJ
14:50:23 2 OP22QI
14:50:59 2 BH59CW
14:51:09 3 KG06AF
14:51:21 2 PB4UGO
14:51:52 3 TS67NH
14:52:16 2 BG54GL
14:53:21 2 SY14LJ
14:53:34 3 HT70JW
14:53:42 3 UM17HA
14:53:47 2 NR80VS
14:53:54 3 ZOOM99
14:54:22 2 PC2013
14:55:07 2 VZ89KR
14:55:14 2 MYBMW
14:55:19 2 SE21VN
14:55:58 2 4MYHSC
14:56:00 3 STQLN
14:57:36 2 VV60FW
14:57:47 2 SXYCAR
14:57:58 2 SC77NC
14:58:16 3 JX64XY
14:58:17 3 JX34SZ
14:58:18 2 OM46VU
14:58:26 3 LEMANS
14:58:28 2 ZX38BC
14:59:55 2 WW54SN
14:59:56 3 WZ11ZN
15:00:00 3 IMLATE
15:01:14 2 SK93IQ
15:02:11 3 FS19UM
15:02:12 2 RP75XK
15:02:17 2 BJ13VY
15:02:21 2 TO56HT
15:04:41 2 VC38LK
15:04:46 2 RC07GN
15:04:47 2 EJ04YX
15:04:48 3 RM08PC
15:05:08 2 KK09LY
15:05:48 2 JT50UU
15:05:50 3 THSTIG
15:05:54 3 LINFOX
15:06:11 2 VF31XW
15:06:28 2 PY43JF
15:06:31 2 PF85NJ
15:06:51 3 TB31YK
15:07:02 2 JQ59CG
15:07:29 3 DU07WI
15:07:32 3 TK72GR
15:08:00 3 SC44IP
15:08:14 2 HN43VZ
15:08:15 2 XY13XS
15:08:23 3 NF00OD
15:08:43 2 XP92CE
15:09:24 3 JX33RT
15:09:35 3 DM13OR
15:09:40 2 LB34KH
15:09:57 2 NQ34LX
15:10:20 3 ZOOM98
15:10:41 2 JS98BQ
15:10:43 2 LM91XR
15:10:50 2 SS80CY
15:10:53 3 AD78YQ
15:11:08 3 YK65QD
15:11:23 3 UA37TY
15:12:27 3 FG43KY
15:13:14 3 MX62VO
15:13:18 3 US00GP
15:14:00 3 CN15EE
15:14:25 2 HP10MT
15:15:19 2 RH80OK
15:15:33 3 OZ26WC
15:15:36 2 HB06VI
15:15:50 3 VQ11GF
15:16:25 3 QW20QT
15:16:48 3 DK82BX
15:17:09 3 H8COPS
15:18:14 3 50BER
15:19:22 3 JA61RD
15:19:41 3 UU91CK
15:19:50 3 RTFM
15:20:16 3 OS61YP
15:20:20 3 NP84HG
15:20:41 3 UL45LZ
15:20:57 3 GI47PC
15:21:01 3 EF04DY
15:21:12 3 RA58EC
15:21:31 3 OJ74JG
15:21:39 3 VW48PU
15:21:59 3 XD22YM
15:22:09 3 BW74CO
15:22:28 2 ZJ46HV
15:22:33 3 QO43DJ
15:24:58 3 OP22QI
15:25:25 3 BH59CW
15:26:04 3 BT73EC
15:26:08 2 EI25KB
15:27:10 3 PC2013
15:27:18 3 PB4UGO
15:28:51 3 ZI31OE
15:29:49 3 SXYCAR
15:30:18 3 NR80VS
15:30:49 3 VZ89KR
15:31:57 3 SE21VN
15:34:09 3 BG54GL
15:34:34 3 OM46VU
15:34:42 3 BJ13VY
15:34:46 3 VV60FW
15:35:14 3 MYBMW
15:35:22 3 SY14LJ
15:35:29 3 KK09LY

Task 3. Peanuts

Available Marks: 11


Copyright ©1968 United Features Syndicate.

The Linus sequence, inspired by this Peanuts cartoon, is a sequence using two symbols, traditionally 1 and 2 but we will use T and F. The sequence is uniquely defined by choosing each element so as to minimise the length of the longest repeated substring at the end of the sequence at that point. (A substring is a contiguous group of elements, and the string alfalfa ends with the repeated substring lfa.)

The first 5 elements of the Linus sequence are T F T T F (not quite the same as the cartoon). If we choose T to be the next symbol the sequence would end in a repeated 3-element substring T F T. If it was F the sequence would end in the repeated substring F (length 1), so F is the right choice as it avoids the longer repeat.

The Sally sequence is the length of the longest repeated substring suffix that was avoided by selecting the appropriate element. It begins 0 1 1 2 1 3 1....

Write a program that generates the first 200 elements of the Linus sequence, displaying them 20 elements per line with a space between each element, then the first 200 elements of the Sally sequence, again 20 per line with a space between them.

For the last 3 marks, determine (by any means) the largest value that occurs in the first 1200 elements of the Sally sequence. You may type this number in the output box, however all other output must be machine-generated.

Task 4. One-Time Pad

Available Marks: 14

A cryptographic system converts messages into a form that it is intended can only be converted back into the original message by the intended recipient. The only completely secure cryptographic system is one that uses no algorithm at all, just assigns a code apparently randomly to each component of the message.

Such so-called one-time pads can be simulated (and were in the old spy stories) by the sender and recipient agreeing to use the same edition of a text such as a novel. For each letter and punctuation in the message, the sender finds such a symbol in the book and assigns a series of numbers (page, paragraph and character position) to it. They transmit the numbers instead of the message, as the receiver can painstakingly consult the book to discover each original character.

For this task we will tidy up the requirements for the encoder to remove any ambiguity. The reference book is Project Gutenberg's copyright-free text edition of J M Barrie's Peter Pan, which you will need to download here.

Encoding and decoding rules

Example

For example, if the reference text began 
It was a dark and stormy night. The wind howled eerily through the trees.
^ ^ ^                 ^ ^^                ^^   ^        ^        ^  ^^
a message I am now here would use the symbols marked and would be encoded as the numbers 0 1 1 17 1 0 16 0 3 8 8 2 0.

Write a program that can encode and decode messages. The input is either a message to be encoded, provided it starts with a letter or punctuation, or an encoded message to be decoded, if it starts with a number. No error checking is required.

Format

Messages to be encoded are on one line only. Messages to be decoded may be spread over multiple lines that each start with a digit. Your output can be spread over multiple lines if you wish.

Test Cases

There are four test cases, given on the line following the Test number in the box below. Each test is a separate run of the program, starting again at the beginning of the book. 

Test 1:
This is a test.

Test 2:
Say, Don't Jackdaws Love My Big Sphinx of Quartz?

Test 3:
87 91 35 126 6 96 16 132 4 153 6 34 11 4 139 4 15 8 1 39 561 44 0 0 56 18 2 12 14

Test 4:
34 7 4 1 17 729 3 2 20 12 14 19 1 0 1 29 24 42 0 631 7 34 40 0 16 3 181 0 27 45 5
224 2 31 3 0 5007 9 53 1 2 4 33 0 3 1 22 3 48 20 27 10 6 21 30 0 16 38 54

Task 5. Gift Wrapping

Available Marks: 19

Given the cartesian coordinates (x, y) of a set of at least three points, the convex hull of the set is a sequence of a subset of the points that forms a convex polygon enclosing all the other points. A convex polygon has interior angles less than 180 degrees. Thus the convex hull of a star shape comprises the tips rather than the whole outline. The hull encloses the set like wrapping a present.


Ref: Wikimedia

Several algorithms exist to generate the convex hull, but you are encouraged to use the simplest of them, published by RA Jarvis in 1973. The Jarvis algorithm starts with the leftmost point p0 and computes the angles to every other point. The one with the smallest angle (relative to an upward vertical line) is the next on the hull. Repeat using the p0 to p1 vector to find p2 and so on (see diagram). The hull is complete when you reach p0 again.

Your task

Write a program that calculates the convex hull of a set of points. The program must read a file in the following format and output a similar file with valid convex hull section and (for full marks) correct area section. This file format is used by an online mapping application that you can use to view the original data and to verify your results. 

title  string
points
x y
x y
...
convex hull
p0 p1 p2 ...
area   areaofhull
end

Example

Input: 

title Trapezium with central point
points
33.1 4
53.7 58.3
45.4 36.3
5.5 51.2
72.1 26.6
end

Output: 

title Trapezium with central point
points
33.1 4
53.7 58.3
45.4 36.3
5.5 51.2
72.1 26.6
convex hull
3 1 4 0 3
area 2061.57
end

Area Calculation

For 4 marks of the available 19, calculate the area A of the convex hull using the Gauss-Green (or Shoelace) formula below. The formula applies to any n-point polygon, with coordinates indexed 0 to n–1. For the purposes of calculation, point n is the same as point 0.

The area should be displayed with at least 6 significant figures.

Assumptions

Test Cases

There are two test cases, the first contains coordinates of buildings and perimeter points on the 40ha UNSW Kensington campus, the second is a roughly circular 100-point cluster.

Test 1Test 2
title UNSW Kensington Campus
points
3360.25 62456.08
3369.57 62456.97
3360.70 62454.75
3364.15 62453.67
3361.80 62458.28
3369.22 62454.28
3365.69 62454.97
3363.40 62457.69
3367.82 62457.45
3359.69 62458.62
3360.81 62456.85
3366.44 62456.83
3366.94 62455.45
3360.25 62458.22
3367.96 62456.44
3369.04 62454.72
3364.19 62456.01
3363.70 62453.29
3363.89 62454.92
3360.72 62453.77
3366.31 62454.97
3361.87 62454.82
3365.36 62452.96
3367.98 62457.35
3368.24 62457.28
3365.25 62452.95
3360.72 62453.77
end

title Cluster 100
points
3937.2 2579.9
4128.1 5160.3
2501.1 3900.7
2058.1 3792.7
5784.5 4456.7
2495.0 4258.2
6444.7 6895.8
3836.9 3711.3
4698.5 2713.9
1963.8 3341.7
7055.1 4802.6
6488.8 1429.1
2185.0 2024.8
5966.3 7293.0
2833.1 2250.8
5804.4 5547.1
2384.0 5385.0
5677.9 4897.5
7321.8 3517.0
7032.0 5483.0
1910.0 6330.1
4579.2 4061.6
4531.6 2181.5
3205.3 2431.5
4139.0 5627.0
1516.4 3047.5
5328.0 5934.1
3372.4 5310.8
1373.5 1460.4
7009.8 5250.8
3196.0 6017.7
5777.5 4677.8
1711.6 1989.4
6716.6 5535.6
2817.8 5453.3
6854.3 6470.0
2468.6 1374.7
3673.3 4601.4
3031.7 4640.9
3709.2 3622.5
1317.1 1877.8
4205.4 4891.3
5542.6 6735.4
5956.5 4213.6
4565.8 3314.1
6710.6 6949.5
5378.2 1093.7
5028.0 6002.0
2440.1 7173.7
3524.7 5062.5
6166.9 6043.8
4433.3 3794.7
2126.7 1126.6
5661.2 2393.7
5781.9 5739.3
2737.5 1918.1
2838.7 6536.2
2434.3 1723.0
2827.5 2566.0
3741.7 4316.9
5707.6 3203.5
4336.1 6787.1
1104.4 5002.4
1122.7 6025.4
7072.5 2370.6
5980.7 5516.1
4092.2 2465.6
6030.1 4060.9
4180.5 1309.1
1389.0 4777.1
5797.9 5845.4
3781.7 2215.5
4764.4 6848.2
1223.0 2365.1
4379.0 4387.5
1323.2 4309.8
3339.5 3168.1
7120.1 1261.3
1917.5 5886.2
7133.7 4407.0
6968.6 6409.5
3156.5 6743.0
4324.6 1143.6
5657.7 2969.4
4783.7 2114.3
6606.6 1616.5
2857.7 7174.7
6667.3 3429.5
2152.7 3643.4
3397.4 3670.7
6224.1 2165.6
2753.6 2602.2
6304.1 6183.1
2941.0 2826.6
6256.3 2857.4
5741.1 3095.1
5830.9 5884.7
3796.5 1968.8
5091.1 6746.8
5101.9 1960.6
end