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.

Book Club : IFPuH Section 1.1

I pushed sample and exercises for section 1.1.

Here is some of what I learned, only a bit from the book:

  • Rudimentary cabal (Haskell build / package util)
  • Rudimentary HUnit (Haskell version of JUnit)
  • Rudimentary Haskell function definitions

I haven’t figured out the naming / script files yet. I feel like I should have better test names than ‘testN’. Still, I’d like to differentiate between sample code and problem set, and maybe have the section name in the test. That may allow fewer files, to the extent that the sample code / solution code remains conflict free.

Barely learned any Haskell yet, but this was productive learning the dev tools needed to build and test the projects. A fulfilling start. The most complicated Haskell was in the HUnit tests, and that was nearly all cut and paste from google searches to get the HUnit tests to compile and run. 

One thing I don’t care for regarding HUnit as run by cabal: the shell output is not what I expected.

$ cabal test

Preprocessing test suite 'tests' for funcprog-0.1.0.0..

Building test suite 'tests' for funcprog-0.1.0.0..

[2 of 2] Compiling MainTest         ( app\test\MainTest.hs, dist\build\tests\tests-tmp\MainTest.o )

Linking dist\build\tests\tests.exe …

Running 1 test suites…

Test suite tests: RUNNING…

Test suite tests: PASS

Test suite logged to: dist\test\funcprog-0.1.0.0-tests.log

1 of 1 test suites (1 of 1 test cases) passed.

The thing is, I had 13 tests cases spread across multiple test groups. To me, the (1 of 1 test cases) passed is misleading. The .log file does show the more typical xUnit runner output, so there is that.

The next most complicated bit I learned was about cabal, the Haskell build and package tool. It took a bit of work to modify the templates / samples I’d seen to match some to the directory structure and names I chose. I am not at all sure how to handle multiple libraries / modules or binaries or test suites. I suspect it will be additional stanzas or possibly nested .cabal files. I expect I’ll find out soonish.

Project Creation IFPuH

I added source, test and build info to kholvoet/funcprog-haskell.

I believe it is the first project I have created on GitHub with any kind of forethought (I searched for outlines and sample projects). In this case, I have a “Hello Haskell” program, and a trivial HUnit unit test file.

I am not quite sure how much of the deep reading of the book will be in the ghci interpreter, the app or the HUnit tests. I expect I will be using the HUnit both as test driven development (TDD) and a way to capture what I am thinking about. And prototyping in the ghci interpreter, only putting things in the app or library module as I move on.

I haven’t decided yet how many modules to create. I am tempted to do one per chapter, but that may be an unnatural partition. I will start with one, and see when / if I get the intuition that I should break things up.

Book Club – Introduction to Functional Programming using Haskell

I have decided to start learning a new language, Haskell, and to improve a neglected area of study, Functional Programming. I will be using the book Introduction to Functional Programming using Haskell (2ed)  (hereafter, IFPuH) by Richard Bird.

Why? Among other reasons, learning to think about problems in a different way. Functional programming is hip. As in old enough to be cool again. Everyone is doing it!

More seriously, one of my favorite classes was an Automated Deduction class I took at UNLV back in the mid-90’s from Dr. Minor. We used LISP and I wrote both a propositional logic and first order predicate logic prover. 

(A painful aside: Years back, but years after I completed the course, I formatted the Linux partition with my theorem provers source. I have a print out of the predicate logic prover, which may not have actually worked adequately. I recall I got less than a 90 out of 100 on it. Please, back up your work, preferably using both local and remote backups.)

I loved the style for many reasons. My undergrad degree was in Mathematics, and for a brief time I was enrolled in a Mathematics PhD program. Then I learned while I liked it, I wasn’t particularly creative at math, which is a severe defect while that kind of program. In fact, I recall complaining to my girl friend (now wife) that I did poorly on an assignment. She basically said, ‘If you’d spent as much time studying and working on the assignment as you do messing around with your computer, you’d ace it”. I responded, “But I don’t want to.” Then she asked me the key question, “Then why are you in a math program rather than computer science?” 

Anyway, currently, the practice of software development is struggling with large, distributed software. It is hard and quality isn’t much better now than before (arguably worse), though it is much prettier for the most part. One of the “new” silver bullets is the idea that immutable state makes distributed computation easier because sharing immutable state is safe. Since functional programming (in a pure form) revolves around immutability (more on that later), functional programming is now cool again. 

It also requires a very different mindset than procedural or object oriented software. That is the main thought I am chasing. Learning how to see, reason about and solve problems from a different vantage point will, in theory, help me be a better developer all around. 

Craftsmen may prefer certain tools, but the more tools they know how to use well makes completing projects easier, and increases the chance of good results while retaining all his fingers.

Hello world!

This post was auto-generated by the WordPress install. Still, since I want this to be a blog about programming, learning and building things, it seems like a useful starting point, so I’ll leave it. 

And this is where it all began: my first program in college (please forgive the scanning damage and yellowing). It is in Pascal, and run on a DEC Vax-11/780 using VMS.

My First Program, Comp Sci I, Fall, 1986