From: Rick DeNatale <rick.denatale@...>
Date: 2006-09-07T05:18:05+09:00
Subject: [QUIZ SOLUTION] Happy Numbers (#93)

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/