Programming Practice Problems

Easy Problems

                  +-------------------------+
                  ¦ 34 ¦ 21 ¦ 32 ¦ 41 ¦ 25  ¦
                  +----+----+----+----+-----¦
                  ¦ 14 ¦ 42 ¦ 43 ¦ 14 ¦ 31  ¦
                  +----+----+----+----+-----¦
                  ¦ 54 ¦ 45 ¦ 52 ¦ 42 ¦ 23  ¦
                  +----+----+----+----+-----¦
                  ¦ 33 ¦ 15 ¦ 51 ¦ 31 ¦ 35  ¦
                  +----+----+----+----+-----¦
                  ¦ 21 ¦ 52 ¦ 33 ¦ 13 ¦ 23  ¦
                  +-------------------------+

1. Do you like treasure hunts? In this problem you are to write a program to explore the above array for a treasure. The values in the array are clues. Each cell contains an integer between 11 and 55; for each value the ten's digit represents the row number and the unit's digit represents the column number of the cell containing the next clue. Starting in the upper left corner (at 1,1), use the clues to guide your search of the array. (The first three clues are 11, 34, 42). The treasure is a cell whose value is the same as its coordinates. Your program must first read in the treasure map data into a 5 by 5 array. Your program should output the cells it visits during its search, and a message indicating where you found the treasure.

2. Write a program to search for the "saddle points" in a 5 by 5 array of integers. A saddle point is a cell whose value is greater than or equal to any in its row, and less than or equal to any in its column. There may be more than one saddle point in the array. Print out the coordinates of any saddle points your program finds. Print out "No saddle points" if there are none.

3. In the game of chess, a queen can attack pieces which are on the same row, column, or diagonal. A chessboard can be represented by an 8 by 8 array. A 1 in the array represents a queen on the corresponding square, and a O in the array represents an unoccupied square. Your program is to read the location of two queens and then update the array appropriately. Then process the board and indicate whether or not the two queens are positioned so that they attack each other.

4. One classic method for composing secret messages is called a square code. The spaces are removed from the english text
and the characters are written into a square (or rectangle). For example, the sentence "If man was meant to stay on the
ground god would have given us roots" is 54 characters long, so it is written into a rectangle with 7 rows and 8 columns.

                ifmanwas
                meanttos        
                tayonthe
                groundgo
                dwouldha
                vegivenu
                sroots

The coded message is obtained by reading down the columns going left to right. For example, the message above is coded as:

imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau

In your program, have the user enter a message in english with no spaces between the words. Have the maximum message length be 81
characters. Display the encoded message. (Watch out that no "garbage" characters are printed.) Here are some more examples:

 Input                                           Output
haveaniceday                                    hae and via ecy
feedthedog                                      fto ehg ee  dd
chillout                                        clu hlt io

5.   The results from the mayor's race have been reported by each precinct as follows:

          Candidate Candidate Candidate Candidate Precinct      A          B          C          D    1         192        48         206        37    2         147        90         312        21    3         186        12         121        38    4         114        21         408        39    5         267        13         382        29
Write a program to do the following:

a. Read the raw vote totals from a data file that contains one row for each precinct.

b. Display the table with appropriate headings for the rows and columns.

c. Compute and display the total number of votes received by each candidate and
the percent of the total votes cast.

d. If any one candidate received over 50% of the votes, the program should print
a message declaring that candidate the winner.

e. If no candidate received 50% of the votes, the program should print a message
declaring a run-off between the two candidates receiving the highest number of
votes; the two candidates should be identified by their letter names.

f. For testing, run the program with the above data, and also with another
   data file where Candidate C receives only 108 votes in precinct 4.

Moderate Problems

Write a program to find all the sentences, or consecutive sequence of sentences, in a text file where: min <= length <= max.
Assume that a sentence ends in a period, question mark, or exclamation point.
In the special case of quoted sentences (that begin with quotes or an apostrophe), include the terminating quote mark or apostrophe.
Count all blanks and punctuation, but assume only one blank between sentences.
(All EOL characters should be converted to blanks).
Precondition: Min and Max will be positive integers less than 1000, and Min <= Max.
The name of the text file is to be provided as a command line argument (not read from Standard Input).

