A Bowling Sequence: a(n) returns the number of possibilities for the number of pins knocked down to reach that score.

Question

Once again, my lack of coding ability prevents me from quickly answering a math question that interests me currently. I imagine one of you wizards can knock this out quickly using brute force.

I am interested currently in a 301 term sequence that returns the number of possibilities for knocked-down pins to reach that score in a game of bowling. I can do some of the easy ones, for example:

a(0) = 1. Only 1 way to score 0 -- knock down 0 pins.

a(1) = 1. Only 1 way to score 1 -- knock down 1 pin.

...

a(11) = 1. Only 1 way to score 11 -- knock down 11 pins.

a(12) = 2. You can either knock down 12 pins, or knock down 11, where one counts double following a spare or a strike.

a(13) = 2. You can either knock down 13 pins, or knock down 12, where one counts double following a spare or a strike. (Note: you cannot knock down 11 where 2 count double, as that would imply a 9-pin spare/strike).

a(14) = 3, similarly

and so on.

Sure, maybe I could do this for a while for small numbers, but the configurations seem to get complicated very quickly in the middle. The large end is actually pretty easy too. a(291) to a(300) are similarly all 1.

Anyone interested enough in this problem to code this and link the sequence for me? I am most interested in where the maximum occurs [guess: around 200] and if there is an upper bound in terms of n (aside from the obvious one, n+1).

Answer 1

One naive brute force approach would be to go through all of the games and see what they score and how many pins are knocked down. However, there are ${66}^{9}*241=5\,726\,805\,883\,325\,784\,576$ games (see All About Bowling Scores). As this is a little over $2^{62}$, it's too many to naively work through, even for a computer. (Admittedly, there may be a semi-naive way to divide and conquer, analogous to what is described in the "Computation Algorithm" section below the Score Distribution Table at All About Bowling Scores.) To cut this down to a reasonable number without requiring clever programming, we can think about what information we need to preserve as we go through a game.

If all we care about is the variety of numbers of pins that can produce a given score, then we don't need to keep track of every possibility for exactly when each pin was hit. We certainly need to keep track of the number of pins hit so far, and the current score. And if we think about scores one throw at a time (useful for spares), then we need to know how many pins are standing in the lane to figure out the possibilities for the next throw. And since we'll need to know when the game ends, we should also keep track of how many frames have been completed.

Finally, because of the way scoring works in bowling, we also need to know the "type" of situation we're in, to know how the next throw will contribute to the score, and what type of situation it will lead to.

For now, let's ignore the special properties of what is officially "Frame 10", and consider things as if we're in the middle of a game (or as if bowling games went on forever).

The types will be: A: start of a frame not after a spare/strike B: start of a frame after a spare (so the next throw counts double) C: start of a frame after a strike (so the next two throws count double) D: start of a frame after two strikes (so next throw counts triple (and the following throw counts at least double)) E: middle of a frame not after a strike F: middle of a frame after a strike in the previous frame (so the next throw counts double)

---

Putting all of this info together summarizes the state of the game. For example $(0, 0, \text{A}, 10, 0)$ is the start where the score is $0$, $0$ pins have been hit, the type of situation is "A", there are $10$ pins standing in the lane, and $0$ frames have been completed.

After one throw, we might be in a state like $(3,3,\text{E},7,0)$ or $(10,10,\text{C},10,1)$. After two throws, maybe we're in $(10,10,\text{B},10,1)$ or $(26,18,\text{F},2,1)$, etc.

Given this sort info as the state of the game, we can calculate all of the possible next states, at least naively (ignoring Frame 10). For convenience, let's say that the state is "$\left(\text{score},\text{pins},\text{type},\text{lane},\text{frame}\right)$". We've already noted a "$\text{multiplier}$" for the score of the next throw, which is $2$ for $\text{type}$ B, C, and F, and $3$ for D (and $1$ for A and E). On our throw, we may hit any number (call it "$\text{hit}$") of pins from $0$ up to $\text{lane}$. After doing so, the new score will be $\text{score}+\text{hit}*\text{multiplier}$, and the new number of pins hit will be $\text{pins}+\text{hit}$.

The other data will depend on whether or not we hit all the pins (i.e. whether $\text{hit}=\text{lane}$). If so, then the new type is C, D, or B depending on whether it was $\text{type}$ was (A or B), (C or D), or (E or F), respectively. And the new number of pins in the lane for the next throw will be $10$. And the frame number will increase by $1$. If we don't hit all the pins, then new type is E or F or A in those same cases. And the new number of pins in the lane will be $10$ if the $\text{type}$ was E or F, and otherwise $10-\text{hit}$. And the frame number will increase by $1$ only if the $\text{type}$ was E or F.

