"El reto de la semana", 1ª edición

Hola a todos.

Hace tiempo, alguien (¿David?) me comentó de una web donde se ponían retos de programación. Son pequeños retos que se ofrecen a la gente para demostrar sus habilidades.

Esta web no lo soporta aunque, realmente basta con utilizar el blog. Bien. Pues eso es exactamente lo que voy a hacer. Si vemos que a la gente le gusta el invento, entonces podemos buscar cómo generalizarlo, poner algún tipo de podium y demás.

Las reglas son básicas: Sólo programación en C, el resultado se expresará como una función (llamada incluída) y dichas funciones tendrán menos de 50 líneas de código. Como "línea de código" es algo ambiguo, se aproximará como número de líneas el número de puntos y comas más el número de condiciones/bucles. Quizá más adelante soportemos otros lenguajes.

Se dispondrá de 15 días a partir de la fecha de publicación del blog correspondiente.

El primer problema es facilito, para ir abriendo boca:

Ejercicio 1: Contar el número de apariciones de cada carácter dado un puntero a fichero (abierto). Se devolverá un vector con 256 posiciones donde cada posición se corresponde con el código ascii de una letra.

int* charCount(FILE* input);

Fe de erratas

Esto de comenzar un proyectillo trae sus problemillas. Perdonad los cambios.

  • Aunque en el ejercicio digo que el fichero llega abierto, en la cabecera aparece un "Char *". La cabecera correcta es:
    int* charCount(FILE* input);
  • La cabecera es OBLIGATORIA (así se podrá corregir más fácilmente).

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de david.villa

Guru of the Week

GotW creo que esa es la página a la que se refería magmax. Pero parece que está un poco de capa caida.

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Imagen de int-0

Estais locos

Pues eso
------------------------------------
init=/bin/bash to conquer the world!

------------------------------------------------------------
$ python -c "print 'VG9udG8gZWwgcXVlIGxvIGxlYSA6KQ==\n'.decode('base64')"
------------------------------------------------------------

Imagen de admin

Con permiso de magmax

Con permiso de magmax, he cambiado el título porque eso de "gurú" me parece un poco pretencioso y queremos que participe todo el mundo.

Imagen de david.villa

Cambio en el prototipo?

Propongo cambiar el prototipo a algo más usable y que permitirá hacer funciones reentrantes e incluso recursivas.

  void charCount(FILE* fd, int* v);

o a elegir (si el fichero se abriese con open() en lugar de fopen())

  void charCount(int fd, int* v);

Sólo hay que hacer la función! Nada de programas para probarlo. Si acaso estaría bien decir qué “includes” necesita la función y se valorará que se necesiten pocos “includes”.

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Mi propuesta

He cambiado ligeramente la signatura para no tener que incluir stdio.h, pero sigue siendo compatible binario con el oficial en compiladores que tengan sizeof(void*)==sizeof(int).

También he añadido algún retorno de carro para hacerlo más digerible. Convenientemente compactado cabe en 168 octetos, incluyendo main.

Como puede verse hago un return en el charCount, pero no es realmente necesario, es por cumplir con la especificación.

Al igual que David, sacrifico tamaño por legibilidad Smiling

#define X charCount
int a[256];X(int f){while(!feof(f))++a[fgetc(f)];return a;}
main(int i,int*v){X(fopen(v[1],"r"));
for(i=0;i<256;++i)a[i]?printf("%d:%d\n",i,a[i]):0;}

Ale, animaros a compactar más

Con el cambio de API de David

La función queda en:

charCount(int f,int*a){while(!feof(f))++a[fgetc(f)];}

Una pequeña nota sobre compilación de esta propuesta:

Sea un fichero main.c:

void charCount(FILE* fd, int* v);

main(int i, char*v[]) {
  int a[256];
  charCount(fopen(v[1],"r"), a);
  for(i=0;i<256;++i)
    if(a[i]) printf("%d:%d\n",i,a[i]);
}

Ese fichero se puede linkar directamente con el objeto resultado de compilar mi solución y funciona siempre que sizeof(int)==sizeof(void*).

Si no ocurriera eso (gcc para AMD64), gana un octeto:

charCount(void*f,int*a){while(!feof(f))++a[fgetc(f)];}

Sin cumplir el API

Curiosamente un programa que hace exactamente lo mismo ocupa solo 128 octetos:

int a[256];main(int i,int*v){i=fopen(v[1],"r");
for(;!feof(i);)++a[fgetc(i)];
for(i=0;i<256;++i)a[i]?printf("%d:%d\n",i,a[i]):0;}

¿Relajamos las restricciones?

Más pequeño todavía

En 124 octetos:

int j,a[256];main(int i,int*v){i=open(v[1],0);while(read(i,&j,1))++a[j];
for(i=0;i<256;++i)a[i]?printf("%d:%d\n",i,a[i]):0;}

¿Más pequeño?

Pues si, más pequeño

121 octetos, y superclaro:

int a[256];main(int i,int*j){for(j=open(j[1],0);read(j,&i,1);++a[i]);
for(i=0;i<256;++i)a[i]?printf("%d:%d\n",i,a[i]):0;}

¿Se puede arañar un poco más?

Imagen de brue

...

Superclaro, sí, yo es en lo primero que he pensado Smiling

--
La especialización excesiva es una muerte rápida

brue

Imagen de david.villa

Ahí va el mio

Quizá se pueda mejorar, pero bueno. De todos modos yo prefiero la legibilidad que el tamaño Smiling

int* charCount(FILE* input)
{
  int* retval = (int*)calloc(256, sizeof(int));
  for (int c; (c = fgetc(input)) != EOF; retval[c]++);
  return retval;
}

Esto es con el estándar de C del 99. O sea, se compila con:

$ gcc -std=C99 file.c

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Imagen de david.villa

Qué tramposillos...

Si yo supongo que el vector es global también me sale una línea

charCount(FILE* fd) {for (int c; (c = fgetc(fd)) != EOF; v[c]++);}

aunque me gusta más el de paco, que con el feof() se ahorra la variable auxiliar:

charCount(FILE* fd) {for(;!feof(fd);)++v[fgetc(fd)];}

Y para mi el ganador, cumpliendo el prototipo que proponía yo, es también de paco, me refiero a:

void charCount(int f,int*a){while(!feof(f))++a[fgetc(f)];}

inmejorable y además muy legible.

¿Cómo se puede hacer igual de pequeña pero con el prototipo de miguel?

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Imagen de brue

pues vaya unos gurús...

Se propone una cosa y la cambiais, eso no es el concurso de gurús.

Nadie duda que lo seais (que lo sois, y Paco es insuperable), pero las reglas son las reglas, y para lucirnos, mejor el breakdance Smiling

--
La especialización excesiva es una muerte rápida

brue

Imagen de david.villa

He dado una solución...

...para el prototipo original (que tiene problemas de diseño). Y he propuesto otro reto modificado (que los resuelve). Pero el reto inicial sigue en pie. ¿Cuál es tu problema? Yo también me he quejado de que se hagan modificaciones "de conveniencia" en el prototipo.

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Imagen de magmax

¿Qué opinas de éste:

¿Qué opinas de éste:

int* charCount(FILE* input)
{
  int* retval = (int*)calloc(256, sizeof(int));
  char c;

  while ((c = fgetc(input)) != EOF)
    ++retval[c];

  return retval;
}

No está probado, pero creo que es bastante más legible. ¿O no?

Como véis, no hay ganadores ni perdedores. Se trata únicamente de una discusión.

Miguel Ángel García
http://magmax.org

Bug, bug!

Ese char c debe ser int c. EOF es -1 y si lo pasas a char entonces terminarias al encontrar caracteres 0xff, que son perfectamente posibles.

Por otro lado no hace falta ese (int*) en el calloc. calloc devuelve un void*, que como su nombre indica es un puntero a cualquier cosa, incluido int.

Imagen de david.villa

Me parece bien

Me parece bien limitar el nº de líneas, pero no creo que un programa más corto sea siempre mejor. Por eso, creo que el número de líneas no es un criterio adecuado para evaluar las soluciones propuestas.

Si el objetivo de "este concurso" es, como creo, despertar el gusto por la buena programación debemos evitar ofuscamientos. Ya haremos un concurso de "offus".

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Imagen de brue

Primera prueba

No sé si me he enterado muy bien …


