Since the function to know whether or not a number is happy is a pure function , we can use it in < a href="https://en.stackoverflow.com/q/33438/64969"> memo .
A very easy way to do memoisation is with recursion. Note that the definition of happy can be interpreted in a recursive way:
If the number in question is 1, he is happy.
If the number is not 1, then it is happy if the sum of the square of its digits is happy.
In case, if the recursion does not converge, then this implies that the number is unfortunate (poor thing = /).
Now, unlike the Collatz conjecture , I can demonstrate that the sequence of the sum of the digits of a number converge for finite loops? Yes we did. (The idea of identifying the links I've caught from the @Bacco response )
Take a large number. We know that it has n digits. Any number with n digits has the maximum sum of the square of its digits as n*9^2 . Just verify that this sum will be less than any number of% with% of digits. The smallest number of n digits is n . So if for the largest sum of squares of digits with 10^(n-1) digits it is less than the smallest number of n digits, then we have that n will be an upper limit to that sum, so there will be no ties with elemetos greater than 10^(n-1) . This also limited the maximum size of the loop to 10^(n-1) .
Let's get with 10^(n-1) . The smallest number is n = 4 . The largest sum is 1000 . This means that any sum made with 4 digits or less will always be limited to 324. This implies that there will be no loops with more than 1000 elements, with all elements limited to a maximum of 1000.
Okay, the limit is actually much smaller, but the relaxed limit is enough for the demo
Taking this idea, we can do the 4*81 = 324 function that does a recursive check for the happiness of the numbers. To do this, I use a "crumb path" which, whenever I touch it, detects the loop and therefore the number unhappiness. 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 feliz and mark my way back with this measure of happiness.
In this case, my memory is positional and each position consists of a state. There are 4 possible states:
-
infeliz : new memory, I have nothing memoised for this position
-
undefined : happy =)
-
'H' : sad = /
-
'M' : my crumb, I do not know yet
Note that for memory to function properly, this crumb path prevents parallel discovery of new memories. If someone puts this algorithm into this memory to serve two questions about the happiness of the numbers in parallel, the result will not be guaranteed. And from that point the memory should be cleared to start over.
An important detail is that the memoization here begins with the base case already in memory: I already start remembering that 'S' .
Follow the most readable version with trace to check memory and only a few tested numbers:
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 more elegantly create the 1 ==> 'H' function. I did not really like to leave the feliz variable in the global scope. We can use a auto-invoked function that returns the memoria function. This version I already sacrifice immediately 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 us to only 50? Let's go to the upper bound relaxed of the loop, what 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...
}
}
