Coding Dojo – Bowling Score

I was in training for a couple days to start the week. Test Driven Development (TTD) with a  side of Extreme Programming (XP) to be precise. The presentation was a bit … hyperbolic. TDD w/XP was presented a the one modern way to create defect free code. I am not persuaded. 

First, creating an algorithm from test cases is more akin regression (in the curve fitting sense) than software development. By that I mean, it is not plausible to think  that given 20 or even a 1000 test cases that we will emergently discover the Fast Fourier Transform (FFT) algorithm.

Second, if we do have behavior defined well enough to be completely determined by some number of test cases, we have the behavior well enough defined to design a solution.

Thirdly, and finally, almost no non-trivial software is well suited to any pure (in the biblical sense of no sin) development strategy. That applies to Structured, OO, Functional, Actor, Reactive, etc. 

The point is, these are all tools. The best hammer in the history of carpentry isn’t going to cut that piece of plywood. Learn to use new tools? Absolutley. Master the tool? Sounds good. Know which problems are best solved with which tools? That, there, is the point where you move from apprentice to journeyman. (I postulate that being able to create tools to solve classes of problems better is where the mastery comes in).

Back to the training. We did a number of group and pair exercises, using katas from http://codingdojo.org/. One of the group katas was http://codingdojo.org/kata/Bowling/.  It was a bit frustrating, but after I read the problem, I think I see what the point was. The key parts of thinks about the problem was the constraints (which we did not review in the session):

Here are some things that the program will not do:

  • We will not check for valid rolls.
  • We will not check for correct number of rolls and frames.
  • We will not provide scores for intermediate frames.

Ah, the point I take from that was to limit pack rat behavior. Keep only the minimum amount of state / information needed to continue accurately processing the data.

I started with the test cases (in good TDD style… just because I wasn’t persuaded, didn’t mean I wasn’t going to learn and use what was presented.) Here are the test cases I eventually created. These are probably not exhaustive, and may leave some edge cases unchecked, but, ehh, this has been a drill, not a life or death process:

package com.mournival.kata.BowlingScoreTest;


import org.junit.Test;

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.util.Arrays.asList;
import static org.junit.Assert.assertEquals;

public class BowlingScoreTest {

@Test
public void testPerfect() {
List<String> rolls = IntStream.range(0, 12).mapToObj(i -> "x").collect(Collectors.toList());
assertEquals(300, BowlingScore.score(rolls));
}

@Test
public void testZeroes() {
List<String> rolls = IntStream.range(0, 20).mapToObj(i -> "0").collect(Collectors.toList());
assertEquals(0, BowlingScore.score(rolls));
}

@Test
public void testOnes() {
List<String> rolls = IntStream.range(0, 20).mapToObj(i -> "1").collect(Collectors.toList());
assertEquals(20, BowlingScore.score(rolls));
}

@Test
public void testTwos() {
List<String> rolls = IntStream.range(0, 20).mapToObj(i -> "2").collect(Collectors.toList());
assertEquals(40, BowlingScore.score(rolls));
}

@Test
public void testThrees() {
List<String> rolls = IntStream.range(0, 20).mapToObj(i -> "3").collect(Collectors.toList());
assertEquals(60, BowlingScore.score(rolls));
}

@Test
public void testFours() {
List<String> rolls = IntStream.range(0, 20).mapToObj(i -> "4").collect(Collectors.toList());
assertEquals(80, BowlingScore.score(rolls));
}

@Test
public void testFive() {
List<String> rolls = IntStream.range(0, 1).mapToObj(i -> "5").collect(Collectors.toList());
assertEquals(5, BowlingScore.score(rolls));
}

@Test
public void testSix() {
List<String> rolls = IntStream.range(0, 1).mapToObj(i -> "6").collect(Collectors.toList());
assertEquals(6, BowlingScore.score(rolls));
}

@Test
public void testSeven() {
List<String> rolls = IntStream.range(0, 1).mapToObj(i -> "7").collect(Collectors.toList());
assertEquals(7, BowlingScore.score(rolls));
}

@Test
public void testEight() {
List<String> rolls = IntStream.range(0, 1).mapToObj(i -> "8").collect(Collectors.toList());
assertEquals(8, BowlingScore.score(rolls));
}

@Test
public void testNine() {
List<String> rolls = IntStream.range(0, 1).mapToObj(i -> "9").collect(Collectors.toList());
assertEquals(9, BowlingScore.score(rolls));
}

@Test
public void spare() {
assertEquals(28, BowlingScore.score(asList("9", "/", "9")));
}

@Test
public void dutch190() {
assertEquals(190, BowlingScore.score(asList(
"9", "/", "9", "/", "9", "/", "9", "/", "9", "/",
"9", "/", "9", "/", "9", "/", "9", "/", "9", "/",
"9"
)));
}
}

