# [QUIZ SOLUTION] Happy Numbers (#93)

Discussion in 'Ruby' started by Glen F. Pankow, Sep 6, 2006.

1. ### Glen F. PankowGuest

--Boundary_(ID_zCkKrjF6PCaT6LJ7LbyhYQ)
Content-type: text/plain; charset=ISO-8859-1; format=flowed
Content-transfer-encoding: 7BIT

--Boundary_(ID_zCkKrjF6PCaT6LJ7LbyhYQ)
Content-type: text/plain; name=quiz-93
Content-transfer-encoding: 7BIT
Content-disposition: inline; filename=quiz-93

#! /usr/bin/ruby
#
# quiz-93 -- Ruby Quiz #93.
#
# See the Ruby Quiz #93 documentation for more information
# (http://www.rubyquiz.com/quiz93.html).
#
# 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)
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 == 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
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)
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" \
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.

--Boundary_(ID_zCkKrjF6PCaT6LJ7LbyhYQ)--

Glen F. Pankow, Sep 6, 2006

2. ### Mike DvorkinGuest

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.rubywizards.com

Mike Dvorkin, Sep 6, 2006

3. ### Simon KrögerGuest

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}
-------------------------------------------------------------------

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

Simon Kröger, Sep 6, 2006
4. ### James Edward Gray IIGuest

On Sep 6, 2006, at 4:02 AM, Simon Kr=F6ger 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 =3D [0, 4, 16, 20, 37, 42, 58, 89, 145].freeze

happy =3D Hash.new do |found, num|
digits =3D num.to_s.split("").sort.delete_if { |d| d =3D=3D "0" }
happiness =3D digits.inject(0) { |sum, d| sum + d.to_i ** 2 }
found[num] =3D if happiness =3D=3D 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

James Edward Gray II, Sep 6, 2006