Test Driven Development Tutorial Roman Numerals (Last Edit: Mar 15 2004 22:54:55)
RecentChanges Edit Search GoodStyle
Referenced By: TutorialRomanNumerals

This tutorial generates a Ruby function to convert any low natural number into a Roman Numeral.

Writing the tutorial caused a couple false starts. TDD is no perfect algorithm generator. Like all hill-climbing algorithms, starting with the wrong abstraction can often make the right one harder, not easier, to climb to. I had to start three times, each time solving "II" a different way, before the algorithm clicked in.

The code to pass the test must be the simplest possible, but the refactoring, after the test passes, must then be very aggressive.

The refactoring here leveraged two simple rules: Make things look similar, then put them next to each other, then make them the same. That practice forms little tables, which eventually become real source tables.

Following those rules as closely as possible allowed a better algorithm to emerge.

The tutorial methods are brief enough that <Page Down> should provide an animation of the code squirming around.



The first test:

    require 'test/unit'
    require 'roman.rb'

    class TestRomanNumerals < Test::Unit::TestCase
        def test_romanNumerals()
            assert_equal('I',    roman(1))

        end
	end


The code to pass this test:
	def roman(num)
		return 'I'
	end



The second test:
            assert_equal('I',    roman(1))
            assert_equal('II',   roman(2))

	def roman(num)
		return 'II'  if num == 2
		return 'I'
	end


Now refactor to cure the duplicated I:
	def roman(num)
		return ''  if num == 0
		return 'I' + roman(num - 1)
	end



Test 3:
            assert_equal('I',    roman(1))
            assert_equal('II',   roman(2))
            assert_equal('III',  roman(3))
That passes.
Test 4:
            assert_equal('I',    roman(1))
            assert_equal('II',   roman(2))
            assert_equal('III',  roman(3))
            assert_equal('IV',   roman(4))


	def roman(num)
		return ''  if num == 0
		return 'IV'  if num == 4
		return 'I' + roman(num - 1)
	end


Refactor to merge I again:
	def roman(num)
		return ''  if num == 0
		return roman(1) + 'V'  if num == 4
		return 'I' + roman(num - 1)
	end

The two lines that call roman() recursively are beginning to look suspiciously similar.
Test 5:
            assert_equal('I',    roman(1))
            assert_equal('II',   roman(2))
            assert_equal('III',  roman(3))
            assert_equal('IV',   roman(4))
            assert_equal('V',    roman(5))
The fake implementation:
	def roman(num)
		return ''  if num == 0
		return 'V'  if num == 5
		return roman(1) + 'V'  if num == 4
		return 'I' + roman(num - 1)
	end

Now refactor to merge the V:
	def roman(num)
		return ''  if num == 0
		return 'V'  if num == 5
		return roman(1) + roman(5)  if num == 4
		return 'I' + roman(num - 1)
	end


Test 6:
            assert_equal('I',    roman(1))
            assert_equal('II',   roman(2))
            assert_equal('III',  roman(3))
            assert_equal('IV',   roman(4))
            assert_equal('V',    roman(5))
            assert_equal('VI',   roman(6))
The fake implementation:
	def roman(num)
		return ''  if num == 0
		return 'V'  if num == 5
		return 'VI'  if num == 6
		return roman(1) + roman(5)  if num == 4
		return 'I' + roman(num - 1)
	end

Refactor to merge V again:
	def roman(num)
		return ''  if num == 0
		return 'V'  if num == 5
		return roman(5) + roman(1)  if num == 6
		return roman(1) + roman(5)  if num == 4
		return 'I' + roman(num - 1)
	end

That code duplicates some magic numbers. Begin to merge them, to show what's really going on:
	def roman(num)
		return ''  if num == 0
		return 'V'  if num == 5
		return roman(5) + roman(num - 5)  if num >= 6
		return roman(1) + roman(5)  if num == 4
		return 'I' + roman(num - 1)
	end

