Final Exam: due May 15

This is a take-home exam. It is open-book and open-note, but you may not work with anyone else (either in the class or not). If you have any questions, come ask me, call me (my office phone is 658-4120), or send me email.

Answer two of the following four questions by writing programs in C++ (or Haskell, although you will need to talk to me about how to do I/O). Save the program source files in a directory named Final in your folder on the I: drive, and send me an email telling me which problems you have solved. I will reply as soon as I can to let you know whether your program works correctly on my test data; if not, you may work on it more and resubmit. Please make sure that your program works on at least the sample input given with each question before you submit; I encourage you to create your own test data to help you understand the problems and debug your code. You may assume that all input will be well-formed; you do not need to do error-checking on the input (although you may find it helpful for debugging purposes).

Programs will be graded based on how they perform on my test data, as well as on program design and style (the issues we discussed in Chapter 1). In particular, your code should be well-documented and appropriately modular. If your program does not work on the test data, I will assign partial credit based on what you have written.

Solutions are due by 5 pm, Thursday, May 15.

Brian's Bowl-A-Rama

You have decided to take a study break at the local bowling alley, but the automatic scoring system is not working. Rather than resort to anything so primitive as paper and pencil, you pull out your laptop computer and quickly write your own scoring program. Since you've been dependent on the automatic system for so many years, here's a review of the scoring rules:

Each frame consists of one or two balls thrown. If you knock down all ten pins on the first ball, that's a strike and the frame is over. Otherwise, you try to knock over the remaining pins on the second ball; if you get all of them, that's a spare.
The score for one frame is the total number of pins knocked down in that frame, plus a bonus if you got a strike or a spare. The bonus for a spare is the number of pins knocked down on the next ball after that frame; the bonus for a strike is the number of pins knocked down on the next two balls after the frame.
One game consists of ten frames, plus up to two extra balls thrown after the tenth frame in case it was a strike or a spare. The extra balls thrown are only to decide the bonus for the tenth frame (and possibly the ninth frame, if both frames were strikes); they are not counted as another frame. If two extra balls are needed and all ten pins are knocked down on the first extra throw, then the pins are reset for the second ball; otherwise, the second extra throw is against the remaining pins from the first.

The input will consist of a sequence of integers giving the number of pins knocked down on each ball thrown. Each will be a number between 0 and 10, inclusive. As you can tell from the rules, a game will consist of between 12 and 21 throws; the input may contain several games, although they will not necessarily be on separate lines. The end of input will be marked by a -1 for the first throw of a game. The output should be the total score for each game read from the input, with each score on a line by itself.

Sample Input

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

Sample Output

300
0
164

Brackets and Braces

(This is loosely based on a true story.) A somewhat misguided committee of computer scientists decides to create a new computer language that requires lots of parentheses. However, they quickly realize that they are going to spend a lot of time counting how many parentheses are still open at the end of an expression and then typing enough closing parentheses to match them all. One of them hits upon the idea of using a closing bracket, ']', to mean ``close any remaining open parentheses all at once.'' Some members of the committee think that this is too drastic to be useful, but they like the idea of using a different kind of delimiter to close more than one open parenthesis at once, so one of them proposes that the closing brace, '}', be used to match two open parentheses at a time. The sane members of the committee protest that this is silly, but they are out-voted and both modifications are passed.

To restate, the rules for a well-formed expression are that each opening left parenthesis, '(', must be matched by a corresponding right parenthesis, ')', with the exceptions that a right brace, '}', will match exactly two opening parentheses, and a right bracket, ']', will match all of the remaining open parentheses.

Here are some examples of well-formed expressions using this rule, where all of the real content of the expression has been left out to just leave the skeleton of parentheses and brackets:

( )
( ) ( )
( ( ) )
( ( ) ( ]
( ( ( } )
( ( ) ( }
( ( ( } ( ( ]
( ( ( ( ( } } )

Your task is to write a program to check that a sequence of opening and closing parentheses plus closing brackets and braces is well-formed according to this rule. The input will be the sequence to be checked, followed by a question mark signalling the end of the input. The output should be the single word YES or NO reporting whether or not the sequence was properly matched up. For example, if the input is

( ( } ( ] ?

then the output should be YES, while if the input is

( ( ] ( } ?

then the output should be NO (since there is only one opening parenthesis remaining when the closing brace is seen). Recall that C++ automatically skips over blanks and newlines in the input if you use cin >> c; for a char variable c, so the spaces in the above examples are irrelevant. You may assume that there will never be more than 100 currently open symbols at any point in a valid expression.

Eeny Meeny

An ancient math problem concerns a group of people who stand in a circle and count off by reciting a rhyme such as ``Eeny Meeny, Miney Mo, ...'' (or simply by counting up to some predetermined number; there are lots of versions of this). Every time the count comes to the end, the last person leaves the circle and the count starts over with the next person. This continues until only one person is left. Some variations end with the last person being killed, while others have the last person as the only survivor. We will consider a much more benign version; the people will be numbered 1 through N, and as each person leaves the circle we will just print out their number. To make matters simple, we will just say ``Eeny Meeny,'' so as we go around the circle, every other person will be eliminated (the ``Meenies'').

For example, if we start with 10 people standing in order from 1 to 10, then the order in which they are eliminated is 2, 4, 6, 8, 10, 3, 7, 1, 9, 5. It is pretty easy to write a program to do this, especially if we have a queue ADT available. After filling up the queue with the appropriate numbers, we repeatedly remove the front element and then either reinsert it at the end or print it out, switching between these in strict alternation.

Instead of working the problem forwards, your problem is to work it backwards: figure out an initial ordering for N people so that when they play ``Eeny Meeny'' the people will be eliminated in strict increasing order, from 1 to N. For example, when N = 10, if we had initially lined them up in the order 8, 1, 6, 2, 10, 3, 7, 4, 9, 5, then the people will be eliminated in the correct order from 1 to 10.

Your program should simply take the number N as input, and print out the correct initial ordering. For instance, if the input is 3, then the output should be (please include the commas and spaces)

2, 1, 3

You may assume that the number N is in the range 1 to 100, inclusive.

Shuffle In, Shuffle Out

The shuffle is commonly used to put a collection of objects, such as playing cards, into a random order. However, some expert card handlers are able to perform what is known as a ``Faro shuffle'', where the two halves of the deck are combined in a strictly alternating fashion: one card from the left, then one from the right, and so on through the deck. If you can develop this skill, it is possible to force a given card in a standard 52-card deck to move to any desired location after at most six shuffles (some players of the card game Faro acquired notoriety for exploiting this skill in the 19th century, hence the name of the shuffle). The trick is to choose between making in and out shuffles: an in shuffle starts by putting the card from the middle of the deck at the top, while an out shuffle leaves the top card in place and puts the middle card second.

For example, if the deck consists of the numbers 1 through 10 in order, with 1 initially on top, then after an in shuffle the deck will be 6, 1, 7, 2, 8, 3, 9, 4, 10, 5. After an out shuffle, the order will be 1, 6, 2, 7, 3, 8, 4, 9, 5, 10.

For this problem, decks will always have an even number of ``cards'', numbered starting at 1. The problem is to read in a number of cards (which will be at most 100), followed by a sequence of characters 'I' or 'O', which give a sequence of in and out shuffles to be performed on a deck which initially contains all the cards in order, starting with 1 on top. The last character in the input will be a '?'; at that point, the output should give the position in the deck where the 1 card is located (the top is location 1, the next card is location 2, ). As usual, ignore spaces in the input.

Sample Input

10 I O I ?

Sample Output