CSE / UNSW / CISRA High Schools Programming Competition 2003

Preliminary Round, Open Competition

Task 1 - Wordsworth

Description

You are to write a program which will work out the value of a piece of text. It is to do this by counting the number of letters in each word in the text.

The text is a list of words, separated by at least one spaces, possibly together with some punctuation and/or line breaks. The length of each word corresponds to a digit in the "value", with a word of length 10 corresponding to the digit 0. There is to be a decimal point after the first digit.

For example the phrase "How I need a monkey" has words of length 3, 1, 4, 1 and 6 respectively. This is worth 3.1416 (coincidentally this is pi to 4 decimal places).

You are to write a program which, given such a message, returns its value.

Examples

Marking Data

If you have electronic access to this document, you can go ahead and evaluate the first 50 decimal places of the following famous text:
(If you do not have cut and paste access, you need not do this.)

Further Input
Poe E Near a Raven Midnights so dreary tired and weary Silently pondering volumes extolling all by now obsolete lore During my rather long nap the weirdest tap An ominous vibrating sound disturbing my chambers antedoor This I whispered quietly I ignore Perfectly the intellect remembers the ghostly fires a glittering ...

Constraints

You may assume that there are between two and sixty words in the message, and that no word is longer than ten letters.

Task 2 - Jumble

We wish to write a program that encrypts a message by jumbling the order of the characters in the message. The precise way the characters are jumbled is determined by a password.

Suppose the password is 5 letter string HOMER. If we were to sort the letters in HOMER into alphabetic order the 4th letter (E) would move to the first place, the first letter (H) would move to the second place, and so on. This tells us to move the 4th letter in the message to the first place, the 1st letter in the message to the second place etc. Thus using the password HOMER to encrypt the 5 letter message "tower" we would get "etwor".

We can easily expand this technique to encrypt messages which are longer than the password, by breaking the message into chunks each the length of the password. If the last chunk is too short your program should add spaces at the end to make it the correct length.

For example if we encrypt "The expanding Potter books!" with the key BREVITY we get "Teehx padnngi Pteort boso!k ".

    Key: BREVITY  BREVITY  BREVITY BREVITY
Message: The exp  anding   Potter  books! "
   Code: Teehx p  adnngi   Pteort  boso!k "

You are to write a program which, given a password and a message, encrypts the message using this method.

Examples:

(we've placed quotes around the strings so you can see the spaces which have been added)

Sample Input		Sample Output
Password	Message
"BREVITY"	"The expanding Potter books!"	"Teehx padnngi Pteort boso!k "
"CHARM"	"Stop that rhyming now, I mean it!"	"oSt path tyrhim ngon w, Iame n!it "
"HUMPERDINK"	"Does anybody want a peanut?"	"n Dyoebsaotad awny?up a nte"
"SAME"	"SAME"	"AEMS"

Marking Data

Constraints

You may assume that the password is just one word and consists only of capital alphabetic letters with no duplicates.

Task 3 - Martian Arithmetic

Description

Martians have seven fingers and so do their arithmetric in base seven. This is why base seven numbers are often referred to as martian numbers. (In this question, to prevent confusion, base ten numbers are written in words and martian numbers are written in digits.)

You are to write a computer program to calculate the last ten digits of a martian number raised to the power of another martian number.

When a matrian writes the number 3542, the rightmost digit, 2, is worth one. The next digit, 4, is worth seven times one (ie seven). The next digit, 5, is worth fourty nine (seven times seven), and the fourth digit is worth three hundred and fourty three (fourty nine times seven). So the value of 3542 in base ten is

     two times one         PLUS
    four times seven       PLUS
    five times fourty nine PLUS
   three times three hundred and fourty three
   ------------------------------------------
   one thousand three hundred and four

For example what is one thousand in base seven?
Well, one thousand = (2 x three hundred and fourty three) + (6 x fourty nine) + (2 x seven) + (6 x one)
So a martian would write the human number one thousand as 2626.

The input to your program is a pair of martian numbers, m and n. Your program is to output the last ten martian digits of mn.

Note that these numbers will be big, so mn will not necessarily fit into data types such as int or long.

Examples

Sample Input		Sample Output
m	n	mn
2	2	4
2	3	11
2	6	121
2	10	242
12345	2	156502314
1000	2	1000000
11	20	4456346201
666666	666666	0001000001
654321	654321	0145350021

Marking Data

Input
m	n
3	3
123456	123
123	123456
123456123	21
654321321	654321
666123456	666666

Constraints

The numbers m and n will be positive martian integers. m will contain no more than nine digits, n will contain no more than six digits. Since they are martian integers, they will only contain the digits 0, 1, 2, 3, 4, 5, and/or 6.

If the answer has leading zeros you may show them or omit them as you chose.

Task 4 - Card Game Simulation

Description

Sometimes writing a computer program to simulate a problem can be much easier than solving it mathematically. In this question we wish to find the probability of winning a particular two player card game.

Working it out mathematically would be very tough, but instead one can use a computer simulation to estimate the probability by seeing how many times you win out of a large number of random runs.

The card game works as follows:
You split the deck so that you have all the red cards, and your friend has all the black cards. Each pile of cards is shuffled and placed face down in front of their owner. You go first, playing the topmost card of your pile. You keep putting down cards until you put down "two of the same" or "three in a row". When this happens, it becomes your opponent's turn, and they keep putting down cards until likewise they put down "two of the same" or "three in a row", when it becomes your turn to put down cards again, and so on. The winner is the first person to put down all their cards.

"Two of the same" means two successive cards which have the same value regardless of suit.

"Three in a row" means three successive cards in increasing or decreasing order regardless of suit, e.g. 4,5,6 or 3,2,Ace (Ace counts as 1).

Notice that the suit of a card (eg hearts etc) is completely irrelevant in this game.

In this game "in a row" does not wrap around. For example, Queen,King,Ace is NOT "three in a row". Also note that it only counts as "two of the same" or "three in a row" if all relevant cards have been played by the same person. For example, if the last card your opponent put down was a 2, and then you put down a 2 on top of it, this doesn't count as "two of the same".

For those unfamiliar with cards: there are 52 cards in a deck. In this game, each person gets 26 cards, two each of the 13 values: Ace (1), 2 through 10, Jack (11), Queen (12) and King (13).

You are to write a computer program which simulates this game, and estimates the probability of winning for the person who goes first. For each simulation, you will need to randomly generate the order of the cards in each player's pile. Then you will need to simulate the game and see who wins. You should run your simulation a large number of times and see how often the player who plays first wins.

There is no input. Your output should be a decimal between 0 and 1 (rounded to 4 decimal places) representing the probability that the person who plays first wins, e.g. 0.5000.

Note - even if you can solve this problem mathematically you are not to do so. You must solve the problem by repeated simulation as described above.

Task 5 - Pathfinder

Description

Two friends are lost in a maze. You are to write a program which, given several lines of text representing the maze, finds a path from one friend to the other.

Empty space will be indicated by - (hyphen) characters. Walls (which cannot be travelled through!) are indicated by * (asterisk) characters. The two friends are indicated by o (small O) characters.

Note that you may move horizontally or vertically in the maze, but not diagonally. (See the second example.)

If no path exists, you must return the message NO PATH. Otherwise, your program must return the image with a direct path drawn in connecting the two friends ("direct path" means no loops). The path should be indicated by o (small O) characters. (If there is more than one path, you may return any correct path).

Examples

Sample Input	Sample Output
----- --o-- -***- --o-- -----	----- --ooo -***o --ooo -----
*------- -*------ --*--o-- --o*---- ----*---	NO PATH
*************** *o*-----*-*---* *-*****-*-*-*-* *---------*-*-* *-****-**-*-*-* *-*--*-**-*-*-* *-*--*------*-* *-*-**-*-**-*-* *---*--*-**-*o* ***************	*************** *o*-----*-*ooo* *o*****-*-*o*o* *ooooooooo*o*o* *-****-**o*o*o* *-*--*-**o*o*o* *-*--*---ooo*o* *-*-**-*-**-*o* *---*--*-**-*o* ***************

Marking Data

----- --o-- -***- --o-- -----

*------- -*------ --*--o-- --o*---- ----*---

*************** *o*-----*-*---* *-*****-*-*-*-* *---------*-*-* *-****-**-*-*-* *-*--*-**-*-*-* *-*--*------*-* *-*-**-*-**-*-* *---*--*-**-*o* ***************

----*---- --*---*-- -*--*--*- --**-**-- ---o*o--- --**-**-- -*-----*- *-------*

---*-*-*-*- -*-*-*-*-*- -*-*-*-*-*- -*-*-*-*-*- -*-*-*-*--o -*---*-*-*- o*-*-*-*-*- -*-*-*-*-*- -*-*-*---*- -*-*-*-*-*-

------------- ------o------ ------------- ----*****---- ---*-----*--- --*--***--*-- --*-*---*-*-- --*-*-o-*-*-- --*-*---*-*-- --*-*-*---*-- --*-*---**--- -----***----- -------------

Constraints

You may assume the lines of text will be rectangular. The line-length will be no more than 80 characters, and there will be no more than 24 lines. The text will only contain relevant characters (-, * and o).

Task 6 - The CSE Problem

Description

The CSE problem is a problem where one must form the string CSE by applying a set of four rules to an initial starting word. Words consist only of the letters C, S, and E.

The four rules are:

1. If a word ends in an S, an E may be added to the end, e.g. CS > CSE
2. If the first letter of a word is a C, one may add to the end of the word all the letters after that first C, e.g. CEEES > CEEESEEES
3. Three successive S's may be replaced by an E, e.g. CSSSS > CES or CSSSS > CSE
4. Two successive E's may be removed, e.g. CEEE > CE

You are to write a program which, given a starting word, must find a way of obtaining the word CSE by repeatedly applying the four rules. Your output must be a list of words, each obtained by applying one of the rules to the previous word, starting with the initial word and ending with the desired goal: CSE. (If there are more than one correct sequences, any correct sequence will be accepted.)

Examples

Sample Input	Sample Output
CSEES	CSEES CSS CSSSS CSE
CSSSSSSS	CSSSSSSS CSSSSSSSE CSESSSE CSEEE CSE

Marking Data

CSEES

CSSSSSSS

CSSESS

CES

Constraints

You may assume that it is possible to get from the given inital word to CSE. We will not give you words from which CSE cannot be reached. Thus, for example, the input word will always start with C.

Summary of Tasks Attempted