Bfec5f7d1a4aaafc5a2451be8c42d26a

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

1
?

Refactorings

No refactoring yet !

Avatar

my other car

September 27, 2007, September 27, 2007 16:02, permalink

No rating. Login to rate! 
1
2
3
the letter is 's'.

Prove me wrong.
Bfec5f7d1a4aaafc5a2451be8c42d26a

macournoyer

September 27, 2007, September 27, 2007 17:52, permalink

No rating. Login to rate!

wrong! see my proof

1
puts chars[51000000000] == 's' # => false
Avatar

dhartmei

September 28, 2007, September 28, 2007 01:39, permalink

No rating. Login to rate!

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"?

880cbab435f00197613c9cc2065b4f5a

danielharan

September 30, 2007, September 30, 2007 21:26, permalink

No rating. Login to rate!

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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

number_writer_test.rb

1
2
3
4
5
6
7
8
9
10
11
12
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
880cbab435f00197613c9cc2065b4f5a

danielharan

October 1, 2007, October 01, 2007 21:19, permalink

2 ratings. Login to rate!

Here's the rest of the solution. Any refactorings or speedups?

1
2
3
4
5
6
7
class ComparableNumber
  include Comparable
  
  def <=>(anOther)
    to_s <=> anOther.to_s
  end
end

number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

range

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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

finder - the code that actually outputs the solution. try "time ruby finder.rb"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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)
880cbab435f00197613c9cc2065b4f5a

danielharan

October 1, 2007, October 01, 2007 22:05, permalink

No rating. Login to rate!

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/

880cbab435f00197613c9cc2065b4f5a

danielharan

October 3, 2007, October 03, 2007 16:31, permalink

2 ratings. Login to rate!

Here is the full solution, after some refactorings that speed it up (almost an order of magnitude) and help readability a bit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
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)
7f00244a6387413b37ee449f234ec045

Marc-Andre

October 18, 2007, October 18, 2007 00:14, permalink

No rating. Login to rate!

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

880cbab435f00197613c9cc2065b4f5a

danielharan

October 18, 2007, October 18, 2007 14:30, permalink

No rating. Login to rate!

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!

7f00244a6387413b37ee449f234ec045

Marc-Andre

October 18, 2007, October 18, 2007 18:04, permalink

2 ratings. Login to rate!

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...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
# 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

Your refactoring





Format Copy from initial code

or Cancel