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
