As the function to know whether a number is happy or not is a pure function, we can use on her memoisation.
A very easy way to do memoization is with recursion. Note that the very definition of happy can be interpreted recursively:
If the number in question is 1, he’s happy.
If the number is not 1, then he is happy if the sum of the square of his digits is happy.
In this case, if the recursion does not converge, then it implies that the number is unhappy (poor thing =/ ).
Now, is that, unlike collatz conjecture, I can demonstrate that the sequence of the sum of digits of a number converges to finite loops? Yes, we did. (The idea of identifying the ties I fished from reply by @Bacco)
Take a big number. We know he has n
digits. Any number with n
digits have as the maximum sum of the square of their digits as n*9^2
. Just then verify that this sum will be less than any number of n
digits. The smallest number of n
digits is 10^(n-1)
. So if for the largest sum of square digits with n
digits it is smaller than the smallest number of n
digits, so we have to 10^(n-1)
will be an upper bound to that sum, so there will be no ties with larger elemets than 10^(n-1)
. That also limited the maximum loop size for 10^(n-1)
.
Let’s take with n = 4
. The smallest number is 1000
. The largest sum is 4*81 = 324
. This means that any sum made with 4 digits or less will always be limited to 324. This implies that there will be no ties with more than 1000 elements, with all elements limited to at most the number 1000.
Okay, the limit is actually much lower, but the relaxed limit is enough for the demonstration
Taking this idea, we can do the function feliz
that makes a recursive check for the happiness of the numbers. For this, I use a "crumb path" that whenever I touch it, I detect the tie and therefore the unhappiness of the number. I also take advantage of previous knowledge of the happiness of others and if the sum of the squares of the digits is already known feliz
or infeliz
and mark my way back with that measure of happiness.
In this case, my memory is positional and each position consists of a state. There are 4 possible states:
undefined
: new memory, I have nothing memoized for that position
'H'
: happy =)
'M'
: sad =/
'S'
: my crumb, I don’t know yet
Note that for memoization to work properly, this crumb path prevents parallel execution of discovery of new memories. If someone puts this algorithm to serve two questions about the happiness of numbers in parallel, the result will not be guaranteed. And from that point the memory must be wiped to start again.
An important detail is that the memoization here begins with the case based already on memory: I already start by remembering that 1 ==> 'H'
.
Follows the most readable version, with trace to check the memory and only few numbers tested:
function soma_quad_digits(numero) {
let soma_quad = 0;
while (numero > 0) {
let dig = numero % 10;
numero = Math.floor(numero/10);
soma_quad += dig*dig;
}
return soma_quad;
}
function felicidade_memoizada(numero, memoria) {
if (memoria[numero] === undefined) {
console.log("indo atrás da felicidade de " + numero + " (soma do quadrado dos dígitos: " + soma_quad_digits(numero) + ")");
// memória aqui é indefinida! oba \o/
memoria[numero] = 'S'; // S de SEARCHING, usado pra marcar loops
let nova_memoria = felicidade_memoizada(soma_quad_digits(numero), memoria); // busca a nova memória recursivamente
memoria[numero] = nova_memoria; // fazendo a memoização
console.log("memorizando que " + numero + " é " + nova_memoria);
return nova_memoria;
} else if (memoria[numero] == 'H') { // H de HAPPY
return 'H'; // sim, achou memória feliz
} else if (memoria[numero] == 'M') { // M de MAD
return 'M'; // caí num caso conhecido de infelicidade
} else if (memoria[numero] == 'S') { // oh, oh... loop
// nesse caso, na recursão que preencheu como SEARCHING originalmente vai marcar esse cara como MAD...
return 'M';
}
}
let memoria = [];
memoria[1] = 'H'; // definição
let feliz = (n) => felicidade_memoizada(n, memoria) == 'H';
console.log(feliz(2));
console.log(feliz(7));
console.log(feliz(19));
console.log(feliz(23));
console.log(feliz(50));
Now, we could have in a more elegant way the creation of the function feliz
. I didn’t really like leaving the variable memoria
in the global scope. We can use a function self-appointed that returns the function feliz
. This version I already sacrifice all comments and readability:
let feliz = (function() {
function soma_quad_digits(numero) {
let soma_quad = 0;
for (let dig = numero % 10; numero > 0; numero = (numero/10)|0, dig = numero%10) {
soma_quad += dig*dig;
}
return soma_quad;
}
function felicidade_memoizada(numero, memoria) {
if (numero > 10000) {
return felicidade_memoizada(soma_quad_digits(numero), memoria);
}
if (memoria[numero] === undefined) {
memoria[numero] = 'S';
return memoria[numero] = felicidade_memoizada(soma_quad_digits(numero), memoria);
} else if (memoria[numero] == 'H') {
return 'H';
} else {
return 'M';
}
}
let memoria = [];
memoria[1] = 'H';
return (n) => felicidade_memoizada(n, memoria) == 'H';
})();
for (let i = 0; i <= 50; i++) {
if (feliz(i)) {
console.log(i);
}
}
But honestly, why limit ourselves to just 50? Let’s go to the upper limit relaxed of the loop, which would be 1000?
let feliz = (function() {
function soma_quad_digits(numero) {
let soma_quad = 0;
for (let dig = numero % 10; numero > 0; numero = (numero/10)|0, dig = numero%10) {
soma_quad += dig*dig;
}
return soma_quad;
}
function felicidade_memoizada(numero, memoria) {
if (numero > 10000) {
return felicidade_memoizada(soma_quad_digits(numero), memoria);
}
if (memoria[numero] === undefined) {
memoria[numero] = 'S';
return memoria[numero] = felicidade_memoizada(soma_quad_digits(numero), memoria);
} else if (memoria[numero] == 'H') {
return 'H';
} else {
return 'M';
}
}
let memoria = [];
memoria[1] = 'H';
return (n) => felicidade_memoizada(n, memoria) == 'H';
})();
for (let i = 0; i <= 1000; i++) {
if (feliz(i)) {
document.write(i + " "); // tentei ficar só no log, mas ficou grande demais...
}
}
Thanks! It was really good.
– Sam
I just made an adaptation:
var nums = []; if (beHappy(i)) nums.push(i);
to create an array with the results– Sam
Can explain the use of
&& !~repeat.indexOf(value)
?– lazyFox
@lazyFox O
~
is a bitwise operator. If the return value of theindexOf
for-1
, then~-1
shall be equal to 0, because-1
is an all 1 bit string. A little hard to understand? Its formula is-(x + 1)
, or-(-1+1) = 0; -(-2+1) = 1; -(3+1) = -4
. The exclamation is to transform the false value into true, similar to the¬
of the truth table.– Valdeir Psr
Thank you so much @Valdeirpsr
– lazyFox