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:

- When converting from roman numerals to decimal digits, it is simplest to process the roman numeral from right to left.
- 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.

January 15th, 2011 on 5:07 pm

Slightly different version using reduce instead of recur:

(def roman-to-arabic (zipmap “IVXLCDM” [1 5 10 50 100 500 1000]))

(defn to-arabic-array [roman]

(map roman-to-arabic roman))

(defn to-arabic [roman]

(first

(reduce

(fn [[sum maxValue] value]

(if (< value maxValue)

[(- sum value) maxValue]

[(+ sum value) (max value maxValue)]))

[0 0]

(reverse (to-arabic-array roman)))))

April 9th, 2011 on 8:14 pm

Looks silly compared to Bob’s, but:

(def r2n (zipmap (into ‘["I" "II" "III" "IV" "V" "VI" "VII" "VIII" "IX"]

‘["X" "L" "C" "D" "M"])

‘[1 2 3 4 5 6 7 8 9 10 50 100 500 1000]))

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

(def re-roman

(re-pattern (apply str (interpose “|” (reverse (sort-by count (keys r2n)))))))

(defn de-romanize [s] (reduce + (map r2n (re-seq re-roman s))))

(defn romanize

[n]

(loop [i n, ; The current number.

s "", ; The result string.

divisors (reverse (sort (keys n2r))), ; Vector of divisors.

d (first divisors)] ; First divisor.

(if (nil? d)

s

(recur

(rem i d)

(apply str s (take (quot i d) (repeat (n2r d))))

(rest divisors)

(first divisors)))))

; Print numbers 1 thru 1000.

(loop [n 1]

(print (str n ” –> ” (romanize n) ” –> “))

(println (de-romanize (romanize n)))

(if (< 999 n)

nil

(recur (inc n))))

April 13th, 2011 on 3:43 pm

sorry but

(get (vec (reductions str “” (vec (repeat 9 “M”)))) %1)

is better write as

(reduce str (vec (repeat %1 “M”)))

April 13th, 2011 on 3:51 pm

Leave a reply eat (int backslash 0)??? rewrite as 48

(ns euler89)

(use ‘[clojure.string :only (replace-first)])

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

(defn

romanize

“Returns the minimal roman numeral representation of n”

[n] {:pre [(pos? n), (> 10000 n)]}

(apply str (rseq (vec (map #(%1 (- (int %2) 48)) [

#(get ["" "I" "II" "III" "IV" "V" "VI" "VII" "VIII" "IX"] %1)

#(get ["" "X" "XX" "XXX" "XL" "L" "LX" "LXX" "LXXX" "XC"] %1)

#(get ["" "C" "CC" "CCC" "CD" "D" "DC" "DCC" "DCCC" "CM"] %1)

#(reduce str (vec (repeat %1 “M”)))] (reverse (str n)))))))

(defn deromanize

“Returns the decimal representation of a roman numeral string s.”

[s]

(reduce + (vec (map {\M 1000,\D 500,\C 100,\L 50,\X 10,\V 5,\I 1}

(reduce #(replace-first %1 (get %2 0) (get %2 1)) s [["IV" "IIII"]

["IX" "VIIII"]["XL" "XXXX"]["XC" "LXXXX"]["CD" "CCCC"]["CM" "DCCCC"]])))))

(defn euler89 [file]

(reduce + (for [l (read-lines file)]

(- (count l) (count (romanize (deromanize l)))))))

(euler89 “roman.txt”)