UNSW Compucon Programming Competition 1998
Preliminary Round, Open Section

Advice to Competitors

We have provided a range of problems of varying difficulty: we expect that very few teams will be able to complete all, or even most of the tasks. Do not be discouraged if you don't get many of them done. There is no pass mark, and points are given to indicate our estimates of their relative difficulty. Even solving one problem is an achievement.

The computer you will use should by now contain a directory UNSWPC98 in which you will find separate directories OpenA, OpenB, and so on to OpenF, and JnrA to JnrD. (If they haven't been installed, copy and unzip the file UNSWPC98.ZIP found on your supervisor's competition disk). These directories contain test files with which to exercise your programs. In particular, files of the form Test1.dat, Test2.dat store input data for the program you will write. To establish how well your program works you need to print a copy of the program output for each of these files. Your supervisor will also ask you at the end of the time period to print program listings for each task at least partially completed.

Because you have to share a single computer you may that find the best strategy is to work on two or three tasks simultaneously (one or two people on each task). The programs should be clearly written and neatly formatted. Do not worry about fancy user interaction: all input will come from a test file. The printed copy of each test run can either be a printed text file or a screen dump.

Good luck. No doubt you will find the competition challenging, but hopefully also rewarding.

Summary of Tasks

There are no points score or extensions for tasks in the Junior Section. Certificates will be issued based on the number of tasks successfully completed. Some of the tasks in the Open Section have extensions, so a range of points is possible.

Task A: Barcode Validation

Description

The number consists of four parts:

• The first two digits represents a type code (93 is for Australian goods, 97 for books)

• The next five digits is a manufacturer's identifying number (for example, 00652)

• The next five digits is the product number assigned by the manufacturer (01091)

• The last (thirteenth) digit is what is called a check digit.

Example

9300652010916
^ ^ ^ ^ ^ ^ ^  odd sum is 9+0+6+2+1+9+6 = 33
 ^ ^ ^ ^ ^ ^   even sum is 3+0+5+0+0+1 = 9
33 + 3*9 = 60

Write a program that reads in any number of bar codes and determines whether or not each is valid. The input consists of a sequence of lines, each containing a 13-digit number. The last line contains 13 zeroes to signal the end of input.

For each code, print the code and either the string "OK" or the string "INVALID".

Sample Input/output

9300652010916
9300652040916
9315626000480
9780805300604
9780803500604
9781875932548
0000000000000

9300652010916 OK
9300652040916 INVALID
9315626000480 OK
9780805300604 OK
9780803500604 INVALID
9781875932548 INVALID
   

Extensions

1. For an additional 2 points, If an input consists of exactly 12 digits, calculate the correct check digit and print the entire 13-digit code followed by "FIXED"

   Input	Output
   9311505275888 931150527588 9311505275883 978187593254 0000000000000	9311505275888 OK 9311505275888 FIXED 9311505275883 INVALID 9781875932542 FIXED

2. For a further 1 point, solve this problem and write or type your answer on the program listing:

   Since adjacent digits are weighted differently (1 or 3 times) in the sum, it may be possible to detect when adjacent digits are accidentally swapped (a common typing mistake). Under what circumstances will this error not be detected?

Constraints

Task B: Matching Suffixes

Description

Say the suffix read on the first line is n characters in length. The program must display each word that matches the suffix, that is, whose last n characters are exactly the same as the suffix. Upper and lower case can be considered either the same or different characters, whichever is more convenient in the language used.

Food for thought: under this definition, can a word be its own suffix?

Display the words on separate lines.

Sample Input/output

ing
Bring on the minstrels, singing and dancing;
keywords: ping telnet TCP/IP finger
ning-nong
Titanic sinking

Bring
singing
ping
sinking
   

Extensions

1. For an additional 2 points, ignore all punctuation (defined as anything other than letters and digits). For example,

   Input	Output
   ing Bring on the clowns, singing and dancing; keywords: ping telnet TCP/IP finger ning-nong Titanic sinking	Bring singing dancing ping ning sinking

2. For a further 2 points, accept between one and ten suffixes on the first line, and display words that match any of them. Suffixes are separated by one or more spaces.

