Single Frame Cleanup
Program Available: Needs Work
I suppose that every program does need work, and this little one is no exception. Before we set it down, let’s clean it up, and then review what we’ve learned this time.
My main issue with the program, as discussed last time, is that I don’t like the interface between the Game and the Frame. The Game knows too much about the Frame’s opinions of things: it asks the Frames whether they are “hungry”, sending them rolls only if they are. Why ask. Just pass the rolls, let everyone take one until they’re gone. Take a look at the relevant code:
public class BowlingGame {
Frame[] frames;
public Integer score(List<Integer> rolls) {
createFrames();
loadFrames(rolls);
Integer score = scoreFrames();
return score;
}
private void createFrames() {
frames = new Frame[10];
for(int frame = 0; frame < 10; frame++)
frames[frame] = new Frame();
}
private void loadFrames(List<Integer> rolls) {
for (Integer pins: rolls) {
boolean consumed = false;
for (Frame frame: frames) {
if (frame.isHungry()) consumed = frame.roll(pins);
if (consumed) break;
}
}
}
private Integer scoreFrames() {
Integer score = 0;
for (Frame frame : frames) {
score += frame.frameScore();
}
return score;
}
}
public class Frame {
List<Integer> rolls;
public Frame() {
rolls = new ArrayList<Integer>();
}
public boolean isHungry() {
if (rolls.size() < 2) return true;
if (mark() && rolls.size() < 3) return true;
return false;
}
private boolean mark() {
return strike() || spare();
}
private boolean spare() {
return !strike()
&& rolls.size() == 2
&& rolls.get(0)+rolls.get(1) == 10;
}
private boolean strike() {
return rolls.get(0) == 10;
}
public boolean roll(Integer pins) {
rolls.add(pins);
if (strike()) return rolls.size() == 1;
return rolls.size() <= 2;
}
public Integer frameScore() {
Integer score = 0;
for (Integer roll: rolls)
score += roll;
return score;
}
}
Basically it’s that red line there that’s bothering me. Seems simple enough to move it all inside. I can see two ways to go. One is to declare isHungry private, and fix the line to compile, then fix the tests to run. The other way is to change the code in loadFrames to work, and then fix the Frame. Much the same thing. I think I’ll do the declaring thing, since that way the compiler may help me a bit more. Declare isHungry in Frame to be private:
private boolean isHungry() {
if (rolls.size() < 2) return true;
if (mark() && rolls.size() < 3) return true;
return false;
}
As soon as I do that, the compiler warns me that it’s never used locally. No surprise. In the Game, we have a reference now that won’t compile, so we’ll change that, in two steps. First make it work, then make it right. The if frame is hungry line won’t compile, so we’ll just remove that bit:
private void loadFrames(List<Integer> rolls) {
for (Integer pins: rolls) {
boolean consumed = false;
for (Frame frame: frames) {
consumed = frame.roll(pins);
if (consumed) break;
}
}
}
I expect the tests to fail … oops … there are lots of calls to isHungry in the Frame test. I’d kind of like to leave those working. I think for now I’ll make isHungry public again, which means I could have guessed at the code above. Live and learn. The tests literally explode.1
The fix is to make roll return false, without doing anything, if the frame is not hungry:
public boolean roll(Integer pins) {
if (!isHungry()) return false;
rolls.add(pins);
if (strike()) return rolls.size() == 1;
return rolls.size() <= 2;
}
Now some minor cleanup to the loadFrames:
private void loadFrames(List<Integer> rolls) {
for (Integer pins: rolls) {
for (Frame frame: frames) {
if (frame.roll(pins)) break;
}
}
}
Basically we just inlined the call to roll. I’m still a bit troubled by the fact that roll has a boolean return value, but I don’t see a better way to code it. Maybe a better name would help? I’m sure the cards and letters will come pouring in.
For now, my last big objection to the code has been resolved. One more quick look … I decide to inline the returning of the score from score():
public Integer score(List<Integer> rolls) {
createFrames();
loadFrames(rolls);
return scoreFrames();
}
Other than that, the code looks good enough to me. I wish I had a pair looking at this with me, but Chet is busy trying to figure out Hibernate. Better him than me. I’m calling this done. Let’s sum up.
What Have We Learned?
Well, we’ve probably learned different things. Here are some suggestions:
This silly little exercise of bowling continues to be a valuable etude. Since the problem is so well known (to me at least), it lets me relax and look at the code and see what it’s telling me. When I’m working on something new, I have to concentrate so hard on the new bits that it’s hard to think as well about all the coding details. An occasional run through the bowling game keeps those understandings sharp. At least that’s my theory …
The recursive solution just kind of evaporated along the way. Did you notice it turning into smoke and disappearing? I think there’s a reason for that: the problem really isn’t one where recursion is the best tool, owing to the need to process ten Frames, no more and no less. So far as my correspondents and I can determine, there is no recursive solution that just stops based on the data coming to an end: all the working solutions basically count up to or down from ten. When you have to do something ten times, you’re looking at iteration. I think it’s appropriate to face that fact.
Creating the Frame object early on, and testing it directly, resulted in an object that didn’t work as well as it might have from the viewpoint of the using object, the Game. It seems to me that this casts a bit of suspicion on the common notion of building objects in isolation, perhaps with mocks. On the other hand, a mock-based solution might not have run into the same issues as this simpler test-driven one. I consider the case against isolation and mocks to be “not proven”, the old Scottish alternative to “not guilty”.
Cards and Letters
I love it when people read these articles and take time to reply. I generally try to reply directly, but often like to mention interesting emails here. Here are a couple:
Ronald Mai
Ronald writes that the Haskell solutions we’ve seen so far aren’t mind-blowing enough, and proposes something like this:
parseFrames r = take 10 $ tail $ iterate (parseOneFrame . snd) (0,r)
{- parse one frame and return a tuple: (score of the parsed frame,
the rest of the rolls need to be parsed) -}
where parseOneFrame r | r!!0 == 10 = (r!!0 + r!!1 + r!!2, drop 1 r)
| r!!0 + r!!1 == 10 = (r!!0 + r!!1 + r!!2, drop 2 r)
| r!!0 + r!!1 < 10 = (r!!0 + r!!1, drop 2 r)
gameScore = (foldr (+) 0) . frameScores
where frameScores = (map fst) . parseFrames
main = print $ gameScore $ replicate 20 10
Now that’s tight … and it appears to work, though Ronald only tested it on one example. I thought you might find that one interesting. In my opinion, it’s almost readable even by someone (like me) who doesn’t know Haskell.
Stephen Royce
Stephen and I have exchanged a few emails. He summarizes his observations this way:
... even though it was clear how the recursive programme worked, it was far from clear whether or not it would work for all circumstances and I did feel uneasy about that. As it turned that hint of suspicion proved to be justified. Furthermore, what was abundantly clear was that it would not work if you did not have a "proper"game of bowling, i.e. one consisting of exactly 10 frames; you could have entered 100 scores and it would keep on calculating. Even though your actual bowling game problem may state that you can assume you only get a "full" game - 10 frames, nothing more, nothing less - and that you won't get invalid scores - < 0 or > 10 - I think that the fact that the Haskell programme would continue to calculate the score until it got to the end of the list is indicative of the major concern with recursive programming: it's challenging to handle boundary conditions in a meaningful and clearly understood manner. So even though the Haskell solution looks elegant and the amount of code is fantastically short, I would suggest that recursive programming only be used where the problem being solved is inherently recursive. The bowling game is - in my opinion, anyway - a serial problem, not a recursive one and is best resolved serially. Personally, if I was doing this from scratch, I be tempted to first convert the data to 10 frames and then calculate the score; I wouldn't even bother with objects, I'd just do it procedurally. This may not be the most elegant solution, but it does allow you to "clean" the data first and clearly identify what you're dealing with before you actually attempt to do the maths. Incidentally, I only partially agree with you about how we think of a bowling game. Whilst I'm actually playing it, I could agree with you that it simply series of scores. But if I were to describe the game to someone else or to think about it for myself from the "outside", I would say that it consists of 10 "goes" of up to 2 "shots" each to knock down 10 pins (each time). The scoring for strikes and spares and their implication for potential extra "shots" in the 10th frame are, to me, ancillary to the actual main concept of the game - although, of course, not to working out who won! All of which serves to only highlight the most fundamental thing: we all think slightly differently about everything and so formalising that thinking with mathematical rigour is incredibly difficult; at least, it is if you want someone else to be able to understand later what you were trying to achieve earlier!
Donald’s observations may be better than mine, though I still have the basic feeling that recursion is a bit harder to manage intellectually than iteration, except in the very simplest cases – and perhaps in cases that basically translate back to iteration. Note that we have seen some solutions here where the Haskell programmers implemented iteration using a recursive approach. I think for that, I’ll take the good old for and foreach statements.
Summary Remarks
It seems to me that we’ve milked the Haskell horse enough, or whipped the Haskell cow, whichever it was. The Java version that I wrote echoing the Haskell solution morphed fairly easily and almost invisibly into a version that actually worked, using iteration.
It’s unfortunate that Dan didn’t have the time to put into making his version work … I suspect that he, and we, might have drawn some interesting conclusions. But the general consensus seems to be that a purely recursive solution (i.e. one that just consumes the list, without a separate iteration variable) cannot be made to work. Perhaps someone will take on the problem and create one, but Pit Capitain’s examples of games all ending 10, 2, 3 but with different results, makes me think it’s not going to happen. Perhaps I should offer a prize. Pizza at Zukey Lake Tavern, perhaps (but you have to pick up your own travel expenses).
I remain fascinated by how much richness can be found in this little finger exercise that I do so often. There are at least a few fundamentally different solutions, ranging from very procedural to solutions just chock full of yummy objects. Additionally, there’s a definite aspect of language-dependent style that comes out: Ruby solutions look different from Java solutions. I suspect that there are even some significant differences between Java and C# solutions, if we’d look. I’m sure there will be significant differences there for larger programs, considering the existence of delegates, not to mention ASP vs JSP. Perhaps we’ll put that on the agenda for a look later on: over on the other side of the table here at the Brighton Borders store, Chet is beavering away working on a JSP application using Hibernate. After he gets it working, maybe we’ll write about that.
For now, thanks for looking at the Haskell, and Haskell-driven ideas, and thanks especially to those who wrote to me with their ideas. Oh, and welcome to my new computer. It seems to be about ten times faster than the old one. See you next time!
- Inside joke. Chet and I like to make fun of people who misuse “literally”. No, we really do. Literally.