UNSW High Schools Programming Competition 2015: 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 program and the program text itself is to be pasted into the submission boxes, unless otherwise explicitly stated. Hand-crafted output will result in the team’s disqualification.
• Good luck and have fun!

The Tasks:

Junior task: Kaprekar Numbers (easy, 7 marks) Task 1. 64 Doors (easy, 7 marks) Task 2. Goonerism Spenerator (easy to moderate, 9 marks) Task 3. Partitions (easy to moderate, 11 marks) Task 4. Google Polyline Encoding (moderate, 14 marks) Task 5. Magic Stars (moderate, 19 marks)

Junior Task. Kaprekar Numbers

Available Marks: 7

This stern looking gentleman is Mr D R Kaprekar (1905–1986), an Indian schoolteacher and recreational mathematician. Among his many achievements is the discovery of a set of numbers with interesting properties that now bear his name.

Consider a positive integer k with n digits. Follow these steps:

1. Square k.
2. Split the result into two pieces, the last n digits and the rest.
3. Add these pieces (if one is empty, treat as zero).
4. If the sum is equal to k, then k is a Kaprekar number, otherwise it's not.

Example

1 and 45 are both Kaprekar numbers because

1*1 = 1 and 0 + 1 = 1
45*45 = 2025 and 20 + 25 = 45

but 123 is not since

123*123 = 15129 and 15 + 129 is not equal to 123

Your task

Write a program that displays all the Kaprekar numbers less than 10000, on one line. A god solution is to write a function that tests an integer to see if it's a Kaprekar number, then use it in a loop that tries all possibilities. If your programming language doesn't support mixing integers and strings, you may need to use a built-in function to convert the number to a string so you can pick off the last n digits. Alternatively you can use modular arithmetic (% or Mod operator).

If you've just started programming, for partial marks just write a program that reads a number, determines if it's a Kaprekar number or not, and displays a suitable message that includes the number. Test it, one at a time, with each of these numbers

45 673 272 2223 7381 7777 9998

Remember, only paste unedited output from your program.

---

Reference: Wolfram Mathworld. Image source: Wikimedia

Task 1. 64 Doors

Available Marks: 7

In a monastery in a faraway country there is a chamber with 64 doors numbered 1 to 64. Every year the 64 monks that live in the monastery participate in the following ritual.

