0votos

El número feliz en C

por josejuan hace 13 días

Hacen ya más de 5 años que propuse una solución en https://www.genbetadev.com/trabajar-como-desarrollador/el-algoritmo-de-dios y nadie parece haberla implementado. Aunque el enunciado del desafío dice lo contrario, mejor trabajar con cadenas que con números. Aquí se construye un índice y con él se pueden calcular nºs con cientos de millones de dígitos en décimas de segundo.

Programar el algoritmo necesario para averiguar si un número es feliz.

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
// general el índice 
#include <stdio.h> 
#include <stdlib.h> 
#include <errno.h> 
#include <string.h> 
 
// reduce un nº que cabe en la máquina 
int reduce(int n) { 
  if(n < 10) return n * n; 
  int u = n / 10, v = n % 10; 
  return reduce(u) + v * v; 
 
// calculando un feliz con cuidado 
char happy(int n) { 
  if(n == 1) return 1; 
  if(n == 4) return 0; 
  return happy(reduce(n)); 
 
int main(int argc, char **argv) { 
 
  if(argc != 2) { 
    fprintf(stderr, "usage: %s <max.digits>\n", argv[0]); 
    return 1; 
 
  // precalcularemos los primeros N naturales en un bitmap 
  long N = 81L * atoi(argv[1]); 
  if(N < 1000) N = 1000; 
 
  char *h = (char *) malloc(1 + (N >> 3)); 
 
  long i; 
 
  // primero con cuidado 
  for(i = 1; i < 1000; i++) if(happy(i)) h[i >> 3] |= 1 << (i & 0x7); 
 
  // después a lo loco, para evitar `reduce`, que es muy lenta, contamos dígito a dígito 
  char d [] = {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 /*, ... */ }; 
  int z = 1, w[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 }, id; 
  for(; i < N; i++) { 
    if(h[z >> 3] & (1 << (z & 0x7))) h[i >> 3] |= 1 << (i & 0x7); 
    for(id = 0; d[id] == 9;) { d[id++] = 0; z -= 81; } 
    z -= w[d[id]]; d[id]++; z += w[d[id]]; 
 
  // a disco 
  FILE *f = fopen("feliz.bitmap", "w"); 
  if(f == NULL) { 
    fprintf(stderr, "ERROR %s: %s\n", argv[0], strerror(errno)); 
    return 1; 
  } else { 
    fwrite(h, 1 + (N >> 3), sizeof(char), f); 
    fclose(f); 
 
  // ok 
  return 0; 
 
/* 
 
[josejuan@centella Solveet]$ gcc -O3 feliz.index.c -o feliz.make.index 
 
[josejuan@centella Solveet]$ time -f "%E" ./feliz.make.index 100000000 
1:27.58 
 
*/ 
 
 
 
 
 
 
 
 
// usar el índice para calcular la felicidad de un nº 
#include <stdio.h> 
#include <stdlib.h> 
#include <errno.h> 
#include <string.h> 
 
int main(int argc, char **argv) { 
  if(argc != 1) { fprintf(stderr, "usage: %s\n\n\tRead number from stdin.\n", argv[0]); return 1; } 
 
  // calculamos las frecuencias de la entrada estandar asumiendo sólo hay dígitos 
  long c[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, r; 
  while((r = getchar()) != EOF) c[r - '0']++; 
 
  // índice 
  int w[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81 }, i; 
  for(r = 0, i = 1; i < 10; i++) r += w[i] * c[i]; 
  long idx = r >> 3; 
 
  FILE *f = fopen("feliz.bitmap", "r"); 
  if(f == NULL || fseek(f, r >> 3, SEEK_SET) == -1) { 
    fprintf(stderr, "ERROR %s: %s\n", argv[0], strerror(errno)); 
    return 1; 
  int y; 
  if((y = fgetc(f)) == EOF) { 
    fprintf(stderr, "ERROR %s: premature end of file\n", argv[0]); 
    return 1; 
  printf("%s\n", (y & (1 << (r & 0x7))) ? "Feliz" : "Infeliz"); 
 
  // ok 
  return 0; 
 
 
 
 
// por ejemplo comparando este método (feliz.indexed) con el típico en haskell (feliz) 
[josejuan@centella solveet]$ cat big-infeliz-99785812-digits | time -f "cpu: %e, mem: %M" ./feliz.indexed 
Infeliz 
cpu: 0.85, mem: 1132 
[josejuan@centella solveet]$ cat big-infeliz-99785812-digits | time -f "cpu: %e, mem: %M" ./feliz 
False 
cpu: 288.47, mem: 6729256 
[josejuan@centella solveet]$ cat big-feliz-99785812-digits | time -f "cpu: %e, mem: %M" ./feliz.indexed 
Feliz 
cpu: 0.83, mem: 1132 
[josejuan@centella solveet]$ cat big-feliz-99785812-digits | time -f "cpu: %e, mem: %M" ./feliz 
True 
cpu: 287.60, mem: 6729308 
[josejuan@centella solveet]$ 
 
 
 
// código en haskell 
import System.Environment 
 
f 1 = True 
f 4 = False 
f n = f $ sum $ map ((^2).read.(:[])) $ show n 
 
main = getContents >>= print . f . read 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.