Blog

# Functional bowling in Scala

25 Jul, 2009

I have read about implementing the bowling game XP-style many years ago in Robert Martin’s book ‘Agile Software Development’. The episode can be found online as well.
Recently he has recently been learning Clojure and attempted to implement the bowling game in Clojure.
It is a nice exercise, and although I like Clojure, I do not regard myself capable in any way to repeat such an attempt. Apart from that Stuart Halloway, author of the excellent ‘Programming in Clojure’ book, has already done this in a much better way than I ever could. I’m slightly more familiar with Scala, so I thought it would be a nice exercise to try some functional bowling using that. My Scala knowledge is in a deplorable state, stuck at pre-beginner level, so I run the risk of making a complete fool of myself. However I’ll take the chance and at least try to learn from the experience.

First, let’s re-iterate the rules of bowling:

1. The game consists of 10 frames. In each frame the player has two opportunities to knock down 10 pins. The score for the frame is the total number of pins knocked down, plus bonuses for strikes and spares.
2. A spare is when the player knocks down all 10 pins in two tries. The bonus for that frame is the number of pins knocked down by the next roll.
3. A strike is when the player knocks down all 10 pins on his first try. The bonus for that frame is the value of the next two balls rolled.
4. In the tenth frame a player who rolls a spare or strike is allowed to roll the extra balls to complete the frame. However no more than three balls can be rolled in tenth frame.

So in some way we need to keep track of frame scores for a game. For simplicity, I’m just using a sequence of integers that represents a game. Each integer just represents the number of pins knocked down by each throw.
This sequence should be divided, or transformed if you like, into a sequence of frames. I started with something like this:
[scala]
case class Frame(first:Int, second:Int, third:Int) {
override def toString() = {"firstThrow: " + first + " secondThrow" + second + " thirdThrow: " + third}
}
def frames(g:List[Int]):List[Frame] = {
g match {
case Nil => Nil
case x::Nil => List(new Frame(x, 0, 0))
case x::xs::Nil => List(new Frame(x, xs, 0))
case 10 :: x::xs => new Frame(10, x, xs.head) :: frames(xs.tail)
case x::xs::xss if ((x + xs) == 10) => new Frame(x, xs, xss.head) :: frames(xss.tail)
case x::xs => new Frame(x, xs.head, 0) :: frames(xs.tail)
}
}
[/scala]
But this might be an excellent candidate for the thedailywtf. This surely cannot be the way how to write proper Scala, and apart from that, it’s not very generic and extensible. So, after thinking about the matter a bit, a second attempt. First of all, why a class when we have functions? A sequence of frames can just be expressed as a list of lists, like so:
[scala]
def frames(g:List[Int]):List[List[Int]] = {
if (g.isEmpty) Nil
else {
val throws = throws_for_frame(g)
g.take(throws)::frames(g.drop(throws))
}
}
def frames(g:List[Int]):List[List[Int]] = {
if (g.isEmpty) Nil
else
g.take(throws_for_frame_score(g))::frames(g.drop(throws_in_frame(g)))
}
def throws_for_frame_score(rolls:List[Int]):Int = {
if (strike(rolls) || spare(rolls)) 3
else 2
}
def throws_in_frame(rolls:List[Int]):Int = {
if (strike(rolls)) 1
else 2
}
def strike(rolls:List[Int]):Boolean = {
}
def spare(rolls:List[Int]):Boolean = {
rolls.take(2).foldLeft(0)(_+_) ==10
}
[/scala]
Not too bad, if you look at it from a distance some little helper functions like strike and spare even seem to be related to some of the bowling rules defined above. A frame is now just a list consisting of either 2 or 3 elements, depending on whether a strike or spare has been scored. Each element is an integer containing the pins that are knocked down.
Scoring a game now becomes a rather trivial affair, we just take the 10 frames that are bowled and add up the pins scored in each frame.
[scala]
def score_game(g:List[Int]):Int = {
framescores(g).foldLeft(0)(_+_)
}
def framescores(game:List[Int]):List[Int] = {
frames_for(game).take(10).map(l => l.foldLeft(0)(_+_))
}
def framesThrown(g:List[Int]) = {
frames(g).length
}
[/scala]
In the REPL, you can easily test these functions:

```scala> framesThrown(List(4,5))
res1: Int = 1
scala> framesThrown(List(4,5,10,3,4,6,7,2))
res2: Int = 4
scala> framescores(List(4,5))
res3: List[Int] = List(9)
scala> framescores(List(4,5,6,3))
res4: List[Int] = List(9, 9)
scala> framescores(List(5,5,6,3))
res5: List[Int] = List(16, 9)
scala> framescores(List(5,5,6,3,10,10,3))
res6: List[Int] = List(16, 9, 23, 13, 3)
scala> framescores(List(10,10,10,10))
res4: List[Int] = List(30, 30, 20, 10)
```