All those magic numbers have a hidden 5 duplicated inside them. Tease it out:
	def roman(num)
		return ''  if num == 0
		return 'V'  if num == 5
		return roman(5) + roman(num - 5)  if num >= 6
		return roman(1) + roman(num + 1)  if num == 4
		return 'I' + roman(num - 1)
	end

Find more 5s:
	def roman(num)
		return ''  if num == 0
		return 'V'  if num == 5
		return roman(5) + roman(num - 5)  if num >= 5 + 1
		return roman(1) + roman(num + 1)  if num == 5 - 1
		return 'I' + roman(num - 1)
	end

Make the return 'I' more similar to the return 5:
	def roman(num)
		return ''  if num == 0
		return 'I'  if num == 1
		return 'V'  if num == 5
		return roman(5) + roman(num - 5)  if num >= 5 + 1
		return roman(1) + roman(num + 1)  if num == 5 - 1
		return roman(1) + roman(num - 1)
	end

Make the last line more similar to the others:
	def roman(num)
		return ''  if num == 0
		return 'I'  if num == 1
		return 'V'  if num == 5
		return roman(5) + roman(num - 5)  if num >= 5 + 1
		return roman(1) + roman(num + 1)  if num == 5 - 1
		return roman(1) + roman(num - 1)  if num >= 1 + 1
	end

Finally pull out a table of target symbols. Also, merge duplication between the statements that sample 5 and those that sample 1:
	Symbols = { 1=>'I', 5=>'V' }

	def roman(num)
		return Symbols[num]  if Symbols.has_key?(num)

		[5, 1].each do |cutPoint|
			return roman(cutPoint) + roman(num - cutPoint)  if num >= cutPoint + 1
			return roman(cutPoint - num) + roman(num + 1)  if num == cutPoint - 1
		end
	end


Test 7 and 8:
            assert_equal('I',    roman(1))
            assert_equal('II',   roman(2))
            assert_equal('III',  roman(3))
            assert_equal('IV',   roman(4))
            assert_equal('V',    roman(5))
            assert_equal('VI',   roman(6))
            assert_equal('VII',  roman(7))
            assert_equal('VIII', roman(8))
These work. The current abstraction is holding firm.
Test 9:
            assert_equal('I',    roman(1))
            assert_equal('II',   roman(2))
            assert_equal('III',  roman(3))
            assert_equal('IV',   roman(4))
            assert_equal('V',    roman(5))
            assert_equal('VI',   roman(6))
            assert_equal('VII',  roman(7))
            assert_equal('VIII', roman(8))
            assert_equal('IX',   roman(9))
That requires the X symbol. First get the tests pass, by adding a fake implementation for 9:
	Symbols = { 1=>'I', 5=>'V' }

	def roman(num)
		return 'IX'  if num == 9
		return Symbols[num]  if Symbols.has_key?(num)

		[5, 1].each do |cutPoint|
			return roman(cutPoint) + roman(num - cutPoint)  if num > cutPoint
			return roman(cutPoint - num) + roman(num + 1)  if num == cutPoint - 1
		end
	end
Now that tests pass, refactoring is safe. Move the 10 into the symbol table, and the list of cutpoints:
	Symbols = { 1=>'I', 5=>'V', 10=>'X' }

	def roman(num)
		return Symbols[num]  if Symbols.has_key?(num)

		[10, 5, 1].each do |cutPoint|
			return roman(cutPoint) + roman(num - cutPoint)  if num >  cutPoint
			return roman(cutPoint - num) + roman(num + 1)   if num == cutPoint - 1
		end
	end


