?
Refactorings
No refactoring yet !
my other car
September 27, 2007, September 27, 2007 16:02, permalink
the letter is 's'. Prove me wrong.
macournoyer
September 27, 2007, September 27, 2007 17:52, permalink
wrong! see my proof
puts chars[51000000000] == 's' # => false
dhartmei
September 28, 2007, September 28, 2007 01:39, permalink
What about blanks and hyphens? Can you give an example, like how would the numbers 1145 and 85000001 translate to words, and how would those look concatenated?
"onethousandfourtyfiveeightyfivemillionone"?
danielharan
September 30, 2007, September 30, 2007 21:26, permalink
Examples are given at ITA's puzzle page: http://www.itasoftware.com/careers/puzzles07.html
I finally solved this one, getting it to solve under a minute. With a bit more work, it should solve under 5 seconds, probably 2. Brute force would take over a day in ruby (I brute forced some parts to verify my shortcuts and was not impressed with the speed, or lack thereof).
Oh, the answer is 'e', as can be seen here:
http://technotales.wordpress.com/2007/09/27/999_999_999/
I'll blog about my solution later. My main problem was a typo: s/fourty/forty. Here's the code that was responsible.
class NumberWriter
UNITS = { 0 => '', 1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four',
5 => 'five', 6 => 'six', 7 => 'seven', 8 => 'eight', 9 => 'nine'}
TEENS = { 10 => "ten", 11 => "eleven", 12 => "twelve", 13 => "thirteen", 14 => "fourteen",
15 => "fifteen", 16 => "sixteen", 17 => "seventeen", 18 => "eighteen", 19 => "nineteen" }
TENS = {10 => "ten", 20 => "twenty", 30 => "thirty", 40 => "forty", 50 => "fifty",
60 => "sixty", 70 => "seventy", 80 => "eighty", 90 => "ninety" }
def self.write(num)
millions = num / 1_000_000
thousands = num % 1_000_000 / 1_000
units = num % 1_000
(millions > 0 ? format_units(millions) + 'million' : '' ) +
(thousands > 0 ? format_units(thousands) + 'thousand' : '' ) +
format_units(units)
end
def self.format_units(value)
hundreds = value / 100
st = (hundreds > 0) ? (UNITS[hundreds] + 'hundred') : ''
remainder = value % 100
tens = remainder / 10
if (tens == 1)
st += TEENS[remainder]
else
st += TENS[tens*10] if (tens > 1)
units = remainder % 10
st += UNITS[units] if units > 0
end
st
end
end
require 'test/unit'
require 'number_writer'
class NumberWriterTest < Test::Unit::TestCase
def test_to_string
{ 1_000_123 => 'onemilliononehundredtwentythree', 4_567_789 => 'fourmillionfivehundredsixtyseventhousandsevenhundredeightynine',
412_045 => 'fourhundredtwelvethousandfortyfive', 13 => 'thirteen', 129 => 'onehundredtwentynine', 1 => 'one'}.each do |key,val|
assert_equal val, NumberWriter.write(key)
end
end
end
danielharan
October 1, 2007, October 01, 2007 21:19, permalink
Here's the rest of the solution. Any refactorings or speedups?
class ComparableNumber
include Comparable
def <=>(anOther)
to_s <=> anOther.to_s
end
end
require 'number_writer'
require 'comparable_number'
class Number < ComparableNumber
def initialize(number)
@value = number
end
def value
@value
end
def size
to_s.size
end
def to_s
NumberWriter.write(value)
end
def self.sorted_numbers
@@sorted_nums ||= (0..999).collect {|num| Number.new num}.sort.collect {|i| i.value}
end
end
require 'number'
require 'enumerator'
require 'comparable_number'
class ITARange < ComparableNumber
include Enumerable
end
class ThousandRange < ITARange
attr_accessor :thousands
def initialize(thousands)
@thousands = thousands
end
def value
to_s
end
def to_s
NumberWriter.write(@thousands * 1_000)
end
def child_values
@thousands * 1_000_000 + 499500
end
def child_sizes
NumberWriter.write(@thousands * 1_000).size * 1_000 + 18440
end
def each
Number.sorted_numbers.each do |i|
yield Number.new(@thousands * 1000 + i)
end
end
end
class MixedRange < ITARange
attr_accessor :millions, :thousands
def initialize(millions,thousands)
@millions = millions
@thousands = thousands
end
def to_s
NumberWriter.write(@millions * 1_000_000 + @thousands * 1_000)
end
def child_values
@millions * 1_000_000_000 + @thousands * 1_000_000 + 499500
end
def child_sizes
NumberWriter.write(@millions * 1_000_000 + @thousands * 1_000).size * 1_000 + 18440
end
def each
Number.sorted_numbers.each do |i|
yield Number.new(@millions * 1_000_000 + @thousands * 1_000 + i)
end
end
end
class MillionRange < ITARange
attr_accessor :millions
def initialize(millions)
@millions = millions
end
def to_s
NumberWriter.write(@millions * 1_000_000)
end
def child_values
@millions * 1_000_000_000_000 + 499_999_500_000
end
def child_sizes
NumberWriter.write(@millions * 1_000_000).size * 1_000_000 + 44_872_000
end
def value
to_s
end
def children
((Number.sorted_numbers - [0]).collect {|i| MixedRange.new(@millions, i) } <<
[MixedRange.new(@millions, 0).to_a]).flatten
end
def each
children.sort.each do |i|
yield i
end
end
end
require 'number'
require 'range'
@target = 51_000_000_000
@sum = @size = 0
# recursion isn't nice to puts
def echo(msg)
puts msg
end
def seek(elements)
elements.each do |e|
if e.class== Number
@sum += e.value
@size += e.size
else
if ((@size + e.child_sizes) > @target)
seek(e) # recurse to avoid overshooting target
else
@sum += e.child_values
@size += e.child_sizes
end
end
if @size == @target
echo "number:" + e.to_s
echo "sum: " + @sum.to_s
exit
end
end
end
seek((1..999).collect {|i| [Number.new(i), MillionRange.new(i), ThousandRange.new(i)]}.flatten.sort)
danielharan
October 1, 2007, October 01, 2007 22:05, permalink
Some explanations for the above code in my blog post:
http://www.danielharan.com/2007/10/02/ita-word-puzzle-ruby-solution-10000-times-faster-than-c/
danielharan
October 3, 2007, October 03, 2007 16:31, permalink
Here is the full solution, after some refactorings that speed it up (almost an order of magnitude) and help readability a bit.
class ITA
class Number
include Comparable
def initialize(millions, thousands=0, units=0)
@millions, @thousands, @units = millions, thousands, units
end
def value
@millions * 1_000_000 + @thousands * 1_000 + @units
end
def size
to_s.size
end
def to_s
@st ||= NumberWriter.write(@millions,@thousands,@units)
end
def self.sorted_numbers
@@sorted_nums ||= (0..999).collect {|num| Number.new 0,0,num}.sort.collect {|i| i.value}
end
def <=>(anOther)
to_s <=> anOther.to_s
end
end
class NumberWriter
UNITS = { 0 => '', 1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four',
5 => 'five', 6 => 'six', 7 => 'seven', 8 => 'eight', 9 => 'nine'}
TEENS = { 10 => "ten", 11 => "eleven", 12 => "twelve", 13 => "thirteen", 14 => "fourteen",
15 => "fifteen", 16 => "sixteen", 17 => "seventeen", 18 => "eighteen", 19 => "nineteen" }
TENS = {10 => "ten", 20 => "twenty", 30 => "thirty", 40 => "forty", 50 => "fifty",
60 => "sixty", 70 => "seventy", 80 => "eighty", 90 => "ninety" }
def self.write(millions, thousands=0, units=0)
(millions > 0 ? format_units(millions) + 'million' : '' ) +
(thousands > 0 ? format_units(thousands) + 'thousand' : '' ) +
format_units(units)
end
def self.string_size(millions,thousands=0,units=0)
(millions > 0 ? @@sizes[millions] + 7 : 0 ) +
(thousands > 0 ? @@sizes[thousands] + 8 : 0 ) +
@@sizes[units]
end
def self.format_units(value)
ret = @@formatted_units[value]
ret
end
def self.format_unit(value)
hundreds = value / 100
st = (hundreds > 0) ? (UNITS[hundreds] + 'hundred') : ''
remainder = value % 100
tens = remainder / 10
if (tens == 1)
st += TEENS[remainder]
else
st += TENS[tens*10] if (tens > 1)
units = remainder % 10
st += UNITS[units] if units > 0
end
st
end
@@formatted_units = (0..999).collect {|i| format_unit(i)}
@@sizes = @@formatted_units.collect {|f| f.size}
end
class Range < Number
include Enumerable
attr_accessor :millions, :thousands
def initialize(millions,thousands=0)
@millions = millions
@thousands = thousands
end
def to_s
@st ||= NumberWriter.write(@millions, @thousands)
end
end
class ThousandRange < Range
def child_values
@thousands * 1_000_000 + 499500
end
def child_sizes
NumberWriter.string_size(0, @thousands) * 1_000 + 18440
end
def each
Number.sorted_numbers.each do |i|
yield Number.new(0, @thousands, i)
end
end
end
class MixedRange < Range
def child_values
@millions * 1_000_000_000 + @thousands * 1_000_000 + 499500
end
def child_sizes
NumberWriter.string_size(@millions, @thousands) * 1_000 + 18440
end
def each
Number.sorted_numbers.each do |i|
yield Number.new(@millions, @thousands, i)
end
end
end
class MillionRange < Range
def child_values
@millions * 1_000_000_000_000 + 499_999_500_000
end
def child_sizes
NumberWriter.string_size(@millions) * 1_000_000 + 44_872_000
end
def children
((Number.sorted_numbers - [0]).collect {|i| MixedRange.new(@millions, i) } <<
[MixedRange.new(@millions, 0).to_a]).flatten
end
def each
children.sort.each do |i|
yield i
end
end
end
end
@target = 51_000_000_000
@sum = @size = 0
# recursion isn't nice to puts
def echo(msg)
puts msg
end
def seek(elements)
elements.each do |e|
if e.class== ITA::Number
@sum += e.value
@size += e.size
else
if ((@size + e.child_sizes) > @target)
seek(e) # recurse to avoid overshooting target
else
@sum += e.child_values
@size += e.child_sizes
end
end
if @size == @target
echo "number:" + e.to_s
echo "sum: " + @sum.to_s
exit
end
end
end
seek((1..999).collect {|i| [ITA::Number.new(0,0,i), ITA::MillionRange.new(i), ITA::ThousandRange.new(0,i)]}.flatten.sort)
Marc-Andre
October 18, 2007, October 18, 2007 00:14, permalink
Hi Daniel!
Congrats on solving this...
I have a couple of comments on your code.
1) You cheated! Well, ok, not cheated per say, but really, the big constants (e.g. 44_872_000) should all be calculated by your code, not hardcoded, no? Imagine for instance that you have to translate this program to French. Besides the obvious lists of words, you would have to change 5 constants in your program for it to work!
2) I think there's a (potential) bug. If the number we're looking for was the last of a range, it wouldn't seek(), add the full size and values and the range would be echoed, so you wouldn't get the right last letter...
3) If you actually do rework the seek method, why not alias child_values/sizes with value & size for the ITA::Number class, this way there won't be a need for the ugly test e.class == ITA::Number
I'm basically done having fun with a further "factorization" (more of a rewrite, actually...) I'll post it tomorrow.
Cheers!
Marc-André Lafortune
danielharan
October 18, 2007, October 18, 2007 14:30, permalink
Cool, I'm looking forward to seeing your rewrite. This code is far from 'perfect' for either aesthetics or performance.
I was hoping some StandoutJobs candidates would suggest some refactorings!
Marc-Andre
October 18, 2007, October 18, 2007 18:04, permalink
Well, I'd say I am such a candidate :-)
So, about your code, the last thing one could note is that it still has a pattern: ThousandRange, MixedRange and MillionRange are really similar and could be factorized. I think the very best way to do this is to go all the way and have a very generic "AnyRange" class (I called it GenericNumber). Coding it to be a bit more general (so that the basic units go only up to 100 instead of 1000) is not that much more difficult, and you end up with something looking like my code below. This can scale without any problem to ridiculously huge values. It took my mac less than 0.1 second to calculate the puzzle's answer, and less than 0.2 seconds to calculate the 33 trillionth letter for all numbers up to a quadrillion (it's "t" :-) It's also shorter.
I had lots of fun with this puzzle, thanks for your code, this site and everything...
# We deal with the problem by writing classes of numbers in tree form.
# Leaves can be a specific number (Centile), a generic centile (GenericValue) or a subtree (another GenericNumber).
# Each such GenericNumber can be expanded one level by replacing the leftmost GenericValue by specific values.
# This is done using GenericNumber.each; the other important method is children, which calculates recursively
# information about all the children: sum, size of strings, number.
# All language dependent constants:
TO_TWENTY = { 0 => '', 1 => 'one', 2 => 'two', 3 => 'three', 4 => 'four',
5 => 'five', 6 => 'six', 7 => 'seven', 8 => 'eight', 9 => 'nine',
10 => 'ten', 11 => 'eleven', 12 => 'twelve', 13 => 'thirteen', 14 => 'fourteen',
15 => 'fifteen', 16 => 'sixteen', 17 => 'seventeen', 18 => 'eighteen', 19 => 'nineteen' }
DECADES = { 2 => 'twenty', 3 => 'thirty', 4 => 'forty', 5 => 'fifty',
6 => 'sixty', 7 => 'seventy', 8 => 'eighty', 9 => 'ninety' }
MAGNITUDES = { 100 => 'hundred', 1000 => 'thousand', 1_000_000 => 'million' }
require 'delegate'
class Centile < DelegateClass(Fixnum)
NAMES = Array.new(100) {|n| n < TO_TWENTY.length ? TO_TWENTY[n] : DECADES[n/10] + TO_TWENTY[n%10]}
def to_s
NAMES[self]
end
def children
{:nb =>1, :including_zero => 0==self.to_i, :sizes => to_s.size, :sum => self.to_i}
end
def <=>(anOther)
to_s <=> anOther.to_s
end
end
VARIABLE='*'
class GenericValue < Range
def initialize(to)
super(0,to,:exclusive)
end
def to_s
VARIABLE
end
def children
@children_cache ||= {:nb => self.end, :including_zero => true, :sizes=> inject(0){|sum, n| sum + n.children[:sizes] }, :sum=>self.end*(self.end-1)/2}
end
def each
super {|n| yield Centile.new(n)}
end
end
class GenericNumber
include Enumerable, Comparable
def initialize(left, right, multiplier = {:name => MAGNITUDES[right.children[:nb]], :value => right.children[:nb]})
@left = left
@right = right
@multiplier = multiplier
end
def each
if @left.children[:nb] > 1
@left.each do |n|
if 0==n
@right.each{|n| yield n}
else
yield GenericNumber.new(n, @right, @multiplier)
end
end
else
@right.each{|n| yield GenericNumber.new(@left, n, @multiplier)}
end
end
def children
# The information on all children is computed with extra care for zeros, because we don't write "(zero)hundred"
@children_cache ||= {
:nb => @left.children[:nb] * @right.children[:nb],
:including_zero => @left.children[:including_zero] && @right.children[:including_zero],
:sizes =>(@left.children[:sizes] + (@left.children[:nb] - (@left.children[:including_zero] ? 1 : 0)) * @multiplier[:name].size) *
@right.children[:nb] + @right.children[:sizes]*@left.children[:nb],
:sum => @left.children[:sum] * @multiplier[:value] * @right.children[:nb] + @right.children[:sum] * @left.children[:nb]
}
end
def to_s
@str_cache ||= @left.to_s + (@left.to_s[-1] == VARIABLE[-1] ? '' : @multiplier[:name] + @right.to_s)
end
def <=>(anOther)
to_s <=> anOther.to_s
end
end
to_ten = GenericValue.new(10)
to_a_hundred = GenericValue.new(100)
to_a_thousand = GenericNumber.new(to_ten, to_a_hundred)
to_a_million = GenericNumber.new(to_a_thousand, to_a_thousand)
to_a_billion = GenericNumber.new(to_a_thousand, to_a_million)
@target = 51_000_000_000
@sum = @size = 0
# Caution: different genericNumbers can be "equal", since they have the same representation,
# for example 1xx == 1xxxxx == 'onehundred*' so we have to deal with groups of similar string values.
def expandAndGroup(genericNumbers)
group = []
genericNumbers.collect{ |n| n.to_a }.flatten.sort.each do |curNumber|
unless curNumber == group[0]
yield group
group = []
end
group <<= curNumber
end
yield group
end
def seek(genericNumbers)
expandAndGroup(genericNumbers) do |group|
new_size = group.inject(@size) { |sum, n| sum + n.children[:sizes] }
# recurse if we'll reach target and we are not dealing with _one_ _fixed_ number:
return seek(group) if (new_size >= @target) && ((group.size > 1) || (group[0].children[:nb]>1))
@size, @sum = new_size, group.inject(@sum) { |sum, n| sum + n.children[:sum] }
return group[0] if new_size >= @target
end
end
puts 'Number is:', seek([to_a_billion]), 'Sum is: ', @sum, 'Size is: ', @size
If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?
From: http://programming.reddit.com/info/2r7qw/comments