For example, given this text:
Black is white. Day is night. Understanding is ignorance. Truth is fiction. Safety is danger.
If min = max = 16 then the output is
    "Black is white."
If min = max = 18 then the output is
    "Truth is fiction."
"Safety is danger."
If min = 30 and max = 37 then the output is
    "Truth is fiction. Safety is danger."
because the two sentences are consecutive sentences with the desired length.

Here is a sample text file for Alice in Wonderland.

1. Write a program to convert roman numerals into their arabic equivalent.

INPUT REQUIREMENTS

Read one or more roman numerals from standard input. Process one line at a time. Each input line contains only one roman numeral, starting in column one. Assume the characters are all upper case with no embedded blanks.

OUTPUT REQUIREMENTS

The arabic equivalent of each input roman numeral is displayed on standard output, starting in column one.

FUNCTIONAL REQUIREMENTS

Here are the arabic equivalents for roman symbols:

The "basic" roman symbols The "auxiliary" roman symbols

I X C M V L D
1 10 100 1000 5 50 500

Convert the roman numeral to arabic processing the symbols from left to right according to the following rules:

1. A symbol following one of greater or equal value adds to its value. (E.g., XII = 12)
2. A symbol preceding one of greater value subtracts its value.(E.g., IV = 4; XL = 40)

ERROR HANDLING REQUIREMENTS

In each of the error conditions below, display the given message and skip the numeral and continue processing the next line.

"Invalid character in input. Valid characters are I,V,X,L,C,D,M."

Only the listed characters are valid. "Invalid numeral: can't subtract auxiliary symbol." It is not permitted to subtract an "auxiliary" symbol. (CML, not LM = 950; XLV not VL, = 45). "Invalid numeral: two consecutive subtractions." Can't do two subtractions in a row, thus LIVX is illegal. "Invalid numeral: additions don't decrease." Additions must decrease, as you go from left to right. Thus, each symbol added must have a value equal or less than the last symbol which was added. Thus, LIIX is wrong, cause we added L, added I, subtracted I, then try to add X.

Phone "words"

Each number on the telephone dial (except 0 and 1) corresponds to three alphabetic characters. Those correspondences are:

 2 ABC  
 3 DEF  
 4 GHI  
 5 JKL 
 6 MNO 
 7 PRS 
 8 TUV 
 9 WXY

Given a seven digit telephone number, print all 2187 possible "words" that number spells. (They may not be real english words, but just some sequence of characters). Since the digits 0 and 1 have no alphabetic equivalent, an input number which contains those digits should be rejected. The input will be one or more seven digit integers from standard input.

The problem can be made a bit more challenging by outputting more than one word per line. Usually about seven words will fit on a line.

Frequency of letter pairs

Write a program to count the occurrences of all letter pairs in a sample of text (like the first paragraph of the Constitution). Disregard differences between lower and upper case letters. (Blanks are not considered as letters). Output the 100 most frequent letter pairs, in order by percent of total. Also show which percent of total pairs is accounted for by this list of 100. Your program should correctly process situations where the input file is empty or where less than 100 pairs occur.

Sample output

th 2.37%     in 2.20%     fj 2.00%  ...  (6 per line)
      ...
      (100 letter pairs)

Output represents 73.44% of 23641 letter pairs.

Computing "subword" combinations.

Accept any number of lines of input entered from standard input. A valid line contains a word and a number. The word comes first, and is up to twenty alphabetic characters (A-Z) in upper or lower case. The word may be preceeded and followed by any number of blanks. The number is a decimal integer greater than zero, and may be followed by any number of blanks or a return. Input is terminated by EOF character. For each input word, print all possible "subwords" that have as many characters as specified by the number. A "subword" is a n-letter word comprised of only characters that are found in the given word. If you are familiar with the game Scrabble, it's as though the input word is your pool of letters, and you want to find all possible arrangements of n letters from your pool. .nf For example, CAT 2 would produce CA CT AC AT TA TC and DOG 1 would produce D O G and BIRD 3 would produce BIR BID IRD RID DIR RIB ... Note, that we are producing combinations WITHOUT replacement, so in the BIRD 3 example, BBB and RRR are NOT possible subwords. The output should echo the input line to standard output, followed by the list of subwords, one word per line, left justified. Each set of output words should be followed by one blank line. The program should respond to invalid input by echoing the input line to the output, and then issuing a one line message indicating the nature of the error:

