1votos

Emulando a Dik T. Winter en JavaScript

por josejuan hace 5 años

Con javascript, sin paralelizar, toma en mi humilde Atom D510 el cálculo para N=9 unos 182 milisegundos...

Un número de N dígitos es narcisista si la suma de las potencias N-ésimas de sus dígitos es él mismo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
function Narcisistas(N) { 
 
    // verificación directa de si es narcisista o no 
    var isN = function (z) { 
        var q = z, s = 0; 
        do { s += P[q % 10]; 
             q = ~~Math.floor(q / 10); 
        } while(q > 0) 
        return z == s; 
    }; 
     
    var P = [], // precálculo de potencias 
        R = {}; // narcisistas encontrados 
    for(var i = 0; i < 10; i++) 
        P[i] = ~~Math.pow(i, N); 
         
    var C = function ( acc // suma de potencias de los dígitos acumulados 
                     , d   // dígito a revisar y meter en el saco 
                     , ds  // número de dígitos disponibles para llenar 
                     ) { 
        if(d == 10) { 
            if(isN(acc)) 
                R[acc] = 0; 
        } else { 
            var p = P[d], b = d + 1, a = acc, n = 0, dss = ds; 
            while(n <= ds) { 
                C(a, b, dss); 
                n++; 
                a += p; 
                dss--; 
    }; 
     
    C(0, 0, N); 
    var L = ~~Math.pow(10, N - 1); 
    return Object.keys(R).filter(function(x){return x >= L}); 
     
 
 
// por ejemplo 
for(var n = 1; n < 10; n++) { 
    var t = new Date(); 
    console.log( 
        "Narcisistas(" + n + ") := " +  
        Narcisistas(n) + 
        " in " + (new Date() - t) + " mS"); 
 
 
/* =========== y la salida ============ 
 
En un único hilo, sobre mi humilde Atom D510 a 1,66 GHz 
 
Narcisistas(1) := 1,2,3,4,5,6,7,8,9 in 27 mS 
Narcisistas(2) :=  in 0 mS 
Narcisistas(3) := 153,370,371,407 in 3 mS 
Narcisistas(4) := 1634,8208,9474 in 4 mS 
Narcisistas(5) := 54748,92727,93084 in 1 mS 
Narcisistas(6) := 548834 in 5 mS 
Narcisistas(7) := 1741725,4210818,9800817,9926315 in 11 mS 
Narcisistas(8) := 24678050,24678051,88593477 in 27 mS 
Narcisistas(9) := 146511208,472335975,534494836,912985153 in 182 mS 
 
*** valores más grandes no pueden calcularse debido a la precisión del nº usado *** 
 
Un posible speedup (ej. para n=9) es utilizar workers sobre el árbol generado 
al calcular las combinaciones de dígitos. 
 
*/ 
6 comentarios
0votos

Escrito por jmgomez hace 5 años

Pues 20 ms le tomaron los 9 al i7 de mi retina, nada mal. :-)
0votos

Escrito por josejuan hace 5 años

En mi AMD Phenom(tm) II X6 1045T 2,7GHz para n=9 le tomó 32mS, ya no le puedo llamar centella :(
0votos

Escrito por jmgomez hace 5 años

Lo ejecutaste en v8?
0votos

Escrito por josejuan hace 5 años

Es casi obligado, ejecutarlo en un explorador es como tirar los dados... XD XD
0votos

Escrito por Pedro-vk hace 5 años

La gran mejora está en que tratas matemáticamente los números, en mi implantación el gran abismo de velocidad se encuentra en que uso cadenas de texto, en lugar de meterme a operaciones matemáticas.

Felicidades, está fenomenal.
0votos

Escrito por josejuan hace 5 años

"La gran mejora está en que tratas matemáticamente los números"

No Pedro, de hecho la mejora es no tratarlos como números :)

El único speedup usado en estas implementaciones (js, f# y haskell) es la invarianza de las posiciones de los dígitos para ser narcisista. Por ejemplo, existen exactamente 362.880 números de 9 dígitos, todos diferentes y sin contar el 0. Pero nos da igual que sus posiciones sean diferentes, porque todos tienen la misma suma de potencias.

Así, tu estás mirando si TODOS los 362.880 números son narcisitas, pero yo sólo lo miro una única vez.

Tu implementación de `String(n)` sí puede ser (depende como esté hecha) algo más lenta que mis `divMod`, pero no arrojaría tanta diferencia.

No los trato como números, porque la "gran mejora" es precisamente calcular el núcleo de las permutaciones (un representante de cada conjunto posible diferente de dígitos sin importar el orden) y eso, es independiente de que sean números o zapatos.

El resto del cálculo más allá del núcleo es prácticamente idéntico al que haces tú.

En mi segunda solución en C existen acotaciones y mejoras que fusionan ambos esquemas (como números y como combinaciones), que aunque es un poco más complicada, puede entenderse sin mucha dificultad (no hay matemáticas avanzadas).

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.