Sudoku Solver in Scala Part 3: Generating cross-dependent test data

This is the last part of my learnings during writing a sudoku solver. It's about several iterations of a property-based test refactoring in an attempt to find the best way to generate input data.

Previous parts:

  1. Injecting validation into the type system
  2. Writing functions instead of methods

What are property-based tests

The difference between usual tests and property-based tests is that you don't manually create function input and then compare output with expected one. Instead you run a test many times with a lot of different pseudorandom input data and check some properties of your implementation that should hold for all inputs. With this approach you cover much more use cases so it's better to stick to property-based tests when possible.

In this case we use the ScalaTest+ScalaCheck combination to run property-based tests.

Our test

Our grid model disallows obviously wrong states. Once you filled a cell with any digit you can't fill the same value in a cell in the same row, column or box. We want this feature to be tested. But also we want this feature to have a right scope: filling any digit should not affect allowance of filling other values. This specific test checks that if you have one digit on the grid, you can still fill another digit in the same column.

To do this we need 5 digits as input: coordinates of first cell, two cell values and one digit for row coordinates of second cell.

All we need to create this test is to define a digit generator. Everything will look kinda like this:

val digitGen: Gen[Digit] = Gen.oneOf(allDigits)

it should "allow setting another digit in same column" in {
    forAll(digitGen, digitGen, digitGen, digitGen, digitGen) {
        (value1: Digit, value2: Digit, row1: Digit, row2: Digit, col: Digit) => {
            val grid = createGrid(rowCol(row1, col) -> value1)
            assert(grid.set(rowCol(row2, col), value2).isDefined)
        }
    }
}

In this case we had to define inputs twice: first time as a list of generators, second time as a list of input parameters. Can we make this better? Yes because ScalaCheck uses the Type Class pattern.

You can define an implicit arbitrary generator for a type to define which generator to pick automatically when you need an input of a specific type.

If we define an arbitrary generator for a Digit type we don't need to provide generators anymore so we need to define input list once and ScalaCheck will find out which data to provide.

val digitGen: Gen[Digit] = Gen.oneOf(allDigits)
implicit def digitAGen: Arbitrary[Digit] = Arbitrary(digitGen)

it should "allow setting another digit in same column" in {
    forAll {
        (value1: Digit, value2: Digit, row1: Digit, row2: Digit, col: Digit) => {
            val grid = createGrid(rowCol(row1, col) -> value1)
            assert(grid.set(rowCol(row2, col), value2).isDefined)
        }
    }
}

Looks much better but if we run this test it will fail. Random input parameters mean we can get same cell values or same row numbers for both cells and we won't be able to fill a second cell.

First I solved it by deliberately ignoring such cases via assert(value1 == value2 || row1 == row2 || ???). This can be done with same logic but in a prettier way using whenever clause:

it should "allow setting another digit in same column" in {
    forAll {
        (value1: Digit, value2: Digit, row1: Digit, row2: Digit, col: Digit) => {
            whenever(value1 != value2 && row1 != row2) {
                val grid = createGrid(rowCol(row1, col) -> value1)
                assert(grid.set(rowCol(row2, col), value2).isDefined)
            }
        }
    }
}

Still this means we have useless iterations when we generate a set of input data and discard it. Not cool. Would be much better to generate input data that's always valid.

This can be achieved by dynamically creating a generator for second digit depending on first digit. Something like "any digit except this one".

New plan is: sequentially run generators, combine results into a tuple and pass this tuple to a test.

val digitGen: Gen[Digit] = Gen.oneOf(allDigits)
def digitExcept(exceptions: Digit*): Gen[Digit] = Gen.oneOf(allDigits.toSet -- exceptions)

it should "allow setting another digit in same column" in {
    forAll(for {
        value1 <- digitGen
        value2 <- digitExcept(value1)
        row1 <- digitGen
        row2 <- digitExcept(row1)
        col <- digitGen
    } yield (value1, value2, row1, row2, col) ) {
        case (value1, value2, row1, row2, col) => {
            val grid = createGrid(rowCol(row1, col) -> value1)
            assert(grid.set(rowCol(row2, col), value2).isDefined)
        }
    }
}

It works nice but it looks even worse than the first version. Now we define every parameter three times. We can't use arbitrary generators anymore because they are independent and we want to generate dependent data.

But this is valid only when we look at the data in the same scope we use it in application logic. We cannot generate two digits assuming they are different but we can generate a tuple of two different digits. The only problem with tuple is it's not telling us anything about relation of digits within. It can be avoided by creating a case class with a very explicit name. Something like TwoDifferentDigits. Then we can create an arbitrary generator for this class.

case class TwoDifferentDigits(a: Digit, b: Digit)

val digitGen: Gen[Digit] = Gen.oneOf(allDigits)
implicit def digitAGen: Arbitrary[Digit] = Arbitrary(digitGen)

def digitExcept(exceptions: Digit*): Gen[Digit] = Gen.oneOf(allDigits.toSet -- exceptions)
implicit def twoDifferentDigitsAGen: Arbitrary[TwoDifferentDigits] = Arbitrary(for {
    a <- digitGen
    b <- digitExcept(a)
} yield TwoDifferentDigits(a, b))


it should "allow setting another digit in same column" in {
    forAll {
        (values: TwoDifferentDigits, rows: TwoDifferentDigits, col: Digit) => {
            val grid = createGrid(rowCol(rows.a, col) -> values.a)
            assert(grid.set(rowCol(rows.b, col), values.b).isDefined)
        }
    }
}

Often we need the same combinations of inputs in different tests so it's worth wrapping input data into classes because they will be reused.

Summary

The latest version of the test was an insight for me. I'm getting used to the idea that you can encapsulate assumptions within a data type (see part 1) but for some reason, I didn't think of doing that for tests before. But it works nicely to combine multiple generated values into a class and to have an arbitrary generator for it. Even if this class will be used only in tests. So when you write a generator depending on another one ask yourself, maybe you should be writing a class instead.

Tags: , , ,


Comments