Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Ruby > [QUIZ SOLUTION] Happy Numbers (#93)

Reply
Thread Tools

[QUIZ SOLUTION] Happy Numbers (#93)

 
 
Rick DeNatale
Guest
Posts: n/a
 
      09-06-2006
Here's my solution.

There are arguments which control what the main program does.

-b , or --base is an integer giving the base - this defaults to 10
-t, or --time-limit is an integer giving the number of seconds to run
looking for the happiest number in a give base. This defaults to 600
seconds (10 minutes)
--levels causes an unlimited time run which prints a "happiest" number
of numbers with the same number of digits in the base. Use break to
stop this.

I cache both unhappy numbers and successful paths so that I can
short-circuit things. Not a small memory solution.

== happynumber.rb ==
#! /usr/local/bin/ruby

class Integer

def Integer.reset_happiness_cache
# Integer#to_s(base) works up to a base of 36
@@cached_unhappy_ints = Array.new(37) {|i| Hash.new }
@@cached_happiness_paths = Array.new(37) {|i| {1 => [1]}}

self.cache_unhappy([0, 4, 16, 20, 37, 42, 58, 89, 145], 10)
end

def Integer.show_hc
puts "unhappies = #{@@cached_unhappy_ints[10].inspect}"
puts "happies = #{@@cached_happiness_paths[10].inspect}"
end

def squared
self * self
end

def sum_squares_of_digits(base=10)
sum = 0
to_s(base).each_byte do |b|
sum += (b.chr.to_i(base)).squared
end
sum
end

def path_to_happiness(base=10,seen=[])
return nil if Integer.known_unhappy?(self, base)
return Integer.cache_unhappy([self], base) if
seen.include?(self)
known_path = Integer.known_happiness_path(self, base)
return known_path.dup if known_path
rest_of_the_way =
sum_squares_of_digits(base).path_to_happiness(base ,seen.dup << self)
if rest_of_the_way
ans = rest_of_the_way.unshift(self)
return Integer.cache_happiness_path(ans, base).dup
else
Integer.cache_unhappy([self], base)
return nil
end
end

def Integer.known_unhappy?(int, base)
@@cached_unhappy_ints[base][int]
end

def Integer.known_happiness_path(int, base)
@@cached_happiness_paths[ base][int]
end

def known_happy?(base)
Integer.known_happiness_path(self, base)
end

def Integer.cache_unhappy(integers, base)
integers.each do | n |
@@cached_unhappy_ints[base][n] = true
end
nil
end

def Integer.cache_happiness_path(path, base)
@@cached_happiness_paths[base][path[0]] = path.dup
path
end

def happy?
!self.path_to_happiness.nil?
end

def happiness
path = path_to_happiness
path_to_happiness ? path_to_happiness.length : 0
end

reset_happiness_cache
end


#generates all numbers in the given range whose digits are in
#nondecreasing order. the order in which the numbers are generated is
#undefined, so it's possible for 123 to appear before 23, for
#example.
# Thanks to Ken Bloom for this idea, which I generalized to an arbitrary base
#
def nondec_digits(range,base=10,&b)
yield 0 if range.first<=0
(1..base-1).each { |x| nondec_digits_internal(x,x,range,base,&b) }
end

def nondec_digits_internal(last,accum,range,base,&b)
(last..base-1).each do |x|
iaccum=accum*base+x
b.call(iaccum) if range.nil? || range.include?(iaccum)
nondec_digits_internal(x,iaccum,range,base,&b) if
iaccum <= range.last
end
end

# enumerate all numbers whose representation in base _base_
# has increasing digits.
def nondec_numbers(base, &b)
start = 0
ten_in_base = "10".to_i(base)
stop = ten_in_base
while true
nondec_digits((start..stop-1), base, &b)
start = stop
stop *= ten_in_base
end
end


def happiest_in_range(range, base=10)
happiest = 1
max_path_length = 1
probes = 0
nondec_digits(range,base) do |i|
probes += 1
path = i.path_to_happiness(base)
if path && path.length > max_path_length
happiest = i
max_path_length = path.length
end
end
[happiest, max_path_length, probes]
end

def base_levels(base=10)
ten_in_base = "10".to_i(base)
start = 0
base_n = ten_in_base
n = 1
while true
h, pl, probes = happiest_in_range((start..base_n-1), base)
puts "one of the happiest #{n} digit base #{base}
numbers is #{h.to_s(base)}, with #{pl} steps after #{probes} probes"
start = base_n
n += 1
base_n *= ten_in_base
end
end

# return the happiest number that can be found in time_limit seconds
def happiest(time_limit=60, base=10)
time_to_stop = Time.now + time_limit
happiest = 1
max_path_length = 1
probes = 0
nondec_numbers(base) do |i|
break if Time.now > time_to_stop
probes += 1
path = i.path_to_happiness(base)
if path && path.length > max_path_length
happiest = i
max_path_length = path.length
end
end

puts "happiest base #{base} number found in #{time_limit}
seconds in #{probes} probes"
puts "was #{happiest.to_s(base)} which has a happiness of
#{max_path_length}"
end


require 'optparse'
opts = OptionParser.new
base = 10
time_limit = 600 # default to 10 minutes
happiest_test = true
opts.on("-b", "--base VAL", Integer) {|val| base = val}
opts.on("--levels") {happiest_test = false}
opts.on("-t", "--time-limit VAL", Integer) {|val| time_limit = val}
opts.parse(ARGV)
happiest(time_limit, base) if happiest_test
base_levels(base) unless happiest_test


--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
OT: Happy Happy Joy Joy! Mike T. MCSE 79 11-19-2006 08:22 PM
[QUIZ SOLUTION] Happy Numbers (#93) - happy bases Daniel Martin Ruby 1 09-06-2006 07:06 PM
HEXUS.opinions :: Have a happy happy gaming holiday Silverstrand Front Page News 0 12-23-2005 04:12 PM
Happy Happy Joy Joy, I recovered my photos Tama Mativa Digital Photography 9 05-24-2004 04:58 PM
happy happy christmas showgun MCSE 26 12-17-2003 07:11 PM



Advertisments