quiz-93 (10.3 KB)
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
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
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
···
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.
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 <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]
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]
Daniel Martin wrote:
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.
I used the attached program to check for happy bases.
$ time ruby hapnr2.rb 10000
2
4
real 1m7.279s
user 1m7.261s
sys 0m0.013s
So, there are no more happy bases up to 10000.
Regards,
Michael
hapnr2.rb (837 Bytes)
···
--
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com
---------------------------------------------------------------
This e-mail is only intended for the recipient and not legally
binding. Unauthorised use, publication, reproduction or
disclosure of the content of this e-mail is not permitted.
This email has been checked for known viruses, but ISIS accepts
no responsibility for malicious or inappropriate content.
---------------------------------------------------------------