# Difference between revisions of "Bowling"

From HaskellWiki

Tomjaguarpaw (talk | contribs) (Deleting page that hasn't been updated for over 10 years) |
m (Reverted edits by Tomjaguarpaw (talk) to last revision by Newacct) |
||

Line 1: | Line 1: | ||

+ | __TOC__ |
||

+ | |||

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

+ | |||

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

+ | |||

+ | == 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: |
||

+ | <haskell>StateT [Int] (Error String) Frame</haskell> |
||

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

+ | |||

+ | <haskell> |
||

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

+ | </haskell> |
||

+ | |||

+ | [[Category:Code]] |

## Latest revision as of 15:19, 6 February 2021

## Contents

## 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)
```