Bowling Game Spikes
Bowling Game SpikesIf you too wrote a bowling calculator after reading the ObjectMentor article (http://www.objectmentor.com/publications/xpepisode.htm), you can post it below:
Here's my ErlangLanguage one (being a wimp and just giving a total score as output :-)
-module(bowling).
-export([score/1]).
score(Throws) -> score(1, Throws).
%% score(FrameNumber, RemainingThrows) => integer() (score)
score(10, [A, B]) when A + B < 10 -> A + B;
score(10, [10, B, C]) -> 10 + B + C;
score(10, [A, B, C]) when A + B == 10 -> A + B + C;
score(F, [A, B | T]) when A + B < 10 -> A + B + score(F+1, T);
score(F, [10 | T]) -> [A, B | _] = T,
10 + A + B + score(F+1, T);
score(F, [A, B | T]) when A + B == 10 -> [C | _] = T,
10 + C + score(F+1, T).
A far less amazing one by LeoScott and WayneConrad is at http://yagni.com/cgi-bin/pywiki?BowlingScores
That one sparked Chad Fowler to issue this challenge on RubyGarden: http://www.rubygarden.org/article.php?sid=38
To answer the challenge, DaveThomas wrote his own rather amazing minimalist version, which you can see here: http://wiki.rubygarden.org/Ruby/page/show/Dave_Bowling_Solution
loop do
if (frame = s.shift) == 10 then frame += s[0] + s[1]
elsif (frame += s.shift) == 10 then frame += s[0]
end
sum += frame
end
He combined the tests that tests from the original article and the tests that Leo and Wayne wrote and made
his code pass them all.
Here's how I would do a totalizer in evil PulseLogic. A squished macro pseudocode version:
#define P(x) ((x)<0?0:1)) //returns 1 if (x) >= 0
int b[21]={1,4,4,5,6,4,5,5,10,0,1,7,3,6,4,10,2,8,6,0,0};
int t=0, bx=0;
for (int i=0; i++; i<10) {
t+=b[bx]+b[bx+1]+P(b[bx]+b[bx+1]-10)*b[bx+2];
bx+=(2-P(b[bx]-10));
}
printf("The total is: %d", t);
-- RichardHenderson.
I just read JackHarich?'s response to the ObjectMentor article (http://smile.jcon.org/soft/info/process/xp/BowlingGame.html). He made two assertions that I take issue with. First, he says that with his approach, the original design didn't change like it did for ObjectMentor. Thus his design was better. Second, he says that his code is higher quality.
The first issue is a RedHerring: the ObjectMentor came up with a design and then coded it test-first, with lots of discussion and refactoring. JackHarich? just coded his design, filling in gaps as he encountered them. It doesn't look like he tried to change his design during the coding process... so of course, it didn't change!
The quality issue is more interesting. Jack says that the ObjectMentor code "produced no artifacts and was uncommented." Later, he says, "Note the high quality of this code compared to [ObjectMentor's]."
Well... let's look at that, shall we?
ObjectMentor code:
This experiment matches my experiences: up-front design will produce working code, but it's code that's more complex than it needs to be.
A quick note about the metrics: I counted statements by hand. Only JavaLanguage statements were counted. Class, method, and variable declarations were not counted. The keyword 'else' was not counted. The 'if' and 'for' statements were counted separately from their body. (Thus, single-line 'if' statements counted as two statements.)
JackHarich?'s code includes a number of GuardCondition?s that throw RuntimeExceptions, as well as a boilerplate print() method. Since the ObjectMentor code didn't include these, I left them out of the Jack's final count.
-- JimLittle
How about this:
//Game.java----------------------------------
import java.util.*;
public class Game
{
static int MAX_POSSIBLE_THROWS = 21;
static int LAST_FRAME = 10;
static int ALL_PINS = 10;
static int MAX_THROWS_IN_FRAME = 2;
void add( int pins )
{
itsThrows[ itsTotalThrows++ ] = pins;
}
int score()
{
return scoreForFrame( LAST_FRAME );
}
int scoreForFrame( int frames )
{
int nextBall = 0;
int score = 0;
while ( nextBall < itsTotalThrows && frames-- > 0 )
{
int frameBalls = 0;
int attempts = MAX_THROWS_IN_FRAME;
while ( attempts > 0 && (( frameBalls += itsThrows[ nextBall++ ] ) < ALL_PINS ))
{
attempts--;
}
score += frameBalls;
for ( int bonus = 0; bonus < attempts; bonus++ )
{
score += itsThrows[ nextBall + bonus ];
}
}
return score;
}
int[] itsThrows = new int[ MAX_POSSIBLE_THROWS ];
int itsTotalThrows = 0;
}
This was my attempt at the bowling game in RubyLanguage. I had read the whole Java dialog, so I had some idea on the algorithm that would work.
But I tried a little experiment. Basically, I wanted to put myself in a bit of a hole when you make the complexity jump from spares to strikes. When you just have spares in your tests, then you can have an algorithm where you basically score as you go, and when you see that you've completed a frame with a spare, you just make a little note to go back and update last frame's score on the next ball. Unfortunately, the code is not shown here, but it was pretty simple and all the "spare" tests passed.
I knew, though, that the strikes would make this approach really cumbersome, so I basically had to bail out on the approach, and load up all the rolls into an array beforehand, so that I could just do a double lookahead on the strikes. It turned out to be not so bad. I basically was able to take my add() method and rename it to revisit(), then I added the array of rolls, which hadn't been there before, then I refactored the spares to use the lookahead (while on the greenbar), then I proceeded with the strikes tests.
Here is the final code:
require 'test/unit'
class Game
def initialize
@roll = []
end
def add(roll)
@roll.push(roll)
end
def revisitRoll(index, roll)
return if @currframe > 10
@pinsdown += roll
@throws += 1
if (@throws == 2 or @pinsdown == 10)
advance_frames(index)
end
end
def advance_frames(index)
@frameScore[@currframe] = @frameScore[@currframe-1] +
@pinsdown + bonus(index)
@throws = 0
@currframe += 1
@pinsdown = 0
end
def bonus(index)
bonus = 0
if @pinsdown == 10
bonus += @roll[index+1]
if @throws == 1
bonus += @roll[index+2]
end
end
bonus
end
def score(frame)
score_whole_game
@frameScore[frame]
end
def score_whole_game
@frameScore = {0 => 0}
@currframe = 1
@throws = 0
@pinsdown = 0
@roll.each_index { |index|
revisitRoll(index, @roll[index])
}
end
end
print "\n\n-------\n"
class MyTests < Test::Unit::TestCase
def testOne
game = Game.new
game.add(7)
game.add(2)
assert_equal(9, game.score(1))
end
def testTwo
game = Game.new
game.add(4)
game.add(1)
game.add(3)
game.add(0)
assert_equal(5, game.score(1))
assert_equal(8, game.score(2))
end
def testSpare
game = Game.new
game.add(4)
game.add(6)
game.add(1)
game.add(0)
assert_equal(11, game.score(1))
assert_equal(12, game.score(2))
end
def testStrike
game = Game.new
game.add(10)
game.add(0)
game.add(4)
game.add(1)
game.add(3)
assert_equal(14, game.score(1))
assert_equal(22, game.score(3))
end
def testPerfectGame
game = Game.new
12.times {
game.add(10)
}
assert_equal(300, game.score(10))
end
def testNearPerfectGame
game = Game.new
11.times {
game.add(10)
}
game.add(9)
assert_equal(299, game.score(10))
end
def testOnlyTenStrikes
game = Game.new
10.times {
game.add(10)
}
game.add(7)
game.add(10)
assert_equal(294, game.score(10))
end
end
-- SteveHowell
Here's a PythonLanguage solution that uses recursion in what I find to be a straightforward way. It wasn't the first way I thought of solving it, but I prefer it to some of the other solutions on this page because I find the logic to be easy to understand. It fits a standard pattern for recursive functions, and is fairly close to the informal way that you might explain scoring to a person. It could probably do with some more polishing, and testing.
I must admit part of what made this difficult for me is that it's not easy to find out the exact rules for scoring bowling, and I had to infer them from examples and test cases I found elsewhere on the web. Plus, being Canadian, I've mainly done 5-pin bowling, which has 3 balls per frame, and I don't even remember how to keep score for that!
pinfall = {0:0, 1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7, 8:8, 9:9, 'X':10}
def score(game):
""" Recursively calculates the score of the tail-end of a bowling game.
"""
# first three cases handle the tenth frame
n = len(game)
if n == 1:
return pinfall[game[0]]
elif n == 2:
return pinfall[game[0]] + pinfall[game[1]]
elif n == 3 and game[1] == '/':
return 10 + pinfall[game[2]]
elif n == 3:
return pinfall[game[0]] + pinfall[game[1]] + pinfall[game[2]]
elif n >= 4:
if is_digit(game[0]) and is_digit(game[1]):
return pinfall[game[0]] + pinfall[game[1]] + score(game[2:])
elif is_digit(game[0]) and game[1] == '/':
return 10 + pinfall[game[2]] + score(game[2:])
elif game[0] == 'X' and game[2] == '/': # strike, then spare
return 10 + 10 + score(game[1:])
elif game[0] == 'X': # strike not followed by spare
return 10 + pinfall[game[1]] + pinfall[game[2]] + score(game[1:])
Very nice. Yes, I think that there is a case to be made for rewriting the methods for calculating score in a functional style, given that they are pure, stateless calculation which FP is naturally good at. Hmm...I think I'll just leave a little [untested, might be totally wrong] Haskell implementation here...
scoreFrame :: Int -> [Int] -> Int
scoreFrame 0 _ = 0 -- Base case, scores of the frames *before* the start of the game are zero.
scoreFrame _ [] = 0 -- Base case, if there are no frames, the score is zero (simplifies implementations somewhat)
scoreFrame n 10:x:x':xs = (10 + x + x') + scoreFrame (n-1) (x:x':xs) -- If this is the last frame, this *won't* be called--strike is treated as a ten.
scoreFrame n 10:x:[] = (10 + x) + scoreFrame n-1 (x:[]) -- special case, correctly handles strikes into uncompleted frames.
scoreFrame n a:b:x:xs | a+b==10 = 10 + x + scoreFrame (n-1) (x:xs)
scoreFrame n a:b:xs = a + b + scoreFrame (n-1) xs
scoreFrame n a:[] = a -- special case, correctly handles uncompleted frames.
scoreFrame 10 xs = scoreFrame 11 xs -- Kludge-y special case, correctly handles the final frame
score :: [Int] -> Int
score = scoreFrame 10
EditText of this page
(last edited September 8, 2013)
or FindPage with title or text search