Bowling
The problem[edit]
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[edit]
On his blog. This is a recursive solution.
Short Solution by Chris Kuklewicz[edit]
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[edit]
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)