# Sample Questions from the 2017 Contest

### Hailstone Sequence

A hailstone sequence is a calculation of numbers that increase and decrease but eventually settles into a repeating pattern of the numbers 4, 2, 1. The sequence is generated by starting with any positive whole number greater than zero and completing the following steps:

• If the number is even, divide it by 2 to calculate a new number
• If the number is odd, multiple it by 3 and add 1 to calculate a new number
• Repeat the above process for calculated numbers until the sequence 4, 2, 1 is generated.

For example, the hailstone sequence for the number 3 is:
10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, . . .

Since the pattern 4, 2, 1 repeats endlessly, the hailstone sequence in our problem will be considered complete when the formula calculates the number 1 the first time. The sequence is called a hailstone sequence because the numbers generated rise and fall like a hailstone in a cloud until “crashing to the ground”.

• A whole number (integer) value greater than zero and
• display the number of iterations required to achieve the ending point (i.e. the first number 1) using a hailstone sequence and the largest number in the hailstone sequence.
• Input will be supplied via a text file (hailstone.txt).
• This file will contain multiple lines (test cases) with each line containing a single starting value.

Although the sample test file (below) has 5 test cases, you cannot assume all test files will have exactly 5 test cases. The test file the judges use may have more or fewer test cases.

### Test Data

Input
(hailstone.txt)
Output
3Starting number: 3; iterations: 7; largest value: 16
12Starting number: 12; iterations: 9; largest value: 16
75128138247Starting number: 75128138247; iterations: 1228; largest value: 319497287463520
132Starting number: 132; iterations: 28; largest value: 132
1599Starting number: 1599; iterations: 73; largest value: 36448

1. You do not need to edit the input data.
2. You do not need to handle exceptions.
4. The judges will test your application with a different set of data that will have a different number of test cases.

### Largest Number

Determine the largest number that can be formed from a group of individual numbers. For example, given the numbers 50, 2, 1, 9 the largest number that can be formed is 95021.

Input will be via a text file with a variable number of positive integers and 0 on the same line separated by a single space. Your output must be the largest number that can be formed. You will be given multiple files to test with. Each file will contain one test case.

Write your solution code to use only the largestnumber.txt file.You can use a text editor to copy and paste data from the other test files (largestnumber2.txt and largestnumber3.txt) into largestnumber.txt.

### Test Data:

Input FileInput DataOutput
largestnumber.txt5 2 1 9 50 5695650521
largestnumber2.txt201 3 77 5632 41 1877563241320118
largestnumber3.txt3412 450 0 73 887345034120

1. You do not need to edit the input data.
2. You do not need to handle exceptions.
4. The judges will test your application with a different set of test cases.

### Isogram

An isogram is a word or phrase without a repeating letter. In this problem you will read a list of words or phrases from a text file. Each word or phrase to be tested will be on its own line in the file. For each word or phrase, display the word or phrase and then display either “is an isogram” or “is not isogram”.

The text file to use for testing (isogram.txt) will contain an unknown number of phrases or words. In other words, the test file provided (isogram.txt) has 14 lines of data. The test used by the judges may have fewer or more lines.

• All letters are lowercase and you do not need to consider comparisons between upper and lower cases.
• There is no punctuation in the phrase or word.
• Phrases may have multiple occurrences of the space character but this is not considered a letter and therefore can never be the cause for a phrase to not be an isogram.

### Test Data:

Input (isogram.txt)Output
lawnmowerlawnmower is not an isogram
documentdocument is an isogram
flameflame is an isogram
pack my box with jugspack my box with jugs is an isogram
flowchartflowchart is an isogram
magneticmagnetic is an isogram
workingworking is an isogram
predictpredict is an isogram
subordinatesubordinate is an isogram
eddyeddy is not an isogram
proposepropose is not an isogram
pack my box with five dozen liquor jugspack my box with five dozen liquor jugs is not an isogram
metalworkingsmetalworkings is an isogram
troublemakingstroublemakings is an isogram

1. You do not need to edit the input data.
2. You do not need to handle exceptions.
4. The judges will test your application with a different set of test cases.