Heh, just realized that when I changed to single roll (to check the string to int mapping for each roll, I left in the IntStream calls. Yuck.

Anyway, development by adding a test case, then code for each case led to this:

package com.mournival.kata.BowlingScoreTest;

import java.util.List;

public class BowlingScore {

public static int score(List<String> rolls) {

int score = 0;
int bonusRoll1 = 0;
boolean bonusRoll2 = false;
int frame = 0;

int thisRoll;
int lastRoll = 0;

for (String r : rolls) {
thisRoll = getPins(r, lastRoll);
lastRoll = thisRoll;

for (int i = 0; i < bonusRoll1; ++i) {
score += thisRoll;
}
if (bonusRoll2) {
bonusRoll1 = 1;
} else {
bonusRoll1 = 0;
}

boolean strike = isStrike(r);
boolean spare = isSpare(r);
if (strike || spare) {
++frame;
}
if (frame < 10) {
bonusRoll2 = strike;
if (bonusRoll2) {
++bonusRoll1;
}
if (spare) {
++bonusRoll1;
}
} else {
bonusRoll2 = false;
}

score += thisRoll;
}
return score;
}

private static boolean matches(String r, String x) {
return r.equalsIgnoreCase(x);
}

private static boolean isStrike(String r) {
return r.equalsIgnoreCase("X");
}

private static boolean isSpare(String r) {
return r.equalsIgnoreCase("/");
}

public static int getPins(String s, int lastRoll) {
if (matches(s, "x"))
return 10;
if (matches(s, "9"))
return 9;
if (matches(s, "8"))
return 8;
if (matches(s, "7"))
return 7;
if (matches(s, "6"))
return 6;
if (matches(s, "5"))
return 5;
if (matches(s, "4"))
return 4;
if (matches(s, "3"))
return 3;
if (matches(s, "2"))
return 2;
if (matches(s, "1"))
return 1;
if (s.equals("/")) {
return 10 - lastRoll;
}
// if (s.equals("0"))
return 0;
}

}

That is, I kept five ints and one boolean to handle the input. Note, I  DID keep track of the frames, because it is not possible to determine that if the input ends with a Strike and two rolls that are less than 10 is the last frame or the the last two frames. This messes with the bonus roll calculation. I suspect that with a stack or two, I could probably fix that, but that would add a lot of complexity and wouldn’t use less memory or save less state. 

Also, I do keep a running total (by throw), so there is some intermediate state, but I not do support array style look up of that score at a particular point. I treat the throws as an input iterator.

There is essentially no error handling / input verification (per the task descirption).

Change in Plan

I started a new job. Yay! I need to learn some different things. Yay? Ah, it is all good. I am having fun. However, the Haskell Book Club is going dormant for the time being.

In it’s place I will be doing an algorithms study, using Robert Sedgewick’s Algorithms (4ed). I have already created a Mastering Algorthms github project.

At the same time, I will be learning Angular and JavaScript / Typescript / ECMAScript. I have already completed a Pluralsight Course (through work) Angular: Getting Started.

Back to Algorithms, I spent an unexpectedly long time on ex 1.27. The idea was to convert recursive binomial probability calculation to recursive w/cached sub problems (in functional terms, memoization). I think I finally got it, but it was weird working through it. Pity I didn’t get further in Haskell / FP.