Bowling

The problem

Convert a list of number of pins knocked over by each ball into a final score for a game of ten pin bowling.

Solution by Eric Kidd

On his blog. This is a recursive solution.

Short Solution by Chris Kuklewicz

import Control.Monad.State

score = sum . evalState (replicateM 10 (State scoreFrame))
  where scoreFrame (10:rest@(a:b:_)) = (10+a+b,rest)
        scoreFrame (x:y:rest) | x+y < 10 = (x+y,rest)
                              | otherwise = (10+head rest,rest)

score2 = fst . (!!10) . iterate addFrame . (,) 0
 where addFrame (total,10:rest@(a:b:_))      = (total+10+a+b       ,rest)
       addFrame (total,x:y:rest) | x+y < 10  = (total+x+y          ,rest)
                                 | otherwise = (total+x+y+head rest,rest)

Solution by Chris Kuklewicz

Listed here. This has a monad-using parser with inferred type:

StateT [Int] (Error String) Frame

The constraint that there are 10 frames is declared by using (replicateM 10). All invalid input lists should be recognized.

module Bowling(Frame(..),Game(..),toGame,toBalls,score) where

import Control.Monad(replicateM,when)
import Control.Monad.State(get,put,evalStateT,StateT(..))
import Control.Monad.Error(throwError)
import Data.Array.IArray(Array,(!),elems,listArray,inRange)

-- | Representation of a finished Game of bowling
data Game = Game { gameScore :: Int
                 , tenFrames :: Array Int Frame }
  deriving (Show,Eq)

-- | Compact representation of a Frame from a finished Game
data Frame = Normal { frameScore, first, second :: Int}
           | Spare  { frameScore, first :: Int}
           | Strike { frameScore, next :: Int}
  deriving (Show,Eq)

-- | Convert a list of pins to a final score
score :: [Int] -> Int
score balls = case toGame balls of
                Left msg -> error msg
                Right g -> gameScore g

-- | Convert a Game to a list of (list of pins) for each frame
toBalls :: Game -> [[Int]]
toBalls (Game {tenFrames = frames}) = map decode (elems frames) ++ final
 where decode (Normal {first=x,second=y}) = [x,y]
       decode (Spare {first=x}) = [x,10-x]
       decode (Strike {}) = [10]
       final = case (frames ! 10) of
                 Normal {} -> []
                 Spare {frameScore=s} -> [[s-10]]
                 Strike {frameScore=s,next=10} -> [[10],[s-20]]
                 Strike {frameScore=s,next=a} -> [[a,s-a-10]]

-- | Try to convert a list of pins to a Game
toGame :: [Int] -> Either String Game
toGame balls = do
  frames <- parseFrames balls
  return $ Game { gameScore = sum (map frameScore frames)
                , tenFrames = listArray (1,10) frames
                }

-- This will only return an error or a list of precisely 10 frames
parseFrames balls = flip evalStateT balls $ do
  frames <- replicateM 10 (StateT parseFrame)
  remaining <- get
  case (last frames,remaining) of
    (Normal {} , []) -> return frames
    (Spare {}  , _:[]) -> return frames
    (Strike {} , _:_:[]) -> return frames
    _ -> err balls "Too many balls"

parseFrame balls@(10:rest) = do
  case rest of
    (a:b:_) -> do
      checkBalls [a,b]
      when ((a /= 10) && (a+b > 10)) $
           err balls "More than 10 pins in frame after a strike"
      return (Strike (10+a+b) a,rest)
    _ -> err balls "Too few balls after a strike"

parseFrame balls@(x:y:rest) = do
  checkBalls [x,y]
  case compare (x+y) 10 of
    GT -> err balls "More than 10 pins in a frame"
    LT -> return (Normal (x+y) x y,rest)
    EQ -> case rest of
            [] -> err balls "No ball after a spare"
            (a:_) -> do checkBall a
                        return (Spare (10+a) x,rest)

parseFrame balls = err balls "Not enough balls"

err balls s = throwError (s ++ " : " ++ show (take 23 balls))
checkBalls = mapM_ checkBall
checkBall x = when (not (inRange (0,10) x))
                   (throwError $ "Number of pins is of out range (0,10) : " ++ show x)