Functional bowling in Scala

25 Jul, 2009
Xebia Background Header Wave

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_inframe(rolls:List[Int]):Int = { if (strike(rolls)) 1 else 2 } def strike(rolls:List[Int]):Boolean = { rolls.headOption.getOrElse(false) == 10 } 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 scoregame(g:List[Int]):Int = { framescores(g).foldLeft(0)(+_) } def framescores(game:List[Int]):List[Int] = { framesfor(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.


Get in touch with us to learn more about the subject and related solutions

Explore related posts