Emulando a Dik T. Winter solucionado en C por josejuan

0votos

Emulando a Dik T. Winter en C

por josejuan hace 5 meses

No he encontrado ninguna propiedad mejor que la invarianza de las posiciones de los dígitos. Dik debía de saber una propiedad muy interesante de los Narcisistas. XD XD He basado mi solución en una optimización agresiva del código en C y una implementación a mano de operaciones en base 10. No arroja malos tiempos.

1223

Emulando a Dik T. Winter

6 soluciones Difícil

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344

/*

Lo primero que haremos será enumerar las combinaciones con repetición de menor a mayor en

un buffer de 39 bytes.

En algún momento, tendrá ésta forma:

     [············5555533331111111]

A la vez que enumeramos las combinaciones con repetición, mantendremos la lista de dígitos.  Lo

haremos en un buffer de bytes (no puede haber más de 39 dígitos, no desbordará 255) de la forma

    [0000000000]

A la vez, necesitamos tener computado el número de dígitos, para no tener que hacer las divisiones

pertinentes. Aunque es un royo, la mejor forma que veo es implementar nosotros la suma de enteros

de N dígitos en base 10.

El buffer del sumador/restador en algún momento tendrá la forma:

    [000000000010011918364638399910108373661]

De este modo, únicamente tenemos que mirar directamente si coincide el nº de dígitos.

El algoritmo es realmente corto, únicamente que he desenrollado manualmente varios bucles para

hacerlo todo lo rápido que se pueda.

En un único hilo de un AMD Phenom X6 a 2,7GHz:

- Calcular los Narcisistas de longitud 20 le lleva  1,91 segundos.

- Calcular los Narcisistas de longitud 25 le lleva 13,12 segundos.

- Calcular los Narcisistas de longitud 39 le lleva 13 minutos (aunque los encuentra mucho antes).

Nos falta entonces conocer alguna propiedad interesante de los Narcisistas, aun así, no está

mal el speedup conseguido.

-----------------------

solveet]$ gcc -O3 cubos.c && time -f "%E" ./a.out # 20 dígitos

63105425988599693916

End

0:01.91

 solveet]$ gcc -O3 cubos.c && time -f "%E" ./a.out # 25 dígitos

1550475334214501539088894

3706907995955475988644380

4422095118095899619457938

3706907995955475988644381

1553242162893771850669378

End

0:13.12

solveet]$ gcc -O3 cubos.c && time -f "%E" ./a.out # 39 dígitos

115132219018763992565095597973971522400

115132219018763992565095597973971522401

End

13:05.94

*/

#include <stdio.h>

#define DIGITS 20

#define byte unsigned char

void print(byte c[]) {

    int n;

    for(n = 0; n < DIGITS; n++)

        printf("%i", *c++);

    printf("\n");

int main(int argc, char **argv) {

    byte P[10][DIGITS] = { // powers

#if DIGITS == 5

        {0,0,0,0,0},

        {0,0,0,0,1},

        {0,0,0,3,2},

        {0,0,2,4,3},

        {0,1,0,2,4},

        {0,3,1,2,5},

        {0,7,7,7,6},

        {1,6,8,0,7},

        {3,2,7,6,8},

        {5,9,0,4,9}

#endif

#if DIGITS == 20

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,4,8,5,7,6},

        {0,0,0,0,0,0,0,0,0,0,3,4,8,6,7,8,4,4,0,1},

        {0,0,0,0,0,0,0,1,0,9,9,5,1,1,6,2,7,7,7,6},

        {0,0,0,0,0,0,9,5,3,6,7,4,3,1,6,4,0,6,2,5},

        {0,0,0,0,3,6,5,6,1,5,8,4,4,0,0,6,2,9,7,6},

        {0,0,0,7,9,7,9,2,2,6,6,2,9,7,6,1,2,0,0,1},

        {0,1,1,5,2,9,2,1,5,0,4,6,0,6,8,4,6,9,7,6},

        {1,2,1,5,7,6,6,5,4,5,9,0,5,6,9,2,8,8,0,1}

#endif

#if DIGITS == 25

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,3,5,5,4,4,3,2},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,8,4,7,2,8,8,6,0,9,4,4,3},

        {0,0,0,0,0,0,0,0,0,1,1,2,5,8,9,9,9,0,6,8,4,2,6,2,4},

        {0,0,0,0,0,0,0,2,9,8,0,2,3,2,2,3,8,7,6,9,5,3,1,2,5},

        {0,0,0,0,0,2,8,4,3,0,2,8,8,0,2,9,9,2,9,7,0,1,3,7,6},

        {0,0,0,1,3,4,1,0,6,8,6,1,9,6,6,3,9,6,4,9,0,0,8,0,7},

        {0,0,3,7,7,7,8,9,3,1,8,6,2,9,5,7,1,6,1,7,0,9,5,6,8},

        {0,7,1,7,8,9,7,9,8,7,6,9,1,8,5,2,5,8,8,7,7,0,2,4,9}