### Sequence of Differences

Given a set of four numbers representing a “circular array” we can test to see if the absolute values of the differences between each adjoining element will eventually coalesce into a single value.

• For example, consider the set of four numbers: {1, 10, 8, 3}.

We can repeatedly take the absolute values of the differences of the adjoining numbers. Since this is a circular array, calculate the value of the last element in the new array as the last number minus the first number.

• For example, starting with {1, 10, 8, 3}

The first iteration will produce {9, 2, 5, 2} calculated as |1 - 10|, |10 - 8|, |8 - 3|, |3 - 1| .
The second iteration will produce {7, 3, 3, 7} calculated as |9 - 2|, |2 - 5|, |5 - 2|, |2 - 9|.
The third iteration will produce {4, 0, 4, 0} calculated as |7 - 3|, |3 – 3|, |3 - 7|, |7 – 7|.
The fourth iteration will produce {4, 4, 4, 4} calculated as |4 - 0|, |0 - 4|, |4 - 0|, |0 - 4|.

We can say the original set {1, 10, 8, 3} required 4 iterations to reach a common number (all values are 4).

In this problem you must read multiple test cases from a text file named numbers.txt.

• Each line in this file will contain exactly 4 numbers separated by a single space.
• Each number will be >= 0 and <= 10000.
• For each set of 4 numbers, determine how many iterations are required before the sequence of the differences coalesces into a single value.

Although there are 7 lines in the test file below, do NOT assume all test files will have 7 lines of input. The files used by the judges may have more or fewer lines.

### Test Data:

Input (numbers.txt)Output
1 0 0 03 iterations were required for 1 0 0 0
0 1 4 115 iterations were required for 0 1 4 11
0 0 0 23 iterations were required for 0 0 0 2
34 12 19 284 iterations were required for 34 12 19 28
100 200 321 3454 iterations were required for 100 200 321 345
7 2 7 21 iterations were required for 7 2 7 2
9934 8543 812 10013 iterations were required for 9934 8543 812 1001

1. You do not need to edit the input data.
2. You do not need to handle exceptions.
4. The judges will test your application with a different set of test cases.

### Largest Substring

In this problem you need to identify the largest substring that occurs more than once within a larger string. You will be given a list of strings. Each string will consist of some random set of lowercase letters of at least one character and at most 100 characters. For example, given the string “abbbcdaabbbczaabbbc” we can identify several substrings that occur more than once:

• ab occurs 3 times
• bbb occurs 3 times
• aabbbc occurs 2 times

For this string (abbbcdaabbbczaabbbc) the largest substring that occurs more than once is “aabbbc”. It is the largest substring because it has 6 characters and the other substrings have fewer characters. In this case, display the following: “abbbcdaabbbczaabbbc has substring aabbbc that occurs 2 times”.

Some strings may have no substring that occurs more than once.

• For example, the string “abcdefg” doesn’t have any substrings that occur more than once. That is, each character appears once and only once.
• For a string like this display the text: “abcdefg has no substring that occurs more than once”.

Some strings may have more than one substring that meets the requirements.

• For example, the string “zyxkkzyklrotilkrotzyx” has two substrings (“zyk” and “rot”) that are both 3 characters long and occur 3 times.
• In a case like this display the first substring.

The test data will be contained in a file named largestsubstring.txt. Each line will contain a single string of characters as shown below.

Although this sample file has 11 strings do NOT assume all test files will have 11 strings (lines) of input. The files used by the judges may have more or fewer lines.

Input (largestsubstring.txt)Output
abcdefabczabcabcdefabczabc has substring abc that occurs 3 times
klghnabcdefabczabcklghnabcdefabczabc has substring abc that occurs 3 times
abcdaabczaabcabcdaabczaabc has substring aabc that occurs 2 times
abbbcdaabbbczaabbbcabbbcdaabbbczaabbbc has substring aabbbc that occurs 2 times
bdfjjklmjjbdfjjklmjj has substring jj that occurs 2 times
bdfjlklmjjbdfjlklmjj has substring j that occurs 3 times
abcdefgabcdefg has no substring that occurs more than once
zyxkkzyklrotilkrotzyxzyxkkzyklrotilkrotzyx has substring zyx that occurs 2 times
abcdeffgabcdeffg has substring f that occurs 2 times
ytrrothhasrotqwhhllhhytrrothhasrotqwhhllhh has substring rot that occurs 2 times
kkkkkkkkkkkk has substring kkk that occurs 2 times

