Happy Numbers
July 23, 2010
Over at SteamCode, Scott LaBounty suggests that writing a program to compute the happy numbers less than n makes a good interview question. According to Wikipedia:
A happy number is defined by the following process. Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers (or sad numbers).
For example, 7 is a happy number, as 72=49, 42+92=16+81=97, 92+72=81+49=130, 12+32+02=1+9+0=10, and 12+02=1+0=1. But 17 is not a happy number, as 12+72=1+49=50, 52+02=25+0=25, 22+52=4+25=29, 22+92=4+81=85, 82+52=64+25=89, 82+92=64+81=145, 12+42+52=1+16+25=42, 42+22=16+4=20, 22+02=4+0=4, 42=16, 12+62=1+36=37, 32+72=9+49=58, and 52+82=25+64=89, which forms a loop.
Your task is to write a function to identify the happy numbers less than a given limit; you should work at the level of a programming interview, taking no more than about fifteen minutes, and giving a short explanation of your work to the interviewer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
My Haskell solution (see http://bonsaicode.wordpress.com/2010/07/23/programming-praxis-happy-numbers/ for a version with comments):
isHappy :: (Read a, Integral a) => a -> Bool isHappy = f [] where f _ 1 = True f xs n = notElem n xs && f (n:xs) (sum . map (^ 2) $ digits n) digits = map (read . return) . show happyUpto :: (Read a, Integral a) => a -> [a] happyUpto n = filter isHappy [1..n - 1]let digits =
let rec go l n =
if n = 0 then l else
go (n mod 10 :: l) (n / 10)
in go []
let sumsqdig = List.fold_left (fun s d -> s + d*d) 0 % digits
let fixpoint f x =
let rec go x y = if x = y then x else go (f (f x)) (f y)
in go (f x) x
let is_happy n = fixpoint sumsqdig n = 1
Decided to maintain state so that future calls can rely on the calculations of earlier calls.
import math class happy: happy = set([1]) nothappy = set() def _sum_of_char_squares(self, i): total = 0 for c in str(i): total = total + math.pow(int(c),2) return int(total) def get_happy_lt_max(self, max): newhappy = set() potential = set() for i in range(2, max): if i in self.happy: newhappy.add(i) continue if i in self.nothappy: continue potential.clear() potential.add(i) current = self._sum_of_char_squares(i) while current not in self.happy \ and current not in self.nothappy \ and current not in potential: potential.add(current) current = self._sum_of_char_squares(i) potential.add(current) if current in self.happy: map(self.happy.add, potential) newhappy.add(i) else: map(self.nothappy.add, potential) return sorted(newhappy) h = happy() h.get_happy_lt_max(2000)Bad whitespace removing function, bad.
[ I fixed your previous comment. See the instructions in the HOWTO at the top of the page so you can do it yourself next time. PP]
Thanks for the fix. I also introduced a bug; line 31 should be sum of (current), not (i). Ability to edit comments would be really nice, since I saw the FAQ on code posting after I messed up my code :)
[…] July 23, 2010 jchiu1106 Leave a comment Go to comments The problem was posted on Programming Praxis. The algorithm itself is pretty straightforward, anyone can do it with a few if/else/fors, but to […]
My Scala version: http://reminiscential.wordpress.com/2010/07/23/finding-happy-numbers-using-scala/
object Happy { import annotation.tailrec @tailrec def isHappyNumber(n:Int, limit:Int, numOfTries:Int, alreadySeen:Set[Int]):Boolean = { val sos = ((n.toString.toCharArray.map { digit => Math.pow(Integer.valueOf("" + digit).doubleValue, 2) }).foldLeft(0.0) { _ + _ }).toInt if (sos == 1) return true else return !alreadySeen.contains(sos) && numOfTries+1 <= limit && isHappyNumber(sos, limit, numOfTries+1, alreadySeen+sos) } def isHappyNumber(n:Int):Boolean = isHappyNumber(n, 10, 0, Set[Int]()) def main(args:Array[String]) { println (1 to 100 filter { isHappyNumber(_) }) } }[…] Todays problem had to do with Happy Numbers. […]
(define (happy? n) ;; use minimal state hare and tortoise algorithm (define (next n) (sum (map square (digits n)))) (let loop ((tortoise n) (hare (next n))) (or (= tortoise 1) (and (not (= tortoise hare)) (loop (next tortoise) (next (next hare)))))))There are 143,070 happy numbers less than 1,000,000.
#!/usr/bin/env python # _ _ _ ___ _____ __ # | || | /_\ | _ \ _ \ \ / / # | __ |/ _ \| _/ _/\ V / # |_||_/_/ \_\_| |_| |_| # # a program to find all the happy numbers less than N # inspired by a challenge on programming praxis # import sys def sum_digits_squared(n): s = 0 while n > 0: n, m = n // 10, n % 10 s = s + m * m return s def is_happy(n): n0, n1 = n, n while True: n0 = sum_digits_squared(n0) if n0 == 1: return True n1 = sum_digits_squared(n1) n1 = sum_digits_squared(n1) if n0 == n1: return False happy = filter(lambda x : is_happy(x), range(int(sys.argv[1]))) for h in happy: print hHmmm. Some spaces/tabs got mucked up there. One more try:
#!/usr/bin/env python # _ _ _ ___ _____ __ # | || | /_\ | _ \ _ \ \ / / # | __ |/ _ \| _/ _/\ V / # |_||_/_/ \_\_| |_| |_| # # a program to find all the happy numbers less than N # inspired by a challenge on programming praxis # import sys def sum_digits_squared(n): s = 0 while n > 0: n, m = n // 10, n % 10 s = s + m * m return s def is_happy(n): n0, n1 = n, n while True: n0 = sum_digits_squared(n0) if n0 == 1: return True n1 = sum_digits_squared(n1) n1 = sum_digits_squared(n1) if n0 == n1: return False happy = filter(lambda x : is_happy(x), range(int(sys.argv[1]))) for h in happy: print hI was hoping I’d be the first to use this particular “cycle detector”, but I see that Gambiteer and Giovanni both beat me to the punch. Quel dommage.
Mark: And 12005034444292997293 less than 10^20. See A068571.
To see such concise implementations in languages like Scala and Haskell is humbling. Awesome, guys! A “larger” Java solution can be seen here.
use v6;
sub n($num){
[+] $num.split(”).map: * ** 2
}
sub isHappy($num){
my @seen;
for $num, {n($^a)} … * {
when any(@seen) { return False }
when 1 { return True }
@seen.push($_);
}
}
sub happyTo($num){
[1 ..^ $num].grep: {isHappy($^a)}
}
say happyTo(50).perl;
Oops. Didn’t realize there was magic to formatting submissions. Let’s see how cpp formats it.
use v6; sub n($num){ [+] $num.split('').map: * ** 2 } sub isHappy($num){ my @seen; for $num, {n($^a)} ... * { when any(@seen) { return False } when 1 { return True } @seen.push($_); } } sub happyTo($num){ [1 ..^ $num].grep: {isHappy($^a)} } say happyTo(50).perl;In Redcode, but it took closer to 30 minutes:
org newcand base equ 10 limit equ 100 tries equ 50 stack dat 0 happy dat 1 cand dat 0 total dat 0 repeat dat 0 newcand mov.ba happy, cand mov #tries, repeat again mov #-1, total digits mov.ab cand, cand mod #base, cand div.a #base, cand mul.b cand, cand add.b cand, total jmn.a digits, cand jmz found, total mov.ba total, cand add.a #1, cand djn again, repeat nexthap seq #limit, happy jmp newcand, >happy dat 0 found mov.b happy, <stack writen mov.b @stack, <stack div #10, >stack mod #10, @stack add #48, @stack jmn writen, <stack add #1, stack wloop sts >stack, 0 jmn wloop, stack sts.a #10, 0 jmp nexthapHere’s the shorter version I made in Python. Similar to other ones already posted, but uses a dictionary (hash) instead of a set for the sequence generated from n (still maintains constant search time, though).
A longer, well-documented version with multiple definitions of is_happy() is available on codepad.org here.
def is_happy(n): n_sequence = {n : 1} while n != 1: n = sum(pow(x,2) for x in _digits(n)) if n in n_sequence: return False n_sequence[n] = 1 return True def _digits(n): if n == 0: return [0] res = [] while n != 0: res.append(n % 10) n //= 10 return res for h in [x for x in xrange(1, 100) if is_happy(x)]: print h// took a LOT of time
// and also copied filter and sys stuff
// from others here
import sys
def sumSqrs( num ):
retVal = 0
while num:
retVal += pow( num % 10, 2 )
num /= 10
return retVal
def isHN( num ):
d = {}
while num != 1:
num = sumSqrs( num )
if num in d:
return False
d[ num ] = True
return True
def HN( num ):
l = []
for i in range( 1, num ):
if isHN( i ):
l.append( i )
print l
return l
def HNUsingFilter( num ):
l = filter(lambda n: isHN(n), range( 1, num ) )
print l
return l
if __name__ == ‘__main__’:
HN( int( sys.argv[ 1 ] ) )
// sorry about the formatting
// my first post @programmingpraxis
// took a LOT of time
// and also copied filter and sys stuff
// from others here
import sys
def sumSqrs( num ):
retVal = 0
while num:
retVal += pow( num % 10, 2 )
num /= 10
return retVal
def isHN( num ):
d = {}
while num != 1:
num = sumSqrs( num )
if num in d:
return False
d[ num ] = True
return True
def HN( num ):
l = []
for i in range( 1, num ):
if isHN( i ):
l.append( i )
print l
return l
def HNUsingFilter( num ):
l = filter(lambda n: isHN(n), range( 1, num ) )
print l
return l
if __name__ == ‘__main__’:
HN( int( sys.argv[ 1 ] ) )
// sorry for the mistakes in formatting
// trying one more time….
// please delete the previous posts
// took a LOT of time
// and also copied filter and sys stuff
// from others here
import sys def sumSqrs( num ): retVal = 0 while num: retVal += pow( num % 10, 2 ) num /= 10 return retVal def isHN( num ): d = {} while num != 1: num = sumSqrs( num ) if num in d: return False d[ num ] = True return True def HN( num ): l = [] for i in range( 1, num ): if isHN( i ): l.append( i ) print l return l def HNUsingFilter( num ): l = filter(lambda n: isHN(n), range( 1, num ) ) print l return l if __name__ == ‘__main__’: HN( int( sys.argv[ 1 ] ) )The ability to switch between treating Perl variables as strings and numbers is a neat parlor trick.
sub is_happy { my ($number) = $@; my %seen = (); while ($number != 1 && ! $seen{$number}) { $seen{$number} = 1; my $next = 0; $next += $_**2 foreach split //, $number; $number = $next; } return $number == 1; } for my $i (1 .. $ARGV[0]) { print "$i\n" if is_happy($i); }A JavaScript version… Short, no tricks, easy to understand. Took me ’bout 15 minutes, mostly because of the syntax in JS…
function isHappyNumber(n, limit) { var sum = 0, i = 0; while(i < limit) { sum = 0; for(var j=0; j < String(n).length; j++) { n_pos_j = parseInt(String(n)[j]); sum += (n_pos_j * n_pos_j); } n = parseInt(sum); if (n == 1) return true; i++; } return false; } alert(isHappyNumber(17,100));Here’s a Common Lisp version with a bit of memoization. It looks a bit long now that I’ve seen the other solutions… probably took me 30 minutes.
(defun cheer (n) (multiple-value-bind (rest digit) (floor n 10) (+ (square digit) (if (zerop rest) 0 (cheer rest))))) (let^ (cyclic '()) (defun recycle () cyclic) (defun happy (n) (labels ((helper (i history) (let^ (next (cheer i)) (cond ((member next cyclic) nil) ((= 1 next) t) ((member next history) (setff union cyclic history) ;(setff sort cyclic #'<) nil) (t (helper next (cons next history))))))) (helper n (list n))))) (iter (for i from 1 to 1000) (when (happy i) (collect i)))This is the java version that i have wrote:
public abstract class HappyNumbers {
public static ArrayList TRIED_NUMBERS;
public static void main(String args[]) {
System.out.println("HAPPY NUMBERS");
for(int i = 0; i < 10000; i++) {
TRIED_NUMBERS = new ArrayList();
if(isHappy(i, 0)) {
System.out.println("The number is happy : " + i);
}
}
}
public static boolean isHappy(int p_nNumber, int p_nTries) {
TRIED_NUMBERS.add(new Integer(p_nNumber));
int nSums = 0;
while(p_nNumber > 0) {
int nSquare = p_nNumber % 10;
nSquare *= nSquare;
nSums += nSquare;
p_nNumber /= 10;
}
if(nSums == 1) {
return true;
} else {
if(TRIED_NUMBERS.contains(new Integer(nSums))){
return false;
} else {
return isHappy(nSums, p_nTries + 1);
}
}
}
}
Clojure naive version. Tested against list of known Happy numbers below 500, found at http://en.wikipedia.org/wiki/Happy_number.
(defn split-digits [n] (if (< n 10) (seq [n]) (map (fn [x] (Integer/parseInt (str x))) (seq (str n)) ))) (defn sum-pow-digits [seq] (let [pows (map (fn [x] (Math/pow x 2)) seq)] (int (apply + pows)) )) (defn seq-has-num? [seq num] (some (fn [x] (= x num)) seq)) (defn happy-number? [n] (loop [seen '() n n] (cond (= n 1) true ;; it forms the closing loop (seq-has-num seen n) false :else (recur (cons n seen) (sum-pow-digits (split-digits n))) ) ) )A bit improved version of Mark VandeWettering.
function is_happy(x) function step(x) local s = 0, d; while x > 0 do d = math.floor(x % 10); x = math.floor(x / 10); s = s + d * d; end return s; end local x1, x2 = x, x; while true do x1 = step(x1); x2 = step(step(x2)); if 1 == x2 then return true; end if x1 == x2 then return false; end end endAlright, I have done this, too.
Implemented in Java. Granted, I am not entirely sure if I went overboard or not, as I ended up with 3 classes in total. However, each of theses classes is pretty short and to the point, so that is quite nice again :)
In more detailed fashion, I have an iterator which implements the sequence of numbers starting at a certain number. This is consistent with what others did, like generators in python or lazy lists in haskell. I have a second class, which overall performs the check if a sequence cycles or stops. I put this in a separate class, because that allowed me to keep everything I need for this algorithm in attributes, which cuts down the boilerplate of parameters, which is kinda nice, I guess. The third class is just a tiny class to tie everything together into a nice package.
Anyway, stats:
– Used about 40 minutes in total, 30 minutes writing precise unit tests, and 10 minutes actually programming everything.
– 200 loc in java (with comments)
– almost 100% test coverage (could not bother to check that remove really throws an error on the iterator ;) )
After talking to the folks on #perl6 I cleaned up the perl6 version to make it a little more idiomatic and to add manual memoizing. The new version is about 30% longer because of the memoizing, but it runs in 1/3 of the time.
use v6; sub n($num){ [+] $num.comb(/\d/).map: * ** 2 } my $happy = 1; my $unhappy = 0; sub isHappy($num){ my $seen = 0; for $num, &n ... * { when any($unhappy, $seen) { $unhappy |= $seen; return False; } when $happy { $happy |= $seen; return True; } $seen |= $_; } } sub happyTo($num){ [1 ..^ $num].grep: &isHappy } happyTo(50).perl.say;;; Common Lisp, with memoization and a hack (knowing that all loops necessarily go through the number 4)
(defparameter *memo* (make-hash-table))
(defun happy (n &optional (it 50) (seen ‘()) (now n))
(let ((the-sum (loop for d across (write-to-string n)
sum (expt (parse-integer (string d)) 2))))
(cond
((or (= 1 the-sum) (eq t (gethash the-sum *memo*)))
(dolist (elt seen) (setf (gethash elt *memo*) t))
now)
((or (zerop it) (= 4 the-sum) (eq ‘nope (gethash the-sum *memo*)))
(dolist (elt seen) (setf (gethash elt *memo*) ‘nope)))
(t (happy the-sum (1- it) (cons the-sum seen) now)))))
(defun main (&optional (up-to 500) (it 50))
(loop for n from 1 to up-to when (happy n it) collect n))
A naive ruby version.
class Fixnum def digits if self >= 10 (self / 10).digits << self % 10 else [self] end end def square self * self end def happy_number?(seen = []) product = digits.map(&:square).sum return true if product == 1 return false if seen.include?(product) product.happy_number?(seen << product) end end class Array def sum self.inject(0){|sum, n| sum + n} end end def happy_numbers_upto(n) (1..n).select{|n| n.happy_number? } end p happy_numbers_upto(50)my c++ solution:
#include <iostream> #include <bitset> using namespace std; bool is_happy_number (int x) { bitset<100000> founds; int itr = x; do { founds.set(itr); int num = 0; while (itr) { int factor = itr % 10; num += factor * factor; itr /= 10; } itr = num; } while (itr != 1 && !founds.test(itr)); if (itr == 1) return true; else return false; } int main(int argc, char *argv[]) { int input; while (cin >> input) cout << boolalpha << is_happy_number (input) << endl; return 0; }A different Clojure implementation, tested against Wikipedia’s list of happy numbers under 500.
(defn char-to-int [c] (- (int c) (int \0))) (defn to-num-seq [n] (map char-to-int (seq (str n)))) (defn happy? ([n] (happy? n {})) ([n hist] (let [sum (apply + (map #(* % %) (to-num-seq n)))] (cond (= 1 sum) true (hist sum) false :default (recur sum (assoc hist sum true)))))) (defn happies [n] (filter happy? (range 1 (inc n))))I wrote a version in Factor and blogged about it:
http://re-factor.blogspot.com/2010/08/happy-numbers.html
[…] (mostly numeric ones) to be solved in any programming language. I was implementing the solution for Happy Numbers and something strange happened, first let’s see my Ruby […]
Hi, as I do much Emacs Lisp these days, here’s it (30 mins)
;;; happy-numbers.el — Dimitri Fontaine
;;
;; https://programmingpraxis.com/2010/07/23/happy-numbers/
;;
(require ‘cl) ; subseq
(defun happy? (&optional n seen)
“return true when n is a happy number”
(interactive)
(let* ((number (or n (read-from-minibuffer “Is this number happy: “)))
(digits (mapcar ‘string-to-int (subseq (split-string number “”) 1 -1)))
(squares (mapcar (lambda (x) (* x x)) digits))
(happiness (apply ‘+ squares)))
(cond ((eq 1 happiness) t)
((memq happiness seen) nil)
(t (happy? (number-to-string happiness)
(push happiness seen))))))
(defun find-happy-numbers (&optional limit)
“find all happy numbers from 1 to limit”
(interactive)
(let ((count (or limit (read-from-minibuffer “List of happy numbers from 1 to: “)))
happy)
(dotimes (n (string-to-int count))
(when (happy? (number-to-string (1+ n)))
(push (1+ n) happy)))
(nreverse happy)))
ELISP> (happy? “7”)
t
ELISP> (happy? “17”)
nil
ELISP> (find-happy-numbers “50”)
(1 7 10 13 19 23 28 31 32 44 49)
Oh, and the plain SQL version too, thanks to PostgreSQL.
http://tapoueh.org/articles/blog/_Happy_Numbers.html
A couple of ruby versions which are closer to what a ruby programmer actually would write. The first looping and the second recursive. Should perhaps be methods on the integer class though.
def happy?(n)
seen={}
begin
seen[n] = true
n = n.to_s.each_char.map { |x| x.to_i ** 2 }.reduce { |x,y| x + y }
end until seen[n]
return n == 1
end
def happy?(n, seen={})
sum = n.to_s.each_char.map { |x| x.to_i ** 2 }.reduce { |x,y| x + y }
return true if n == 1
return false if seen[sum]
seen[sum] = true
return happy?(sum, seen)
end
Javascript version that shares unhappy numbers between calls to `is_happy`
function is_happy(/*integer*/n, /*?object?*/unhappy) { var visited = {}; unhappy = unhappy || {}; var n0 = n; while (true) { n = iter( n ); if (n === 1) return true; if (visited[n] || unhappy[n]) { unhappy[n0] = true; return false; } visited[n] = true; } function iter(n) { var ret = 0; while (n) { var p = n % 10; ret += p * p; n = (n / 10) >> 0; } return ret; } } function find_happy(n) { var ret = [], unhappy = {}; for (var a = 1; a <= n; a++) if (is_happy(a, unhappy)) ret.push(a); return ret; } console.log( find_happy(100).join(' ')); // 1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 94 97 100This is my Python version. Is it ok?
def happynumber(n, lst): total = sumofsquareofdigits(n) if total == 1: return True elif lst.__contains__(total): return False lst.append(total) return happynumber(total, lst) def sumofsquareofdigits(n): return sum([int(data) * int(data) for data in str(n)])sorry I missed the inputs:
Forth version, works in current BASE.
: sumsqd ( n1 -- n2 ) 0 swap BEGIN ?dup WHILE base @ /mod >r dup * + r> REPEAT ; : happy? ( n -- ? ) dup sumsqd BEGIN 2dup <> WHILE swap sumsqd swap sumsqd sumsqd REPEAT drop 1 = ; 23 happy? . -1 ok 27 happy? . 0 okand a Java solution:
import java.util.HashSet;
import java.util.Set;
public class HappyNumber {
String str;
Set checkedValues = new HashSet();
int sum = 0;
public void printHappyNumbers(int limit) {
for (int i = 1; i <= limit; i++) {
checkedValues = new HashSet();
if (isHappy(i))
System.out.println(i);
}
}
public boolean isHappy(int value) {
sum = 0;
str = Integer.toString(value);
for (int i = 0; i < str.length(); i++) {
sum = sum
+ (int) Math.pow(Character.getNumericValue(str.charAt(i)),
2);
}
if (sum == 1) {
return true;
} else if (checkedValues.contains(sum)) {
return false;
} else {
checkedValues.add(sum);
return isHappy(sum);
}
}
public static void main(String[] args) {
HappyNumber hn = new HappyNumber();
hn.printHappyNumbers(50);
}
}
check my code it is very optimized:-
#include
#include
void main()
{
int a,b,c=0;
clrscr();
printf(“enter a number”);
scanf(“%d”,&a);
while(a!=0)
{
{ b=a%10;
c=c+(b*b);
a=a-b;
a=a/10;
}
if(a==0)
if(c>=10)
{
a=c;
c=0;
}
}
if(c==1)
{
printf(“your number is happy”);
}
else
{
printf(“Not a happy number”);
}
getch();
}
static int calculateHappyNum(int num) {
if (num == 1)
return 1;
int sum = 0;
List lst = new ArrayList();
while (num > 0) {
int x = num % 10;
sum = sum + (x * x);
num = num / 10;
boolean isRepeated = false;
if (sum != 1 && num < 1) {
if (!lst.contains(sum)) {
lst.add(sum);
} else {
isRepeated = true;
}
num = sum;
System.out.println(num);
sum = 0;
// counter++
}
if (isRepeated)
return 0;
}
return sum;
}
Can u do it on Blue-j windows
thank you so much brooo………………………. vinay singh
can anybody tell me whats the problem in this code
/*Question : Write your code to find whether the number is a happy number or not (for max 10 cycles).
int number : The number to be determined whether it is happy or not
int finalNumber : Store the resultant value in this variable
int cycle_no : Store the number of iterations done to determine whether the ‘number’ is happy or not */
void detectHappy(int number, int &finalNumber, int &cycle_no) {
for(int c=1;c0)
{
int rem;
rem=number%10;
squareSum += rem*rem;
}
return squareSum;
}
if(squareSum==1){
cycle_no=c;
finalNumber=1;
break;
}
else{
finalNumber=squareSum;
number=squareSum;
}
}
}
July 23rd, 2010.cpp:
#include "seal_tree.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_tree.h> */ #include <string.h> #include <limits.h> #include <stdlib.h> #include <stdio.h> bool f_StringToUnsignedInt( const char * const p_string, unsigned int * const p_number ); bool f_StringToUnsignedInt( const char * const p_string, unsigned int * const p_number ) /* Returns true if: * p_number != NULL; * p_string != NULL; * p_string points to a string comprised of – and only of – one or more digits in the range [ 0, 9 ]; * and the number represented by the string pointed to by p_string is in the range [ 0, UINT_MAX ]. */ { if( p_number == NULL ) return false; size_t i = 0; // The index of the first non-zero digit in p_string. if( p_string == NULL ) return false; if( strlen( p_string ) == 0 ) return false; for( ; i < strlen( p_string ); i ++ ) if( p_string[ i ] != '0' ) break; size_t k = strlen( p_string ); unsigned long long multiplier = 0, number = 0; for( ; k > i; k -- ) { if( multiplier == 0 ) multiplier = 1; else { multiplier *= 10; if( multiplier > UINT_MAX ) return false; } const char digit = p_string[ k - 1 ]; if(( digit >= '0' ) && ( digit <= '9' )) { number += (( digit - '0' ) * multiplier ); if( number > UINT_MAX ) return false; } else return false; } *p_number = number; return true; } char *f_ReadStringFromFile( FILE * const p ); char *f_ReadStringFromFile( FILE * const p ) { char c, *s = ( char* )malloc( sizeof( char )); size_t s_length = 1; while(( fscanf( p, "%c", &c ) != EOF ) && ( c != '\n' )) { s[ s_length - 1 ] = c; s_length ++; s = ( char* )realloc( s, sizeof( char ) * s_length ); } s[ s_length - 1 ] = '\0'; return s; } unsigned int f_SumOfSquaresOfDigits( unsigned int p ); unsigned int f_SumOfSquaresOfDigits( unsigned int p ) { unsigned int sum_of_squares_of_digits = 0; while( p != 0 ) { const unsigned int digit = p % 10; p /= 10; sum_of_squares_of_digits += ( digit * digit ); } return sum_of_squares_of_digits; } typedef enum { k_IsAHappyNumber_Unknown, k_IsAHappyNumber_Yes, k_IsAHappyNumber_No } t_IsAHappyNumber; struct t_Number_struct { unsigned int m_number; t_IsAHappyNumber m_isAHappyNumber; }; class NumberTree : public seal_Tree<struct t_Number_struct*, unsigned int> { public: ~NumberTree( void ) { p_Empty(); } void p_Set( unsigned int p ) { struct t_Number_struct *number = ( struct t_Number_struct* )malloc( sizeof( struct t_Number_struct )); number->m_number = p; number->m_isAHappyNumber = k_IsAHappyNumber_Unknown; seal_Tree<struct t_Number_struct*, unsigned int>::p_Set( number ); } void p_SetIsAHappyNumber( const bool p ) { p_SetIsAHappyNumber( m_root, p ); } private: void p_SetIsAHappyNumber( struct t_seal_TreeNode<struct t_Number_struct*> * const p_n, const bool p_isAHappyNumber ) { if( p_n != NULL ) { if( p_n->m_content->m_isAHappyNumber == k_IsAHappyNumber_Unknown ) if( p_isAHappyNumber ) p_n->m_content->m_isAHappyNumber = k_IsAHappyNumber_Yes; else p_n->m_content->m_isAHappyNumber = k_IsAHappyNumber_No; p_SetIsAHappyNumber( p_n->m_l, p_isAHappyNumber ); p_SetIsAHappyNumber( p_n->m_r, p_isAHappyNumber ); } } public: t_IsAHappyNumber f_GetIsAHappyNumber( unsigned int p ) { struct t_Number_struct *number = f_Get( p ); return number->m_isAHappyNumber; } private: t_seal_TREE_BRANCH_DIRECTION f_Compare_TT( struct t_Number_struct *p_old, struct t_Number_struct *p_new ) { if( p_new->m_number < p_old->m_number ) return k_seal_TREE_BRANCH_DIRECTION__LEFT; if( p_new->m_number == p_old->m_number ) return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT; return k_seal_TREE_BRANCH_DIRECTION__RIGHT; } t_seal_TREE_BRANCH_DIRECTION f_Compare_TU( struct t_Number_struct *p_content, unsigned int p_identifier ) { if( p_identifier < p_content->m_number ) return k_seal_TREE_BRANCH_DIRECTION__LEFT; if( p_identifier == p_content->m_number ) return k_seal_TREE_BRANCH_DIRECTION__STRAIGHT; return k_seal_TREE_BRANCH_DIRECTION__RIGHT; } struct t_Number_struct *f_IsNotInTree( unsigned int p ) { #ifndef __MWERKS__ FILE * const print_error_message_to = stderr; const char * const error_message_terminated_by = "\n"; #else FILE * const print_error_message_to = stdout; const char * const error_message_terminated_by = ""; #endif fprintf( print_error_message_to, "\nSorry, an error occurred: number_tree.f_IsInTree( %u ) == false.\n%s", p, error_message_terminated_by ); exit( EXIT_FAILURE ); } void p_Delete( struct t_Number_struct *p ) { free( p ); } }; int main( const int argc, const char * const argv[] ) { bool error_occurred; unsigned int limit; #ifndef __MWERKS__ error_occurred = argc != 2; if( !error_occurred ) error_occurred = !f_StringToUnsignedInt( argv[ 1 ], &limit ); if( !error_occurred ) error_occurred = limit < 2; if( error_occurred ) { printf( "\nThis program must be passed, via the command line, an integer in the range [ 2, %u ]; this program will then determine the \"happy number(s)\" less than that integer.\n\n", UINT_MAX ); exit( EXIT_FAILURE ); } #else do { printf( "Please enter an integer in the range [ 2, %u ]; this program will then determine the \"happy number(s)\" less than that integer.\n", UINT_MAX ); printf( "\nYour input: " ); char *s = f_ReadStringFromFile( stdin ); error_occurred = !f_StringToUnsignedInt( s, &limit ); free( s ); if( !error_occurred ) error_occurred = limit < 2; if( error_occurred ) { printf( "\nSorry, an error occurred: your input was not an integer in the range [ 2, %u ].\n", UINT_MAX ); printf( "\nPlease press the Return key to try again." ); free( f_ReadStringFromFile( stdin )); printf( "\n" ); } } while( error_occurred ); #endif NumberTree number_tree; unsigned int i = 1; size_t number_of_happy_numbers = 0; unsigned int *happy_numbers = NULL; number_tree.p_Set( 1 ); number_tree.p_SetIsAHappyNumber( true ); for( ; i < limit; i ++ ) { t_IsAHappyNumber is_a_happy_number = k_IsAHappyNumber_Unknown; unsigned int number = i; while( is_a_happy_number == k_IsAHappyNumber_Unknown ) { if( number_tree.f_IsInTree( number )) { is_a_happy_number = number_tree.f_GetIsAHappyNumber( number ); if( is_a_happy_number == k_IsAHappyNumber_Yes ) { number_tree.p_SetIsAHappyNumber( true ); if( ++ number_of_happy_numbers == 1 ) happy_numbers = ( unsigned int* )malloc( sizeof( unsigned int )); else happy_numbers = ( unsigned int* )realloc( happy_numbers, sizeof( unsigned int ) * number_of_happy_numbers ); happy_numbers[ number_of_happy_numbers - 1 ] = i; } else { is_a_happy_number = k_IsAHappyNumber_No; number_tree.p_SetIsAHappyNumber( false ); } } else { number_tree.p_Set( number ); number = f_SumOfSquaresOfDigits( number ); } } } printf( "\nThere " ); if( number_of_happy_numbers == 1 ) printf( "is" ); else printf( "are" ); printf( " " ); if( number_of_happy_numbers == 0 ) printf( "no" ); else printf( "%u", number_of_happy_numbers ); printf( " \"happy number%s\" in the range [ 1, %u )", ( number_of_happy_numbers == 1 )?"":"s", limit ); if( number_of_happy_numbers > 0 ) { printf( ": " ); size_t i = 0; for( ; i < number_of_happy_numbers; i ++ ) { if( i > 0 ) if( number_of_happy_numbers == 2 ) printf( " and " ); else { printf( ", " ); if( i + 1 == number_of_happy_numbers ) printf( "and " ); } printf( "%u", happy_numbers[ i ] ); } } printf( ".\n" ); if( happy_numbers != NULL ) free( happy_numbers ); printf( "\n" ); #ifdef __MWERKS__ printf( "This program will now quit.\n" ); #endif exit( EXIT_SUCCESS ); }The program is known to run on an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) on both Mac OS 9.2.2 (International English) (the program compiled using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition)) and Mac OS X 10.4.11 (the program compiled using Xcode 2.2.1).
(I’ve just completed a gig at London South Bank University and so I’m again just trying to solve the problems posed by this ‘site whilst I try to get a job (and I’ve solved this problem in particular to test my
seal_Treetemplate class I might use in the fourth version of my SDL2 joystick interrogator utility); I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )[…] looked at happy numbers in a previous exercise. Recently, Fermat’s Library re-published a proof by Arthur Porges, first published in the […]
[…] Code, and Sloane’s, so it is well worth a look; we even did a version of this task in a previous exercise. Here is the Project Euler version of the […]