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.