TDD Kata 07 – Coin Changer

Dies ist mein wöchentlicher Kata Post. Lies den ersten um zu erfahren, worum es hier geht.

Letzte Woche: Römische Zahlen

Die Kata war aufschlussreich. Ich habe mit verschiedenen Ansätzen begonnen, die nicht funktionierten und fand schließlich, mit Hilfe der richtigen Tests eine einfache Lösung.

Meine ersten Versuche endeten mit Ergebnissen wie diesem:

Expected :'IX'
Actual :'VIV'

Sobald ich auf den Trichter kam, “IV”, “IX” usw. wie einzelne Ziffern zu behandeln, war die Lösung einfach.

Als ich die Umkehrfunktion implementierte, stellte ich fest dass es in dem Fall einfacher ist, zuerst die “Ziffern” mit zwei Zeichen wie “IV” zu prüfen, dann die mit einem Zeichen. Anstatt also die selbe Liste von (arabic,roman) Tupeln für beide Aufgaben zu nutzen und unterschiedlich zu sortieren, entschied ich mich für zwei explizite Konstanten $romanDigitsByValue und $romanDigitsByLength. Das ist zwar eine kleine Duplizierung von Information aber das Opfer war ich bereit zu bringen, um den Code verständlicher zu machen. So lange diese Listen nur für die Konvertierungs-Methoden gebraucht werden, machte es Sinn für mich.

Am nächsten Tag versuchte ich etwas anderes und anstatt wie beim ersten Versuch mit einzelnen Ziffern zu beginnen, dann mit Regeln für Addition, dann für Subtraktion, fing ich an mit 1, 2, 3, 4, 5, …

Die Implementierung entwickelte sich vollkommen anders und ich hatte den Eindruck dass es sich logischer auf die finale Lösung hin entwickelte. Vielleicht war ich voreingenommen wiel ich diesmal den Trick schon kannte, aber ich glaube dennoch, dass die Auswahl der Tests eine Rolle spielte.

Es fing an mit der Wiederholung von “I”, n mal, dann wurde ein Sonderfall für 4 eingeführt, dann einer für 5, einer für 6. Dann wurde eine Map für die Sonderfälle eingeführt, wo ich zuerst prüfe, ob die Eingabe ein Schlüssel in der Map ist. Bei 8 fügte ich Rekursion hinzu und konnte schließlich einige der Sonderfälle entfernen.

Von da an mussten nur noch neue Werte zur Map hinzugefügt werden, bis alle Zahlen abgebildet werden konnten.

Finale Lösung (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

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

Die Originalquelle der Kata von Todd Sedano ist nicht mehr online, kann aber immer noch in der archive.org “Wayback Machine” gefunden werden:
https://web.archive.org/web/20130216063932/http://craftsmanship.sv.cmu.edu/exercises/coin-change-kata