Test 10 to 19:
            assert_equal('I',    roman(1))
            assert_equal('II',   roman(2))
            assert_equal('III',  roman(3))
            assert_equal('IV',   roman(4))
            assert_equal('V',    roman(5))
            assert_equal('VI',   roman(6))
            assert_equal('VII',  roman(7))
            assert_equal('VIII', roman(8))
            assert_equal('IX',   roman(9))
            assert_equal('X',    roman(10))
            assert_equal('XI',   roman(11))
            assert_equal('XII',  roman(12))
            assert_equal('XIII', roman(13))
            assert_equal('XIV',  roman(14))
            assert_equal('XV',   roman(15))
            assert_equal('XVI',  roman(16))
            assert_equal('XVII', roman(17))
            assert_equal('XVIII', roman(18))
            assert_equal('XIX',  roman(19))
These all work. Our code is beginning to show Wiki:OpenClosedPrinciple - we extend it the way it designs to extend. Not by changing its statements.
Refactor the test, to make adding tests easier:
        def test_romanNumerals()
   	    resource = [ 
		    ['I',     1], ['II',     2], ['III',   3], ['IV',    4],
		    ['V',     5], ['VI',     6], ['VII',   7], ['VIII',  8],
		    ['IX',    9], ['X',     10], ['XI',   11], ['XII',  12],
		    ['XIII', 13], ['XIV',   14], ['XV',   15], ['XVI',  16],
		    ['XVII', 17], ['XVIII', 18], ['XIX',  19], ['XX',   20],
		    ]
	    resource.each do |expect, input|
		    assert_equal(expect, roman(input))
		    end

        end

Add more tests until 40 breaks - because we don't do L yet:
   	    resource = [ 
		    ['I',      1], ['II',     2], ['III',    3], ['IV',     4],
		    ['V',      5], ['VI',     6], ['VII',    7], ['VIII',   8],
		    ['IX',     9], ['X',     10], ['XI',    11], ['XII',   12],
		    ['XIII',  13], ['XIV',   14], ['XV',    15], ['XVI',   16],
		    ['XVII',  17], ['XVIII', 18], ['XIX',   19], ['XX',    20],
		    ['XXI',   21], ['XXIII', 23], ['XXIV',  24], ['XXV',   25],
		    ['XXIX',  29], ['XXX',   30], ['XXXIV', 34], ['XXXVI', 36],
		    ['XXXIX', 39], ['XL',    40],
		    ]
	    resource.each do |expect, input|
		    assert_equal(expect, roman(input))
		    end
That failed, as expected, so Fake it till we Make it:
	Symbols = { 1=>'I', 5=>'V', 10=>'X' }

	def roman(num)
		return 'XL'  if num == 40
		return Symbols[num]  if Symbols.has_key?(num)

		[50, 10, 5, 1].each do |cutPoint|
			return roman(cutPoint) + roman(num - cutPoint)  if num >  cutPoint
			return roman(cutPoint - num) + roman(num + 1)   if num == cutPoint - 1
		end
	end

The current code assumes a "subtractor" of I. But Romans permit X and C to subtract. So add the subtractor to the table of cutpoints:
	Symbols = { 1=>'I', 5=>'V', 10=>'X', 50=>'L' }

	def roman(num)
		return Symbols[num]  if Symbols.has_key?(num)

		[[50,10], [10,1], [5,1], [1,0]].each do |cutPoint, subtractor|
			return roman(cutPoint) + roman(num - cutPoint)          if num >  cutPoint
			return roman(cutPoint - num) + roman(num + subtractor)  if num == cutPoint - subtractor
		end
	end

And reformat for clarity:
	Symbols = { 
		 1=>'I', 
		 5=>'V', 
		10=>'X', 
		50=>'L',
		}

	def roman(num)
		return Symbols[num]  if Symbols.has_key?(num)

		[ [50, 10], 
		  [10,  1], 
		  [ 5,  1], 
		  [ 1,  0],
			  ].each do |cutPoint, subtractor|
			return roman(cutPoint)       + roman(num - cutPoint)    if num >  cutPoint
			return roman(cutPoint - num) + roman(num + subtractor)  if num == cutPoint - subtractor
		end
	end


