Rules • Any ﬁles referenced in the questions are available in the folder for that speciﬁc question in the zip ﬁle available at http://tinyurl.com/chsprogcomp. • All the questions are worth 10 marks, but for every 3 incorrect submissions you make, the maximum number of points you can achieve for that question will decrease by 1. That is, if you make 2 incorrect submissions, then you will get 10 points.
If you make 3, you will get 9 points. If you make 7, for example, you would get 8 points. If you made 5 incorrect submissions and did not end up getting it correct, you would not lose any marks (but obviously you would not get any marks either). • Achievements work in the same way, but are only worth 5 marks. • If people are on the same score, the time at which the people recieved said score is used as a tiebreaker
• You may ask us non programming related questions, such as ”when will we ﬁnish”, ”why is there no smoke coming out of my monitor”, and ”what does ¡insert question here¿ mean by ¡insert statement here¿”. We may make an announcement about the problem in question if it is relevant to everyone.
• You may also ask implementation questions, such as ”what is the function that calculates the sum of numbers in a list in python”. • No web browsers (except to download the question data and to submit answers). • You may open this booklet at 3:15pm. Have fun, and good luck!
Consider the following python code (can be run in python3 or python2): n = int(input("Enter the size: ")) for i in range(1, n + 1, 2): spaces = (n - i) // 2 print((" " * spaces) + ("*" * i)) This code is also available in example.py. When run in IDLE, it draws a triangle of suns - try it out! An input of 10 draws 25 suns. How many suns does it draw when the input is 100?
Achievement: Metasuns Let us deﬁne a metasun as a set of suns drawn in a sun-like shape. To begin with, we can draw a diamond of suns by extending the code above to print 2 triangles (ﬁrst growing, then shrinking). Then we can add 4 straight ’rays’ of length 3 that extend 1 unit away from the sun’s center (in 4 directions). Like the triangle from the previous question, a metasun of even size will look the same as a metasun of 1 size smaller. For example, a metasun of size 9 or 10 would look like this ( represents a space): ________*________
________*________ ________*________ _________________ ________*________ _______***_______ ______*****______ _____*******_____ ***_*********_*** _____*******_____ ______*****______ _______***_______ ________*________ _________________ ________*________ ________*________ ________*________ In the metasun of size 10, 53 suns are printed (41 for the main part, 12 around it). How many suns will be printed in a metasun of size 1000?
Most Common Word
There is a copy of pride and prejudice text of Pride and Prejudice located at pandp.txt. What is the most commonly occurring word with 5 letters or more, and how many times does it occur? If the answer was ”programming”, and it occured 92 times, you would input into the answer column ”programming 92” (minus the quotation marks). The restrictions on a word are:
• Case does not matter: treat ”Then” and ”then” and ”ThEn” as the same word. • Punctuation should be ignored
Achievement: Bigram A bigram is two words that appear in a row. For example, in the phrase ”The big red ball is near the big box”, the trigram ”the big” occurs twice, but ”big red” only occurs once. Find the most common bigram in the text ﬁle. What is this bigram, and how many times does it occur? Similar to the answer to the previous question, if the answer was ”programming rocks”, and it occured 73 times, you would input into the answer column ”programming rocks 73” (minus the quotation marks).
Tilt is a new arcade game that involves rolling a single ball down a pinball style machine. The ball (called a tiltball) starts on the top of the machine. The player can tilt the playing surface left or right whilst playing to inﬂuence the horizontal movement of the ball, but cannot slow the ball’s descent towards the bottom. Unlike pinball, there ane no paddles to bounce the ball back - once it reaches the ﬁnal row, the game ends. Each square on the game board is associated with a score, which you gain if the Tiltball passes through that square.
The ball descends fairly fast, so you are unable to score more than one square on each row. However, by tilting the surface, you are able to decide which of the two squares immediately below the current square you will hit next. Being a programmer, you decide to write a pragram to calculate your maximum score. Consider the following game. By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum score from top to bottom is 23. 3
7 4 2 4 6 85 9 3 That is, 3 + 7 + 4 + 9 = 23. Find the highest score you can reach by playing tilt on the machine located at small.txt.
Achievement: Professional Tiltballer After having some fun playing regular tilt, you decide to challenge yourself by playing on one of the jumbo machines, which has a much larger board (and hence a much larger total score). Finding the maximum total score on this new grid will be tougher, as there are many more combinations - Maybe a diﬀerent technique is in order. Find the score produced by the best path down the jumbo tilt machine located at large.txt.
It is World Youth Day, and you have joined the masses in Sydney ﬂocking to see the Pope. The crowds are enormous, and you decide there is only one way that you will be able to meet His Holiness to obtain an autograph: crowd surﬁng.
The stadium is a large rectangle with the Pope standing in the south-east corner. Your hope is the crowd will carry you above their heads from where you are standing all the way across to the Pope. Unfortunately the crowd is not very organised–some sections of the crowd will carry you south, some sections will carry you east, and some sections are so disorganised that they will just drop you back onto the ground.
As an example, consider the map above, where the stadium is broken into a 4 x 5 grid of squares. The arrows show the direction in which the crowd will carry you from each square, and the stars indicate squares in which the crowd will drop you. Suppose you begin in the top left square. The crowd will carry you south, then east, then south, then three squares east, then south again to where the Pope is standing. On the other hand, suppose you begin in the bottom left square. In this case, the crowd will carry you two squares east and then drop you.
Your task is to decide how many starting points are bad, i.e., will lead you to being dropped. For the example above, there are eight bad starting points; these are indicated with crosses in the diagram below.
The input will describe the stadium as a grid of squares, and will show how the crowd moves you from each square. Each square of the grid will be described by one of the characters ’v’, ’>’, ’*’, or ’+’:
• The character ’v’ represents a downward pointing arrow, i.e., the crowd moves you south. • The character ’>’ represents a right pointing arrow, i.e., the crowd moves you east.
• The character ’*’ represents a square in which the crowd drops you.
• The character ’+’ represents the pope. This will appear as the ﬁnal character of the ﬁnal line, and will not appear anywhere else in the grid.
It is guaranteed that no arrow will point outside the grid. That is, no arrows in the rightmost column will point right, and no arrows in the bottom row will point down. For example, the following data represents the diagram earlier: v*v>v
>v>*v v>>>v >>*>+ Calculate the amount of bad squares in the 100x100 grid in small.txt.
Achievement: Large crowds Calculate the amount of bad squares in the 1000x1000 grid given in large.txt.