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. ]]]