Add more passing tests, sneaking up on 90:
   	    resource = [ 
		    ['I',      1], ['II',     2], ['III',    3], ['IV',      4],
		    ['V',      5], ['VI',     6], ['VII',    7], ['VIII',    8],
		    ['IX',     9], ['X',     10], ['XI',    11], ['XII',    12],
		    ['XIII',  13], ['XIV',   14], ['XV',    15], ['XVI',    16],
		    ['XVII',  17], ['XVIII', 18], ['XIX',   19], ['XX',     20],
		    ['XXI',   21], ['XXIII', 23], ['XXIV',  24], ['XXV',    25],
		    ['XXIX',  29], ['XXX',   30], ['XXXIV', 34], ['XXXVI',  36],
		    ['XXXIX', 39], ['XL',    40], ['L',     50], ['LIV',    54],
		    ['LVIII', 58], ['LIX',   59], ['LXXVI', 76], ['LXXXIX', 89],
		    ]
	    resource.each do |expect, input|
		    assert_equal(expect, roman(input))
		    end

Test 90:
   	    resource = [ 
		    ['I',      1], ['II',     2], ['III',    3], ['IV',      4],
		    ['V',      5], ['VI',     6], ['VII',    7], ['VIII',    8],
		    ['IX',     9], ['X',     10], ['XI',    11], ['XII',    12],
		    ['XIII',  13], ['XIV',   14], ['XV',    15], ['XVI',    16],
		    ['XVII',  17], ['XVIII', 18], ['XIX',   19], ['XX',     20],
		    ['XXI',   21], ['XXIII', 23], ['XXIV',  24], ['XXV',    25],
		    ['XXIX',  29], ['XXX',   30], ['XXXIV', 34], ['XXXVI',  36],
		    ['XXXIX', 39], ['XL',    40], ['L',     50], ['LIV',    54],
		    ['LVIII', 58], ['LIX',   59], ['LXXVI', 76], ['LXXXIX', 89],
		    ['XC',    90],
		    ]
	    resource.each do |expect, input|
		    assert_equal(expect, roman(input))
		    end
Add a fake implementation:
	Symbols = { 
		 1=>'I', 
		 5=>'V', 
		10=>'X', 
		50=>'L',
		}

	def roman(num)
		return 'XC'  if num == 90
		return Symbols[num]  if Symbols.has_key?(num)

		[ [50, 10], 
		  [10,  1], 
		  [ 5,  1], 
		  [ 1,  0],
			  ].each do |cutPoint, subtractor|
			return roman(cutPoint) + roman(num - cutPoint)          if num >  cutPoint
			return roman(cutPoint - num) + roman(num + subtractor)  if num == cutPoint - subtractor
		end
	end

Now refactor to extend the abstraction again:
	Symbols = { 
		  1=>'I', 
		  5=>'V', 
		 10=>'X', 
		 50=>'L',
		100=>'C',
		}

	def roman(num)
		return Symbols[num]  if Symbols.has_key?(num)

		[ [100, 10], 
		  [ 50, 10], 
		  [ 10,  1], 
		  [  5,  1], 
		  [  1,  0],
			  ].each do |cutPoint, subtractor|
			return roman(cutPoint) + roman(num - cutPoint)          if num >  cutPoint
			return roman(cutPoint - num) + roman(num + subtractor)  if num == cutPoint - subtractor
		end
	end


