UNSW High Schools Programming Competition 2017: 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: Fitness Friend (easy, 7 marks) Task 1. Isomorphic Word Pairs (easy, 7 marks) Task 2. Rats (easy to moderate, 9 marks) Task 3. Queue Jumpers (easy to moderate, 10 marks) Task 4. Inheritance (moderate, 14 marks) Task 5. Connect-4 (moderate to hard, 20 marks)Task J. Fitness Friend
Available Marks: 7
Smart watches now provide heart rate, walking speed, energy consumption, step counters and sometimes even the time. Everyone knows they should try to walk a certain minimum number of steps each day, and watches will often set a new target daily based on the number of steps taken over the last few days and the current target. Fitness Friend, ProgComp's proposed software that will only get to market if you can implement it for us, goes one step (sorry) further.
Some people are discouraged if they keep failing to reach their target: they have low motivation. Others try to outdo themselves every day and want an always-increasing target: they're highly motivated. Fitness Friend introduces a self-nominated motivation factor M, an integer between 0 and 100. The way it works is shown in the diagram below.
The new-target calculation is given by two similar formulas, depending on whether today's target was reached:
For example, if M is 45, T is 7500 and S is 7125, the second formula gives
T ′ = 7500 + 0.3025 * (7125 – 7500) = 7500 + 0.3025 * (–375) = 7500 – 113.4375 = 7386.5625
Your task
Write a program that calculates the daily targets given motivation and daily step counts, collecting simple statistics to report at the end. The first line of input has the Motivation Factor and starting target, separated by a space. The rest of the input has the daily steps, one per line. A negative value ends the list (and isn't counted as step data of course).
Your program should list all the targets on one line, then on a new line show
- motivation
- the number of days
- the mean (average) daily number of steps
- the percentage of days when the target was reached
- the final calculated target
Example
80 7500 8231 7700 9015 6000 -1produces...
7500 7967 7956 8633 8527 Motivation 80, days 4, mean steps 7736, goal reached 50%. Final target 8527If the same step data is used but the motivation is changed from 80 to 30, the targets are more modest and the goal is reached more easily:
7500 7565 7577 7706 6870 Motivation 30, days 4, mean steps 7736, goal reached 75%. Final target 6870
Test data
Test your program using the following data.
60 8200 8350 10245 9254 7957 7880 7885 8194 8114 10176 9625 8492 9550 9483 10498 10511 9033 9215 10655 9791 8210 10664 8251 9800 8310 9614 7682 9327 7785 10527 9881 -1
Bonus Points
Simple programs can sometimes be used as tools to analyse aspects of the problem area. In this case there's an interesting relationship between motivation and the final target, which is monotonic increasing (this just means the greater the motivation, the higher the final target). By changing the motivation in the data file and rerunning the program, you could identify points on the relationship curve, or estimate the motivation required to set a specified target for this data set.
Use the program, without changing it at all, to find out what motivation is required to achieve a final target of 9888 for the steps in the test file (888 is an auspicious number in some cultures). Be smart about this, like the watch: try 50, halfway between 0 and 100. if the result is too high try 25 (halfway between 0 and 50), otherwise try 75. Keep going this way, choosing the midpoint between the deduced smallest and largest possible motivation, according to each result. This technique is called binary search, and is an important programming principle. While you're not programming it here, you are applying it to avoid having to try all possibilities. It will give you the answer in no more than 7 tries (log2 100). For bonus points, show each motivation value you tried, the last one being the answer. You get one for the correct answer but two for the binary search technique (if done approximately correctly). Note: bonus points are not included in the qualifying score for the finals, sorry.
Assessment
- 5 marks - target calculations
- 2 marks - statistics
- Bonus 3 marks - analysis (not counted toward the finals)
Image source: myelmm.com
Task 1. Isomorphic Word Pairs
Available Marks: 7
Two words are called isomorphs (or more accurately, form an isomorphic pair) if they have the same length and the same pattern of repeated letters. The letters don't need to match between the words, only the positions where the repetitions occur. Isomorphs are of interest because one could be converted to the other using a simple substitution cipher.
Consider the words estate and tenant. In both cases the first letter is repeated five places later, and the third letter two places later. Letters in the other positions are not repeated. Define a repetition pattern to be an ordered list of relative positions where each letter is next repeated, with 0 indicating no repetition and a + preceding the repetitions for better readability. Thus both words have the repetition pattern
+5 0 +2 0 0 0The same rules apply even if a letter occurs more than twice, so the words cannon and kisses have the pattern
0 0 +1 +2 0 0People who like wordplay look for isomorphic pairs that form an incongruous phrase, like dysfunctional ventriloquism, but that level of semantic analysis is beyond even ProgComp entrants.
Your task
Write a program that identifies whether pairs of words are ismorphs. Input consists of the number of pairs on the first line (maximum 20), and then each pair on subsequent lines, separated by a space. Words are between 1 and 20 letters long, all lower-case, no punctuation.
For each pair, your program should list the two words and classify them as either
- different lengths, or
- not isomoprhs, or
- isomorphs, and show the common repetition pattern.
Example
6 secret cowboy yummy tweet exponential amputations reflective programmer financial turnaround cutthroat communismproduces...
secret, cowboy are isomorphs with repetition pattern 0 +3 0 0 0 0 yummy, tweet are isomorphs with repetition pattern +4 0 +1 0 0 exponential, amputations are isomorphs with repetition pattern +5 0 0 0 +2 0 0 0 0 0 0 reflective, programmer are not isomorphs financial, turnaround have different lengths cutthroat, communism are isomorphs with repetition pattern 0 0 +1 +5 0 0 0 0 0
Test data
Test your program using the following input.
20 all inn doll door level kayak squeaky sunlamp gutless sheriff trapdoor flywheel mistiest monsoons throwaway hepatitis explosive magnesium wealthiest subterfuge kookaburra toothbrush sportswomen spokeswoman tightfisted hitchhikers cryptography manipulation sharpshooter marshmallows ambidextrous thunderclaps incompatible housewarming sportsmanlike environments disfranchised stepdaughters fastidiousness lasciviousness
Source:
Task 2. Rats
Available Marks: 9
RATS (in this context) stands for Reverse, Add, Then Sort, applied to a positive decimal integer. It's the generating algorithm for an integer sequence that either diverges, or enters a reasonably short cycle. Consider the integer 180. Reversing the digits gives 081, or just 81. 180 + 81 = 261. Sorting the digits gives 126.
Continuing,
126 + 621 = 747, sorted = 477 477 + 774 = 1251, sorted = 1125 1125 + 5211 = 6336, sorted = 3366 3366 + 6633 = 9999, sorted = 9999 9999 + 9999 = 19998, sorted = 18999 18999 + 99981 = 118980, sorted = 011889 11889 + 98811 = 110700, sorted = 000117 117 + 711 = 828, sorted = 288 288 + 882 = 1170, sorted = 117So the sequence ends in a cycle of period 2 (the period of a cycle is the number of different values it contains).
Only a small number of different cycles can occur, we want to find them.
Your task
Write a program that identifies all cycles that occur for starting numbers less than 10000 (or 1000 for fewer marks). If any sequence element exceeds 1012, you may assume the sequence diverges. Complete answers depend on your computer using 64-bit arithmetic. In the event that your calculations use 32-bit arithmetic and overflow occurs, you will not be penalised provided the other cycles are reported correctly.
Your program's output should consist of one cycle on each line, ordered by period and then by the smallest member of the cycle. Each line should show three data items:
- the cycle period;
- the number of starting values that lead to that cycle; and
- the members of the cycle in order of occurrence, starting with the smallest member.
Period: 2, occurs 100 times, cycle: 117 288
Assessment
Full marks will be awarded for correctly identifying all cycles and displaying the details according to the requirements.
Deductions apply for incorrect identification, or if you don't cover all 9999 starting values, or for not displaying the data in the required order.
Reference: Weisstein, Eric W. RATS Sequence. From MathWorld--A Wolfram Web Resource.
Image: and bear makes 3. Photographer: Jessica Florence
Task 3. Queue Jumpers
Available Marks: 10
The residents of Q-Town love queuing for the theatre. Some of them also consider particular position numbers to be lucky, so there can be a lot of undignified jostling while waiting in line. The Mayor of Q-Town wants to put a stop to this unseemly behaviour. She decrees that all theatregoers must adhere to the following rules:
- People initially form a queue in the order they arrive at the theatre.
- Just before the theatre opens, everyone in decreasing age order is allowed to nominate a position in the queue they would like to occupy.
- Nobody can nominate a position that has already been nominated, so all nominations are distinct, and
- Nominations are optional.
On the mayor's signal, everyone re-orders themselves in a dignified way. Those who did not nominate a position are shuffled up or down the queue as needed, maintaining their relative order.
Your task
Write a program to manage Q-Town's orderly queuing system. Input consists of one queuing problem per line, preceded by the number of problems. Each queuing problem consists of the number of patrons, to a maximum of 26, and the position each one would like to occupy. Positions are counted from 1, and 0 means no nomination.
People are allocated an upper-case letter in the original queue order, and the solution is the new arrangement of letters representing the revised queue. Assume the data is valid. The program should show both the original order and the final order on separate lines, with a space between each letter.
Example
3 3 0 0 0 9 9 8 7 6 5 4 3 2 1 5 0 1 5 0 2produces...
A B C A B C A B C D E F G H I I H G F E D C B A A B C D E B E A D C
Test data
Test your program using the following data.
5 4 4 2 3 1 6 0 0 5 3 4 1 13 0 0 1 2 3 4 5 6 7 8 9 10 11 26 12 13 3 0 15 0 9 10 8 0 0 14 0 2 4 5 0 7 0 11 1 0 0 0 6 0 1 0
Assessment
- 2 marks per problem.
Image: Microsoft Corp. clipart
Task 4. Inheritance
Available Marks: 14
The system of inheritance that applied to most families with land or a title in England until recent times was called entailment. It was designed to keep the family estate intact as far as possible, by passing ownership to one (generally male) person at a time. Instead of all children, or even just all sons, inheriting the estate on the death of an owner, the eldest surviving son inherits the lot. This rule then applies recursively to his sons. Thus all his male descendents are ahead of his younger brothers, his brothers are ahead of his uncles, and so on.
If all male descendents of the original owner are deceased, surviving females are next in line to inherit, but under these conditions:
- The inheritance rules still follow the eldest male line in order to rank females, and
- Sisters inherit equally (thus potentially breaking up the estate, which would be transferred to other families on marriage).
Example
The family tree below shows all the descendents of the original owner, M0. M0 and his eldest son M1 are deceased, and M1's eldest son is the present owner. The numbers in parentheses record the order of inheritance that would apply when M4 dies.
First in line is M4's brother M5 (because M4 has no male heirs), then M5's first son, his grandson, etc. Following all 10 surviving males, the same rules apply to females, starting with M4's daughters, who are jointly 10th in line. In practice males are assigned on a pre-order traversal of the male-line tree and females on a post-order traversal of the male-line tree, which is why F6 inherits ahead of F1.
Note that the structure doesn't depend on who's still alive: although dead people can't inherit, their living descendents can.
Your task
Write a program that analyses a family tree and prints the order of inheritance. Input consists of one line for each male, listing his children in descending order of age. The first input line is the number of males. Each person is identified by gender (M or F) and a non-negative integer, unique to that gender. The original owner is always M0, other numbers can be assigned in any order, but without gaps.
For each line the patriarch's ID is followed by an optional symbol and a colon, then the IDs of the children. The symbol is either
- x, indicating the person is deceased, or
- *, indicating the present owner.
Output is the present owner and the order of inheritance in one line, separated by spaces.
Sample data
This describes the tree above. It's already sufficiently complex to fully exercise your program.
12 M0x: M1 F1 M2 M3 M1x: M4 M5 F2 M6 F3 M3: M4*: F4 F5 M5: M8 M9 M10: M8: M11 M6: M10 M7: F6 M2: M7 M9: M11:produces...
M4 M5 M8 M11 M9 M6 M10 M2 M7 M3 F4+F5 F2+F3 F6 F1
Test data
Test your program using the following two test cases.
Test 1:
11 M0*: M3 M6 M1: M5 M2: M1 M3: M4: M10 M2 M5: M6: M7 M9 M7: M8: M9: M8 M4 M10:
Test 2:
17 M0x: M3 M14 M11 M4: M8x: F2 M4 M15 M5 M12: M8 M10 M16: M5: M14x: F3 M12 F5 M3*: M9: M6: M13 F4 M10: M9 M6 M2 M2x: M13x: M11: M16 F1 M1 M1: M15: M7 M7:
Assessment
- 5 marks for Test 1
- 9 marks for Test 2
Reference: Background information and example are from
Churchyard, Henry (2004-2011).
Pride and Prejudice -- Notes on Education, Marriage, Status of Women, etc. Republic of Pemberley.
Image: talentenbank
Task 5. Connect-4
Available Marks: 20
The Connect-4 game board consists of 7 vertical slots or columns, numbered from 0 to 6, each of which can accommodate up to 6 tokens. Two players take turns to place a token in a slot, we're calling them Red and Yellow. The winner is the first player who has 4 of their tokens in a line, horizontally, vertically or diagonally.
Although the game can be fully solved with enough effort, a fair-to-average player can be simulated by scoring possible game positions and looking only a couple of plies ahead (a ply is an action by one player, two plies make up a move). The scoring system assigns points to each sequence of a player's tokens that have a reasonable chance of becoming a winning line. The scoring system to use for this task is as follows:
- To simplify the problem only contiguous lines of tokens are considered, not those with a gap that could be closed by a future move.
- A PWP occurs when there are three tokens in a line, with an empty spot where the fourth would be (that's what we mean by aligned), plus exactly one empty spot below it. If the opponent chooses this column (and doesn't win) your reply in the same column will produce a win.
- Three in a line can score PWP or triple at both ends, depending on how many empty positions there are, but a pair scores only once.
- The last two features bias the selection toward the middle columns in the early part of the game, because those columns figure in all but vertical wins.
The board is represented by 7 fixed-length strings, one for each vertical slot or column. This format best suits operations such as temporarily adding or removing a token, used in game play. Each character is a token (R or Y) or an empty position (a dot). Every legal board column thus begins with zero or more tokens, then empty symbols to make up 6 characters. You can use a different internal representation of course, but input/output uses this format.
Consider the following board:
RR.... ...... YRRYR. YYR... RYYR.. RYY... Y.....It scores 37 for player R (majority in col 2, pair in col 0, pair in row 2 and a diagonal line of three producing a triple at one end and a PWP at the other). For player Y the same board scores 44 (centre col majority, pair in col 5, triple on row 1, two diagonal triples in one direction and one in the other).
Your task
Write a program that can read boards and score them for a designated player, and for full marks, can also play a full game against a player using a limited strategy. Input consists of board layouts preceded by a line containing score and either R or Y. A line containing the word end terminates the input. Output is a copy of the board in the same format (so we know you've read it properly) and the nominated player and calculated score on the next line. If you were scoring R for the above layout the output would be
RR.... ...... YRRYR. YYR... RYYR.. RYY... Y..... Player R scores 37
To play the game (say after processing the normal input), use the following strategy exactly:
- The board is initially empty, you are Red and you move first.
- For each move, consider each of your possible 7 choices (fewer if a slot is filled), and for each of these positions calculate (a) your score, and (b) the maximum that your Yellow opponent could then score for any possible reply.
- Display (a) and (b) for the judges to check or N/A if that slot is full, and choose the first column that maximises the difference (a)–(b).
- Having made your part of the move, allow your opponent to choose their reply with the column that maximises their score. However they do not look ahead to your response: they have only a 1-ply lookahead compared to your 2-ply. This means R can block but Y doesn't know how to, so you should win.
- Display the board after each full move is complete (yours and your opponent's), and after the game ends.
R..... Y..... YRRY.. YYRY.. RYR... R..... Y..... Move 9: scores 48-29, 34-40, 47-29, 45-29, 54-20, 37-37, 45-26 R selects column 4 Reply score 20 Y selects column 5 R..... Y..... YRRY.. YYRY.. RYRR.. RY.... Y.....
Test data
Test your program using the following data.
score Y ...... YRR... YY.... YRR... RRR... YYY... RRY... score R ...... YR.... RYR... YYRRY. YRYYY. RRY... RRY... score Y RYRYY. RYY... RRRYR. YRY... RYRY.. R..... RRR... score R RRYRYY YRY... YRRRYR RYRY.. YRYRY. ...... RRR... score Y YRYRY. RYRYR. YRYRY. YRYRYR RRYRR. Y..... RY.... score R RYRY.. YRYR.. YRR... RYYR.. RYY... YRYR.. RYRY.. end
Assessment
- 14 marks - scorer
- 6 marks - game play
Image source: wikimedia