2007-11-28

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

1 comentario:

Flor dijo...

Ehmm...sí, estoy en un 100% de acuerdo con TOOOOOODOOOOOOO lo que se mention above... Sólo quería saludarte,aunque sea en medio de algo que nada tiene que ver!!! Jaja. Bueno, Aure, los anormales no se rinden y seguirán...con la frente alta (????) LA pasé bárbaro el viernes con vos y la chicas (que no se malentienda jaja) Un besote y nos estamos viendo. Saludos a Agustina y a tu gato marrón! =D