lisp-random / miscellaneous_exercises / roman-numerals.lisp

;;;; roman-numerals.lisp
;;;; Copyright (c) 2012 Robert Smith

;;;; Convert Roman numerals to decimal in O(N).

(defvar *roman-letters* '((#\M . 1000)
                          (#\D .  500)
                          (#\C .  100)
                          (#\L .   50)
                          (#\X .   10)
                          (#\V .    5)
                          (#\I .    1)))

(defun number->roman (n)
  (assert (and (integerp n)
               (plusp n)))
  (format nil "~@R" n))

(defun roman-letter->value (letter)
  (cdr (assoc letter *roman-letters*)))

(defun string->list (string)
  (coerce string 'list))

(defun roman->number (roman)
  (let ((letters (map 'list #'roman-letter->value roman)))
    (labels ((rec (numbers cur acc)
               (if (null numbers)
                   (+ cur acc)
                   (let ((next (car numbers)))
                     (if (> next cur)
                         (rec (cdr numbers)
                              (- next cur)
                         (rec (cdr numbers)
                              (+ cur acc)))))))
      (rec (cdr letters)
           (car letters)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Test ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(defun id (n)
  (let* ((nr (number->roman n))
         (rn (roman->number nr)))
    (values rn nr)))

(defun test (&optional (trials 1000))
  (loop :repeat trials
        :for rand := (1+ (random 3999)) :then (1+ (random 3999))
        :unless (= rand (id rand))
          :collect (cons rand (number->roman rand))))
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.