1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 char* get_prefix(int number) {
6 char* text;
7 int tmpI;
8 switch (number) {
9 case 20:
10 text = "twenty ";
11 break;
12 case 30:
13 text = "thirty ";
14 break;
15 case 40:
16 text = "forty ";
17 break;
18 case 50:
19 text = "fifty ";
20 break;
21 case 60:
22 text = "sixty ";
23 break;
24 case 70:
25 text = "seventy ";
26 break;
27 case 80:
28 text = "eighty ";
29 break;
30 case 90:
31 text = "ninety ";
32 break;
33 default:
34 text = "";
35 }
36 return text;
37 }
38
39 int strlenNoSpaces(char* str) {
40 int cont = 0;
41 for (int i = 0; str[i] != '\0'; i++) {
42 if (str[i] != ' ') cont++;
43 }
44 return cont;
45 }
46
47 char* get_number_spelled(int number) {
48 char* text;
49 char* tmpS1;
50 char* tmpS2;
51 char* tmpS3;
52 int tmpI;
53 if (number < 1)
54 text = "";
55 else if (number == 1)
56 text = "one";
57 else if (number == 2)
58 text = "two";
59 else if (number == 3)
60 text = "three";
61 else if (number == 4)
62 text = "four";
63 else if (number == 5)
64 text = "five";
65 else if (number == 6)
66 text = "six";
67 else if (number == 7)
68 text = "seven";
69 else if (number == 8)
70 text = "eight";
71 else if (number == 9)
72 text = "nine";
73 else if (number == 10)
74 text = "ten";
75 else if (number == 11)
76 text = "eleven";
77 else if (number == 12)
78 text = "twelve";
79 else if (number == 13)
80 text = "thirteen";
81 else if (number == 14)
82 text = "fourteen";
83 else if (number == 15)
84 text = "fifteen";
85 else if (number == 16)
86 text = "sixteen";
87 else if (number == 17)
88 text = "seventeen";
89 else if (number == 18)
90 text = "eighteen";
91 else if (number == 19)
92 text = "nineteen";
93 else if (number >= 20 && number < 100 ) {
94 tmpI = 10 * (number / 10);
95 tmpS1 = get_prefix(tmpI);
96 tmpS2 = get_number_spelled(number - tmpI);
97 text = malloc((sizeof(char) * strlen(tmpS1) + 1) +
98 (sizeof(char) * strlen(tmpS2) + 1));
99 strcpy(text, tmpS1);
100 strcat(text, tmpS2);
101 } else if (number >= 100 && number < 1000 ) {
102 tmpI = number / 100;
103 tmpS1 = get_number_spelled(tmpI);
104 tmpS2 = number == 100 * tmpI ? " hundred " : " hundred and ";
105 tmpS3 = get_number_spelled(number - tmpI * 100);
106 text = malloc((sizeof(char) * strlen(tmpS1) + 1) +
107 (sizeof(char) * strlen(tmpS2) + 1) +
108 (sizeof(char) * strlen(tmpS3) + 1));
109 strcpy(text, tmpS1);
110 strcat(text, tmpS2);
111 strcat(text, tmpS3);
112 } else if (number >= 1000 && number < 10000) {
113 tmpI = number / 1000;
114 tmpS1 = get_number_spelled(tmpI);
115 tmpS2 = " thousand ";
116 tmpS3 = get_number_spelled(number - tmpI * 1000);
117 text = malloc((sizeof(char) * strlen(tmpS1) + 1) +
118 (sizeof(char) * strlen(tmpS2) + 1) +
119 (sizeof(char) * strlen(tmpS3) + 1));
120 strcpy(text, tmpS1);
121 strcat(text, tmpS2);
122 strcat(text, tmpS3);
123 }
124 return text;
125 }
126
127 int main() {
128 char* text;
129 long cont = 0L;
130 for (int i = 1; i < 1001; i++) {
131 text = get_number_spelled(i);
132 //printf("%d => %s, chars: %d\n", i, text, strlenNoSpaces(text));
133 cont += strlenNoSpaces(text);
134 }
135 printf("%ld chars\n", cont);
136 return 0;
137 }
138
martes, 25 de octubre de 2016
Euler #17
https://projecteuler.net/problem=17
jueves, 20 de octubre de 2016
Euler #13, #14, #15 y #16
https://projecteuler.net/problem=13
Problema trivial, se resuelve en una sola línea Python:
https://projecteuler.net/problem=14
En PHP:
https://projecteuler.net/problem=15
En Python, implementación recursiva. No es muy buena para valores muy grandes. De hecho, tras varias horas de ejecución, el script no termina.
Probamos el mismo algoritmo en C:
Ahora sí. En una hora el problema está resuelto. Se sabe que Python no se lleva especialmente con la recursividad.
https://projecteuler.net/problem=16
El problema 16 son tres líneas de código, se puede hacer el el mismo intérprete.
Problema trivial, se resuelve en una sola línea Python:
1 input = [37107287533902102798797998220837590246510135740250,
2 46376937677490009712648124896970078050417018260538,
3 74324986199524741059474233309513058123726617309629,
4 91942213363574161572522430563301811072406154908250,
5 23067588207539346171171980310421047513778063246676,
6 89261670696623633820136378418383684178734361726757,
7 28112879812849979408065481931592621691275889832738,
...
100 53503534226472524250874054075591789781264330331690]
101
102 print str(sum(input))[0:10]
https://projecteuler.net/problem=14
En PHP:
1 <?php
2
3 function generateCollatz($num) {
4 $ret = array($num);
5 $next = end($ret);
6 while (true) {
7 $next = $next % 2 == 0 ? $next / 2 : 3*$next + 1;
8 $ret []= $next;
9 if ($next == 1) break;
10 }
11 return $ret;
12 }
13
14
15 $longest = 1;
16 $maxCount = 0;
17 for ($x = 1; $x < 1000000; $x++) {
18 $collatz = generateCollatz($x);
19 $nCollatz = count($collatz);
20 if ($nCollatz > $maxCount) {
21 $longest = $x;
22 $maxCount = $nCollatz;
23 echo "El número $x tiene $nCollatz términos\n";
24 }
25
26 }
27
https://projecteuler.net/problem=15
En Python, implementación recursiva. No es muy buena para valores muy grandes. De hecho, tras varias horas de ejecución, el script no termina.
1 nPaths = 0;
2 def move_point(point, limit):
3 global nPaths
4 if point == limit:
5 # print("Finished!")
6 nPaths += 1
7 if point[1] < limit[1]:
8 # Continue down...
9 new_point = (point[0], point[1]+1)
10 # print("From", point, "to", new_point)
11 move_point(new_point, limit)
12 # And lets go right too
13 if point[0] < limit[0]:
14 new_point = (point[0]+1, point[1])
15 # print("From", point, "to", new_point)
16 move_point(new_point, limit)
17 elif point[0] < limit[0]:
18 new_point = (point[0]+1, point[1])
19 # print("From", point, "to", new_point)
20 move_point(new_point, limit)
21
22 move_point((0, 0), (20, 20))
23 print("N Paths", nPaths)
24
Probamos el mismo algoritmo en C:
1 #include <stdio.h>
2
3 unsigned long n_paths = 0;
4 void move_point(int x, int y, int xmax, int ymax) {
5 if (x == xmax && y == ymax) {
6 n_paths++;
7 } else if (y < ymax) {
8 move_point(x, y + 1, xmax, ymax);
9 if (x < xmax) {
10 move_point(x + 1, y, xmax, ymax);
11 }
12 } else if (x < xmax) {
13 move_point(x + 1, y, xmax, ymax);
14 }
15 }
16
17 int main() {
18 move_point(0, 0, 20, 20);
19 printf("n_paths: %lu\n", n_paths);
20 return (0);
21 }
22
Ahora sí. En una hora el problema está resuelto. Se sabe que Python no se lleva especialmente con la recursividad.
https://projecteuler.net/problem=16
El problema 16 son tres líneas de código, se puede hacer el el mismo intérprete.
Python 2.7.11 (default, Aug 9 2016, 15:45:42)
[GCC 5.3.1 20160406 (Red Hat 5.3.1-6)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> sum = 0
>>> for a in str(2**1000):
... sum += int(a)
...
>>> print sum
1366
>>>
martes, 18 de octubre de 2016
Euler #12
En Perl:
https://projecteuler.net/problem=12
No es un lenguaje que me guste mucho, pero tengo buenos recuerdos de Perl. Uno de mis primeros proyectos fue desarrollado con Perl -un sistema de gestión de usuarios para un ISP- (en 1.999, aproximadamente).
Ya van unos cuantos problemas del proyecto Euler que tratan de divisores y factorización de números y se revela lo costosos que son estos cálculos cuando se emplean algoritmos poco pulidos (como estoy haciendo yo) o por fuerza bruta.
Este 12.pl ha estado más de 6 horas corriendo, ahí va la traza (de vez en cuando saco un mensaje para ver "por donde va" el cálculo):
https://projecteuler.net/problem=12
1 #!/usr/bin/perl
2
3 sub get_factors {
4 my $num = shift;
5 my @factors;
6 for ($i = 1; $i <= $num; $i++) {
7 if ($num % $i == 0) {
8 push @factors, $i;
9 }
10 }
11 return @factors;
12 }
13
14 my $i = 1;
15 my $num = 1;
16 while (true) {
17 my @factors = get_factors($num);
18 my $nfactors = @factors;
19 if ($num % 1000 == 0) {
20 print "Calculando para número $num..., tiene $nfactors factores.\n";
21 }
22 if ($nfactors > 500) {
23 print "$num tiene $nfactors factores: " . join(", ", @factors) . "\n";
24 last;
25 }
26 $i++;
27 $num += $i;
28 }
29
No es un lenguaje que me guste mucho, pero tengo buenos recuerdos de Perl. Uno de mis primeros proyectos fue desarrollado con Perl -un sistema de gestión de usuarios para un ISP- (en 1.999, aproximadamente).
Ya van unos cuantos problemas del proyecto Euler que tratan de divisores y factorización de números y se revela lo costosos que son estos cálculos cuando se emplean algoritmos poco pulidos (como estoy haciendo yo) o por fuerza bruta.
Este 12.pl ha estado más de 6 horas corriendo, ahí va la traza (de vez en cuando saco un mensaje para ver "por donde va" el cálculo):
~$ clear && date && perl 12.pl && date
mar oct 18 22:29:31 CEST 2016
Calculando para número 195000..., tiene 80 factores.
Calculando para número 946000..., tiene 80 factores.
Calculando para número 1999000..., tiene 32 factores.
Calculando para número 2001000..., tiene 128 factores.
Calculando para número 3444000..., tiene 192 factores.
Calculando para número 5697000..., tiene 128 factores.
Calculando para número 7998000..., tiene 160 factores.
Calculando para número 8002000..., tiene 40 factores.
Calculando para número 10693000..., tiene 96 factores.
Calculando para número 14448000..., tiene 256 factores.
Calculando para número 17997000..., tiene 128 factores.
Calculando para número 18003000..., tiene 128 factores.
Calculando para número 21942000..., tiene 240 factores.
Calculando para número 27199000..., tiene 64 factores.
Calculando para número 31996000..., tiene 96 factores.
Calculando para número 32004000..., tiene 288 factores.
Calculando para número 37191000..., tiene 384 factores.
Calculando para número 43950000..., tiene 120 factores.
Calculando para número 49995000..., tiene 240 factores.
Calculando para número 50005000..., tiene 80 factores.
Calculando para número 56440000..., tiene 140 factores.
Calculando para número 64701000..., tiene 384 factores.
Calculando para número 71994000..., tiene 240 factores.
Calculando para número 72006000..., tiene 160 factores.
76576500 tiene 576 factores: 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 20, 21, 22, 25, 26, 28, 30, 33, 34, 35, 36, 39, 42, 44, 45, 50, 51, 52, 55, 60, 63, 65, 66, 68, 70, 75, 77, 78, 84, 85, 90, 91, 99, 100, 102, 105, 110, 117, 119, 125, 126, 130, 132, 140, 143, 150, 153, 154, 156, 165, 170, 175, 180, 182, 187, 195, 198, 204, 210, 220, 221, 225, 231, 234, 238, 250, 252, 255, 260, 273, 275, 286, 300, 306, 308, 315, 325, 330, 340, 350, 357, 364, 374, 375, 385, 390, 396, 420, 425, 429, 442, 450, 455, 462, 468, 476, 495, 500, 510, 525, 546, 550, 561, 572, 585, 595, 612, 630, 650, 660, 663, 693, 700, 714, 715, 748, 750, 765, 770, 780, 819, 825, 850, 858, 875, 884, 900, 910, 924, 935, 975, 990, 1001, 1020, 1050, 1071, 1092, 1100, 1105, 1122, 1125, 1155, 1170, 1190, 1260, 1275, 1287, 1300, 1309, 1326, 1365, 1375, 1386, 1428, 1430, 1500, 1530, 1540, 1547, 1575, 1625, 1638, 1650, 1683, 1700, 1716, 1750, 1785, 1820, 1870, 1925, 1950, 1980, 1989, 2002, 2100, 2125, 2142, 2145, 2210, 2244, 2250, 2275, 2310, 2340, 2380, 2431, 2475, 2550, 2574, 2618, 2625, 2652, 2730, 2750, 2772, 2805, 2860, 2925, 2975, 3003, 3060, 3094, 3150, 3250, 3276, 3300, 3315, 3366, 3465, 3500, 3570, 3575, 3740, 3825, 3850, 3900, 3927, 3978, 4004, 4095, 4125, 4250, 4284, 4290, 4420, 4500, 4550, 4620, 4641, 4675, 4862, 4875, 4950, 5005, 5100, 5148, 5236, 5250, 5355, 5460, 5500, 5525, 5610, 5775, 5850, 5950, 6006, 6188, 6300, 6375, 6435, 6500, 6545, 6630, 6732, 6825, 6930, 7140, 7150, 7293, 7650, 7700, 7735, 7854, 7875, 7956, 8190, 8250, 8415, 8500, 8580, 8925, 9009, 9100, 9282, 9350, 9625, 9724, 9750, 9900, 9945, 10010, 10500, 10710, 10725, 11050, 11220, 11375, 11550, 11700, 11781, 11900, 12012, 12155, 12375, 12750, 12870, 13090, 13260, 13650, 13860, 13923, 14025, 14300, 14586, 14625, 14875, 15015, 15300, 15470, 15708, 15750, 16380, 16500, 16575, 16830, 17017, 17325, 17850, 17875, 18018, 18564, 18700, 19125, 19250, 19500, 19635, 19890, 20020, 20475, 21420, 21450, 21879, 22100, 22750, 23100, 23205, 23375, 23562, 24310, 24750, 25025, 25500, 25740, 26180, 26775, 27300, 27625, 27846, 28050, 28875, 29172, 29250, 29750, 30030, 30940, 31500, 32175, 32725, 33150, 33660, 34034, 34125, 34650, 35700, 35750, 36036, 36465, 38250, 38500, 38675, 39270, 39780, 40950, 42075, 42900, 43758, 44625, 45045, 45500, 46410, 46750, 47124, 48620, 49500, 49725, 50050, 51051, 53550, 53625, 55250, 55692, 56100, 57750, 58500, 58905, 59500, 60060, 60775, 64350, 65450, 66300, 68068, 68250, 69300, 69615, 70125, 71500, 72930, 75075, 76500, 77350, 78540, 81900, 82875, 84150, 85085, 86625, 87516, 89250, 90090, 92820, 93500, 98175, 99450, 100100, 102102, 102375, 107100, 107250, 109395, 110500, 115500, 116025, 117810, 121550, 125125, 128700, 130900, 133875, 136500, 139230, 140250, 145860, 150150, 153153, 154700, 160875, 163625, 165750, 168300, 170170, 173250, 178500, 180180, 182325, 193375, 196350, 198900, 204204, 204750, 210375, 214500, 218790, 225225, 232050, 235620, 243100, 248625, 250250, 255255, 267750, 278460, 280500, 294525, 300300, 303875, 306306, 321750, 327250, 331500, 340340, 346500, 348075, 364650, 375375, 386750, 392700, 409500, 420750, 425425, 437580, 450450, 464100, 490875, 497250, 500500, 510510, 535500, 546975, 580125, 589050, 607750, 612612, 643500, 654500, 696150, 729300, 750750, 765765, 773500, 841500, 850850, 900900, 911625, 981750, 994500, 1021020, 1093950, 1126125, 1160250, 1178100, 1215500, 1276275, 1392300, 1472625, 1501500, 1531530, 1701700, 1740375, 1823250, 1963500, 2127125, 2187900, 2252250, 2320500, 2552550, 2734875, 2945250, 3063060, 3480750, 3646500, 3828825, 4254250, 4504500, 5105100, 5469750, 5890500, 6381375, 6961500, 7657650, 8508500, 10939500, 12762750, 15315300, 19144125, 25525500, 38288250, 76576500
mié oct 19 04:40:43 CEST 2016
~$
Suscribirse a:
Entradas (Atom)