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.

---------------------------------------------------------------