1998 ACM South Central USA Collegiate Programming Contest
Rice University

Bowl

Solution Judge's input Judge's output Clarifications Comments

`Scenario`

Technology hasn't come quickly to Joe's Bowl-a-rama. Minimum wage teens, and not those fancy machines, still reset the pins, and the grizzled veteran bowlers still mark up their own score sheets. Unfortunately for Joe Junior, who now runs the Bowl-a-rama, people his age are a little shaky on the scoring, especially after the second beer, and are staying away in droves, bowling instead at the new CyberBowl 2000 down the street, which scores automatically. Joe Junior figures that if he puts a cheap PC next to every lane, he can get a cheap, semi-automatic scoring system going. His plan is for the PC's to run software that only requires a bowler to enter the number of pins that remain standing after every throw -- and the software will keep score and tell the bowler when his game is over. Joe Junior would like to hire you to write the software.

Of course, since you may not know how to score a game of bowling either, Joe Junior has provided a description of the rules. The basic game consists of ten frames. In a frame, you get two chances to throw a ball down the alley and knock over as many pins as you can. There are ten pins standing at the beginning of a frame, and none are replaced after getting knocked over on the first ball, so the most pins you can knock over in a frame is ten. You get one point for each pin knocked over. In addition, there are two bonuses you can earn. If you knock over all ten pins on your first ball of the frame, you have scored a ``strike''; besides the ten points for the pins, your score in this frame is increased by the total number of pins knocked down with your next two balls. Those next two balls are usually part of another frame (or two) and score points in that frame (or those frames) as well. If you knock over all ten pins in a frame, but it takes you two balls to do it, you have scored a ``spare''; in addition to your ten points for pins knocked down, your score for the frame is increased by the number of pins you knock down on your next ball. Of course, those pins also count as part of the next frame. If you score a spare (or strike) in the final (tenth) frame, you are entitled to one (or two) extra balls to determine your tenth frame bonus. A perfect game scores 300 points, because each frame scores 30, 10 for knocking down 10 pins, and 20 for knocking down 20 pins with the next two balls combined.

Now, are you ready to sign on to write the software?

`Input`

The file ``bowl.inp'' contains several complete or partial games. A game is described by a single line with a single name, not to exceed 12 characters, and sequence of numbers, one for each ball thrown indicating the number of pins still standing after that throw. According to the rules, there are from 11 to 21 throws in a game; no input line will show throws beyond the last throw of the game. The number of games described in a file is not predetermined, so you'll have to detect the end of the input file.

`Output`

The standard output will contain, on successful completion of the program, two output lines for each input line. The first output line contains the name of the bowler and a record of the throws in each frame. This record shows, for each frame, the number of pins knocked down for each throw as a digit, with some exceptions. For a throw that knocks down no pins, a dash (\verb$-$) is used instead of a `0'. An 'X' indicates a throw that knocks down all 10 pins on the first try. A slash ('/') indicates a throw that finishes knocking down all the pins, after the previous throw left some standing. Otherwise, a throw is shown as a digit (`1' to `9'). The number of throws in a frame may be one (a strike in frames 1 to 9), or three (a strike or spare in frame 10, followed by bonus balls), but is usually two. Here are examples of throw markings for a variety of situations:

Marking	Comment
81	Knocked down 8 balls on the first throw, one on the next
7/	Knocked down 7 balls on the first throw, then the rest
X	Knocked down all balls on the first throw
9-	Knocked down 9 balls on the first throw, none on the next
8/X	Knocked down 8 balls on the first throw of frame 10, then the rest, then all the pins on the bonus throw
X-/	Knocked down ten balls on the first throw of frame 10, then missed all the pins on the first bonus throw and knocked them all down on the second bonus throw

The second output line shows cumulative scores. The cumulative score for the first frame is just the score for pins knocked down in frame, plus bonus points if they apply. The cumulative score for any other frame is the cumulative score for the previous frame plus the score for pins knocked down in that frame, plus the bonus pins that may have been earned for a strike or spare in this frame. It is possible to have markings on line one for a frame, but no score on line two, in the event that the frame is a strike or spare but the bonus points for the frame aren't yet known.

The format for this output requires that the bowler's name be left-justified. The fields for each frame are three characters wide, with a space separating each field. The fields begin in columns 14, 18, 22, and so on. The record of the throws in the first line is left justified in its field. The cumulative score is right justified in its field. There is a blank line that separates the scores of one bowler from the scores of another.

`Sample Input`

Chuck 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Solly 0 0 0 0 0 0 0 0 0 0 0 8
Lothar 10 0 10 0 10 0
Brutus 5 1 2 0 6 0 9
McGillicuddy 0 0 1 0
Homer 0 10 0 0 0 0
Barney 0 0 0 0 0 0 0 0 0 0 1 0

`Sample Output`

The line of digits is intended to guide you in proper output alignment, and is not part of the output that your solution should produce.

1234567890123456789012345678901234567890123456789012
Chuck 9/ 9/ 9/ 9/ 9/ 9/ 9/ 9/ 9/ 9/9
19 38 57 76 95 114 133 152 171 190