All doors in the chamber are initially closed. Each monk is assigned a unique integer between 1 and 64. The monks then enter the chamber one at a time, in numeric order (though that doesn't affect the outcome). If a monk is assigned the integer k, he changes the state of every k-th door. That is, if the door is closed he opens it and if it's open he closes it.

So the first monk changes every door (from closed to open), the second changes doors #2, #4, #6 etc, the third changes #3, #6, #9 etc, and so on until the last monk, who just changes #64.

At the end of the ritual the doors that are currently open lead to (spiritual) treasures, so their numbers are significant.

Your task

Write a program that simulates the ritual and displays the numbers of the doors that are open at the end, on one line.

---

Task adapted from: Rosetta Code. Image source: info.xfactorllc.com

Task 2. Goonerism Spenerator

Available Marks: 9

Spoonerisms are phrases where the non-vowel prefixes of non-trivial words are mixed up. For example, "a crushing blow" might become "a blushing crow". They are named after the Reverend William Spooner (1844–1930), an Oxford lecturer whose tongue (it is said) could never keep up with his thought processes.

The spoonerism generator to be written to solve this task must follow certain rules.

1. Each input phrase consists of words in lower case separated by a space.
2. Trivial words are unchanged (see list below).
3. Words starting with a vowel (a e i o u) are unchanged.
4. The prefix of each word starting with a non-vowel replaces the prefix in the next word to its right that has a prefix, with the last prefix replacing the first. A prefix consists either of all initial non-vowels or the special prefix "qu".

For the purposes of this task, trivial words are words with 2 or fewer letters, or any of the following.

for has have she that the this will with
"for", "has", "have", "she", "that", "the", "this", "will", "with"

The quoted list may be suitable to copy to your program.

Your task

Write a program that reads in phrases and displays the corresponding spoonerisms. The first line of input contains the number of phrases (up to 20). The remaining lines have one phrase each. Each phrase has between 1 and 25 words, and a total length of up to 100 characters.

Example

4
bouncing tree
a blushing crow
we will have the flags hung out
the three little pigs and the big bad wolf

produces...

trouncing bee
a crushing blow
we will have the hags flung out
the wee thrittle ligs and the pig bad bolf

Test data

Test your program using the following input text.

18
belly jeans
bat flattery
flutter by
pop corn
this is the fun part
my spoonerism generator
a lack of pies
go and take a shower
i hate with my mind
pain in the posterior
anthropomorphism 
hickory dickory dock
the rain in spain falls mainly on the plain
pack my box with frumpy dozen lusty jugs
strange women lying in ponds distributing swords is no basis for a system of government
this caged parrot is no more
the quick brown fox jumps over the lazy dog
back home after jiving she expired with quizzicality

You can obtain part marks for a limited solution, for example only swapping two word prefixes or not ignoring trivial words, but your program must at least correctly identify word prefixes.

---

Image source: Wikimedia, via telegraph.co.uk

Task 3. Partitions

Available Marks: 11

A partitioning algorithm rearranges a list of values into contiguous groups that have similar properties. The boundary between adjacent groups is called a partition. The partitioning algorithm to be developed for this task moves negative elements to the left of the array, moves positive elements to the right of the array, and moves zero elements to the middle. Within the three partitioned groups the order of values doesn't matter (this is not a sorting algorithm on its own). Partitioning is trivial if an additional array is used, but the problem is more interesting if only scalar (single element) variables are used.

Your task

Write a program that partitions lists of integers. The first line of input contains the number of lists and their length (between 1 and 25). Each subsequent line contains a list, with elements separated by a space. The program should display the partitioned lists, one per line. For display purposes, the partitions are to be shown with a vertical bar and a space either side.

Example

The upper chart on right shows the list

4 0 -5 -2 1 0 8 -9 6 4 0 7 -5

It has many possible partitionings, one of which is shown on the lower chart. It would be displayed as

-5 -9 -5 -2 | 0 0 0 | 8 6 4 1 7 4

Restrictions

1. You may use only one array or list structure to hold the original list, and that array must be partitioned in place by moving or exchanging elements.
2. Elements must be inspected and altered by indexing, no high order functions such as map or equivalent may be used.
3. Apart from input and output, your algorithm must not make more than 2 passes over the array.

Recommended Approach

Although you can try to do a 3-way partition in one pass, a good approach is to write a much simpler 2-way partition procedure, and use it twice, once to push elements of a particular sign to the appropriate end, and then to partition out zeroes in the other part of the array. Each pass will handle zeroes slightly differently.

Test data

Test your program using the following input.

8 17
-7 -9 -3 -4 -66 -3 -2 1 7 5 32 1 4 67 8 5 3
1 2 4 3 7 2 0 3 1 0 0 4 1 8 0 3 0
-1 -2 -9 -4 -3 -1 -7 -88 -34 -21 -3 -76 -4 -9 -12 -51 -94
0 4 -3 0 1 1 0 -4 -5 5 0 3 -4 5 2 7 0
10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6
-1 -1 -1 -1 -1 3 -2 -3 1 0 1 1 0 1 1 1 1
0 1 2 3 2 1 0 -1 -2 -3 -2 -1 0 1 0 1 0
1 2 3 2 1 2 3 2 1 2 3 2 1 2 3 2 1

---

Task 4. Google's Polyline Encoding

Available Marks: 14

Among the Google Map API's useful tools is the ability to define linear features such as tracks and contours. In normal circumstances the coordinates defining the feature are supplied through a series of LatLng object instantiations, such as this javascript code:

var lineCoordinates = [
  new google.maps.LatLng(-36.44368, 148.32638),
  new google.maps.LatLng(-36.44375, 148.32634),
  new google.maps.LatLng(-36.44377, 148.32633),
  new google.maps.LatLng(-36.44388, 148.32630),
  new google.maps.LatLng(-36.44388, 148.32631),
  new google.maps.LatLng(-36.44387, 148.32632),
  new google.maps.LatLng(-36.44400, 148.32631),
  new google.maps.LatLng(-36.44421, 148.32627),
  new google.maps.LatLng(-36.44425, 148.32620),
  new google.maps.LatLng(-36.44433, 148.32614),
  new google.maps.LatLng(-36.44446, 148.32610),
  new google.maps.LatLng(-36.44459, 148.32606)
];

To save bandwidth the API also supports a compact format for a sequence of coordinates that form a series of connected lines (a polyline). The encoding algorithm is described in the API documentation thus:

Encoding Latitudes and Longitudes

The encoding process converts a binary value into a series of character codes for ASCII characters using the familiar base64 encoding scheme: to ensure proper display of these characters, encoded values are summed with 63 (the ASCII character '?') before converting them into ASCII. The algorithm also checks for additional character codes for a given point by checking the least significant bit of each byte group; if this bit is set to 1, the point is not yet fully formed and additional data must follow.

Additionally, to conserve space, points only include the offset from the previous point (except of course for the first point). All points are encoded in Base64 as signed integers, as latitudes and longitudes are signed values. The encoding format within a polyline needs to represent two coordinates representing latitude and longitude to a reasonable precision. Given a maximum longitude of +/- 180 degrees to a precision of 5 decimal places (180.00000 to -180.00000), this results in the need for a 32 bit signed binary integer value.

Note that the backslash is interpreted as an escape character within string literals. Any output of this utility should convert backslash characters to double-backslashes within string literals.

The steps for encoding such a signed value are specified below.

1. Take the initial signed value:
   -179.9832104
2. Take the decimal value and multiply it by 1e5, rounding the result:
   -17998321
3. Convert the decimal value to binary. Note that a negative value must be calculated using its two's complement by inverting the binary value and adding one to the result:
   00000001 00010010 10100001 11110001
   11111110 11101101 01011110 00001110
   11111110 11101101 01011110 00001111
4. Left-shift the binary value one bit:
   11111101 11011010 10111100 00011110
5. If the original decimal value is negative, invert this encoding:
   00000010 00100101 01000011 11100001
6. Break the binary value out into 5-bit chunks (starting from the right hand side):
   00001 00010 01010 10000 11111 00001
7. Place the 5-bit chunks into reverse order:
   00001 11111 10000 01010 00010 00001
8. OR each value with 0x20 if another bit chunk follows:
   100001 111111 110000 101010 100010 000001
9. Convert each value to decimal:
   33 63 48 42 34 1
10. Add 63 to each value:
    96 126 111 105 97 64
11. Convert each value to its ASCII equivalent:
    `~oia@

The table below shows some examples of encoded points, showing the encodings as a series of offsets from previous points.