1. You do not need to edit the input data.
2. You do not need to handle exceptions.
4. The judges will test your application with a different set of test cases.

### Number Chain

Given a number, we can form a number chain by

1. Arranging its digits in descending order.
2. Arranging its digits in ascending order.
3. Subtracting the number obtained in (2) from the number obtained (1) to form a new number.
4. Repeating these steps until the new number matches the result from the previous calculation.

For example given an original number of 1234, the process would be:
4321 - 1234 = 3087
8730 - 378 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
Chain length = 4

The number of distinct numbers in the chain is the length of the chain. You are to write a program that reads numbers and displays the length of the chain for each number read. Some numbers may not result in a new number that matches the result from the previous calculation.

• For example, the number 84723 can go through more than 1000 iterations and still not reach the ending point.
• In cases like this, stop after 1000 iterations and indicate the chain length is greater than 1000 as shown in the sample output below.

The input will consist of a text file named numberchain.txt. This file will contain a sequence of positive integer numbers each on its own line.

Although the sample file below has 5 numbers (lines) do NOT assume all test files will have 5 numbers (lines) of input. The files used by the judges may have more or fewer numbers.

Input (numberchain.txt)Output
1234original number was 1234 and chain length = 4
123456789original number was 123456789 and chain length = 2
84723original number was 84723 and chain length > 1000
8080original number was 8080 and chain length = 7
9235original number was 9235 and chain length = 6

1. You do not need to edit the input data.
2. You do not need to handle exceptions.
4. The judges will test your application with a different set of test cases.

### Word Search

Professor Plum enjoys playing word search puzzles when on airplanes. The objective is to locate words hidden in a table of letters. The word might be written in a horizontal or vertical orientation. It might be written from bottom to top (upside down) or left to right (backwards). A particularly fun version of a word search puzzle is one where the words can be written with changes in direction. A word that starts out being written from top to bottom might take a turn in the middle and continue left to right.

For example, if you are searching for the word “halifax”, it might be written like this:

h
a
l
i f a x

If you are looking for “yellow“, it might appear like this:

w
o l
l
e y

In this problem you will write a program to read a word search grid from a file and then ask the user what word they would like to search for.

• The user will enter the word from the keyboard.
• When you locate the word in the grid, display the location of each letter in the word by displaying its cell location in the table.

Here is an example of a word search grid.

 s o f t s w e s k a o l z i l k l q m t r e y o y

Suppose you want to find the word "eskimo".

• It can be found beginning at location Row 2, Column 2 and the path is expressed like this:
e:2,2 s:2,3 k:2,4 i:3,4 m:4,4 o:5,4
• Words will always be contiguous in the grid, and the turns must be 90 degrees. Using the sample grid above, the word “salty” is:
s:1,5 a:2,5 l:3,5 t:4,5 y:5,5

You must also handle the case where a word the user enters doesn’t exist in the gird.

• Using the sample grid above, the word "pizza" could not be found. In that case, display the word (pizza) and “cannot be found” as shown in the sample output below.
• All letters will be lower case as will the words to be searched for. The same letter may appear more than once but correct combinations of letters will only appear once. For example, if the hidden word is “eskimo” the letters e and s may appear many times individually but will only appear “together” once.

The input will consist of a text file named wordsearch.txt. The first two pieces of data on the file will be the number of rows and the number of columns in the word search puzzle. This will be followed by the correct number of letters to fill up the word search puzzle. All the data will be on a single line in the file. Each piece of data will be separated by a single space.

Input (wordsearch.txt)
5 5 s o f t s w e s k a n m z i l k c q m t r u f o y

Prompt the user to enter the word to search for as shown in the table below. You can execute (run) your application multiple times testing one word with each execution.

