Happy numbers: Difference between revisions
(→{{header|Python}}: exploiting default arguments for the cache) |
m (Undo revision 41564 Why use a default arg for the cache?) |
||
Line 403: | Line 403: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
Includes a cache of precomputed values. |
Includes a cache of precomputed values. |
||
<lang python>>>> def happy(number |
<lang python>>>> def happy(number): |
||
cycle = set() |
cycle = set() |
||
while number != 1 and number not in cycle: |
while number != 1 and number not in cycle: |
||
if number in cache: |
if number in happy.cache: |
||
number = 1 if cache[number] else 0 |
number = 1 if happy.cache[number] else 0 |
||
break |
break |
||
cycle.add(number) |
cycle.add(number) |
||
Line 417: | Line 417: | ||
happiness = number==1 |
happiness = number==1 |
||
for n in cycle: # all in cycle share the same happiness |
for n in cycle: # all in cycle share the same happiness |
||
cache.setdefault(n, happiness) |
happy.cache.setdefault(n, happiness) |
||
return happiness |
return happiness |
||
>>> happy.cache={} |
|||
>>> [x for x in range(1,50) if happy(x)] # First few happy numbers |
>>> [x for x in range(1,50) if happy(x)] # First few happy numbers |
||
[1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49] |
[1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49] |
Revision as of 07:28, 6 June 2009
You are encouraged to solve this task according to the task description, using any language you may know.
From Wikipedia, the free encyclopedia:
- 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.
Task: Find and print the first 8 happy numbers.
ALGOL 68
<lang algol>INT base10 = 10, num happy = 8;
PROC next = (INT in n)INT: (
INT n := in n; INT out := 0; WHILE n NE 0 DO out +:= ( n MOD base10 ) ** 2; n := n OVER base10 OD; out
);
PROC is happy = (INT in n)BOOL: (
INT n := in n; FOR i WHILE n NE 1 AND n NE 4 DO n := next(n) OD; n=1
);
INT count := 0; FOR i WHILE count NE num happy DO
IF is happy(i) THEN count +:= 1; print((i, new line)) FI
OD</lang> Output:
+1 +7 +10 +13 +19 +23 +28 +31
AutoHotkey
<lang AutoHotkey> Loop {
if isHappy(A_Index) { out .= (out="" ? "" : ",") . A_Index i ++ if (i = 8) { MsgBox, The first 8 happy numbers are: %out% ExitApp } } }
isHappy(num, list="") {
list .= (list="" ? "" : ",") . num Loop, Parse, num sum += A_LoopField ** 2 if (sum = 1) return true else if sum in %list% return false else return isHappy(sum, list) }
</lang>
AWK
<lang awk>function is_happy(n) {
if ( n in happy ) return 1; if ( n in unhappy ) return 0; cycle[""] = 0 while( (n!=1) && !(n in cycle) ) { cycle[n] = n new_n = 0 while(n>0) { d = n % 10 new_n += d*d n = int(n/10) } n = new_n } if ( n == 1 ) { for (i_ in cycle) { happy[cycle[i_]] = 1 delete cycle[i_] } return 1 } else { for (i_ in cycle) { unhappy[cycle[i_]] = 1 delete cycle[i_] } return 0 }
}
BEGIN {
cnt = 0 happy[""] = 0 unhappy[""] = 0 for(j=1; (cnt < 8); j++) { if ( is_happy(j) == 1 ) { cnt++ print j } }
}</lang>
C
<lang c>#include <stdio.h>
- include <stdbool.h>
- include <stdlib.h>
- include <string.h>
- include <assert.h>
typedef struct list {
int val; struct list *next;
} list_t;
bool in_cycle(list_t *c, int n) {
for( ; c != NULL; c = c->next ) if ( n == c->val ) return true; return false;
}
void add_cycle(list_t **c, int n) {
list_t *p = malloc(sizeof(list_t)); assert(p!=NULL); p->val = n; p->next = NULL; if ( *c == NULL ) { *c = p; } else { p->next = *c; *c = p; }
}
void kill_cycle(list_t *c) {
list_t *t; for(;c!=NULL; c=t) { t = c->next; free(c); }
}
bool is_happy(int n) {
list_t *cycle = NULL; int new_n;
while( (n != 1) && !in_cycle(cycle, n) ) { add_cycle(&cycle, n); new_n = 0; while( n > 0 ) { int d = n % 10; new_n += d*d; n /= 10; } n = new_n; } kill_cycle(cycle); return (n == 1);
}
int main() {
int i; int cnt = 0; for(i=1; cnt < 8; i++) { if (is_happy(i)) { printf("%d\n", i); cnt++; } } return EXIT_SUCCESS;
}</lang>
C++
<lang cpp>#include <map>
- include <set>
bool happy(int number) {
static std::map<int, bool> cache;
std::set<int> cycle; while (number != 1 && !cycle.count(number)) { if (cache.count(number)) { number = cache[number] ? 1 : 0; break; } cycle.insert(number); int newnumber = 0; while (number > 0) { int digit = number % 10; newnumber += digit * digit; number /= 10; } number = newnumber; } bool happiness = number == 1; for (std::set<int>::const_iterator it = cycle.begin(); it != cycle.end(); it++) cache[*it] = happiness; return happiness;
}
- include <iostream>
int main() {
for (int i = 1; i < 50; i++) if (happy(i)) std::cout << i << std::endl; return 0;
}</lang>
Alternative version without caching:
<lang cpp> unsigned int happy_iteration(unsigned int n) {
unsigned int result = 0; while (n > 0) { unsigned int lastdig = n % 10; result += lastdig*lastdig; n /= 10; } return result;
}
bool is_happy(unsigned int n) {
unsigned int n2 = happy_iteration(n); while (n != n2) { n = happy_iteration(n); n2 = happy_iteration(happy_iteration(n2)); } return n == 1;
}
- include <iostream>
int main() {
unsigned int current_number = 1;
unsigned int happy_count = 0; while (happy_count != 8) { if (is_happy(current_number)) { std::cout << current_number << " "; ++happy_count; } ++current_number; } std::cout << std::endl;
} </lang>
Cycle detection in is_happy()
above is done using Floyd's cycle-finding algorithm.
Common Lisp
<lang lisp>(defun happyp (n &aux (seen ()))
(loop (when (= n 1) (return t)) (when (find n seen) (return nil)) (push n seen) (setf n (reduce #'+ (map 'list (lambda (c &aux (x (position c "0123456789"))) (* x x)) (format nil "~d" n))))))
(loop
with happy = 0 for n from 0 until (= 8 happy) when (happyp n) do (incf happy) and do (format t "~d~%" n))</lang>
Forth
<lang forth>
- next ( n -- n )
0 swap begin 10 /mod >r dup * + r> ?dup 0= until ;
- cycle? ( n -- ? )
here dup @ cells + begin dup here > while 2dup @ = if 2drop true exit then 1 cells - repeat 1 over +! dup @ cells + ! false ;
- happy? ( n -- ? )
0 here ! begin next dup cycle? until 1 = ;
- happy-numbers ( n -- )
0 swap 0 do begin 1+ dup happy? until dup . loop drop ;
8 happy-numbers \ 1 7 10 13 19 23 28 31 </lang>
Haskell
<lang haskell>import Data.Char (digitToInt)
happys :: [Int] happys = filter (p []) [1..]
where p _ 1 = True p l n | n `elem` l = False | otherwise = p (n : l) (f n) f = sum . map ((^2) . digitToInt) . show
main = mapM_ print $ take 8 happys</lang>
Java
<lang java5>import java.util.LinkedList; public class Happy{
public static boolean happy(long number){ long m = 0; int digit = 0; LinkedList<Long> cycle = new LinkedList<Long>(); while(number != 1 && !cycle.contains(number)){ cycle.add(number); m = 0; while(number > 0){ digit = (int)(number % 10); m += digit*digit; number /= 10; } number = m; } return number == 1; }
public static void main(String[] args){ for(long num = 1,count = 0;count<8;num++){ if(happy(num)){ System.out.println(num); count++; } } }
}</lang>
JavaScript
<lang javascript> function happy(number) {
var m, digit ; var cycle = new Array() ;
while(number != 1 && cycle[number] != true) { cycle[number] = true ; m = 0 ; while (number > 0) { digit = number % 10 ; m += digit * digit ; number = (number - digit) / 10 ; } number = m ; } return (number == 1) ;
} ;
var cnt = 8 ; var number = 1 ;
while(cnt-- > 0) {
while(!happy(number)) number++ ; document.write(number + " ") ; number++ ;
} </lang>
Perl
<lang perl>use List::Util qw(first sum);
sub is_happy ($)
{for (my ($n, @seen) = shift ;; $n = sum map {$_**2} split //, $n) {$n == 1 and return 1; defined first {$_ == $n} @seen and return 0; push @seen, $n;}}
for (my ($n, $happy) = (1, 0) ; $happy < 8 ; ++$n)
{is_happy $n or next; print "$n\n"; ++$happy;}</lang>
Python
Includes a cache of precomputed values. <lang python>>>> def happy(number):
cycle = set() while number != 1 and number not in cycle: if number in happy.cache: number = 1 if happy.cache[number] else 0 break cycle.add(number) newnumber = 0 while number > 0: number, digit = divmod(number, 10) newnumber += digit*digit number = newnumber happiness = number==1 for n in cycle: # all in cycle share the same happiness happy.cache.setdefault(n, happiness) return happiness
>>> happy.cache={} >>> [x for x in range(1,50) if happy(x)] # First few happy numbers [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49] >>> </lang>
Smalltalk
In addition to the "Python's cache mechanism", the use of a Bag assures that found e.g. the happy 190, we already have in cache also the happy 910 and 109, and so on. <lang smalltalk>Object subclass: HappyNumber [
|cache negativeCache| HappyNumber class >> new [ |me| me := super new. ^ me init ] init [ cache := Set new. negativeCache := Set new. ]
hasSad: aNum [ ^ (negativeCache includes: (self recycle: aNum)) ] hasHappy: aNum [ ^ (cache includes: (self recycle: aNum)) ] addHappy: aNum [ cache add: (self recycle: aNum) ] addSad: aNum [ negativeCache add: (self recycle: aNum) ]
recycle: aNum [ |r n| r := Bag new. n := aNum. [ n > 0 ] whileTrue: [ |d| d := n rem: 10. r add: d. n := n // 10. ]. ^r ]
isHappy: aNumber [ |cycle number newnumber| number := aNumber. cycle := Set new. [ (number ~= 1) & ( (cycle includes: number) not ) ] whileTrue: [ (self hasHappy: number) ifTrue: [ ^true ] ifFalse: [ (self hasSad: number) ifTrue: [ ^false ]. cycle add: number. newnumber := 0. [ number > 0 ] whileTrue: [ |digit| digit := number rem: 10. newnumber := newnumber + (digit * digit). number := (number - digit) // 10. ]. number := newnumber. ] ]. (number = 1) ifTrue: [ cycle do: [ :e | self addHappy: e ]. ^true ] ifFalse: [ cycle do: [ :e | self addSad: e ]. ^false ] ]
].</lang>
<lang smalltalk>|happy| happy := HappyNumber new.
1 to: 30 do: [ :i |
(happy isHappy: i) ifTrue: [ i displayNl ]
].</lang>
Tcl
using code from Sum of squares#Tcl <lang tcl>proc is_happy n {
set seen [list] while {$n > 1 && [lsearch -exact $seen $n] == -1} { lappend seen $n set n [sum_of_squares [split $n ""]] } return [expr {$n == 1}]
}
set happy [list] set n -1 while {[llength $happy] < 8} {
if {[is_happy $n]} {lappend happy $n} incr n
} puts "the first 8 happy numbers are: [list $happy]"</lang>
the first 8 happy numbers are: {1 7 10 13 19 23 28 31}