In software development there are no silver bullets, but I am always looking out for the next bronze one.

Tuesday, March 10, 2009

Bowling in Yet Another Language (F#)

Another day, another blog posting involving bowling and a functional programming language. This one is in F#, which is very interesting language for the .NET platform. Code:

#light

module Bowling

open System;;

let scoreToInt x =
match x with
Some y -> y
| None -> -1;;

let rec tallyScores accum x =
match x with
[] -> []
| x::rest -> let score = scoreToInt x in
if (score >= 0) then
let total = (accum + score) in total :: tallyScores total rest;
else
[];;

let rec take n l =
if (n > 0) then
match l with
x::rest -> let newn = n-1 in x :: take newn rest
| [] -> []
else
[];;

let rec reduce f ys =
if ys <> [] then
let (x, ys') = f ys in x::reduce f ys'
else [];;

let scoreFrame rolls =
match rolls with
x1::x2::x3::rest -> if (x1 = 10) then (Some (x1+x2+x3), x2::x3::rest)
else if (x1 + x2 = 10) then
(Some (x1+x2+x3), x3::rest)
else (Some(x1+x2), x3::rest)
| x1::x2::[] -> if (x1 + x2 < 10) then
(Some(x1 + x2), [])
else (None, []);
| _ -> (None, []);;

let scoreTenFrames rolls =
take 10 (reduce scoreFrame rolls);;

let tallyGame rolls =
tallyScores 0 (scoreTenFrames rolls);;

let printGame rolls =
List.iter (fun x -> Console.Write(int x); Console.Write " ") (tallyGame rolls);
Console.Write "\n";;

let assertTrue expression =
if (expression = false) then
failwith "Assertion Not True";;

assertTrue ([30;60;90;120;150;180;210;240;270;300] = tallyGame[10;10;10;10;10;10;10;10;10;10;10;10]);;
assertTrue ([30;60;90;120;150;180;210;240;270;299] = tallyGame[10;10;10;10;10;10;10;10;10;10;10;9]);;
assertTrue ([30;60;90;120;150;180;210;240;270;290] = tallyGame[10;10;10;10;10;10;10;10;10;10;10;0]);;
assertTrue ([20;50;80;110;140;170;200;230;260;290] = tallyGame[9;1;10;10;10;10;10;10;10;10;10;10;10]);;
assertTrue ([30;60;90;120;150;180;210;240;269;289] = tallyGame[10;10;10;10;10;10;10;10;10;10;9;1]);;
assertTrue ([30;60;90;120;150;180;210;240;269;288] = tallyGame[10;10;10;10;10;10;10;10;10;10;9;0]);;
assertTrue ([30;60;90;120;150;180;210;240;260;280] = tallyGame[10;10;10;10;10;10;10;10;10;10;0;10]);;
assertTrue ([20;40;70;100;130;160;190;220;250;280] = tallyGame[10;9;1;10;10;10;10;10;10;10;10;10;10]);;
assertTrue ([30;60;90;120;150;180;210;239;259;279] = tallyGame[10;10;10;10;10;10;10;10;10;9;1;10]);;
assertTrue ([30;60;90;120;150;180;210;240;260;270] = tallyGame[10;10;10;10;10;10;10;10;10;10;0;0]);;
assertTrue ([20;40;60;80;100;120;140;160;180;200] = tallyGame[10;9;1;10;9;1;10;9;1;10;9;1;10;9;1;10]);;
assertTrue ([19;38;57;76;95;114;133;152;171;190] = tallyGame[9;1;9;1;9;1;9;1;9;1;9;1;9;1;9;1;9;1;9;1;9]);;
assertTrue ([19;38;57;76;95;114;133;152;171;180] = tallyGame[9;1;9;1;9;1;9;1;9;1;9;1;9;1;9;1;9;1;9;0]);;
// Partial games
assertTrue ([] = tallyGame[]);;
assertTrue ([] = tallyGame[0]);;
assertTrue ([] = tallyGame[9]);;
assertTrue ([] = tallyGame[10]);;
assertTrue ([] = tallyGame[9;1]);;
assertTrue ([] = tallyGame[10; 9]);;
assertTrue ([] = tallyGame[10; 10]);;
assertTrue ([0] = tallyGame[0; 0]);;
assertTrue ([1] = tallyGame[0; 1]);;
assertTrue ([9] = tallyGame[8; 1]);;
assertTrue ([9] = tallyGame[9; 0]);;
assertTrue ([19] = tallyGame[9; 1; 9]);;
assertTrue ([19; 28] = tallyGame[10; 9; 0]);;
assertTrue ([19; 28] = tallyGame[9; 1; 9; 0]);;
assertTrue ([20] = tallyGame[10; 9; 1]);;
assertTrue ([30] = tallyGame[10; 10; 10]);;
assertTrue ([30; 59] = tallyGame[10; 10; 10; 9]);;
assertTrue ([30; 59; 78; 87] = tallyGame[10; 10; 10; 9; 0]);;

Note that I've included a quick and dirty assertTrue method to validate the functions.


The above example can be used via the interactive shell (fsi) like below:



C:\DotNET\src>fsi

Microsoft F# Interactive, (c) Microsoft Corporation, All Rights Reserved
F# Version 1.9.6.2, compiling for .NET Framework Version v2.0.50727

Please send bug reports to fsbugs@microsoft.com
For help type #help;;

> #load "bowling.fs";;
[Loading C:\DotNET\src\bowling.fs]

namespace FSI_0002
val scoreToInt : int option -> int
val tallyScores : int -> int option list -> int list
val take : int -> 'a list -> 'a list
val reduce : ('a list -> 'b * 'a list) -> 'a list -> 'b list
val scoreFrame : int list -> int option * int list
val scoreTenFrames : int list -> int option list
val tallyGame : int list -> int list
val printGame : int list -> unit
val assertTrue : bool -> unit

> Bowling.printGame [10; 10; 10; 10; 10; 10; 10; 10; 10; 10; 10; 10];;
30 60 90 120 150 180 210 240 270 300
val it : unit = ()
> Bowling.printGame [10; 9;1; 10; 9;0; 10; 8;2; 10; 10; 9;1; 9;1; 10];;
20 40 59 68 88 108 137 157 176 196
val it : unit = ()

Each element on the list represents a roll of the ball. The program will figure out which frames the rolls belong to. For example, "[9;1]" represents single frame consisting of a nine count followed by spare of the remaining pin. This implementation assumes valid input and is not designed to handle such things as more than 10 pins in a frame on a negative value for a roll.

2 comments:

Dan Lewis said...

2 questions:

1. If I had time to learn only one functional language, would you recommend F#?

2. What did you use to present your code snippet? Looks good. :)

tdalton said...

1> I would recommend F#. It's pretty pure functional language and has the added benefit on being on .NET which helps us Java guys maintain/gain proficiency on that platform.

2> The code snippet uses a Javascript library aptly named SyntaxHighlighter (http://alexgorbatchev.com/wiki/SyntaxHighlighter)