Constraints

• Suffix length: up to 10 characters

• Word length: up to 40 characters

• Number of suffixes: 1, or up to 10 with second extension

• Number of input lines: unlimited.

Task C: Pascal's Triangle

Description

                 1
               1   1
             1   2   1
           1   3   3   1
         1   4   6   4   1
       1   5  10  10   5   1
     1   6  15  20  15   6   1
   1   7  21  35  35  21   7   1    
              . . .

Each value apart from the outside 1s is the sum of the two values diagonally above it. For example, on the third row 2 = 1 + 1; on the fourth 3 = 1 + 2 and on the seventh 6 = 1 + 5, 15 = 5 + 10 and 20 = 10 + 10. (The values may be familiar to you: they are the binomial co-efficients.)

Write a program that generates the first 13 rows of Pascal's triangle. All entries for the triangle of this size are 1, 2 or 3 digit numbers only. Format the output so that each number uses four characters including leading spaces. This way the numbers will align so that the derivation is apparent.

Constraints

Scoring

Task D: Integer Substrings

Description

Your program will be given an integer n as input. It must display all integer substrings of n in any order.

Sample Input/output

6158

6
1
5
8
61
15
58
615
158
6158

Extensions

1. For an additional 2 points, Sort the list in decreasing numeric order (so the original number comes first). For example,

   Input	Output
   6158	6158 615 158 61 58 15 8 6 5 1

2. For a further 5 points, determine which of the substrings are prime numbers. After printing all substrings of original number n in order (first extension) display n followed by either

   • the largest prime integer substring of n, if any of the integer substrings are prime numbers, or

   • the message "has no prime substrings" otherwise. For example, The largest prime substring of 2795975 is 97, while 46864 has no prime substrings.
   Remember that the smallest prime number is 2.

Constraints

Task E: Square Root Calculator

Description

We want to find out the square root of n, where n is some positive real number. If we guess a value x, then a better estimate of sqrt(n) is given by

(x + n / x) / 2

where / is the real division operator.

If we use the new estimate in the same formula, we will get a value even closer to sqrt(n), until, after a sufficient number of iterations, the successive x values converge to the required result.

Write a program that calculates square roots using the Newton-Raphson method. Input consists of a real number on each line. For each input number n, the output should consist of

• The number read in,

• optionally followed by the exact square root as produced by a built-in sqrt function (if available), then

• the sequence of x values that are produced by the algorithm until it converges.

Sample Input/output

2

-2

10000

0.0457

sqrt(2):   1.414214 (built-in)
    2.000000
    1.500000
    1.416667
    1.414216
    1.414214
sqrt(-2): undefined
sqrt(10000): 100.000000 (built-in)
  10000.000000
  5000.500000
  2501.250000
  1252.624023
  630.303650
  323.084503
  177.018082
  116.754745
  101.202187
  100.007141
  100.000000
  100.000000
sqrt(0.0457):   0.213776 (built-in)
    0.045700
    0.522850
    0.305128
    0.227451
    0.214187
    0.213776
    0.213776

Scoring

Constraints

Task F: Rotation Cipher

Description

Given a fairly long file encoded this way, the aim of the program is to determine what the original message was. It could try all 26 possible values for k, but that would be tedious. Fortunately, we can use the fact that certain letters occur frequently in English to identify one probable substitution, and work out k from that. This will only work for a relatively long piece of text.

Use the following heuristic (an approximate rule that produces good results most of the time):

• Determine the letter that occurs most frequently.

• If that letter occurs at least one third of the time as the first letter of a word, assume the letter represents "t"

• If the letter occurs at least one half the time as the last letter of a word, assume the letter represents "n"

• Otherwise, assume the letter represents "e"

Note that your program has to read the input file twice, once to tally letter frequencies and once to decode the message. Make sure you write and test it in such a way that you can re-read the input. Saving the entire file in an array is possible, though not desirable (it incurs a 3-point penalty).

The output of the program is just the deciphered text: if the program is incorrect the result will be meaningless.

Scoring

Constraints