testing a random die roll

What tests would I write? Maybe I'd start by testing it only rolls 1 to 6
def test_doesnt_roll_less_than_1_or_greater_than_6
  1200.times do
    die = roll_die
    assert 1 <= die && die <= 6
  end
end
That's a good start. But it's not nearly enough. One way to think about testing is to imagine someone is deliberately writing the code so that it passes the tests but is nevertheless completely incorrect. Take, for example, sorting an array of N integers. What tests would you write? Now suppose I tell you the incorrect implementation simply returns an array of N 42's. Are you testing the output array is a permutation of the input array?

Back to rolling the die... an implementation of roll_die() which always returned 3 would pass my first test. I need to test all of 1-6 get returned.
def test_rolls_1_to_6_at_least_once_each_in_600_rolls
  rolls = [-1,0,0,0,0,0,0]
  600.times do
    die = roll_die
    rolls[die] += 1
  end
  assert rolls[1] >= 1
  assert rolls[2] >= 1
  assert rolls[3] >= 1
  assert rolls[4] >= 1
  assert rolls[5] >= 1
  assert rolls[6] >= 1
end
Why 600 rolls? You might be thinking it's too large. That a decent roll_die() should return at least one each of 1-6 after a lot fewer than 600 rolls. Or, to put it another way, if I have to wait till the 600th roll to get my first 5 then roll_die() is looking a bit suspect. Fair enough.

The tests form a specification. If I want to specify a "tighter" implementation of roll_die() I can simply change 600 to, 200 say. The 200 is then part of the specification.

Once again, it's easy to imagine an incorrect implementation that passes all the tests. How about one that simply cycles repeatedly through 1-6...
$n = 1

def roll_die
  $n += 1
  $n %= 6
  $n + 1
end
I've tested the "die" part of "random die". I've got to the "random" part of "random die". My incorrect implementation is not very random. It's very regular. It's very ordered. Suppose I call roll_die() 1200 times, save the 1200 values in a file, and then compress the file. I should get a lot of compression. Let's try it…
dice = ""
1200.times { dice += roll_die.to_s }
File.open('dice.txt', 'w') { |f| f.write(dice) }
unzipped_size = File.size('dice.txt')
assert_equal 1200, unzipped_size
`zip dice.txt.zip dice.txt`
zipped_size = File.size('dice.txt.zip')
p zipped_size
On my macbook I get a value of 184. As expected, a lot of compression. Let's compare the compression to an implementation that isn't deliberately incorrect.
def roll_die
  [1,2,3,4,5,6].shuffle[0]
end
This gives a zipped file size of around 680. A lot less compression. I can use that as part of the specification.
def test_roll_is_random_entropically
  dice = ""
  1200.times { dice += roll_die().to_s }
  File.open('dice.txt', 'w') { |f| f.write(dice) }
  unzipped_size = File.size('dice.txt')
  assert_equal 1200, unzipped_size
  `zip dice.txt.zip dice.txt`
  zipped_size = File.size('dice.txt.zip')
  assert zipped_size > 600
end
Imagine someone is deliberately writing the code so that it passes the tests but is nevertheless completely incorrect…


2 comments:

  1. How about testing for the maximum length of a sequence of the same number? That should occur as often as any other sequence of the same length, though a fake program may have been written by someone who didn't take that into account.

    ReplyDelete
  2. I'm sure there are hundreds of tests that look at some aspect of randomness! The main point I wanted to get across was the idea of imagining writing the code incorrectly but so it still passes the tests.

    ReplyDelete