Lost in time and space...

I returned to Lisp (aka CLisp) after a long gap. Infact, last lisp program i wrote was back in my first year at grad school. Lisp at that time was not interesting to me as i had already started with windows programming & was more into "UI" . Now when i look into it, i'm amazed at the simplicity and power Lisp... especially when you want to try out new algorithms. So, here my first non-trivial lisp program.

Problem statement: Given a number as expressed in words (ex. "two hundred thousand"), convert it to its numeric representation. The test data & expected result i set for myself was:

1. "ninety one" - 91
2. "one hundred ninety nine" - 199
3. "twenty one hundred" - 2100
4. "ninety nine hundred" - 9900 .. notice this should be same as "nine thousand nine hundred"
5. "ninety nine thousand nine hundred ninety nine" - 99999
6. "nine million ninety nine thousand nine hundred fifty" - 999950
   

To keep things simple, i discounted the "and" word that usually comes as the 2nd last word. So, "two hundred and fifty" is not a valid sentence.

Solution: One of the algorithm which will work for most of the practical cases would be:

BASIC_UNIT -> one | two | three |...|twenty|thirty|forty|...|ninety
HIGHER_DEGREE -> hundred | thousand | million
N_ATOM -> BASIC_UNIT
N_ATOM -> BASIC_UNIT HIGHER_DEGREE
NUMBER -> N_ATOM+, constraint N_ATOM[i].HIGHER_DEGREE < N_ATOM[j].HIGHER_DEGREE for all j >i

Though the algo is tested in Lisp, converting it to any other language (java, c#) should be straightforward. The constraint basically says that a number is a sequence of N_ATOM(s), given an atom in the sequence, all subsequent atom should have its "higher degree" factor less than it. It basically means that once you have written "thousand" you cannot in subsequent word write "thousand" or higher degree like "million". So sentence like "one thousand thousand" or "one thousand million" is not valid under this grammar (I'll talk about more refined grammar in my subsequent posts).

If you are wondering how to translate this grammar in program, then here's the Lisp code :)
For simplicity sake, i've assigned token to each number word (ideally there should a pre-phase of converting string to token.... but that should be simple). Here's how you'll call for the test cases -

1. (w2n ninety one) - 91
2. (w2n one hundred ninety nine) - 199
3. (w2n twenty one hundred - 2100
4. (w2n ninety nine hundred) - 9900
   
5. (w2n ninety nine thousand nine hundred ninety nine) - 99999
6. (w2n nine million ninety nine thousand nine hundred fifty) - 999950
   


(setf one 1)
(setf two 2)
(setf three 3)
(setf four 4)
(setf five 5)
(setf six 6)
(setf seven 7)
(setf eight 8)
(setf nine 9)
(setf ten 10)
(setf eleven 11)
(setf twelve 12)
(setf thirteen 13)
(setf fourteen 14)
(setf fifteen 15)
(setf sixteen 16)
(setf seventy 17)
(setf eighteen 18)
(setf nineteen 19)
(setf twenty 20)
(setf thirty 30)
(setf forty 40)
(setf fifty 50)
(setf sixty 60)
(setf seventy 70)
(setf eighty 80)
(setf ninety 90)
(setf hundred 100)
(setf thousand 1000)
(setf million 100000)

;198,149
; BASIC_UNIT := one | two | three |...|twenty|thirty|forty|...|ninety
; HIGHER_DEGREE := hundred | thousand | lakh | crore
; N_ATOM := BASIC_UNIT
; N_ATOM := BASIC_UNIT HIGHER_DEGREE
; N_ATOM := N_ATOM+, constraint N_ATOM[i].HIGHER_DEGREE < N_ATOM[j].HIGHER_DEGREE for all j = i+1 ... N_ATOMS.COUNT

(defun w2n (&rest word-list)
(w2n-aux word-list 0 0 0)
); end of function body

(defun w2n-is-higher-degree (x)
(or (or (equal x hundred) (equal x thousand)) (equal x million))
)

(defun w2n-aux (word-list w2n_result w2n_s0 w2n_h0)
(let ((x (first word-list))
(next_list (cdr word-list))
)
(if (endp word-list) (+ w2n_result w2n_s0)
(if (w2n-is-higher-degree x) (if (or (equal w2n_h0 0) (< x w2n_h0))
(w2n-aux next_list (if (> w2n_s0 0) (+ w2n_result (* w2n_s0 x)) (* w2n_result x)) 0 x)
; else we have issue ... not a well formed wording
(print "Error: words not well formed.")
)

; else
(w2n-aux next_list w2n_result (+ w2n_s0 x) w2n_h0)
)
)
) ; end of let
); end of defun