UNSW High Schools Programming Competition 2016: 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 or partly-working program and the program text itself is to be pasted into the submission boxes, unless otherwise explicitly stated. Do not submit code fragments that are a long way from doing anything, or requests for sympathy marks (requested sympathy marks are negative). Hand-crafted output will result in the team’s disqualification.
• Good luck and have fun!

The Tasks:

Junior task: Palindromes (easy, 7 marks) Task 1. Numeroman (easy, 7 marks) Task 2. Human Time (easy, 9 marks) Task 3. Traffic (easy to moderate, 11 marks) Task 4. Kris Kringle (moderate, 14 marks) Task 5. Moo (moderate to hard, 19 marks)

Task J. Palindromes

Available Marks: 7

A palindrome is a word or sentence that reads the same when written backwards, ignoring punctuation and treating capital letters and small letters as the same. So

radar
taco cat
Cigar? Toss it in a can. It is so tragic!

are all palindromes.

Your task

Write a program that determines whether phrases are palindromes or not. The first line of input contains the number of phrases (up to 20). The remaining lines have one phrase each. Each phrase has up to 70 characters. Your output is either Yes or No, followed by the phrase enclosed in quote characters.

Example

5
rotor
gnu dung
O Geronimo, no major ego.
Ten animals we slam in a net.
Harpo: not on Oprah?

produces...

Yes "rotor"
Yes "gnu dung"
 No "O Geronimo, no major ego."
 No "Ten animals we slam in a net."
Yes "Harpo: not on Oprah?"

Test data

Test your program using the following input text.

20
racecar
racing car
Tumut
a
stressed was I ere I saw desserts
Straw? No, too stupid a fad; I put soot on warts
Was it a car or a cab I saw?
Ed, I saw Harpo Marx ram Oprah W. aside.
Yes, Mel Gibson is a casino's big lemon.
Mr Owl ate my metallic worm.
Go hang a salami, I'm a lasagna hog!
On a clover, if alive, erupts a vast, pure evil; a fire volcano.
Dennis, Nell, Edna, Leo, Noel and Ellen sinned.
A man, a plan, a cat, a ham, a yak, a yam, a bat, a canal--Panama!
Steven, I left an oily lion at feline vets.
Put Eliot's toilet up.
Marg, let's send a sadness telegram!
Yawn....Madonna fan? No damn way!!
Red rum, sir, is murder!
'Reviled did I live,' said I, 'as evil I did deliver.'

Task 1. Numeroman

Available Marks: 7

Numeroman—is that a mathematical superhero? No, just a renamed number representation from a couple of thousand years ago. The Romans represented positive integers using 7 symbols, whose values are shown in the table below.

A numeroman number consists of a series of terms, and the value of the number is the sum of the terms. Each term is either

• a simple term, consisting of a single roman symbol, or
• a compound term, comprising a pair of symbols where the value of the first value is less than that of the second. The value of a compound term is the second symbol's value minus the first symbol's value. Thus XC is worth 90 and IV is worth 4.

To be valid, a numeroman must follow these rules

1. It must have at least one symbol, and only combinations of the seven symbols may occur.
2. Every term except the first must be no greater than the term to its left (otherwise the number would be ambiguous).
3. The term following a compound term must be worth less than the first symbol in the compound term.
4. Only the symbols C X and I can be used as the first (subtractive) symbol in a compound term.

(The original Roman Number system was slightly more restrictive than this.)

Your task

Write a program that determines whether a numeroman is valid, and if so converts it to decimal. The first line of input contains the number of numeromans (up to 20). The remaining lines have one numeroman each. Your output is either

• the decimal value of the numeroman if it is valid, followed by the input string, or
• The string "Bad" and the number of the rule violated (assume only one error can occur), again followed by the input string.

Example

6
DXI
CCXCVII
DM
DXCC
MCMLXXXVI
IXI

produces...

511    DXI
297    CCXCVII
Bad2   DM
Bad3   DXCC
1986   MCMLXXXVI
Bad3   IXI

Test data

Test your program using the following input text.

20
C
II
XXX
VI
MMXVI
MCC
MMMMDCCCLXXVIII
IV
XLI
CXCX
MCMLIV
DCLXVI
XCVYI
DCCM
MCMLXLIX
LC
XIX
XCV
XCI
LLIX

Assessment

• 5 marks - valid cases
• 2 marks - detecting invalid numeromans

Task 2. Human Time

Available Marks: 9

Telling the time on an analogue clock is one of the many things we have to learn as children. Digital clocks are accurate but boring, 10:45 is exactly what it says, 10 hours and 45 minutes. But to most people, that's a quarter to 11.

To humanise dull 24-hour digital robot times we will convert them to what a person might say if they saw the corresponding analogue clock (and knew what part of the day is it). Elements of the response include:

• mention minutes before the hour, but skip minutes completely if it's zero.
• use a minute if it's exactly 1 (by the way, any programmer whose software produces the phrase "1 items" or any other plural should be kicked out of the programmer's club).
• if the time is before the half-hour it's so many minutes past the hour, otherwise it's so many minutes to the next hour.
• use a quarter and half where appropriate.
• am or pm follows the hour, except for 12 noon and 12 midnight.

Your task

Write a program that efficiently converts robot time to human time (efficiency is defined below). The first line of input contains the number of times to be converted, a maximum of 20. The remaining lines have one 24-hour time each, in the form of four decimal digits. Each time is valid: that is, the first two digits lie between 00 and 23 and the second pair between 00 and 59.

For each time, display the original time, "is" and the human time according to the guidelines above, and consistent with the following example:

Example

7
0017
0400
0915
1155
1230
1445
2301

produces...

0017 is 17 minutes past 12 midnight
0400 is 4am
0915 is a quarter past 9am
1155 is 5 minutes to 12 noon
1230 is half past 12 noon
1445 is a quarter to 3pm
2301 is a minute past 11pm

Coding Efficiency

One measure of the quality of a correctly functioning program is how few decision points are used. For this kind of algorithm a decision point is typically a single comparison used in an if or elseif construct, or each branch of a multiway selection statement (switch, Select Case), or ternary conditional operator (? :, IIF). Multiple conditions combined with and or or count extra.

A good algorithm makes best use of every single decision, a poor algorithm will have many redundant decisions. The very worst algorithm to solve this problem would have 1439 decision points, a giant if-elseif... construct that treats each of the 1440 possible inputs separately.

Your secondary goal is to minimise the number of decision points in your solution (correctness is the primary goal of course). Target efficiency and corresponding acknowledgments are as follows:

Decision points	Achievement	Marks
*8 (or fewer)	Excellent	3/3
9 or 10	Good to very good	2/3
11 or 12	Not bad, could be factored better	1/3
more than 12	Still developing these skills	0/3

---

Hint: you might be able to eliminate one decision point (as defined) by using modular arithmetic. *A table that stores partial literal solutions counts the number of decision points it would require to set it up programmatically.

Test data

Test your program using the following input.

20
0000
0030
0315
0824
0830
0831
0845
1059
1100
1145
1155
1229
1244
1313
1533
2145
2252
2330
2337
2359

Assessment

• 6 marks - correctness
• 3 marks - efficiency

Task 3. Traffic

Available Marks: 11

Aspects of traffic flow can be analysed using quite simple models based on what are called cellular automata. One such model represents an intersection through which red cars move left to right and blue cars move top to bottom.

Each cycle of the model consists of two half-cycles,

• the red half-cycle, where the red cars move if possible, followed by
• the blue half-cycle, where the blue cars move if possible.