KeyboardOutput
Enter the word: softs:1,1 o:1,2 f:1,3 t:1,4
Enter the word: eskimoe:2,2 s:2,3 k:2,4 i:3,4 m:4,4 o:5,4
Enter the word: saltys:1,5 a:2,5 l:3,5 t:4,5 y:5,5
Enter the word: yellowy:5,3 e:5,2 l:4,2 l:3,2 o:3,1 w:2,1

Write your solution code to use only the wordsearch.txt file. You can use a text editor to copy and paste data from the other test file (wordsearch1.txt) into wordsearch.txt.

Input (wordsearch1.txt)
7 6 s o f t w a e s k q e r m i l k c q p u t e r o m o c e r t p u i o p p r o g r a m
KeyboardOutput
Enter the word: milkm:3,1 i:3,2 l:3,3 k:3,4
Enter the word: softwares:1,1 o:1,2 f:1,3 t:1,4 w:1,5 a:1,6 r:2,6 e:2,5
Enter the word: programp:6,1 r:7,1 o:7,2 g:7,3 r:7,4 a:7,5 m:7,6
Enter the word: computerc:5,3 o:5,2 m:5,1 p:4,1 u:4,2 t:4,3 e:4,4 r:4,5
Enter the word: milkeecomm:3,1 i:3,2 l:3,3 k:3,4 e:4,4 e:5,4 c:5,3 o:5,2 m:5,1

1. You do not need to edit the input data.
2. You do not need to handle exceptions.
4. The judges will test your application with a different set of test cases.

### Maximal Layers

Consider a group of points. Each point is made of an x and y coordinate. A point from that group is considered maximal if there is no other point in the group that is “north” and “east” of it. Given the points:

5,5  4,9  10,2  2,3  15,7

We can identify the points 4,9 and 15,7 as maximal. Mathematically this is true because there are no other points that have a larger x coordinate AND a larger y coordinate.

• For example, point 4, 9 is maximal because there is no other point “north” of it (i.e there is no other point with a larger y value).
• Point 15, 7 is maximal because there is no other point “east” of it (i.e. there is no other point with a larger x value).

These maximal points can be joined to form maximal layer (Layer 1) as shown below.

Additional maximal layers can be created in the same manner by using the rule:

• Each layer consists of the points that are maximal excluding the points in the previous layer.

This results in 3 layers for this group of points as shown below.

In this problem you will be given a group of points. You must identify the points in each layer as shown in the sample output below. The input will consist of a text file with the x and y coordinates for at least 1 and up to 15 points. Each x and y value for a point will be on its own line. The x and y values for a point will be separated by a single space. The coordinates will be integer values between 1 and 20. Some points will have the same x coordinate and some points will have the same y coordinate but there will be no duplicate points. That is, no points will have the same x AND y coordinates.

You will have 3 test files to use as shown below. Each will have a slightly different name.

Write your solution code to use only the maximal.txt file. You can use a text editor to copy and paste data from the other test files (maximal2.txt and maximal3.txt) into maximal.txt. The points listed in each layer do not need to be in the same order as you see in the sample output.

• For example, Layer 2 in the sample below could be 10,2 and then 5,5 instead of 5,5 and then 10,2.
Input (maximal.txt)Output
5 5Layer 1: 4,9 15,7
4 9Layer 2: 5,5 10,2
10 2Layer 3: 2,3
2 3
15 7
Input (maximal2.txt)Output
5 5Layer 1: 15,15 15,7 15,2
10 2Layer 2: 2,14 12,10
2 3Layer 3: 1,7 7,7 10,2
15 7Layer 4: 5,5
2 14Layer 5: 1,4 2,3
1 1Layer 6: 1,1
15 2
1 7
7 7
1 4
12 10
15 15
Input (maximal3.txt)Output
6 2Layer 1: 1,20 19,19 20,10
13 18Layer 2: 13,18 13,13
9 9Layer 3: 2,15 2,14 12,12 5,12
20 10Layer 4: 9,9
19 19Layer 5: 3,3 6,2
12 12
3 3
2 15
13 13
5 12
2 14
1 20