"Illegal character in word"

"Illegal character in number"

"Number greater than length of word"

"Word longer than 20 characters"

After issuing the message, processing should resume with the next input line. When all input has been processed, issue a message indicating the number of input words that were processed (including word with errors) e.g., "End of input encountered, 4 words processed."

Calculating bowling match scores

A bowling match consists of ten frames. Each frame except for the tenth consists of one or two balls, or attempts to knock down the ten pins at the end of the alley. Doing so on the first ball of the frame is called a strike, and the second ball of the frame is not rolled. Knocking down all ten pins with both balls (having left some up with the first ball) is called a spare. If both attempts to knock down the pins leave some standing, the frame is called an open frame. A spare in the tenth frame gives the bowler one extra ball; a strike in the tenth gives him or her two extra balls. A bowling score is computed as follows. A strike counts as 10 points plus the sum of the next two balls. A spare counts as 10 points plus the next ball. Any other balls merely count as themselves, as do any bonus balls rolled as a result of a strike or a spare in the tenth frame. Suppose for example that the sequence of balls was

9 1   0 10   10   10   6 2   7 3   8 2   10   9 0   9 1   10

The score for the ten frames would be

Frame   score
-----   ----- 
 1       10 
 2       30 
 3       56 
 4       74 
 5       82 
 6      100 
 7      120 
 8      139 
 9      148 
 10     168

Write a program to accept from standard input the scores for a sequence of balls and output the scores for the ten frames. There may be multiple lines of input, where each input line will be the scores for one player. The scores will be separated by one or more blanks. You may assume that the number of scores on the line is valid.

Lotto Guesser

Cobbletown has a lottery (a small version of California's Lotto) in which players guess four number between 1 and 9. Larry likes to play and thinks he has a scheme to pick winning numbers. He keeps a history of past winning numbers in a text data file. Larry thinks that if a number hasn't occurred recently then it is more likely to show up as a winner. (Obviously Larry isn't familiar with the statistical fact that each number has an equal likelihood of being picked, since each week's drawing is an independent event). Larry wants us to write a program to assist him in his wacky scheme.

INPUT REQUIREMENTS

The lotto history data: a file of unknown length, with four integers per line. Each integer is in the range 1 to 9.

OUTPUT REQUIREMENTS

1. The four least frequently occurring integers in the history data. (That is, counting all the weeks, the four numbers that appeared fewer times than any others).

2. The one integer with longest time since last occurrence. (That is, if you count backward from now, the number for which you count the most weeks since it occurred).

FUNCTIONAL REQUIREMENTS

(You may assume that no data validity checking is required).

1. Determine and display the four integers which occur least often in the history data.

Note: To make the problem easier, if there is a tie between two or more numbers for fourth place, it doesn't matter which one is printed.

2. Determine and display the integer which has gone the longest without appearing in a winning sequence.

At a minimum your program must work correctly for the following sample data.

Test Data

1 2 3 4

5 6 7 8

8 7 6 5

1 5 6 7

4 3 2 1

Castles and Creatures

Write a program to play a simple "adventure"-style interactive game. The adventure world consists of up to five castles each of which has up to seven rooms (35 total). Each room has a treasure, worth a certain number of points, and a creature guarding the treasure. The treasure can be captured by bluffing or fighting the creature. Bluffing always has a 30% chance of succeeding. The odds for winning a fight vary from creature to creature. The object of the game is to visit different rooms and gain as many treasure points as possible. The player begins with 9 lives and each fight lost costs a life. (There's no penalty for losing a bluff.) When all the lives (or all treasures) are gone the game ends. The adventure world information (like castle and room names) is stored in a text file. The program must read the text file and create a data structure to represent the world. (HINT: Use a record structure for each room.) The program must handle interaction with the player, including display of menus for castle and room choices, display of current lives and treasure points accumulated, and responding to one-character commands to fight, bluff, or move around the world.

Sudoku Solver

Sudoku Solver assignment

Last modified on 05/13/2001 12:36:16