Happy Numbers (#93)

Ruby
1

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], 

  1. 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 B. 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/