From: Glenn Parker <glenn.parker@...>
Date: 2005-03-28T10:28:15+09:00
Subject: Re: [SOLUTION] English Numerals (#25)

Note: I'm afraid I could not bring myself to code up some random 
ill-defined method of expressing numbers in English, so I did it the way 
I was taught in school, using hypens and absolutely no "ands" or commas. 
  I think I've got Strunk & White on my side.  Regardless, I'll be 
somewhat surprised if my answer comes out very different from others.

Brute force was not a very practical option when looking for the answer, 
so I assumed it would be OK to do a little bit of analysis and simplify 
the problem.  If my analysis was wrong, then I'll probably lose badly on 
this one.  :)  There may also be a much more elegant way to express all 
of this, but I thought I would just give you a short brain dump here.

Every number from 1 to 10**10 can be expressed in English as a 
concatenation of one or more independent phrases.  Each phrase expresses 
the value of a triplet of numerals from the original number.  For 
example, 56_106_021 uses three phrases: "fifty-six million" for the 
millions triplet (56), "one hundred six thousand" for the thousands 
triplet (106), and "twenty-one" for the ones triplet (021).  I don't 
allow "twelve hundred" for 1200, but I think it would only complicate 
the logic slightly to handle this.

I proceed to find the lowest possible phrase for each of the four 
triplets in the range of interest.  It must be possible to express the 
lowest number name using a subset of the lowest possible phrases for 
each triplet.  And since the desired number must be odd, valid subsets 
will all end with the ones triplet phrase.

The ones triplet range has only 500 phrases: the odd numbers from 1 to 
999.  The thousands triplet has 1000 phrases: the multiples of 1000 from 
1000 to 999_999.  Likewise, the millions triplet has 1000 phrases.  The 
billions triplet has only ten phrases because we stop caring after 
10_000_000_000 (instead of going to 999_999_999_999).  Finding the four 
lowest phrases for each triplet requires examining only 2510 numbers. 
There are only eight combinations of the resulting four phrases that 
represent an odd number.

The result: "eight billion eight hundred eight million eight hundred 
eight thousand eight hundred eighty-five".



#!/usr/bin/ruby

class Integer

   Ones = %w[ zero one two three four five six seven eight nine ]
   Teen = %w[ ten eleven twelve thirteen fourteen fifteen
              sixteen seventeen eighteen nineteen ]
   Tens = %w[ zero ten twenty thirty forty fifty
              sixty seventy eighty ninety ]
   Mega = %w[ none thousand million billion ]

   def to_english
     places = to_s.split(//).collect {|s| s.to_i}.reverse
     name = []
     ((places.length + 2) / 3).times do |p|
       strings = Integer.trio(places[p * 3, 3])
       name.push(Mega[p]) if strings.length > 0 and p > 0
       name += strings
     end
     name.push(Ones[0]) unless name.length > 0
     name.reverse.join(" ")
   end

   private

   def Integer.trio(places)
     strings = []
     if places[1] == 1
       strings.push(Teen[places[0]])
     elsif places[1] and places[1] > 0
       strings.push(places[0] == 0 ? Tens[places[1]] :
                    "#{Tens[places[1]]}-#{Ones[places[0]]}")
     elsif places[0] > 0
       strings.push(Ones[places[0]])
     end
     if places[2] and places[2] > 0
       strings.push("hundred", Ones[places[2]])
     end
     strings
   end

end

# If there are command-line args, just print out English names.
if ARGV.length > 0
   ARGV.each {|arg| puts arg.to_i.to_english}
   exit 0
end

# Return the name of the number in the specified range that is the
# lowest lexically.
def minimum_english(start, stop, incr)
   min_name = start.to_english
   start.step(stop, incr) do |i|
     name = i.to_english
     min_name = name if min_name > name
   end
   min_name
end

# Find the lowest phrase for each 3-digit cluster of place-values.
# The lowest overall string must be composed of elements from this list.
components =
   [ minimum_english(10**9, 10**10, 10**9),
     minimum_english(10**6, 10**9 - 1, 10**6),
     minimum_english(10**3, 10**6 - 1, 10**3),
     minimum_english(10**0, 10**3 - 1, 2) ]

$result = components[-1]
def search_combinations(list, selected = [])
   if elem = (list = list.dup).shift
     if list.empty?
       # Always include the final element from list in the selection.
       string = selected.dup.push(elem).join(" ")
       $result = string if $result > string
     else
       search_combinations(list, selected)
       search_combinations(list, selected.dup.push(elem))
     end
   end
   $result
end

puts search_combinations(components)



-- 
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/>