A car can move only when the cell ahead of it is empty at the start of the half cycle: consequently in any contiguous block of cars only the first one moves, not the whole block. The edges wrap around, so a car can move off the right edge to the left-most cell (if it's empty), and similarly from the bottom cell to the top cell.

In the diagram below (a) shows a configuration of order N=3, which is the length of each arm (maximum 40 for this task). There are 4N+1 cells in all. During the first half-cycle (b) two of the four red cars move, one of which wraps around to the left-hand cell. To complete the cycle (c) two of the three blue cars move, including one into the central cell. The bottom one can't move because the top was occupied at the start of the half-cycle.

We define velocity as the proportion of cars that move in a cycle, in this case the velocity is (2+2)/(4+3) or about 0.571. Velocity can change over time, and can trend to 1 (freeflowing traffic with no blocked cars), or to 0 (gridlock), or it can become periodic as the system stabilises.

Your task

Write a program that simulates this traffic flow model. Input consists of three lines: the first contains N, the system size, and the required number of cycles to be simulated. The second line contains the layout for the red row (left to right) and the third contains the layout for the blue column (top to bottom). R or B represents a car and a dot (.) represents an empty space. The central cell is shown twice. Assume the data is valid.

During the simulation you must keep track of the velocity on each cycle. At the end of the simulation display the last cycle velocity and the average velocity, then the final configuration in the same format as the input.

Example

This is the above example, but iterated over 5 complete cycles.

3 5
.RRR..R
B.BR..B

produces...

Current velocity: 0.714, average velocity = 0.600
.RR..RR
B.B.B..

Test data

Test your program using the following 3 test cases.

Test 1:

4 7
R..R..R..
..B..B..B

Test 2:

17 80
.RRRRRRRRRR.RRRRRBR..RRRRRRRRRRRRRR
BB.BBBB.BBBBBBBBBBB.BBBBBBB.BBBBBBB

Test 3:

40 100
.RRRR.RR..RR....RR..R.....R.R.RR......R....RR....RR..R..RR.RR..R....RR.R.....R.R.
..B.....B.BBB.BBB.B......B..B...B.B..BB.........B....B.B.BBB..B.B.B.BB.BBB...BB.B

Assessment

• 3 marks for Test 1
• 4 marks each for Tests 2 and 3

Task 4. Kris Kringle

Available Marks: 14

In a largish group of friends or extended family buying presents for everyone can be difficult and expensive. A simple scheme to manage the problem is for each person (a gifter) to be assigned just one other person (the giftee). The giftee doesn't know the identity of the gifter, who masquerades as the anonymous Kris Kringle or Secret Santa.

To make the assignment of the giftees more interesting, members of certain groups such as immediate families are never assigned giftees within their group. Further, in any solution there are no gifting cycles of length less than N, the number of people. A gifting cycle is where A gives to B, B gives to C, ..., and eventually X gives to A. For example, if Peter gives to Anne, Anne gives to Isan and Isan gives to Peter, the cycle length is 3.

Your task

Write a program that assigns giftees for a Kris Kringle system. The first line of input contains two numbers: the number of people and the number of groups that follow. The remainder of the input is a list of groups (including groups with one member), one per line. Group members are strings without spaces, each up to 10 characters in length, separated by a space.

Output should consist of one possible solution to the problem, in the form of a gifting cycle, if one exists, followed by the number of distinct solutions. A distinct solution is one that can't be derived from another by rotation: every solution has N rotations that are all equivalent, they just have different starting points.

Example

8 3
Amy Chunjie Eve Gail
Bruno
Dave Feng Heidi

produces...

Amy Bruno Chunjie Dave Eve Feng Gail Heidi Amy
Solutions: 144

(or any of the 143 other possible solutions).

Test data

Test your program using the following 3 test cases.

Test 1:

8 8
Angela
Ka-Ho
Sophia
Yusuf
Elise
Junjie
Kevin
Lakshan

Test 2:

7 3
C-3PO R2-D2
Chewbacca HanSolo Luke Leia
Yoda

Test 3: (Android Kris Kringle)

12 3
bWUJVG3818 VhbiBO8820 TWVtYm8623 VyIDEg9042 QgTmFt3907
ZQlUZW5706 JlciAx4231 VGVhbS5340 ZXIgMi5162 BGaXJz1610
YmVyID2004 dCBOYW6101

Assessment

• 4 marks for Test 1
• 5 marks each for Tests 2 and 3

Task 5. Moo

Available Marks: 19

In the game of Bulls 'n' Cows, one player thinks of a 4-digit number with no repetition, an initial zero is allowed. The other player tries to guess it. Each guess is scored according to the number of bulls (correct digits in the right place) and cows (correct digits but in the wrong place). The second player then uses logic to identify the secret number using as few guesses as possible.

For example,

secret number  0638
guess          6438
score          BBC

indicating two bulls and one cow. Note that scoring is symmetric: you get the same response if you swap the guess and the secret number.

Computer simulations of the second player have been around since the late 1960's. The simplest approach is for the program to maintain a list of candidates, or numbers that could still be the secret one. After each guess and response, candidates that produce a different response when matched against that guess are removed from the candidate list. The candidate list reduces to a single answer in around five guesses, even when guesses are chosen arbitrarily from among the candidates.

To implement the whole game in one program we have to modify the scoring algorithm so the answer isn't immediately obvious to you while you're coding and running it. There are two parts to the SOB (Slightly Obfuscated Bulls'n'cows) scorer:

1. An encoder that converts a 4-digit number g to a positive integer r less than 2³⁰ using this algorithm:
   
   where mod is the modulus (remainder) operator, represented in most programming languages by %.
2. A matcher that produces the score from two encoded numbers gcode and scode using this algorithm:
   
   where the brackets denote truncation to integer. The score is the string b followed by the string c.

Your task

Write a program that firstly implements the encoder, then the matcher, and finally solves the game for any given valid encoded secret number (or encoding).

Hint: for testing purposes, encode(4791) = 620781575. When your encoder is working, you can easily generate test cases for the scorer. For example, by inspection match(620781575, encode(7094)) = BCC.

To make the results consistent, your program should select the middle element of the remaining candidates in order as the guess (if there's an even number of elements, use the larger of the two midpoint indexes). It should also display the progress of the game in a format similar to this, which is for the encoding 83916806:

Initial candidate list size = 5040.
Guess 1 5012 gives BC   Candidates remaining: 720
Guess 2 5304 gives      Candidates remaining: 48
Guess 3 6172 gives CCC  Candidates remaining: 14
Guess 4 2917 gives BBCC Candidates remaining: 2
Guess 5 9217 gives BCCC Candidates remaining: 1
Solution: 2719

Assessment

• 3 marks - encoder
• 4 marks - matcher
• 11 marks - full game solver
• 1 mark - finding the dodgy encoding, but –1 for guessing incorrectly