Problem 89 was kind of fun: we needed to convert some sloppily written roman-numerals into their more efficient, minimal representations.

There are two tricks to doing this easily:

  1. When converting from roman numerals to decimal digits, it is simplest to process the roman numeral from right to left.
  2. Since I can only be placed before V and X, X before L and C, and C before D and M, the symmetry of these results as you move up by powers of ten suggests that we use a few simple cond statements to handle numbers from 1 to 10, and recurse to handle the increasingly higher powers of ten.

The code to implement these rules wasn’t particularly long. As usual, zipmap is very concise at creating mappings from characters to digits.

(use '[clojure.contrib.duck-streams :only (read-lines)])

(def r2n (zipmap "IVXLCDM" [1 5 10 50 100 500 1000]))

(def n2r (zipmap (vals r2n) (keys r2n)))

;; Do things in reverse and it's so much easier to solve!
(defn de-romanize
  "Returns the decimal representation of a roman numeral string s. "
  ([s] (de-romanize (reverse (map r2n s)) 0 0))
  ([s total mx] (if-let [c (first s)]
                  (if (>= c mx)
                    (recur (rest s) (+ total c) (max c mx))
                    (recur (rest s) (- total c) mx))
                  total)))

(defn romanize
  "Returns the minimal roman numeral representation of n"
  ([n]
     {:pre [(<= n 10000 )]}
     (romanize (quot n 10) (rem n 10) 1))
  ([q r x]
     (if (> x 100)
       (repeat (+ q r) (n2r x))
       (->> (concat
             (romanize (quot q 10) (rem q 10) (* x 10))
             (cond
              (< r 4) (repeat r (n2r x))
              (= r 4) [(n2r x) (n2r (* 5 x))]
              (< r 9) (concat [(n2r (* 5 x))] (repeat (- r 5) (n2r x)))
              (= r 9) [(n2r x) (n2r (* 10 x))]
              :else ""))
           (apply str )))))

(defn euler-89 [file]
  (reduce
   +
   (for [l (read-lines file)]
     (- (count l)
        (count (romanize (de-romanize l)))))))

(euler-89 "roman.txt")

You may notice that I used preconditions to indicate the romanize function only works for numbers less than 10000.