Functional bowling in Scala

Arjan Blokzijl

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:

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)
   }                
}

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:

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 = {
     rolls.headOption.getOrElse(false) == 10
}

def spare(rolls:List[Int]):Boolean = {
     rolls.take(2).foldLeft(0)(_+_) ==10
}

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.

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
}    

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:

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)))
    }    
}

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:

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
}

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.

Comments (7)

  1. Andrew Phillips - Reply

    July 27, 2009 at 8:00 am

    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]].

    • Arjan Blokzijl - Reply

      July 28, 2009 at 6:07 pm

      Hi Andrew,

      Indeed, my version deals with data structures, and functions that essentially know how to handle that (for which the first attempt was embarrassingly wrong by the way, see the update on the post). But your suggestion could certainly be a viable alternative. Perhaps I might give that a try as well, to see how it looks compared to my current version. For me, there's still a steep learning curve in writing proper Scala code.

  2. Jason Zaugg - Reply

    July 27, 2009 at 8:59 am

    >rolls.headOption.getOrElse(false) == 10

    I would write this:

    rolls.headOption.map(_ == 10) getOrElse false

    Or even better, using the typesafe equals from Scalaz 4

    import scalaz.Scalaz._

    rolls.headOption.map(_ === 10) getOrElse false

    Or even:

    import scalaz.Scalaz._
    ~rolls.headOption.map(_ === 10)

    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)

  3. ilan berci - Reply

    July 27, 2009 at 8:59 pm

    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.

    • Arjan Blokzijl - Reply

      July 28, 2009 at 7:09 am

      Hi Ilian,

      You're correct, my reading of the bowling rules was completely wrong. I should just read the rules better, or possibly go out more... In any case, I've updated the post with your comments to a version that now (hopefully) is correct, thanks for pointing this out.

  4. Sander Mak - Reply

    July 27, 2009 at 9:50 pm

    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.

    • Arjan Blokzijl - Reply

      July 28, 2009 at 9:27 am

      Hello Sander,

      Thanks for your reply, I agree that you're pattern match at least looks better than mine. However, it is indeed flawed as Ilan has pointed out. Personally I find the implementation using little functions a bit more expressive, demonstrating a bit more what the rules of the game are. I've updated to post with a more correct implementation (although I left the first pattern match intact, would perhaps a good exercise to try if we still can capture the whole game in one pattern match).

      Arjan

Add a Comment