Roman numeral conversion in Clojure, part II

Previously I translated Roman numerals to decimals with this code:

(def numerals {\I 1, \V 5, \X 10, \L 50, \C 100, \D 500, \M 1000})

(defn add-numeral [n t]
  (if (> n (* 4 t)) (- n t) (+ t n)))

(defn roman [s]
  (reduce add-numeral (map numerals (reverse s))))

Now I want to continue my Clojure practise by doing the reverse: translating from decimals to Roman numerals.

I started where I left off previously, so I already have the numerals map defined. I figure the inverse of this map will be handy for doing look-ups of decimals, and sure enough clojure has a handy function - map-invert:

=> (use '[clojure.set :only (map-invert)])
nil

=> (doc map-invert)
––––––––––––––––
clojure.set/map-invert
([m])
  Returns the map with the vals mapped to the keys.
nil

Inverting my numerals map gives:

=> (map-invert numerals)
{10 \X, 5 \V, 1000 \M, 50 \L, 1 \I, 500 \D, 100 \C}

Great, but that highlights a lack of foresight in my original naming of the numerals map, so I define a new one named numerals-to-decimals, and decimals to numerals as its inverse:

(def numerals-to-decimals {\I 1, \V 5, \X 10, \L 50, \C 100, \D 500, \M 1000})
(def decimals-to-numerals (map-invert numerals-to-decimals))

Now I can convert easily to numerals where there is an exact match for the decimal:

=> (decimals-to-numerals 10)
\X

But I get nil if there's no match:

=> (decimals-to-numerals 11)
nil

In Roman numerals there is no zero, but they did use the concept of nul (nulla), so I start composing a function which I will incrementally improve as I figure out more steps:

(defn decimal-to-roman [d]
  (cond
    (= 0 d) "nulla"
    :else 
      (decimals-to-numerals d)))

Which yields the following results:

=> (decimal-to-roman 0)
"nulla"
=> (decimal-to-roman 5)
\V
=> (decimal-to-roman 11)
nil

So now I need to tackle the case where the decimal value can only be represented by some composite of the available Roman numerals. Clearly this is going to need to involve dividing the decimal number by the largest available numeral, then repeating for the remainder. Lets try for a single numeral:

(defn decompose-decimal-with-numeral [d v n]
  [n (quot d v) (rem d v)])

Testing that gives:

=> (decompose-decimal-with-numeral 23 10 \X)
[\X 2 3]
=> (decompose-decimal-with-numeral 3 10 \X)
[\X 0 3]

Where the resulting vector contains the numeral, the number of times it divides into the decimal value, and the remainder. Lets apply that function to our map of decimals-to-numerals:

(defn decompose-decimal-with-numerals [d]
  (for [[v n] decimals-to-numerals]
    (decompose-decimal-with-numeral d v n)))

Applying this function to the decimal 123 gives me the following:

=> (decompose-decimal-with-numerals 123)
([\X 12 3] [\V 24 3] [\M 0 123] [\L 2 23] [\I 123 0] [\D 0 123] [\C 1 23])

That's useful progress, but now I want to get the result of the biggest divisor only. To do that I need to filter when the divisors are larger than the input, and sort the results. Filtering is relatively straight-forward by supplying a :when filter function to the comprehension.

(defn decompose-decimal-with-numerals [d]
  (for [[v n] decimals-to-numerals :when (#(>= d v))]
    (decompose-decimal-with-numeral d v n)))

I could sort at various points along the way. Most efficient is probably to work with a sorted list of numerals from the outset, so lets create one:

(def numerals-desc (sort-by first > decimals-to-numerals))

Printing the new list gives:

=> (println numerals-desc)
([1000 M] [500 D] [100 C] [50 L] [10 X] [5 V] [1 I])

Using that in the decompose method gives:

(defn decompose-decimal-with-numerals [d]
  (for [[v n] numerals-desc :when (#(>= d v))]
    (decompose-decimal-with-numeral d v n)))

=> (decompose-decimal-with-numerals 123)
([\C 1 23] [\L 2 23] [\X 12 3] [\V 24 3] [\I 123 0])

Sweet! We only actually need the result for the largest available divisor, so lets re-write this function to do that:

(defn largest-divisor [d]
  (first (for [[v n] numerals-desc :when (#(>= d v))]
    (decompose-decimal-with-numeral d v n))))

=> (largest-divisor 123)
[\C 1 23]

Actually what I really want is the string representation of the numeral * the number of occurrences, so I create a new function n-numerals which concatenates N of the numeral together into a string and modify the decompose-decimal-with-numeral function:

(defn n-numerals [n num]
  (apply str (for [n (range 0 n)] num)))

(defn decompose-decimal-with-numeral [d v n]
  [(n-numerals (quot d v) n) (rem d v)])

Now I can apply decompose-decimal-with-numerals and see the break-down for each numeral:

=> (decompose-decimal-with-numerals 23)
(["XX" 3] ["VVVV" 3] ["IIIIIIIIIIIIIIIIIIIIIII" 0])

Good to see that it is giving the correct values, but more importantly I can use largest-divisor to see the Roman numeral form of the quotient:

=>(largest-divisor 323)
["CCC" 23]

What remains is to apply this recursively until the remainder is zero:

(defn decompose-decimal-recursively [d]
  (let [[n r] (largest-divisor d)]
    (if (= 0 r) n (apply str n (decompose-decimal-recursively r)))))

Here I'm using tail recursion and the recursion can never be very deep because the set of numerals is small, so there should be no danger of blowing the stack. Testing the function gives:

=> (decompose-decimal-recursively 424)
"CCCCXXIIII"
=> (decompose-decimal-recursively 1984)
"MDCCCCLXXXIIII"

These are correct answers, but there are two problems: First, the results are not optimal - we have runs of 4 numerals, for example IIII which can be written more succinctly as IV. Second, I think I've over-complicated things by using division instead of subtraction.

The decimal-to-roman translation program so far looks like:

(use '[clojure.set :only (map-invert)])

(def numerals-to-decimals {\I 1, \V 5, \X 10, \L 50, \C 100, \D 500, \M 1000})
(def decimals-to-numerals (map-invert numerals-to-decimals))

(def numerals-desc (sort-by first > decimals-to-numerals))

(defn n-numerals [n num]
  (apply str (for [n (range 0 n)] num)))

(defn decompose-decimal-with-numeral [d v n]
  [(n-numerals (quot d v) n) (rem d v)])

(defn largest-divisor [d]
  (first (for [[v n] numerals-desc :when (#(>= d v))]
    (decompose-decimal-with-numeral d v n))))

(defn decompose-decimal-recursively [d]
  (let [[n r] (largest-divisor d)]
    (if (= 0 r) n (apply str n (decompose-decimal-recursively r)))))

I'm going to try to simplify before fixing the optimisation problem. I can find the next largest numeral that can be subtracted from the total like this:

(defn largest-numeral-in [d]
  (first (for [[v n] numerals-desc :when (#(>= d v))] [v n])))

Then I can recursively use this to eat away at the target decimal, like this:

(defn decimal-to-roman [d]
  (let [[v n] (largest-numeral-in d) [r] [(- d v)]]
    (if (= 0 r) (str n) (apply str n (decimal-to-roman r)))))

The program just got a lot simpler! From 4 functions in 10 lines to 3 functions in 6 lines. Here it is in entirety:

(use '[clojure.set :only (map-invert)])

(def numerals-to-decimals {\I 1, \V 5, \X 10, \L 50, \C 100, \D 500, \M 1000})
(def decimals-to-numerals (map-invert numerals-to-decimals))

(def numerals-desc (sort-by first > decimals-to-numerals))

(defn largest-numeral-in [d]
  (first (for [[v n] numerals-desc :when (#(>= d v))] [v n])))

(defn decimal-to-roman [d]
  (let [[v n] (largest-numeral-in d) [r] [(- d v)]]
    (if (= 0 r) (str n) (apply str n (decimal-to-roman r)))))

Now to optimise the results. After noodling with this for a while I realise that there really aren't all that many optimisation cases. They are: 4, 9, 40, 45, 49, 90, 95, 99, 400, 450, 490, 495, 499, 900, 950, 990, 995, and 999. 18 cases. I could generate these and then just do a lookup

(def optimisations (apply hash-map (flatten 
  (for [[n1 d1] numerals-to-decimals]
    (for [[n2 d2] numerals-to-decimals :when (#(< d2 (quot d1 2)))]
      [(- d1 d2) (str n2 n1)])))))

I'm sure there's a much neater way of doing that, but it does the trick and produces this map:

=> (println optimisations)
{450 LD, 99 IC, 995 VM, 4 IV, 900 CM, 999 IM, 40 XL, 9 IX, 
490 XD, 45 VL, 495 VD, 400 CD, 49 IL, 499 ID, 950 LM, 90 XC, 
990 XM, 95 VC}

Now I can simply check this map in addition to the map of single numerals. Even better if there was just one map containing all of these numerals, so:

(def opt-decimals-to-numerals
  (merge decimals-to-numerals optimisations))

Redefining numerals-desc to include the optimisations should be all I need to do:

(def numerals-desc (sort-by first > opt-decimals-to-numerals))

So now when I invoke decimal-to-roman I get:

=> (decimal-to-roman 1999)
"MIM"
=> (decimal-to-roman 1954)
"MLMIV"
=> (decimal-to-roman 1984)
"MLMXXXIV"
=> (decimal-to-roman 313)
"CCCXIII"
=> (decimal-to-roman 413)
"CDXIII"
=> (decimal-to-roman 419)
"CDXIX"

The program in entirety now looks like this:

(use '[clojure.set :only (map-invert)])

(def numerals-to-decimals {\I 1, \V 5, \X 10, \L 50, \C 100, \D 500, \M 1000})
(def decimals-to-numerals (map-invert numerals-to-decimals))

(def optimisations (apply hash-map (flatten 
  (for [[n1 d1] numerals-to-decimals]
    (for [[n2 d2] numerals-to-decimals :when (#(< d2 (quot d1 2)))]
      [(- d1 d2) (str n2 n1)])))))

(def opt-decimals-to-numerals
  (merge decimals-to-numerals optimisations))

(def numerals-desc (sort-by first > opt-decimals-to-numerals))

(defn largest-numeral-in [d]
  (first (for [[v n] numerals-desc :when (#(>= d v))] [v n])))

(defn decimal-to-roman [d]
  (let [[v n] (largest-numeral-in d) [r] [(- d v)]]
    (if (= 0 r) (str n) (apply str n (decimal-to-roman r)))))

There's quite a chunk of code there simply for converting the map of numerals-to-decimals to include the optimisations. The code would be shorter if I simply created that map to begin with:

(def numerals-desc 
  '([1000 "M"] [999 "IM"] [995 "VM"] [990 "XM"] [950 "LM"] [900 "CM"] 
   [500 "D"] [499 "ID"] [495 "VD"] [490 "XD"] [450 "LD"] [400 "CD"] 
   [100 "C"] [99 "IC"] [95 "VC"] [90 "XC"] [50 "L"] [49 "IL"] [45 "VL"] 
   [40 "XL"] [10 "X"] [9 "IX"] [5 "V"] [4 "IV"] [1 "I"]))

(defn largest-numeral-in [d]
  (first (for [[v n] numerals-desc :when (#(>= d v))] [v n])))

(defn decimal-to-roman [d]
  (let [[v n] (largest-numeral-in d) [r] [(- d v)]]
    (if (= 0 r) (str n) (apply str n (decimal-to-roman r)))))

Nice! Now to put everything together so that I can convert both ways - decimal-to-roman and roman-to-decimal:

(use '[clojure.set :only (map-invert)])

(def numerals-desc 
  '([1000 "M"] [999 "IM"] [995 "VM"] [990 "XM"] [950 "LM"] [900 "CM"] 
   [500 "D"] [499 "ID"] [495 "VD"] [490 "XD"] [450 "LD"] [400 "CD"] 
   [100 "C"] [99 "IC"] [95 "VC"] [90 "XC"] [50 "L"] [49 "IL"] [45 "VL"] 
   [40 "XL"] [10 "X"] [9 "IX"] [5 "V"] [4 "IV"] [1 "I"]))

(def numerals-to-decimals
  (map-invert (apply hash-map (flatten numerals-desc))))

(defn largest-numeral-in [d]
  (first (for [[v n] numerals-desc :when (#(>= d v))] [v n])))

(defn decimal-to-roman [d]
  (let [[v n] (largest-numeral-in d) [r] [(- d v)]]
    (if (= 0 r) (str n) (apply str n (decimal-to-roman r)))))

(defn add-numeral [n t]
  (if (> n (* 4 t)) (- n t) (+ t n)))

(defn roman-to-decimal [r]
  (reduce add-numeral 
    (map numerals-to-decimals (map str (reverse r)))))

(defn optimise-roman [r]
  (decimal-to-roman (roman-to-decimal r)))

For fun I added one extra function optimise-roman which takes a roman-numeral string and returns the optimal representation, for example:

=> (optimise-roman "VIIII")
"IX"
=> (optimise-roman "XCVIIII")
"IC"
=> (optimise-roman "MDCCCCLXXXXVIIII")
"MIM"

I confess I am struggling with the mind-shift from imperative to functional programming. I find myself thinking of various convoluted ways to avoid recursion (why!?) and struggling to remember to use list comprehensions, even though (I think) I understand them well enough.

I'm not sure if it was because of this or in spite of it that it took me quite a while to realise that I was starting with a too-complex algorithm (division) when a much simpler one existed (subtraction).

Still, Clojure is fun :)