#endif

#if DIGITS == 39

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,4,9,7,5,5,8,1,3,8,8,8},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,5,2,5,5,5,1,5,3,0,1,8,9,7,6,2,6,7},

        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,2,2,3,1,4,5,4,9,0,3,6,5,7,2,9,3,6,7,6,5,4,4},

        {0,0,0,0,0,0,0,0,0,0,0,1,8,1,8,9,8,9,4,0,3,5,4,5,8,5,6,4,7,5,8,3,0,0,7,8,1,2,5},

        {0,0,0,0,0,0,0,0,2,2,2,7,9,1,5,7,5,6,4,7,3,9,5,5,6,7,7,9,7,3,1,4,0,9,9,6,0,9,6},

        {0,0,0,0,0,0,9,0,9,5,4,3,6,8,0,1,2,9,8,6,1,1,4,0,8,2,0,2,0,5,0,1,9,8,8,9,1,4,3},

        {0,0,0,1,6,6,1,5,3,4,9,9,4,7,3,1,1,4,4,8,4,1,1,2,9,7,5,8,8,2,5,3,5,0,4,3,0,7,2},

        {0,1,6,4,2,3,2,0,3,2,6,8,2,6,0,6,5,8,1,4,6,2,3,1,4,6,7,8,0,0,7,0,9,2,5,5,2,8,9}

/*

        115132219018763992565095597973971522400

        115132219018763992565095597973971522401

*/