Solly X X X X X X X X X XX2
30 60 90 120 150 180 210 240 270 292

Lothar -/ -/ -/
10 20

Brutus 54 8/ 4/ 1
9 23 34

McGillicuddy X X 9/
29 49

Homer X -/ X X X
20 40 70

Barney X X X X X X X X X X9/
30 60 90 120 150 180 210 240 269 289

Solution

#include <iostream.h>
#include <fstream.h>
#include <strstream.h>
#include <iomanip.h>

int main()
{
ifstream fin("bowl.inp");

int firstTime = 1;
char name[13];
while (fin >> name)
    {
      if (!firstTime)
        cout << "\n";           // separating line
      firstTime = 0;

      char marks[4];
      unsigned nextMark = 0;
      unsigned score = 0;
      unsigned frame = 1;
      unsigned ball = 0;
      unsigned bonus = 0;
      ostrstream line1;
      ostrstream line2;

      line1.setf(ios::left);
      line1 << setw(12) << name << " ";
      line2 << setw(12) << " ";

      unsigned pinsUp, prevPinsUp = 10;
      while (fin >> pinsUp)
        {
          unsigned pinsDowned = prevPinsUp - pinsUp;

          if (bonus % 2 == 1)
            // this ball completes the scoring in some other frame
            {
              score += 10 + pinsDowned;
              line2 << setw(4) << score;
              --bonus;
            }
          if (bonus == 2)
            // the previous frame was a strike; this is ball 0
            {
              score += pinsDowned;
              bonus = 1;
            }

          marks[nextMark++] = (pinsUp?
                               "-123456789"[pinsDowned]:
                               "X/"[ball]);

          if (ball == 0 && pinsUp)
            ball = 1;
          else                  // ball == 1 || !pinsUp
              {
                if (!pinsUp)    // strike or spare
                  bonus += 2-ball;
                else            // open frame
                  {
                    score += 10-pinsUp;
                    line2 << setw(4) << score;
                  }
                if (frame < 10)
                  {
                    marks[nextMark++] = '\0';
                    line1 << setw(4) << marks;
                    nextMark = 0;
                  }
                ball = 0;
                pinsUp = 10;
                ++frame;
              }

          prevPinsUp = pinsUp;
        }
      marks[nextMark++] = '\0';
      line1 << setw(4) << marks;

line1 << "\n" << ends;
line2 << "\n" << ends;

      char* l1 = line1.str();
      char* l2 = line2.str();
      cout << l1 << l2;
      delete[] l1;
      delete[] l2;

      // must've stumbled across the next name by now
      fin.clear();
    }
return 0;
}

Judge's Input

Chuck 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Solly 0 0 0 0 0 0 0 0 0 0 0 8
Lothar 10 0 10 0 10 0
Brutus 5 1 2 0 6 0 9
McGillicuddy 0 0 1 0
Homer 0 10 0 0 0 0
Barney 0 0 0 0 0 0 0 0 0 0 1 0
Connie 2 1 2 0 0 0 0 0 0 0 0 0 9
Sal 1 0 2 0 0 0 3 1 0 3 1 4 0 0 2 0
Ethel
Bobby 0 0 0 0 0 0 0 0 0 0 0 1
Earl 1 0 0 0 0 0 0 0 0 0 0 0 0
Stan 0 0 0 0 0 0 0 0 0 0 0 0
Stoney 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
Speedy 0 1 0 2 1 3 1 2 0 3 0 1 1 3 2 1 0 0

Judge's Output

Chuck 9/ 9/ 9/ 9/ 9/ 9/ 9/ 9/ 9/ 9/9
19 38 57 76 95 114 133 152 171 190

Solly X X X X X X X X X XX2
30 60 90 120 150 180 210 240 270 292

Lothar -/ -/ -/
10 20

Brutus 54 8/ 4/ 1
9 23 34

McGillicuddy X X 9/
29 49

Homer X -/ X X X
20 40 70

Barney X X X X X X X X X X9/
30 60 90 120 150 180 210 240 269 289

Connie 81 8/ X X X X X X X X1
9 29 59 89 119 149 179 209 230

Sal 9/ 8/ X X 72 X 72 6/ X 8/
18 38 65 84 93 112 121 141 161

Ethel

Bobby X X X X X X X X X XX9
30 60 90 120 150 180 210 240 270 299

Earl 9/ X X X X X X X X XXX
20 50 80 110 140 170 200 230 260 290

Stan X X X X X X X X X XXX
30 60 90 120 150 180 210 240 270 300

Stoney -- -- -- -- -- -- -- --
0 0 0 0 0 0 0 0

Speedy X 9/ 81 72 8/ 7/ 9- 71 9/ X
20 38 47 56 73 92 101 109 129

Clarifications

No significant clarifications were necessary for this problem.

Comments

The part of this problem that gave people the most trouble was our bowler Ethel, who hasn't yet thrown a ball. At least one submission hung indefinitely when they reached Ethel. Another general problem was the tenth frame and the special cases it creates. Although not many solved it, I believe that this was a successful problem.