Test 94:
   	    resource = [ 
		    ['I',      1], ['II',     2], ['III',    3], ['IV',      4],
		    ['V',      5], ['VI',     6], ['VII',    7], ['VIII',    8],
		    ['IX',     9], ['X',     10], ['XI',    11], ['XII',    12],
		    ['XIII',  13], ['XIV',   14], ['XV',    15], ['XVI',    16],
		    ['XVII',  17], ['XVIII', 18], ['XIX',   19], ['XX',     20],
		    ['XXI',   21], ['XXIII', 23], ['XXIV',  24], ['XXV',    25],
		    ['XXIX',  29], ['XXX',   30], ['XXXIV', 34], ['XXXVI',  36],
		    ['XXXIX', 39], ['XL',    40], ['L',     50], ['LIV',    54],
		    ['LVIII', 58], ['LIX',   59], ['LXXVI', 76], ['LXXXIX', 89],
		    ['XC',    90], ['XCIV',  94], 
		    ]
	    resource.each do |expect, input|
		    assert_equal(expect, roman(input))
		    end
That forced out a bug:
	Symbols = { 
		  1=>'I', 
		  5=>'V', 
		 10=>'X', 
		 50=>'L',
		100=>'C',
		}

	def roman(num)
		return Symbols[num]  if Symbols.has_key?(num)

		[ [100, 10], 
		  [ 50, 10], 
		  [ 10,  1], 
		  [  5,  1], 
		  [  1,  0],
			  ].each do |cutPoint, subtractor|
			return roman(cutPoint) + roman(num - cutPoint)      if num >  cutPoint
			return roman(subtractor) + roman(num + subtractor)  if num >= cutPoint - subtractor and num < cutPoint
		end
	end

The bug (introduced very early) was the lower left call to roman() should not have called roman(cutPoint - num). Adding C to the system exposed the bug,

because I forgot to test 44 before.
Test 99:
   	    resource = [ 
		    ['I',      1], ['II',     2], ['III',    3], ['IV',      4],
		    ['V',      5], ['VI',     6], ['VII',    7], ['VIII',    8],
		    ['IX',     9], ['X',     10], ['XI',    11], ['XII',    12],
		    ['XIII',  13], ['XIV',   14], ['XV',    15], ['XVI',    16],
		    ['XVII',  17], ['XVIII', 18], ['XIX',   19], ['XX',     20],
		    ['XXI',   21], ['XXIII', 23], ['XXIV',  24], ['XXV',    25],
		    ['XXIX',  29], ['XXX',   30], ['XXXIV', 34], ['XXXVI',  36],
		    ['XXXIX', 39], ['XL',    40], ['L',     50], ['LIV',    54],
		    ['LVIII', 58], ['LIX',   59], ['LXXVI', 76], ['LXXXIX', 89],
		    ['XC',    90], ['XCIV', 94],  ['XCVIII', 98], ['IC', 99], 
		    ]
	    resource.each do |expect, input|
		    assert_equal(expect, roman(input))
		    end
That extends the existing abstraction:
	Symbols = { 
		  1=>'I', 
		  5=>'V', 
		 10=>'X', 
		 50=>'L',
		100=>'C',
		}

	def roman(num)
		return Symbols[num]  if Symbols.has_key?(num)

		[ [100,  1], 
		  [100, 10], 
		  [ 50, 10], 
		  [ 10,  1], 
		  [  5,  1], 
		  [  1,  0],
			  ].each do |cutPoint, subtractor|
			return roman(cutPoint) + roman(num - cutPoint)      if num >  cutPoint
			return roman(subtractor) + roman(num + subtractor)  if num >= cutPoint - subtractor and num < cutPoint
		end
	end


Because we forced out a bug, and showed many boundary situations, even though the existing implementation is incomplete, we have confidence that its abstraction is robust. The existing code might not translate 49 to IL, but - because we watched the design grow and now understand it, we are confident we can add [50, 1] to one of the tables. Similarily, we know we can add D and M to the system without changing it.

In conclusion, we used relentless change to create an abstraction that is now resistant to change.

--PhlIp



Epilog: An e-colleague read the tests and noticed the specs are wrong. The code I cannot subtract C. The fix is to comment out the rule that permits I to subtract C, #[100, 1], and change the test to ['XLIX', 99].


[[[??? 99 is XCIX, I think. ]]]