If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
Permalink: http://projecteuler.net/problem=17
To solve this problem we need some sort of mapping that defines association
between number and its string representation, e.g 123 = one hundred and twenty three.
This can be done with maps in clojure in form {:1 "one" :2 "two"}.
But if pay more atention to this map, we see that key is a numeric value.
Exactly what plain arrays do.
Then we just define all mappings, obtain all arrays string elements, find their lengths and sum them.
One problem that providing mapping for each number between 1 and 1000 is a “bit” routine task, so we need some formula to calculate representation instead of hardcoding it. We come to defining groups.
First group is just first 20 numbers:
(def first20 ["one" "two" "three" "four" "five"
"six" "seven" "eight" "nine" "ten"
"eleven" "twelve" "thirteen" "fourteen" "fifteen"
"sixteen" "seventeen" "eighteen" "nineteen"])
Note: there is no “zero” as we don’t use it in spoken language.
Second group is numbers that divides 10:
(def decas ["" "ten" "twenty" "thirty" "forty" "fifty" "sixty" "seventy" "eighty" "ninety"])
Note: empty first element here is used to reduce additional check. Its length is 0, that has no effect at all.
And the last ones are three used values:
(def h "hundred")
(def t "thousand")
(def a "and")
The basic function will calculate the length string representation of some number.
Let’s call it word-length.
(defn word-length [n]
(cond (= n 1000) (+ (count t) (count (nth first20 1)))
(< n 100)
(let [q (quot n 10) m (mod n 10)
d (count (nth decas q))]
(if (zero? m) d
(if (< q 2) (count (nth first20 (dec (+ m (* 10 q)))))
(+ d (count (nth first20 (dec m)))))))
(< n 1000)
(let [q (quot n 100) m (mod n 100)]
(if (zero? m) (+ (word-length q) (count h))
(+ (count a) (count h) (word-length q) (word-length m))))))
Little explanation:
1000 then the length of string “one” + “thousand”, 11.100 then extract its decade part. If there is no
reminder for division by 10, the length is length of that decade part.first20, length taken from array first20.1000 then extract hundred part. If there is no
reminder for division by 100, the length is “hundred” plus number of hundreds.100.Awful word-presentation of algorithm, because of… Reading code is much simpler, I know.
And the last part just sum up all word-lengths:
(reduce + (map word-length (range 1 1001)))
Check the code here.
P.S. In fact algorithm is very simple, but needs some time to understand few branches. By the way, the problem is little boring.
mishadoff 09 April 2013