Asp Forum - [QUIZ SOLUTION] Happy Numbers (#93

Glen F. Pankow

9/6/2006 1:35:00 AM

#! /usr/bin/ruby
#
# quiz-93 -- Ruby Quiz #93.
#
# See the Ruby Quiz #93 documentation for more information
# (http://www.rubyquiz.com/q...).
#
# I do the basic quiz, and in addition try to come up with meaningful
# unhappiness values and constuct interesting path strings. See the
# documentation to findHappiness() below for more information.
#
# Glen Pankow 09/02/06
#

# class Integer
class Fixnum

#
# Map from digit characters to the squares of integer values.
#
@@squares = { '0' => 0, '1' => 1, '2' => 4, '3' => 9, '4' => 16,
'5' => 25, '6' => 36, '7' => 49, '8' => 64, '9' => 81,
'a' => 100, 'b' => 121, 'c' => 144, 'd' => 169, 'e' => 196,
'f' => 225, 'g' => 256, 'h' => 289, 'i' => 324, 'j' => 361,
'k' => 400, 'l' => 441, 'm' => 484, 'n' => 259, 'o' => 576,
'p' => 625, 'q' => 676, 'r' => 729, 's' => 784, 't' => 841,
'u' => 900, 'v' => 961, 'w' =>1024, 'x' =>1089, 'y' =>1156,
'z' =>1225 }

#
# Return the sign of the current number. That is, return 1 for non-
# negative numbers, and -1 otherwise.
#
def sign
self >= 0? 1 : -1
end

#
# Return the sum of the squares of the digits of the current number in
# the base <base>.
#
def sqrSum(base = 10)
to_s(base).split(//).inject(0) { |sum, dig| sum += @@squares[dig] }
end

#
# Return a string representation of the current number in the base <base>.
# If the base is not decimal (and the number is not small), we tack onto
# the string representation its decimal representation in curly braces.
#
def inspect(base = 10)
return to_s(base) if ( (base == 10) || ((self >= 0) && (self < 10) && (self < base)) || ((self < 0) && (-self < 10) && (self < base)))
"#{to_s(base)}{#{to_s(10)}}"
end

end

#
# happiness = findHappiness(n, base = 10, stack = nil)
#
# Find and return the number <n>'s (un)happiness in the base <base>. <stack>
# is an optional stack of numbers in a chain of digit-square-sums (assumedly
# also computed in <base>) that lead to <n>.
#
# These globals are updated as a side effect:
# $happinesses -- [Array] the (un)happiness value for <n> indexed by <n>
# (and so forth for all subsequent numbers in the digit-square-sum chain
# created from <n>).
# $paths -- [Array] path representation string of the digit-square-sum
# chain created from <n>, indexed by <n> (and so forth ...).
# $cycledNs -- [Hash] those <n>s that form self-contained unhappy loops.
# These globals are assumed to exist (and cleared for calculations in each
# base). I.e., these or similar commands should be run prior to a new set of
# calculations:
# $happinesses = [ ]
# $happinesses[1] = 0
# $paths = [ ]
# $paths[1] = '1 (happy!)'
# $cycledNs = { }
#
# We also take pains to compute meaningful unhappiness values and to construct
# useful path strings (hence the complexity of this method). And thus, all
# (un)happiness values here are treated as counts of the number of steps needed
# before we reach 1 (happiness!) or we reach a loop (unhappy). Note that the
# count for happy numbers is one more than the rank of the number as specified
# by the Quiz.
#
# Regarding unhappiness, we want to note their values from the first number
# seen that forms a loop. This is somewhat tricky, due to the fact that these
# first numbers seen vary in shared loops created from different source numbers.
# So when we see a loop, we generate all shared forms of the loop. E.g. the
# loop [ 89 => 145 => 42 => 20 => 4 => 16 => 37 => 58 => 89 ] is equivalent to
# the loop [ 4 => 16 => 37 => 58 => 89 => 145 => 42 => 20 => 4 ] (and likewise
# for all of the other numbers seen in the loop).
#
def findHappiness(n, base = 10, stack = nil)

#
# If we've already found n's happiness, just return it.
#
return $happinesses[n] unless ($happinesses[n].nil?)

#
# Look for loops up the stack. If we find one, note its unhappiness, and
# likewise for its sister loops.
#
unless (stack.nil?)
(stack.size-2).downto(0) do |i|
if (stack[i] == n) # ooh! found a loop!!!
loopLen = i - stack.size + 1
i.upto(stack.size-2) do |j|
jN = stack[j]
$happinesses[jN] = loopLen
$paths[jN] = '[ ' + jN.inspect(base)
(j+1).upto(stack.size-2) { |k|
$paths[jN] << ' => ' << stack[k].inspect(base) }
(stack.size-1).upto(j-loopLen) { |k|
$paths[jN] << ' => ' << stack[k+loopLen].inspect(base) }
$paths[jN] << ' ]'
$cycledNs[jN] = true
end
return loopLen
end
end
end

#
# Our happiness depends on the happiness of the next digit-square-sum in
# the chain. Push ourself on the stack and recurse if the next happiness
# isn't yet known.
#
nextN = n.sqrSum(base)
nextHappiness = $happinesses[nextN]
if (nextHappiness.nil?)
stack = [ ] if (stack.nil?) ; stack << n
nextHappiness = findHappiness(nextN, base, stack)
return $happinesses[n] unless ($happinesses[n].nil?)
end

#
# And increment/decrement the happiness value from the next in the chain.
#
if (nextHappiness == 0) # happy?
$happinesses[n] = 1
$paths[n] = n.inspect(base) + ' -> 1 (happy!)'
else
$happinesses[n] = nextHappiness + nextHappiness.sign
# if ($cycledNs.has_key?(nextN))
# $paths[n] # = "#{n.inspect(base)} -> #{nextN.inspect(base)} [loops!]"
# else
$paths[n] = n.inspect(base) + ' -> ' + $paths[nextN]
# end
end
$happinesses[n]
end

# 2.upto(36) do |base|
10.upto(10) do |base|
# maxN = base * base
maxN = 100000
print "\nFor the base #{base}, 1 <= n <= #{maxN}:\n"
$happinesses = [ ]
$happinesses[1] = 0
$paths = [ ]
$paths[1] = '1 (happy!)'
$cycledNs = { }
happiestN = 0
happiestHappiness = 0
saddestN = 0
saddestHappiness = 0
numHappies = 0
numUnhappies = 0
(1..maxN).each do |n|
happiness = findHappiness(n, base)
printf "%9s (happiness %3d) -> %s\n",
n.inspect(base), happiness, $paths[n]
numHappies += 1 if (happiness >= 0)
numUnhappies += 1 if (happiness < 0)
happiestN, happiestHappiness = n, happiness if (happiness > happiestHappiness)
saddestN, saddestHappiness = n, happiness if (happiness < saddestHappiness)
end
print "For the base #{base} (numbers 1..#{maxN.inspect(base)}):\n" " We saw #{numHappies} happy numbers and #{numUnhappies} unhappy ones.\n"
print " *** ALL HAPPY ***\n" if (numUnhappies == 0)
print " !!! ALL UNHAPPY !!!\n" if (numHappies == 0)
print " The happiest number is #{happiestN.inspect(base)}" " with a happiness rank of #{happiestHappiness-1}!\n" " #{happiestN.inspect(base)}: #{$paths[happiestN]}\n" if (numHappies > 0)
# Note: we say happiestHappiness-1 here to convert from my happiness
# count (number of steps to 1) and the Quiz' rank (number of numbers
# between n and 1).
print " The saddest number is #{saddestN.inspect(base)}" " with a happiness rank of #{saddestHappiness}!\n" " #{saddestN.inspect(base)}: #{$paths[saddestN]}\n" if (numUnhappies > 0)
# if (numUnhappies > 0)
# print " The unhappy cycles seen:\n"
# $cycledNs.keys.sort.each do |n|
# printf " %8s is a cycle: %s\n", n.inspect(base), $paths[n]
# end
# end
end

#
# Sample output:
#
# For the base 5, 1 <= n <= 25:
# 1 (happiness 0) -> 1 (happy!)
# 2 (happiness -3) -> 2 -> [ 4 => 31{16} => 4 ]
# 3 (happiness -4) -> 3 -> 14{9} -> 32{17} -> [ 23{13} => 23{13} ]
# 4 (happiness -2) -> [ 4 => 31{16} => 4 ]
# 10{5} (happiness 1) -> 10{5} -> 1 (happy!)
# 11{6} (happiness -4) -> 11{6} -> 2 -> [ 4 => 31{16} => 4 ]
# 12{7} (happiness 2) -> 12{7} -> 10{5} -> 1 (happy!)
# 13{8} (happiness -4) -> 13{8} -> 20{10} -> [ 4 => 31{16} => 4 ]
# 14{9} (happiness -3) -> 14{9} -> 32{17} -> [ 23{13} => 23{13} ]
# 20{10} (happiness -3) -> 20{10} -> [ 4 => 31{16} => 4 ]
# 21{11} (happiness 2) -> 21{11} -> 10{5} -> 1 (happy!)
# 22{12} (happiness -5) -> 22{12} -> 13{8} -> 20{10} -> [ 4 => 31{16} => 4 ]
# 23{13} (happiness -1) -> [ 23{13} => 23{13} ]
# 24{14} (happiness -4) -> 24{14} -> 40{20} -> [ 31{16} => 4 => 31{16} ]
# 30{15} (happiness -4) -> 30{15} -> 14{9} -> 32{17} -> [ 23{13} => 23{13} ]
# 31{16} (happiness -2) -> [ 31{16} => 4 => 31{16} ]
# 32{17} (happiness -2) -> 32{17} -> [ 23{13} => 23{13} ]
# 33{18} (happiness -1) -> [ 33{18} => 33{18} ]
# 34{19} (happiness 2) -> 34{19} -> 100{25} -> 1 (happy!)
# 40{20} (happiness -3) -> 40{20} -> [ 31{16} => 4 => 31{16} ]
# 41{21} (happiness -3) -> 41{21} -> 32{17} -> [ 23{13} => 23{13} ]
# 42{22} (happiness -4) -> 42{22} -> 40{20} -> [ 31{16} => 4 => 31{16} ]
# 43{23} (happiness 2) -> 43{23} -> 100{25} -> 1 (happy!)
# 44{24} (happiness -6) -> 44{24} -> 112{32} -> 11{6} -> 2 -> [ 4 => 31{16} => 4 ]
# 100{25} (happiness 1) -> 100{25} -> 1 (happy!)
# For the base 5 (numbers 1..100{25}):
# We saw 7 happy numbers and 18 unhappy ones.
# The happiest number is 12{7} with a happiness rank of 1!
# 12{7}: 12{7} -> 10{5} -> 1 (happy!)
# The saddest number is 44{24} with a happiness rank of -6!
# 44{24}: 44{24} -> 112{32} -> 11{6} -> 2 -> [ 4 => 31{16} => 4 ]
#
# For the base 10 (numbers 1..100000):
# ...
# We saw 14377 happy numbers and 85623 unhappy ones.
# The happiest number is 78999 with a happiness rank of 6!
# 78999: 78999 -> 356 -> 70 -> 49 -> 97 -> 130 -> 10 -> 1 (happy!)
# The saddest number is 15999 with a happiness rank of -19!
# 15999: 15999 -> 269 -> 121 -> 6 -> 36 -> 45 -> 41 -> 17 -> 50 -> 25
# -> 29 -> 85 -> [ 89 => 145 => 42 => 4 => 16 => 37 => 58 => 89 ]
#
### No bases in 2..36 other than 2 and 4 were happy.

6 Answers

Mike Dvorkin

9/6/2006 5:11:00 AM

Here's my quick version of happy? method that uses recursion to count
sums and static hash to test for infinity:

class Integer
@@found = {}
def happy?
sum = 0
self.to_s.scan(/./u) { |c| sum += c.to_i ** 2 }
sum == 1 || @@found[sum] ? 1 : (@@found[sum] = 1; sum.happy?)
end
end

puts 1234567890.happy? # => 1

Thanks for the quiz!

Best,
Mike Dvorkin
http://www.rubyw...

Simon Kröger

9/6/2006 9:03:00 AM

Well, here is my version:

-------------------------------------------------------------------
happy = Hash.new do |h, k|
sum = k.to_s.split('').inject(0) {|s, i| s + i.to_i * i.to_i}
sum != 1 ? (h[k] = 0) : (next h[k] = 1)
h[k] = (h[sum.to_s.split('').sort.join.to_i].nonzero? || -1) + 1
end

puts (1..100000).max {|a, b| happy[a] <=> happy[b]}
-------------------------------------------------------------------

I just posted it because i didn't saw a solution using the block
form of Hash.new yet. (But i have to admit i haven't read all the
solutions...)

This version calculates the happiest number between 1 and 100000
(78999) in 7s on my laptop.

cheers

Simon

James Gray

9/6/2006 2:13:00 PM

On Sep 6, 2006, at 4:02 AM, Simon Kröger wrote:

> I just posted it because i didn't saw a solution using the block
> form of Hash.new yet.

My own solution, inspired by Simon's:

#!/usr/bin/env ruby -w

UNHAPPY = [0, 4, 16, 20, 37, 42, 58, 89, 145].freeze

happy = Hash.new do |found, num|
digits = num.to_s.split("").sort.delete_if { |d| d == "0" }
happiness = digits.inject(0) { |sum, d| sum + d.to_i ** 2 }
found[num] = if happiness == 1
true
elsif UNHAPPY.include? happiness
false
else
found[happiness]
end
end

(1..100_000).each { |n| p n if happy[n] }

__END__

James Edward Gray II

Daniel Martin

9/6/2006 2:57:00 PM

Here's my solution to find happy bases - note that I don't find any
happy bases (aside from 2 and 4) before I run out of memory, somewhere
near base 1700. It wouldn't surprise me if no other happy bases
exist.

The program checks up to 2*(base-1)*(base-1) for numbers that fall
into an infinite loop (that is not '1' forever) when applying the
digit-square-sum function. This is all that's needed, as it can
easily be shown that any number will eventually get less than that.

There's almost certainly some stuff I could do to be more parsimonious
with memory, chief among them finding a copy of narray that has the
mod! method. (I may revisit this and use a combination of div!, mul!
and sbt! to cut down on temporary arrays) However, this program as it
stands very quickly checks much farther out than I would have thought
necessary if there really were other happy bases out there to be
found.

#!/usr/bin/env ruby
require 'narray'

def dodigsum(base, initial)
tmp = initial / (base ** NArray.to_na([[0],[1],[2]]))
# I would use mod!, but my copy of narray doesn't have mod!
tmp = tmp % base
tmp.mul!(tmp)
initial.fill!(0).add!(tmp.sum(1))
end

def checkbase(base = 10)
base = base.to_i
checklimit = 2*(base-1)*(base-1)
check = NArray.int(checklimit + 1).indgen!
check_initial = check.dup

while true do
dodigsum(base,check)
if check.eq(check_initial).count_true > 2
#Gobs of debugging info
# lp = check.mul!(check.eq(check_initial)).mask(check.ge(2)).min
# puts "#{base} has a loop on #{lp}"
break
end
if check.le(1).count_true > checklimit
puts "#{base} is a happy base"
break
end
end
end

2.upto(3000) { |b|
begin
checkbase(b)
rescue Interrupt
puts "Checking #{b}"
checkbase(b)
rescue Error => e
puts "Bailing on #{b}"
raise e
end
}

__END__

--
s=%q( Daniel Martin -- martin@snowplow.org
puts "s=%q(#{s})",s.map{|i|i}[1] )
puts "s=%q(#{s})",s.map{|i|i}[1]

Daniel Martin

9/6/2006 6:11:00 PM

Daniel Martin <martin@snowplow.org> writes:

> Here's my solution to find happy bases - note that I don't find any
> happy bases (aside from 2 and 4) before I run out of memory, somewhere
> near base 1700. It wouldn't surprise me if no other happy bases
> exist.

And here's a faster version, and I also corrected the "Error" to
"Exception" mistake I'd made in my earlier version. This version
makes it through bases 2 - 100 in the blink of an eye, but really
starts to slow down around base 700.

I haven't had a chance to run this one as far as it can go without
running out of memory; maybe later today.

Still haven't found any other happy bases...

#! /usr/bin/env ruby
require 'narray'

def dodigsum(initial, base)
tmp = initial / (base ** NArray.to_na([[0],[1],[2]]))
# I would use mod!, but my copy of narray doesn't have mod!
tmp = tmp % base
tmp.mul!(tmp)
initial.fill!(0).add!(tmp.sum(1))
end

def checkbase(base = 10)
# As shown on the list, you're guaranteed that eventually every
# number will be two digits or less, and once there the highest
# you'll ever get again is...
checklimit = 2*(base-1)*(base-1)
check = NArray.int(checklimit + 1).indgen!
check_initial = check.dup
dodigsum(check,base)
checkp = check.dup

while true do
if check.eq(check_initial).count_true > 2
#lp = check.mul!(check.eq(check_initial)).mask(check.ge(2)).min
#puts "#{base} has a loop on #{lp}"
print (base % 100 > 0 ? "." : "x")
break
end
if check.le(1).count_true > checklimit
puts "#{base} is a happy base"
break
end
check[0] = check[checkp]
end
end

2.upto(3000) { |b|
begin
checkbase(b)
GC.start if (b > 300 and b % 5 == 0)
sleep(1) if (b % 100 == 0)
rescue Interrupt
puts "Checking #{b}"
checkbase(b)
rescue Exception => e
puts "Bailing on #{b}"
raise e
end
}

__END__

--
s=%q( Daniel Martin -- martin@snowplow.org
puts "s=%q(#{s})",s.map{|i|i}[1] )
puts "s=%q(#{s})",s.map{|i|i}[1]

Daniel Martin

9/6/2006 7:07:00 PM

And here's my narray-based solution to find the happiest number under
1_000_000 - it's not the shortest solution I've seen, but it's pretty
fast. It eliminates numbers that end up in loops by setting all
looping numbers to 0.

#!/usr/bin/env ruby
require 'narray'

def dodigsum(initial, base)
ndigits = (Math.log(initial.max)/Math.log(base)).ceil
tmp = initial / (base ** NArray.to_na((0...ndigits).map{|x|[x]}))
tmp = tmp % base
tmp.mul!(tmp)
initial.fill!(0).add!(tmp.sum(1))
end

limit = ARGV[0] || 1_000_000
base = ARGV[1] || 10

limit = limit.to_i
base = base.to_i

check = NArray.int(limit + 1).indgen!
check_initial = check.dup
check_initial[1] = 0
dodigsum(check, base)
checkp = check.dup

onemask = check.eq(1)
# onemask now contains the location of "0 order" happy numbers
order = 0
found_ex = nil
while (check.ge(2).count_true > 0) do
check.mul!(check.ne(check_initial))
check = check[checkp]
newmask = check.eq(1)
order = order + 1
if (not newmask == onemask)
found_ex = [newmask.gt(onemask).where.min, order]
end
onemask = newmask
end
puts "Happiest is #{found_ex[0]}, with happiness order #{found_ex[1]}"
__END__

--
s=%q( Daniel Martin -- martin@snowplow.org
puts "s=%q(#{s})",s.map{|i|i}[1] )
puts "s=%q(#{s})",s.map{|i|i}[1]

comp.lang.ruby

[QUIZ SOLUTION] Happy Numbers (#93

Glen F. Pankow

Mike Dvorkin

Simon Kröger

James Gray

Daniel Martin

Daniel Martin

Daniel Martin

x Login to ForumsZone