[QUIZ SOLUTION] Happy Numbers (#93)

Discussion in 'Ruby' started by Rick DeNatale, Sep 6, 2006.

  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], 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/
     
    Rick DeNatale, Sep 6, 2006
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. email55555 email55555

    [SOLUTION] Ruby Quiz #14 LCD Numbers ( solution #2 )

    email55555 email55555, Jan 9, 2005, in forum: Ruby
    Replies:
    16
    Views:
    295
    David Tran
    Jan 10, 2005
  2. David Tran
    Replies:
    9
    Views:
    216
    David Tran
    Jan 21, 2005
  3. Ruby Quiz

    [QUIZ] Happy Numbers (#93)

    Ruby Quiz, Sep 1, 2006, in forum: Ruby
    Replies:
    45
    Views:
    782
    Matthew Moss
    Sep 7, 2006
  4. Daniel Martin
    Replies:
    1
    Views:
    178
    Daniel Martin
    Sep 6, 2006
  5. Glen F. Pankow

    [QUIZ SOLUTION] Happy Numbers (#93)

    Glen F. Pankow, Sep 6, 2006, in forum: Ruby
    Replies:
    3
    Views:
    252
    James Edward Gray II
    Sep 6, 2006
Loading...

Share This Page