# Bowling

### From HaskellWiki

(Difference between revisions)

(Add example code) |
m |
||

(2 intermediate revisions by one user not shown) | |||

Line 9: | Line 9: | ||

[http://www.randomhacks.net/articles/2007/04/28/bowling-in-haskell On his blog]. This is a recursive solution. | [http://www.randomhacks.net/articles/2007/04/28/bowling-in-haskell On his blog]. This is a recursive solution. | ||

− | == Solution by | + | == Short Solution by Chris Kuklewicz == |

+ | |||

+ | <haskell> | ||

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

+ | </haskell> | ||

+ | |||

+ | == Solution by Chris Kuklewicz == | ||

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

Line 42: | Line 58: | ||

-- | Convert a Game to a list of (list of pins) for each frame | -- | Convert a Game to a list of (list of pins) for each frame | ||

toBalls :: Game -> [[Int]] | toBalls :: Game -> [[Int]] | ||

− | toBalls (Game {tenFrames = frames}) = | + | toBalls (Game {tenFrames = frames}) = map decode (elems frames) ++ final |

where decode (Normal {first=x,second=y}) = [x,y] | where decode (Normal {first=x,second=y}) = [x,y] | ||

decode (Spare {first=x}) = [x,10-x] | decode (Spare {first=x}) = [x,10-x] |

## Latest revision as of 08:56, 13 December 2009

## Contents |

## [edit] 1 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.

## [edit] 2 Solution by Eric Kidd

On his blog. This is a recursive solution.

## [edit] 3 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)

## [edit] 4 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)