Spelling Numbers
July 3, 2020
First we write a program that converts a number to words; we did this in a previous exercise, but it’s fun to do it again:
(define (spell n) (let ((ones '("" "one" "two" "three" "four" "five" "six" "seven" "eight" "nine" "ten" "eleven" "twelve" "thirteen" "fourteen" "fifteen" "sixteen" "seventeen" "eighteen" "nineteen")) (tens '("" "" "twenty" "thirty" "forty" "fifty" "sixty" "seventy" "eighty" "ninety"))) (cond ((negative? n) (error 'spell "too small")) ((zero? n) "zero") ((< n 20) (list-ref ones n)) ((< n 100) (string-append (list-ref tens (quotient n 10)) (list-ref ones (modulo n 10)))) ((= n 100) "onehundred") (else (error 'spell "too big")))))
We ignore spaces because they don’t affect the sort. Then it’s just a matter of calling the sort:
> (sort (lambda (a b) (string<? (spell a) (spell b))) (range 101)) (8 18 80 88 85 84 89 81 87 86 83 82 11 15 50 58 55 54 59 51 57 56 53 52 5 40 48 45 44 49 41 47 46 43 42 4 14 9 19 90 98 95 94 99 91 97 96 93 92 1 100 7 17 70 78 75 74 79 71 77 76 73 72 6 16 60 68 65 64 69 61 67 66 63 62 10 13 30 38 35 34 39 31 37 36 33 32 3 12 20 28 25 24 29 21 27 26 23 22 2 0)
You can run the program at https://ideone.com/AHCNhf, or look at A036747.
As usual a Perl response… But this one has a Schwartzian transform – which makes the sort appreciably faster (although another approach can be memoization to cache the spellings). The transform adds an index to the sort {in this case the spelled out number}, sorts by the index and then removes it. It is a standard Perl technique to speed up these sorts of sorts.
Here’s a different way to solve the problem, by constructing a Finite State Automaton:
I can’t resist showing off that the Common Lisp format function can output integers in English.
@Jan: Other languages have libraries to do such things, eg. num2words in Python:
but where is the fun in that?
I was needlessly verbose there:
I’m disappointed that num2words doesn’t seem to support Catalan.
In Python for numbers in dutch (the language was not specified in this exercise). The rules for dutch number spelling are a little more complicated than for english number spelling.
@Paul: nice. How are you getting the right sorting order for the Dutch? Locale setting?
Or ICU works nicely:
@matthew: I did not really think about the sorting order in the Dutch language. I should have done that, of course. The official Dutch alphabet ordering is like string.ascii_lower. The characters é and ë are supposed to be the same as e for ordering. That results in the order that you gave in your last post.
Here’s a solution in Python.
Output: