Google billion'th letter

billion.rb

# 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