And to satisfy Uncle Bob, some unit tests:
[scala]
class BowlingTest {
def repeat[T](n: Int)(what: => T): List[T] = {
if (n==0)List.empty
else what::repeat(n-1)(what)
}
@Test
def scoreForTwoThrows = {
assertEquals(9, score(List(4,5)))
}
@Test
def strikeShouldGiveTwoExtraThrowsForScore = {
assertEquals(List(30,30,20,10), framescores(repeat(4)(10)))
assertEquals(24, score(List(5, 3, 4, 5, 3,4)))
assertEquals(32, score(List(10, 3, 4, 5, 3)))
}
@Test
def spareShouldGiveOneExtraThrowsForScore = {
assertEquals(24, score(List(5, 3, 4, 5, 3, 4)))
assertEquals(30, score(List(5, 5, 4, 5, 3, 4)))
}
@Test
def spareAtEndShouldGiveOneExtraThrowsForScore = {
assertEquals(60, score(List(4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 6, 5)))
assertEquals(54, score(List(4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 5, 5)))
}
@Test
def strikeAtEndShouldGiveTwoExtraThrowsForScore = {
assertEquals(65, score(List(4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 10, 5, 5)))
assertEquals(54, score(List(4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 1, 4, 5, 5)))
}
@Test
def tears = {
assertEquals(299, score(List(10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 9)))
}
@Test
def perfectGameShouldScore300 = {
assertEquals(300, score(repeat(12)(10)))
}
@Test
def allOnesShouldScore20 = {
assertEquals(20, score(repeat(20)(1)))
}
}
[/scala]
It’s still a bit simplistic (for example, framesThrown doesn’t really check whether a frame is finished, i.e. whether two or three throws have been made, there’s no validation that the number of pins knocked down cannot be larger than 10, games can have an infinite length, etc, etc). However I’ll leave it at this for the moment, and will try to perfect it later. It has already been a nice exercise so far in any case. As stated, my Scala knowledge is such that this implementation can most likely be heavily improved upon. If you have suggestions for improvements (or have an implementation of your own) your comments are highly appreciated.
Update
As Ilian Berci has pointed out, my satisfaction at my original attempt was completely misguided. Somehow I managed to misinterpret the bowling rules completely. I managed to get into my mind that a strike would give two extra throws, in each frame. However, if you have once taken up a game of bowling yourself you know that this is complete nonsense. It is only so that the next two throws (which are then part of another frame) contribute to the frame in which the strike is scored. It is only at the tenth frame that the bowler gets an extra frame (consisting of maximum two throws) if he scores a strike at his final games. So, my original framescores function and helper function looked like below:
[scala]
def frames(g:List[Int]):List[List[Int]] = {
if (g.isEmpty) Nil
else {
val throws = throws_for_frame(g)
g.take(throws)::frames(g.drop(throws))
}
}
def throws_for_frame(rolls:List[Int]):Int = {
if (strike(rolls) || spare(rolls)) 3
else 2
}
[/scala]
which is utterly wrong, since it places all the throws that contribute to a frame score in the same frame (and removes them from the remaining games list). This makes that a game in my original version could take up to 30 throws, instead of the 21 maximum throws possible.
So, in my original version, the framescores functions behaved like this:

```scala> framescores(List(5,5,6,3))
res14: List[Int] = List(16, 3)
scala> framescores(List(10,10,10,10,10))
res15: List[Int] = List(30,20)
```

Fixing it didn’t take much time however, which was a relief because I thought I had completely messed up. I’ve updated the post with a version which is (hopefully) now correct (so you can see the fix in the frame function and helper functions throws_for_frame_score and throws_in_frame), and also updated the tests into some more sensible ones. The wtf version is still left to its original, fixing that would probably even make it more horrible than its original. Thanks to Ilian for pointing this out, clearly can’t beat Uncle Bob.

Inline Feedbacks
Andrew Phillips
12 years ago

Would Spare, Strike and "Normal" (for want of a better name) not be good candidates for a case class? In your second version you’ve defined functions for them that essentially know how to “extract” the relevant scores for this type of frame from the complete list of scores, which looks rather like a constructor. This would also seem to be a fairly natural place for validation.
Furthermore, you’d be back to List[Frame] as the type of a game, which is a little more expressive than List[List[Int]].

Jason Zaugg
12 years ago

I would write this:
Or even better, using the typesafe equals from Scalaz 4
import scalaz.Scalaz._
Or even:
import scalaz.Scalaz._
This expands with the help of implicits to:
val mappedOption = rolls.headOption.map((i: Int) => Identity.ToIdentity(i).===(10)(Eq.IntEqual))
val wrappedOption = OptionW.OptionTo(mappedOption)
val result = wrappedOption.unary_~(Zero.BooleanZero) // Zero.BooleanZero defines that ‘false’ is the ‘zero’, ie the default, for the type Boolean.
println(result)

ilan berci
12 years ago

Uncle bob would not be satisfied because the algorithm is flawed.. Remember that in the case of spares and strikes, some of the balls count their value in 2 or more frames..
scala> framescores(List(5,5,6,3))
res14: List[Int] = List(16, 3)
should be:
List(16, 9)
Another example where the test case only asserts the error condition.. (The class example also exposes the same logic error).. please write your test cases prior to writing the code if you really want to appease uncle Bob.

Sander Mak
12 years ago

I thought the pattern matching approach wasn’t completely out of whack, this would be how I’d do it: http://www.gulic.org/pastebin/45
Also note the type synonym Frame, which gives the nice name (though only used once in my code) without having to define case classes. Oh, and I noticed that I forgot to take(10) of the tokenized list. Furthermore I took the behavior from your example, so it suffers from the same problem ilan just pointed out I guess.