51 x 10^9

Como estuve con un poquito de tiempo libre me puse a programar un toque este sábado a la noche (sí que soy divertido :p). Y encontré un problemita intereseante en el blog de una .com. El problema es el mismo que proponen en ITA para tomarte como programador.

El mismo consiste en saber cuál es la letra número 51 x 10^9 (o sea 51000000000) de la secuencia de agarrar todos los números entre 1 y 1000000000 y transformarlos en letras, saber a que número pertenece y cuanto vale la suma de todos los números por los que pasaste para llegar a esa letra desde el principio. La solución del problema es un bardo, así que no lo hice todo, pero escribí un programa para obtener la letra en la posición x en la secuencia de números que va del 1 al 1000, a qué número pertenece y cuál fue la suma acumulada hasta ahí.

Acá les pongo a continuación el enunciado del problema:

"If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?"

To be precise: if the integers from 1 to 999,999,999 are expressed in words (omitting spaces, 'and', and punctuation[1]), and sorted alphabetically so that the first six integers are

• eight
• eighteen
• eighteenmillion
• eighteenmillioneight
• eighteenmillioneighteen
• eighteenmillioneighteenthousand

and the last is

• twothousandtwohundredtwo

then reading top to bottom, left to right, the 28th letter completes the spelling of the integer "eighteenmillion".

The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point?

[1] For example, 911,610,034 is written "ninehundredelevenmillionsixhundredtenthousandthirtyfour"; 500,000,000 is written "fivehundredmillion"; 1,709 is written "onethousandsevenhundrednine".

Y este es mi programa en ruby. Una generalización trivial para correrlo con los números que vayan desde 1 a 1000000000 requeriría (según estimo) unos 100GB de espacio libre en el disco rígido, varios días de tiempo de procesamiento para correr e implementar una rutina de external sorting. Pero me parece que los números tienen suficiente estructura como para cortar camino, así que si se me ocurre algo mejor lo postiaré por acá también.

#!/usr/bin/env ruby

class Result
  attr_accessor :letters_advanced
  attr_accessor :letters_missing
  attr_accessor :sum
  attr_accessor :number

  def initialize(letters_missing=0) 
    self.letters_missing = letters_missing
    self.sum = 0
    self.letters_advanced = 0
    self.number = -1 # not set
  end

  def << (other_result)
    self.letters_advanced += other_result.letters_advanced
    self.sum += other_result.sum
    self.letters_missing -= other_result.letters_advanced
    self.number = other_result.number
  end
end

class Hundred

  attr_reader :value
  attr_reader :name
  attr_reader :next_number

  def initialize( name, value, next_number )
    @name = name
    @value = value
    @next_number = next_number
  end

  def description
    r = Result.new
    r.letters_advanced = self.name.length
    r.sum = self.value
    r.number = self.value
    r
  end

  ONES = [ "", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" ] 
  TEENS = ["ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" ]
  ORIG_TENS = [ "twenty", "thirty", "fourty", "fifty", "sixty", "seventy", "eighty", "ninety" ]
  
  tens = Array.new
  ONES.each { |n| tens << n }
  TEENS.each { |n| tens << n }
  ORIG_TENS.each do
    |ten| 
    ONES.each do
      |one|
      tens << ten + one
    end
  end
  
  TENS = tens
  
  HUNDREDS = ONES.map do 
    |hundred|
    root = hundred == "" ? "" : hundred + "hundred"
    numbers = tens.map do
      |ten|
      root + ten
    end
    numbers
  end.flatten
  
  number = 0
  NAMED_HUNDREDS = HUNDREDS.map do
    |name|
    value = { :number => number, :name => name }
    number += 1
    value
  end.sort_by { |pair| pair[:name] }.reverse

  last = nil
  NAMED_HUNDREDS.each do 
    |pair|
    last = Hundred.new(pair[:name], pair[:number], last)
  end

  @last = last

  def self.first
    @last
  end
end

position = ARGV[0].to_i
result = Result.new(position)
number = Hundred.first
while( result.letters_missing > 0 )
  result << number.description
  number=number.next_number
end

p result