Last week: Roman Numerals
I liked that kata. I started with different approaches that did not work and found a simple one in the end, aided by the tests.
My first tries ended at something like this:
Expected :'IX'
Actual :'VIV'
As soon as it occured to me to treat “IV”, “IX” and so on as single digits, it was dead simple.
When I implemented the reverse, I noticed that it would be easier to check for two character “digits” like “IV” first, then for single characters. Instead of using the same list of (arabic,roman) tupels for both tasks, I decided to explicitly write both as constants $romanDigitsByValue and $romanDigitsByLength. This is a minor duplication of knowledge but I made that sacrifice to make the code more obvious. As long as these lists are only used for the conversion methods, that made sense to me.
The next day I tried something different and instead of starting with single digits, then continue with addition rules, then substraction rules, like the first time, I started with 1, 2, 3, 4, 5, …
The implementation evolved entirely different and I felt like it came more naturally towards the final solution (that might be biased because I already knew the trick, but I still believe so)
It started with repeating “I” n times, then a special case for 4 was introduced, one for 5, one for 6, then I moved the special cases into a map where I checked if the input was a key in the map. When I came to 8, I added recursion and removed some of the special cases.
From there on it was just adding values to the map.
Final solution (in Ruby):
def roman n
digits = {1000 => 'M', 900 => 'CM', 500 => 'D', 400 => 'CD', 100 => 'C', 90 => 'XC', 50 => 'L', 40 => 'XL', 10 => 'X', 9 => 'IX', 5 => 'V', 4 => 'IV', 1 => 'I'}
digits.each {|arab, rom|
if n >= arab then
return rom + roman(n - arab)
end
}
''
end
Seventh Kata: Coin Changer
Write a program that will correctly determine the least number of coins to be given to the user such that the sum of the coins’ value would equal the correct amount of change.
- Input: change amount
- Input: coin denomination array (ie [1, 5, 10, 25, 100] )
- Output: number of coins array (ie [1, 0, 1, 0, 0] would represent $0.11
For example
- An input of 15 with [1, 5, 10, 25, 100] should return fifteen cents or [0, 1, 1, 0, 0]
- An input of 40 with [1, 5, 10, 25, 100] should return two dimes or [0, 1, 1, 1, 0]
- If you prefer to return a hash instead of am array, that’s ok too. {1 => 1, 5 => 0, 10 => 1, 25 => 0, 100 => 0} equals $0.11
Use Test Driven Development (TDD) to solve this problem. Start writing tests, write enough code to get the tests to pass, and then refactor your code. Allow your design to emerge from writing tests; don’t try to solve the problem first.
The original source of the kata by Todd Sedano no longer is online, but it still can be found on the archive.org wayback machine:
https://web.archive.org/web/20130216063932/http://craftsmanship.sv.cmu.edu/exercises/coin-change-kata