int* charCount(FILE* input){

int contador256; // Suponemos a 0 todos = {0,0,0,0,0,…,0} while((int car = fgetc(input))!=EOF) contador[car]+=1; return contador; }
— La especialización excesiva es una muerte rápida

brue

Imagen de magmax

Corrección a brue

No puedes decir "suponemos a 0 todos", teniendo en cuenta que has declarado tú la variable. Las suposiciones se hacen de lo que se pasa por parámetro, no en lo que se declara uno mismo.

Por lo demás está bastante bien... Estoy yo pensando que, a lo mejor, deberíamos pensar un sistema para que no aparezcan las soluciones hasta que acabe el plazo... Lo más importante: ¿Os mola la idea?

Miguel Ángel García
http://magmax.org

Imagen de brue

Otra más corregida... y la última

Yo era por no poner los 256 ceros ...
Corregido el static del array, si no, no funciona al ser una variable local.
Esta versión está probada con GCC, aunque seguro que con otro compilador menos estricto se podría reducir aun más.
He quitado la definición del entero.

---

int* charCount(FILE* input){
  
  static int contador[257] = {0,0,0,0,0,...[257 Ceros en total]..,0};
  while((contador[256]=fgetc(input))!=EOF)contador[contador[256]]+=1;
  return contador;
}

--
La especialización excesiva es una muerte rápida

brue

Imagen de brue

Sí funciona...

/* Uso ./programa */
#include
#include

int* charCount(FILE* input);

int main(int argc, char** argv){ FILE * pFile; pFile=fopen (argv1,“r”); if (pFile==NULL) exit(1); int* h = charCount(pFile); for(h256=0;h256<256;h256++) printf(”%d: %d \n”,h256,h[h256]); return 0;
}

int* charCount(FILE* input){

static int contador257 = {0,0,0,0,0,…,0}; while((contador256 = fgetc(input))!=EOF) contador[contador256]+=1; return contador; }
— La especialización excesiva es una muerte rápida

brue

Imagen de david.villa

Poner 256 ceros no parece

Poner 256 ceros no parece muy elegante. Usa memset. ¿Y por qué pones 257? ¿Y por qué contador[256]? Que forma más rara de usar una variable auxiliar.

Y lo del static es mala idea. ¿Qué pasa si alguien hace esto?

FILE* fd1 = fopen("fichero1.txt", "r");
int* contador1 = charCount(fd1);
FILE* fd2 = fopen("fichero2.txt", "r");
int* contador2 = charCount(fd2);

comparaFrecuencias(contador1, contador2);

No funciona porque contador1 y contador2 apuntan al mismo vector, que contiene los datos acumulados de los dos ficheros (en el caso de que inicializaran con los 256 ceros).

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Cuestion de estilo

El API implícito en el programa de Sergio exige hacer:

FILE *f1, *f2;
int c1[256], c2[256];
... opens...
memcpy(charCount(f1), c1, sizeof(c1));
memcpy(charCount(f1), c2, sizeof(c2));

comparaFreq(c1,c2);

Y no por ello es incorrecto o mal estilo. En cambio si que me parece MUY mal estilo el allocatar un array en el heap en una función como esta. Si no quieres usar un array estático lo lógico sería usar una signatura del estilo charCount(FILE*,int*).

Imagen de david.villa

No he dicho que sea un estilo malo

, digo que me parece mala idea porque conlleva ese problema.

No soy portavoz de ningún colectivo, grupo o facción. Mi opinión es personal e intransferible.

Imagen de brue

Aclaraos con las reglas y con lo que se pretende

Creí que de lo que se trataba era de hacer un código pequeño, mínimo más bien.

No he entendido bien las reglas y me retiro, perdonad por la intromisión Eye-wink

--
La especialización excesiva es una muerte rápida

brue

Imagen de magmax

Sí que lo has entendido

Lo has entendido perfectamente: se trata de que cada uno aporte sus soluciones. Como puede observarse, no hay una solución óptima Eye-wink

Miguel Ángel García
http://magmax.org

Imagen de brue

... de parte de David, una mejora

Como es una declaración static, se inicializa a 0 Eye-wink

int* charCount(FILE* input){
  
  static int contador[257];
  while((contador[256] = fgetc(input))!=EOF) contador[contador[256]]+=1;
  return contador;
}

--
La especialización excesiva es una muerte rápida

brue

Las globales también se inicializan

Es mas corto usar una global pero, al igual que con static, tiene el defecto que solo funciona la primera vez que se llama.

int _c[256];

int* charCount(FILE* in){
  int i; while((i=fgetc(in))!=-1) ++_c[i];
  return _c;
}
Imagen de brue

...

5 lineas de código versus 4 del anterior ... no es más corto Sticking out tongue

--
La especialización excesiva es una muerte rápida

brue