51 x 10^9 (parte 2)

En mi mi último post, mostré un problema que usan en ITA para reclutar gente. Parece que anda mal porque el resultado que encuentra no coincide con el fin de un número, como dice en el enunciado. Pero como me quedé desvelado una noche haciendolo, les mandé un mail con mi solución. Mientras tanto aprovecho y les pregunto a ustedes.

¿Le ven algún quilombo al código de abajo?

#!/usr/bin/env ruby

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

  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
    self.name = other_result.name
  end

  def to_s
    string = "name:#{name} - number:#{number} - " + 
      "letters_advanced:#{letters_advanced} - " +
      "letters_missing:#{letters_missing} - sum:#{sum}" 
    string += " - letter:#{name[name.length-1+letters_missing,1]}" if letters_missing <= 0
  end
end

class Block

  attr_reader :value
  attr_reader :name
  attr_accessor :next_block
  attr_reader :position # 0 for ones, 1 for thousands, 2 for millions

  def initialize( name, number, position )
    @name = name
    @value = number * (1000 ** position)
    @position = position
  end

  # Inserts a block somewhere after this block, hopefully close (if not, takes a long time)
  def insert_block(new_block)
    before = self
    after = self.next_block
    while( after != nil && new_block.name > after.name )
      before = after
      after = before.next_block
    end
    before.next_block = new_block
    new_block.next_block = after
  end

  def advance(min_position, max_position)
    current = self.next_block
    while !current.nil? && !current.position.between?(min_position, max_position)
      current = current.next_block
    end
    current
  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|
    new = Block.new(pair[:name], pair[:number], 0)
    new.next_block = last
    last = new
  end

  @last = last.next_block # Ignore zero

  #Add higher level blocks (thousand and millions)
  current = last
  while( current != nil ) 
    if current.position == 0 then
      current.insert_block( Block.new(current.name + "thowsand", current.value, 1) )
      current.insert_block( Block.new(current.name + "million", current.value, 2) )
    end
  
    current = current.next_block
  end

  def self.first( position=0 )
    first = @last
    while (first.position != position)
      first = first.next
    end
    first
  end
end

class Number 

  def initialize( pos2, pos1, pos0 )
    @blocks = [pos0, pos1, pos2]
  end

  def name
    @blocks.reverse.inject("") do 
      |acum, block|
      acum += block ? block.name : ""
    end
  end

  def value
    @blocks.inject(0) do
      |acum, block|
      acum += block ? block.value : 0
    end
  end

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

  def next_number(min_pos=0)
    max_pos = min_pos + 1
    while @blocks[max_pos].nil? && max_pos < 3
      max_pos += 1
    end
    max_pos -= 1
    new_block = @blocks[min_pos] ? @blocks[min_pos].advance(min_pos, max_pos) : Block.first(min_pos)
    @blocks[min_pos] = nil
    if (new_block) then
      @blocks[new_block.position] = new_block
    else #carry
      self.next_number(min_pos + 1)
    end
    self
  end

  unit_letter_count = 0
  unit_accumulated_values = 0
  block = Block.first(0)
  while( block )
    unit_letter_count += block.name.length
    unit_accumulated_values += block.value
    block = block.advance(0,0)
  end
  UNIT_LETTER_COUNT = unit_letter_count
  UNIT_ACCUMULATED_VALUES = unit_accumulated_values

  def step(result)
    
    if (@blocks[1] && !@blocks[0])
      big_step_char_count = self.name.length * 1000 + UNIT_LETTER_COUNT 
      if big_step_char_count < result.letters_missing then
        step_result = Result.new
        step_result.letters_advanced = big_step_char_count
        step_result.number = step_result.sum = self.value * 1000 + UNIT_ACCUMULATED_VALUES
        result << step_result
        self.next_number(1)
        return
      end
    end
    # Big step is not taken
    result << self.description
    self.next_number
  end

  def self.first
    self.new( nil, nil, Block.first )
  end

  def self.result( letter_position) 
    result = Result.new(position)
    number = Number.first
    while( result.letters_missing > 0 )
      result << number.description
      number=number.next_number
    end
    result
  end

end


position = ARGV[0].to_i
result = Result.new(position)
number = Number.first
count = 0
while( result.letters_missing > 0 )
  number.step(result)

  count += 1
  if (count % 100000) == 0 then
    puts "Partial result"
    p result
  end
end

puts "Final result"
puts result