Euler #22

https://projecteuler.net/problem=22 => Names scores

Este problema ha sido interesante resolverlo porque ilustra cómo se simplifica un problema cuando el lenguaje que utilizamos tiene funcionalidades de alto nivel. Primero veamos la implementación en C, en la que reconozco que he copiado un poco a los maestros Kernighan y Ritchie en su clásico libro:

#include <stdio.h>
#include <string.h>

#define MAXLENGHT 47000
#define NWORDS 5163

void swap(char *v[], int i, int j) {
    char *temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}

void myqsort(char *v[], int left, int right) {
    int i, last;
    if (left >= right) return;
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left + 1; i <= right; i++) 
        if (strcmp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    myqsort(v, left, last - 1);
    myqsort(v, last + 1, right);
}

int evaluate_word(char *word) {
    int len = strlen(word);
    int value = 0;
    for (int i = 0; i < len; i++) 
        value += (word[i] - 'A' + 1);
    return value;
}

int main() {
    FILE *fp;
    char line[MAXLENGHT];
    char *words[NWORDS];
    char delimiter[] = "\",\"";
    char *word;
    double sum = 0.0;

    fp = fopen("p022_names.txt", "r");
    int cont = 0;
    if (fp != NULL && fgets(line, MAXLENGHT, fp) != NULL) {
        word = strtok(line, delimiter);
        while (word != NULL) {
            words[cont] = word;
            word = strtok(NULL, delimiter);
            cont++;
        }
    }
    fclose(fp);

    myqsort(words, 0, NWORDS-1);

    for (int i = 1; i <= NWORDS; i++) {
       sum += i * evaluate_word(words[i-1]);
    }

    printf("%.0f", sum);
    return 0;
}

Veamos el mismo problema en Python:

#!/usr/bin/env python

def get_value(name):
 s = 0
 for c in name:
  s += (ord(c) - ord('A') + 1)
 return s

f = open('p022_names.txt', 'r')
txt = f.read().strip().replace('"', '')
names = txt.split(',')
names.sort()
cont = 1
total = 0
for name in names:
 total += cont * get_value(name)
 cont += 1

print total

La diferencia en cuanto a la facilidad de escribirlo en Python (o cualquier otro lenguaje de alto nivel) es clara, pero veamos los tiempos de ejecución:



167ms Python vs 39ms para C. La ejecución en Python tarda 4 veces más aproximadamente. Para un conjunto de datos más grande, en el que el tiempo de ejecución de las rutinas de ordenación depende del tamaño... la diferencia podría ser más acusada. Vamos a comprobarlo copiando el diccionario del sistema.



Son 234.371 palabras. Vamos a dejar el fichero en las mismas condiciones, esto es, con las palabras en mayúsculas, entrecomilladas y separadas por comas:

cat /usr/share/dict/words | tr '[:lower:]' '[:upper:]' | sort | uniq | tr '\n' "," | sed -e 's/,/","/g' > p022_words.txt

Editamos el fichero para corregir la primera y última comilla, cambiamos los nombres de los ficheros en el código fuente y allá vamos:



Ahora Python es unas 8 veces más lento que C.

Euler #17

https://projecteuler.net/problem=17

   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 

Euler #13, #14, #15 y #16

https://projecteuler.net/problem=13

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
>>>