Kodekata: Romertall

mandag 5. juli 2010 Clojure Testing Kata

roman_numerals_kata

KataRomanNumerals er en kodekata beskrevet på codingdojo.org. Vanskelighetsgraden er enkel, men den kan være lærerik likevel. Her snakker jeg om hvordan jeg løste den i Clojure, og viser også en implementasjon i C#.

Oppgaven går rett og slett ut på å lage en metode som konverterer et tall fra titallssystemet til et romertall. Du kan stoppe når du når 3000, romerne hadde sjelden behov for å gå høyere enn det selv.

Dette er en typsik TDD-kata, som fungerer veldig bra om du ikke har peiling på hvordan algoritmen for å konvertere fra titallssystemet til romertall egentlig er. Bare begynn med tallet 1. Når du har en fungerende test som beviser at romertall(1) == "I" fortsetter du med å konvertere 2 til "II". Alt du trenger er en oversikt over romertall. Etterhvert vil du kunne se et mønster i koden du skriver for å få testene til å passere, og du kan gjøre en generalisering mot algoritmen du er ute etter.

Har du ikke implementert denne algoritmen før? Popp da opp din favoritt-editor og begynn å kode! Ikke fortsett med blogposten før du har løsningen – å lese videre vil bare gjøre deg forutinntatt, og det er langt fra sikkert min løsning er like elegant som det du kan komme opp med.

Trenger du et par "avanserte" testcases for å validere algoritmen kan du for eksempel bruke 1990 == MCMXC og 2008 == MMVIII.

Min løsning

Babysteps! Her ser du hvordan jeg startet kataen: Én test hvor jeg konverterer tallet 1, og sjekker at resultatet er "I". TDD sier at jeg skal gjøre det enkleste jeg kan for å få testen til å passere, og det vil si å bare returnere "I" fra funksjonen min.

1 (ns marosoft.kata.roman-numerals
2     (:use clojure.test))
3
4 (defn number-to-roman [number]
5       "I")
6
7 (deftest test-1
8          (is (= "I" (number-to-roman 1))))
9
10 (run-tests)

Og så bare fortsatte jeg. I kodeblokken nedenfor ser du hvordan det så ut etter noen minutters koding. For å spare meg for endel cut'n'paste valgte jeg å bare ha én test, som itererte over et sett med tester. Implementasjonen av number-to-roman er foreløbig ganske naiv; i bunn og grunn en lang "switch".

Allerede på testcase 3 == "III" valgte jeg forresten å bruke rekursjon. I et språk som Clojure er det mye enklere enn å opprette og modifisere verdier i en loop, som kanskje hadde vært det jeg hadde brukt om jeg løste oppgaven i for eksempel C# eller Ruby.

1 (ns marosoft.kata.roman-numerals
2     (:use clojure.test))
3
4 (defn in-range [x a b]
5       (and (>= x a) (<= x b)))
6
7 (defn number-to-roman
8       ([number] (number-to-roman number ""))
9       ([number roman]
10        (if (zero? number) roman
11          (cond
12            (<= number 3) (recur
13                            (dec number)
14                            (str roman "I"))
15            (= number 4) (str roman "IV")
16            (in-range number 5 8) (recur
17                                    (- number 5)
18                                    (str roman "V"))
19            (= number 9) (str roman "IX")
20            (in-range number 10 39) (recur
21                                      (- number 10)
22                                      (str roman "X"))
23            (in-range number 40 49) (recur
24                            (- number 40)
25                            (str roman "XL"))
26            (in-range number 50 59) (recur
27                                      (- number 50)
28                                      (str roman "L"))))))
29
30 (def test-cases {
31       1 "I" 2 "II" 3 "III"
32       4 "IV" 5 "V" 6 "VI" 7 "VII" 8 "VIII"
33       9 "IX" 10 "X" 11 "XI" 12 "XII" 13 "XIII"
34       14 "XIV" 15 "XV" 16 "XVI" 17 "XVII" 18 "XVIII"
35       19 "XIX" 20 "XX" 21 "XXI"
36       30 "XXX" 38 "XXXVIII" 39 "XXXIX"
37       40 "XL" 41 "XLI" 45 "XLV" 49 "XLIX"
38       50 "L" 54 "LIV"
39       })
40
41 (defn test-convertion
42       [number expected]
43       (is (= (number-to-roman number) expected)))
44
45 (deftest test-all
46          (doseq [[num roman] test-cases]
47                 (test-convertion num roman)))
48
49 (run-tests)

Det var nå ikke lenger noe vanskelig å se et tydelig mønster i algoritmen, og dermed var det på tide å refakturere. Etter å ha gjort det, og lagt til resten av testene, stod jeg igjen med følgende implementasjon av Romertall-kataen:

1 (ns marosoft.kata.roman-numerals
2     (:use clojure.test))
3
4 (defn <-> [x a b] (and (>= x a) (<= x b)))
5
6 (defstruct <->-> :range-start :range-end :roman-suffix)
7
8 (def conversion-steps
9      [ (struct <->-> 1 3 "I") (struct <->-> 4 4 "IV")
10        (struct <->-> 5 8 "V") (struct <->-> 9 9 "IX")
11        (struct <->-> 10 39 "X") (struct <->-> 40 49 "XL")
12        (struct <->-> 50 89 "L") (struct <->-> 90 99 "XC")
13        (struct <->-> 100 399 "C") (struct <->-> 400 499 "CD")
14        (struct <->-> 500 899 "D") (struct <->-> 900 999 "DM")
15        (struct <->-> 1000 3999 "M") ])
16
17 (defn get-step [number]
18       (first (filter
19                #(<-> number (% :range-start) (% :range-end))
20                conversion-steps)))
21
22 (defn aggregate-roman [number roman]
23       (if (zero? number)
24         roman
25         (let [step (get-step number)]
26           (recur
27             (- number (step :range-start))
28             (str roman (step :roman-suffix))))))
29
30 (defn number-to-roman [number]
31       (aggregate-roman number ""))
32
33 (deftest test-all
34          (doseq
35            [[num roman]
36             {
37             1 "I" 2 "II" 3 "III" 4 "IV" 5 "V" 6 "VI" 7 "VII" 8 "VIII"
38             9 "IX" 10 "X" 11 "XI" 12 "XII" 13 "XIII" 14 "XIV" 15 "XV"
39             16 "XVI" 17 "XVII" 18 "XVIII" 19 "XIX" 20 "XX" 21 "XXI"
40             30 "XXX" 38 "XXXVIII" 39 "XXXIX" 40 "XL" 41 "XLI" 45 "XLV"
41             49 "XLIX" 50 "L" 54 "LIV" 60 "LX" 89 "LXXXIX" 90 "XC"
42             96 "XCVI" 100 "C" 152 "CLII" 399 "CCCXCIX" 432 "CDXXXII"
43             500 "D" 610 "DCX" 900 "DM" 1000 "M" 3000 "MMM" }]
44                 (is (= (number-to-roman num) roman))))
45
46 (run-tests)

Her har jeg byttet ut den lange "switchen" med en datastruktur (lookup-tabell om du vil) basert på StructMaps (som jeg presenterte i posten om algebraiske datatyper). For å være litt fancy gav jeg strukten et litt spesielt navn, nemlig <->->, som liksom skal bety at den definerer romertall-output "->" for en gitt range "<->" (jeg kalte også funksjonen for å sjekke om et tall er innenfor en range for <->). Geekpoints? ;)

Og så litt C#

Om du har litt vanskeligheter med å tyde Clojure-koden min har jeg kodet opp en C#-versjon, som så godt det lar seg gjøre bruker de samme teknikkene som Clojure-løsningen (bortsett fra at jeg har gjort den litt objektorientert ved å innføre en Roman-klasse). Linq-uttrykket i AggregateRoman-metoden tilsvarer for eksempel get-step-funksjonen i koden over.

1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using NUnit.Framework;
5
6 namespace Marosoft.Kata.Roman
7 {
8     [TestFixture]
9     public class RomanNumbersSpecification
10     {
11         [Test]
12         public void Test()
13         {
14             var testCases = new Dictionary<int, string>
15             {
16         {1, "I"}, {2, "II"}, {3, "III"}, {4, "IV"}, {5, "V"}, {6, "VI"}, {7, "VII"}, {8, "VIII"},
17         {9, "IX"}, {10, "X"}, {11, "XI"}, {12, "XII"}, {13, "XIII"}, {14, "XIV"}, {15, "XV"},
18         {16, "XVI"}, {17, "XVII"}, {18, "XVIII"}, {19, "XIX"}, {20, "XX"}, {21, "XXI"},
19         {30, "XXX"}, {38, "XXXVIII"}, {39, "XXXIX"}, {40, "XL"}, {41, "XLI"}, {45, "XLV"},
20         {49, "XLIX"}, {50, "L"}, {54, "LIV"}, {60, "LX"}, {89, "LXXXIX"}, {90, "XC"},
21         {96, "XCVI"}, {100, "C"}, {152, "CLII"}, {399, "CCCXCIX"}, {432, "CDXXXII"},
22         {500, "D"}, {610, "DCX"}, {900, "DM"}, {1000, "M"}, {3000, "MMM"},
23             };
24
25             foreach (var item in testCases)
26                 new Roman(item.Key).StringRepresentation
27                     .ShouldEqual(item.Value);
28         }
29     }
30
31     public class Roman
32     {
33         class ConversionStep
34         {
35             internal int RangeStart;
36             internal int RangeEnd;
37             internal string RomanSuffix;
38         }
39
40         private static List<ConversionStep> _conversionSteps = new List<ConversionStep>
41         {
42             new ConversionStep { RangeStart = 1, RangeEnd = 3, RomanSuffix = "I" },
43             new ConversionStep { RangeStart = 4, RangeEnd = 4, RomanSuffix = "IV" },
44             new ConversionStep { RangeStart = 5, RangeEnd = 8, RomanSuffix = "V" },
45             new ConversionStep { RangeStart = 9, RangeEnd = 9, RomanSuffix = "IX" },
46             new ConversionStep { RangeStart = 10, RangeEnd = 39, RomanSuffix = "X" },
47             new ConversionStep { RangeStart = 40, RangeEnd = 49, RomanSuffix = "XL" },
48             new ConversionStep { RangeStart = 50, RangeEnd = 89, RomanSuffix = "L" },
49             new ConversionStep { RangeStart = 90, RangeEnd = 99, RomanSuffix = "XC" },
50             new ConversionStep { RangeStart = 100, RangeEnd = 399, RomanSuffix = "C" },
51             new ConversionStep { RangeStart = 400, RangeEnd = 499, RomanSuffix = "CD" },
52             new ConversionStep { RangeStart = 500, RangeEnd = 899, RomanSuffix = "D" },
53             new ConversionStep { RangeStart = 900, RangeEnd = 999, RomanSuffix = "DM" },
54             new ConversionStep { RangeStart = 1000, RangeEnd = 3999, RomanSuffix = "M" },
55         };
56
57         public Roman(int number)
58         {
59             Number = number;
60             StringRepresentation = AggregateRoman(Number, string.Empty);
61         }
62
63         public int Number { get; private set; }
64         public string StringRepresentation { get; private set; }
65
66         private string AggregateRoman(int number, string roman)
67         {
68             if (number == 0)
69                 return roman;
70
71             var step = (from ConversionStep cs in _conversionSteps
72                        where cs.RangeStart <= number && cs.RangeEnd >= number
73                        select cs).Single();
74
75             return AggregateRoman(number - step.RangeStart, roman + step.RomanSuffix);
76         }
77     }
78 }

Løsningen jeg kom opp med er som antydet tidligere nok ikke den mest optimale. For en mere grundig gjennomgang av problemet og en "slimmere" løsning i C# kan du ta en titt på denne linken.