Putting this all together into a Mathematica function yields something like:

naiveNextStates[state_] := 
  With[{score = state[[1]], pins = state[[2]], type = state[[3]], 
    lane = state[[4]], frame = state[[5]], 
    multiplier = Switch[state[[3]], "a" | "e", 1, "b" | "c" | "f", 2, "d", 3]}, 
   Table[Join[{score + hit*multiplier, pins + hit}, 
     If[hit == lane, 
	{Switch[type, "a" | "b", "c", "c" | "d", "d", "e" | "f", "b"], 10, frame + 1}, 
      Join[{Switch[type, "a" | "b", "e", "c" | "d", "f", "e" | "f", "a"]}, 
	Switch[type, "e" | "f", {10, frame + 1}, _, {10 - hit, frame}]]]], 
	{hit, 0, lane}]];

---

This works fine when $\text{frame}<10$, except that the game's Frame 10 might not be over yet when it outputs a new $\text{frame}$ of $10$. And it doesn't calculate the scoring of Frame 10 correctly, either. As such, we'll have to supplement it with more cases. For convenience, we'll use $\text{frame}$ to mean "how many times the pins have been reset", so that a near-perfect game allows $\text{frame}$ to be as high as $12$ at the end of the game. We'll also add a new $\text{type}$ for the End of a game.

For convenient idempotence, if the $\text{type}$ is End, then the only next state is the current state. And note that if $10$ frames have been completed and $\text{type}$ is A, then really the game is over since there are no extra throws for a final spare/strike, and we should just change the $\text{type}$ to End.

Otherwise (if $\text{frame}$ is $10$ but $\text{type}$ is not A), the score can only go up by the number of pins hit unless we're in $\text{type}$ D in which case we get double (not triple) points for pins hit. If $\text{type}$ is B, E, or F, then the game ends after this throw (with $\text{frame}$ at $11$). In the remaining $\text{type}$s of C and D, the result depends on whether all $10$ pins are hit. If so, then the new $\text{type}$ is D and the lane is set up with $10$ new pins. If not, then the new $\text{type}$ is F and there are only $10-\text{hit}$ pins left and we do not advance to $\text{frame}$ $11$.

Finally, in the rare event where $\text{frame}$ is $11$ but the game isn't over (because the official Frame 10 began with two strikes, making $\text{type}$ D), score rises by the number of pins hit and then the game ends.

Leveraging the previous code and memoization, this all could be written in Mathematica code as:

nextStates[state_] := 
 nextStates[state] = 
  With[{score = state[[1]], pins = state[[2]], type = state[[3]], 
    lane = state[[4]], frame = state[[5]]}, 
   Which[frame < 10, naiveNextStates[state], type == "end", {state}, 
    frame == 10, 
    Switch[type, "a", {{score, pins, "end", 10, 10}}, _, 
     Table[Join[{score + Switch[type, "d", 2, _, 1]*hit, pins + hit}, 
       Switch[type, "b" | "e" | "f", {"end", 10, 11}, 
	"c" | "d", If[hit == 10, {"d", 10, 11}, {"f", 10 - hit, 10}]]], 
	{hit, 0, lane}]], 
	frame == 11, 
    Table[{score + hit, pins + hit, "end", 10, 12}, {hit, 0, 10}]]];

---

Now that we have a way to generate the next states from a current one, we can generate all of the game states by iterating. If we have a list of possible states, we could map nextStates over it to make a list of lists of possible states after the next throw. Then flatten it one level to a list of states, and delete duplicates. In Mathematica, this could be generateStep[list_] := DeleteDuplicates[Flatten[Map[nextStates, list], 1]];

We know the set of start positions is $\left\{(0,0,\text{A},10,0)\right\}$ and that a game of bowling has at most $21$ throws (so that there are definitely no more than $22$ iterations of generateStep needed). As such we can use starts = {{0, 0, "a", 10, 0}}; everyGameEnd = Nest[generateStep, starts, 22]; to create a list of every possible game end state (it turns out there are $24\,043$ of them).

Finally, we can take just the scores and pins out of those, delete the duplicates, and count the desired numbers of possible $\text{pins}$-values for each score. One way to do this in Mathematica is with the obscure code KeyValueMap[List, CountsBy[DeleteDuplicates[Map[#[[1;;2]] &, everyGameEnd]], First]].

---

All the code together (plus a little more to show summaries of all $485\,974$ states considered) is shown below.

Wolfram Language (Mathematica), 1653 bytes

naiveNextStates[state_] := 
  With[{score = state[[1]], pins = state[[2]], type = state[[3]], 
    lane = state[[4]], frame = state[[5]], 
    multiplier = Switch[state[[3]], "a" | "e", 1, "b" | "c" | "f", 2, "d", 3]}, 
   Table[Join[{score + hit*multiplier, pins + hit}, 
     If[hit == lane, 
	{Switch[type, "a" | "b", "c", "c" | "d", "d", "e" | "f", "b"], 10, frame + 1}, 
      Join[{Switch[type, "a" | "b", "e", "c" | "d", "f", "e" | "f", "a"]}, 
	Switch[type, "e" | "f", {10, frame + 1}, _, {10 - hit, frame}]]]], 
	{hit, 0, lane}]];
nextStates[state_] := 
 nextStates[state] = 
  With[{score = state[[1]], pins = state[[2]], type = state[[3]], 
    lane = state[[4]], frame = state[[5]]}, 
   Which[frame < 10, naiveNextStates[state], type == "end", {state}, 
    frame == 10, 
    Switch[type, "a", {{score, pins, "end", 10, 10}}, _, 
     Table[Join[{score + Switch[type, "d", 2, _, 1]*hit, pins + hit}, 
       Switch[type, "b" | "e" | "f", {"end", 10, 11}, 
	"c" | "d", If[hit == 10, {"d", 10, 11}, {"f", 10 - hit, 10}]]], 
	{hit, 0, lane}]], 
	frame == 11, 
    Table[{score + hit, pins + hit, "end", 10, 12}, {hit, 0, 10}]]];
generateStep[list_] := DeleteDuplicates[Flatten[Map[nextStates, list], 1]];
starts = {{0, 0, "a", 10, 0}};
everyGame = Apply[Union, NestList[generateStep, starts, 22]];
everyGameEnd = Nest[generateStep, starts, 22];
CountsBy[everyGame, {#[[3]], #[[5]]} &] // Print
statesPerFrame = CountsBy[everyGame, #[[5]] &];
statesPerFrame // Print
Total[Values[statesPerFrame]] // Print
CountsBy[everyGameEnd, #[[3]] &] // Print
KeyValueMap[List,CountsBy[
	DeleteDuplicates[Map[#[[1;;2]] &, everyGameEnd]],
	 First]] // Print

Try it online!

---

The table of values of the sequence goes $$\begin{matrix}0 & 1 & 43 & 19 & 86 & 48 & 129 & 67 & 172 & 53 & 215 & 39 & 258 & 25\\1 & 1 & 44 & 20 & 87 & 49 & 130 & 67 & 173 & 53 & 216 & 39 & 259 & 24\\2 & 1 & 45 & 21 & 88 & 49 & 131 & 67 & 174 & 53 & 217 & 38 & 260 & 24\\3 & 1 & 46 & 21 & 89 & 50 & 132 & 67 & 175 & 52 & 218 & 38 & 261 & 24\\4 & 1 & 47 & 22 & 90 & 51 & 133 & 66 & 176 & 52 & 219 & 38 & 262 & 23\\5 & 1 & 48 & 23 & 91 & 51 & 134 & 66 & 177 & 52 & 220 & 37 & 263 & 23\\6 & 1 & 49 & 23 & 92 & 52 & 135 & 66 & 178 & 51 & 221 & 37 & 264 & 23\\7 & 1 & 50 & 24 & 93 & 53 & 136 & 65 & 179 & 51 & 222 & 37 & 265 & 22\\8 & 1 & 51 & 25 & 94 & 53 & 137 & 65 & 180 & 51 & 223 & 36 & 266 & 22\\9 & 1 & 52 & 25 & 95 & 54 & 138 & 65 & 181 & 50 & 224 & 36 & 267 & 22\\10 & 1 & 53 & 26 & 96 & 55 & 139 & 64 & 182 & 50 & 225 & 36 & 268 & 21\\11 & 1 & 54 & 27 & 97 & 55 & 140 & 64 & 183 & 50 & 226 & 35 & 269 & 21\\12 & 2 & 55 & 27 & 98 & 56 & 141 & 64 & 184 & 49 & 227 & 35 & 270 & 21\\13 & 2 & 56 & 28 & 99 & 57 & 142 & 63 & 185 & 49 & 228 & 35 & 271 & 20\\14 & 3 & 57 & 29 & 100 & 57 & 143 & 63 & 186 & 49 & 229 & 34 & 272 & 19\\15 & 3 & 58 & 29 & 101 & 58 & 144 & 63 & 187 & 48 & 230 & 34 & 273 & 17\\16 & 4 & 59 & 30 & 102 & 59 & 145 & 62 & 188 & 48 & 231 & 34 & 274 & 16\\17 & 4 & 60 & 31 & 103 & 59 & 146 & 62 & 189 & 48 & 232 & 33 & 275 & 14\\18 & 5 & 61 & 31 & 104 & 60 & 147 & 62 & 190 & 47 & 233 & 33 & 276 & 13\\19 & 5 & 62 & 32 & 105 & 61 & 148 & 61 & 191 & 47 & 234 & 33 & 277 & 11\\20 & 6 & 63 & 33 & 106 & 61 & 149 & 61 & 192 & 47 & 235 & 32 & 278 & 10\\21 & 6 & 64 & 33 & 107 & 62 & 150 & 61 & 193 & 46 & 236 & 32 & 279 & 8\\22 & 7 & 65 & 34 & 108 & 63 & 151 & 60 & 194 & 46 & 237 & 32 & 280 & 7\\23 & 7 & 66 & 35 & 109 & 63 & 152 & 60 & 195 & 46 & 238 & 31 & 281 & 6\\24 & 8 & 67 & 35 & 110 & 64 & 153 & 60 & 196 & 45 & 239 & 31 & 282 & 6\\25 & 8 & 68 & 36 & 111 & 65 & 154 & 59 & 197 & 45 & 240 & 31 & 283 & 5\\26 & 9 & 69 & 37 & 112 & 65 & 155 & 59 & 198 & 45 & 241 & 30 & 284 & 5\\27 & 9 & 70 & 37 & 113 & 66 & 156 & 59 & 199 & 44 & 242 & 30 & 285 & 4\\28 & 10 & 71 & 38 & 114 & 67 & 157 & 58 & 200 & 44 & 243 & 30 & 286 & 4\\29 & 10 & 72 & 39 & 115 & 67 & 158 & 58 & 201 & 44 & 244 & 29 & 287 & 3\\30 & 11 & 73 & 39 & 116 & 68 & 159 & 58 & 202 & 43 & 245 & 29 & 288 & 3\\31 & 11 & 74 & 40 & 117 & 69 & 160 & 57 & 203 & 43 & 246 & 29 & 289 & 2\\32 & 12 & 75 & 41 & 118 & 69 & 161 & 57 & 204 & 43 & 247 & 28 & 290 & 2\\33 & 13 & 76 & 41 & 119 & 70 & 162 & 57 & 205 & 42 & 248 & 28 & 291 & 1\\34 & 13 & 77 & 42 & 120 & 70 & 163 & 56 & 206 & 42 & 249 & 28 & 292 & 1\\35 & 14 & 78 & 43 & 121 & 69 & 164 & 56 & 207 & 42 & 250 & 27 & 293 & 1\\36 & 15 & 79 & 43 & 122 & 69 & 165 & 56 & 208 & 41 & 251 & 27 & 294 & 1\\37 & 15 & 80 & 44 & 123 & 69 & 166 & 55 & 209 & 41 & 252 & 27 & 295 & 1\\38 & 16 & 81 & 45 & 124 & 68 & 167 & 55 & 210 & 41 & 253 & 26 & 296 & 1\\39 & 17 & 82 & 45 & 125 & 68 & 168 & 55 & 211 & 40 & 254 & 26 & 297 & 1\\40 & 17 & 83 & 46 & 126 & 68 & 169 & 54 & 212 & 40 & 255 & 26 & 298 & 1\\41 & 18 & 84 & 47 & 127 & 67 & 170 & 54 & 213 & 40 & 256 & 25 & 299 & 1\\42 & 19 & 85 & 47 & 128 & 67 & 171 & 54 & 214 & 39 & 257 & 25 & 300 & 1\end{matrix}$$

Here's a graph of the values of the sequence:

The maximum is at $a(119)=a(120)=70$, and a fairly tight upper bound for $a(n)$ is $\frac35n+1$.