#endif

};

    byte S[DIGITS + 1][DIGITS]; // sumas progresivas de potencias

    byte dd[30] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; // división por 10

    byte rr[30] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // restos de dividir por 10

    byte C[DIGITS];                 // almacena la combinación activa (de der a izq)

    byte *End = &(C[0]) - 1;        // centinela de fin de combinación (tendremos una)

    byte *Start = &(C[0]) + DIGITS; // centinela de fin de recursión (fin del proceso)

    byte *iC = Start - 1;           // posición con el último dígito añadido

    int dC[10];                     // contador de dígitos de C

    byte id = 0;                    // contador de dígito activo 0, 1, 2, ... es como iC

        int n;

        for(n = 0; n < 10; n++) dC[n] = 0;

        for(n = 0; n < DIGITS; n++) S[0][n] = 0;

    dC[0]++;

    *iC = 0;

    for(;;) {

        byte k = *iC--;

            { // debemos sumar a S[id] la potencia P[id] y dejarlo en S[id + 1]

                byte acc = 0;

                byte *pwr = &(P[k][0]);

                byte *src = &(S[id][0]);

                byte *dst = &(S[id + 1][0]);

#if DIGITS >= 39

                acc += src[38] + pwr[38]; dst[38] = rr[acc]; acc = dd[acc];

                acc += src[37] + pwr[37]; dst[37] = rr[acc]; acc = dd[acc];

                acc += src[36] + pwr[36]; dst[36] = rr[acc]; acc = dd[acc];

                acc += src[35] + pwr[35]; dst[35] = rr[acc]; acc = dd[acc];

                acc += src[34] + pwr[34]; dst[34] = rr[acc]; acc = dd[acc];

                acc += src[33] + pwr[33]; dst[33] = rr[acc]; acc = dd[acc];

                acc += src[32] + pwr[32]; dst[32] = rr[acc]; acc = dd[acc];

                acc += src[31] + pwr[31]; dst[31] = rr[acc]; acc = dd[acc];

                acc += src[30] + pwr[30]; dst[30] = rr[acc]; acc = dd[acc];

                acc += src[29] + pwr[29]; dst[29] = rr[acc]; acc = dd[acc];

                acc += src[28] + pwr[28]; dst[28] = rr[acc]; acc = dd[acc];

                acc += src[27] + pwr[27]; dst[27] = rr[acc]; acc = dd[acc];

                acc += src[26] + pwr[26]; dst[26] = rr[acc]; acc = dd[acc];

                acc += src[25] + pwr[25]; dst[25] = rr[acc]; acc = dd[acc];

#endif

#if DIGITS >= 25

                acc += src[24] + pwr[24]; dst[24] = rr[acc]; acc = dd[acc];

                acc += src[23] + pwr[23]; dst[23] = rr[acc]; acc = dd[acc];

                acc += src[22] + pwr[22]; dst[22] = rr[acc]; acc = dd[acc];

                acc += src[21] + pwr[21]; dst[21] = rr[acc]; acc = dd[acc];

                acc += src[20] + pwr[20]; dst[20] = rr[acc]; acc = dd[acc];

#endif

#if DIGITS >= 20

                acc += src[19] + pwr[19]; dst[19] = rr[acc]; acc = dd[acc];

                acc += src[18] + pwr[18]; dst[18] = rr[acc]; acc = dd[acc];

                acc += src[17] + pwr[17]; dst[17] = rr[acc]; acc = dd[acc];

                acc += src[16] + pwr[16]; dst[16] = rr[acc]; acc = dd[acc];

                acc += src[15] + pwr[15]; dst[15] = rr[acc]; acc = dd[acc];

                acc += src[14] + pwr[14]; dst[14] = rr[acc]; acc = dd[acc];

                acc += src[13] + pwr[13]; dst[13] = rr[acc]; acc = dd[acc];

                acc += src[12] + pwr[12]; dst[12] = rr[acc]; acc = dd[acc];

                acc += src[11] + pwr[11]; dst[11] = rr[acc]; acc = dd[acc];

                acc += src[10] + pwr[10]; dst[10] = rr[acc]; acc = dd[acc];

                acc += src[ 9] + pwr[ 9]; dst[ 9] = rr[acc]; acc = dd[acc];

                acc += src[ 8] + pwr[ 8]; dst[ 8] = rr[acc]; acc = dd[acc];

                acc += src[ 7] + pwr[ 7]; dst[ 7] = rr[acc]; acc = dd[acc];

                acc += src[ 6] + pwr[ 6]; dst[ 6] = rr[acc]; acc = dd[acc];

#endif

                acc += src[ 5] + pwr[ 5]; dst[ 5] = rr[acc]; acc = dd[acc];

                acc += src[ 4] + pwr[ 4]; dst[ 4] = rr[acc]; acc = dd[acc];

                acc += src[ 3] + pwr[ 3]; dst[ 3] = rr[acc]; acc = dd[acc];

                acc += src[ 2] + pwr[ 2]; dst[ 2] = rr[acc]; acc = dd[acc];

                acc += src[ 1] + pwr[ 1]; dst[ 1] = rr[acc]; acc = dd[acc];

                acc += src[ 0] + pwr[ 0]; dst[ 0] = rr[acc]; acc = dd[acc];

        id++;

        if(iC == End) {

            // si coinciden el nº de dígitos

            if(S[DIGITS][0] != 0) {

                byte ok = 1;

                    byte *src = &(S[DIGITS][0]);

                    int dR[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, n;

#if DIGITS >= 39

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

#endif

#if DIGITS >= 25

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

#endif

#if DIGITS >= 20

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

#endif

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    dR[*src++]++;

                    for(n = 0; n < 10; n++) if(dC[n] != dR[n]) {ok = 0; break;}

                if(ok) {

                    print(S[DIGITS]);

            iC++;

            id--;

            while(iC != Start) if(*iC == 9) {dC[9]--; iC++; id--;} else break;

            if(iC == Start) {printf("End\n"); break;}

            dC[*iC]--;

            ++(*iC);

            dC[*iC]++;

            { // debemos sumar a S[id] la potencia P[id] y dejarlo en S[id + 1]

                byte acc = 0;

                byte *pwr = &(P[*iC][0]);

                byte *src = &(S[id][0]);

                byte *dst = &(S[id + 1][0]);

#if DIGITS >= 39

                acc += src[38] + pwr[38]; dst[38] = rr[acc]; acc = dd[acc];

                acc += src[37] + pwr[37]; dst[37] = rr[acc]; acc = dd[acc];

                acc += src[36] + pwr[36]; dst[36] = rr[acc]; acc = dd[acc];

                acc += src[35] + pwr[35]; dst[35] = rr[acc]; acc = dd[acc];

                acc += src[34] + pwr[34]; dst[34] = rr[acc]; acc = dd[acc];

                acc += src[33] + pwr[33]; dst[33] = rr[acc]; acc = dd[acc];

                acc += src[32] + pwr[32]; dst[32] = rr[acc]; acc = dd[acc];

                acc += src[31] + pwr[31]; dst[31] = rr[acc]; acc = dd[acc];

                acc += src[30] + pwr[30]; dst[30] = rr[acc]; acc = dd[acc];

                acc += src[29] + pwr[29]; dst[29] = rr[acc]; acc = dd[acc];

                acc += src[28] + pwr[28]; dst[28] = rr[acc]; acc = dd[acc];

                acc += src[27] + pwr[27]; dst[27] = rr[acc]; acc = dd[acc];

                acc += src[26] + pwr[26]; dst[26] = rr[acc]; acc = dd[acc];

                acc += src[25] + pwr[25]; dst[25] = rr[acc]; acc = dd[acc];

#endif

#if DIGITS >= 25

                acc += src[24] + pwr[24]; dst[24] = rr[acc]; acc = dd[acc];

                acc += src[23] + pwr[23]; dst[23] = rr[acc]; acc = dd[acc];

                acc += src[22] + pwr[22]; dst[22] = rr[acc]; acc = dd[acc];

                acc += src[21] + pwr[21]; dst[21] = rr[acc]; acc = dd[acc];

                acc += src[20] + pwr[20]; dst[20] = rr[acc]; acc = dd[acc];

#endif

#if DIGITS >= 20

                acc += src[19] + pwr[19]; dst[19] = rr[acc]; acc = dd[acc];

                acc += src[18] + pwr[18]; dst[18] = rr[acc]; acc = dd[acc];

                acc += src[17] + pwr[17]; dst[17] = rr[acc]; acc = dd[acc];

                acc += src[16] + pwr[16]; dst[16] = rr[acc]; acc = dd[acc];

                acc += src[15] + pwr[15]; dst[15] = rr[acc]; acc = dd[acc];

                acc += src[14] + pwr[14]; dst[14] = rr[acc]; acc = dd[acc];

                acc += src[13] + pwr[13]; dst[13] = rr[acc]; acc = dd[acc];

                acc += src[12] + pwr[12]; dst[12] = rr[acc]; acc = dd[acc];

                acc += src[11] + pwr[11]; dst[11] = rr[acc]; acc = dd[acc];

                acc += src[10] + pwr[10]; dst[10] = rr[acc]; acc = dd[acc];

                acc += src[ 9] + pwr[ 9]; dst[ 9] = rr[acc]; acc = dd[acc];

                acc += src[ 8] + pwr[ 8]; dst[ 8] = rr[acc]; acc = dd[acc];

                acc += src[ 7] + pwr[ 7]; dst[ 7] = rr[acc]; acc = dd[acc];

                acc += src[ 6] + pwr[ 6]; dst[ 6] = rr[acc]; acc = dd[acc];

                acc += src[ 5] + pwr[ 5]; dst[ 5] = rr[acc]; acc = dd[acc];

#endif

                acc += src[ 4] + pwr[ 4]; dst[ 4] = rr[acc]; acc = dd[acc];

                acc += src[ 3] + pwr[ 3]; dst[ 3] = rr[acc]; acc = dd[acc];

                acc += src[ 2] + pwr[ 2]; dst[ 2] = rr[acc]; acc = dd[acc];

                acc += src[ 1] + pwr[ 1]; dst[ 1] = rr[acc]; acc = dd[acc];

                acc += src[ 0] + pwr[ 0]; dst[ 0] = rr[acc]; acc = dd[acc];

        } else {

            *iC = k;

            dC[k]++;

    return 0;

Emulando a Dik T. Winter en C

Comenta la solución