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

Vale, hora del siguiente reto (aunque sea la misma semana)

Subreto 1:

El fácil: Codificar un programa que admita una cadena de texto como argumento y detecte si esa cadena de texto es un palíndromo o no.

Un palíndromo es un texto que se lee igual al derecho que al revés (ej: Dábale arroz a la zorra el abad).

Nótese que las tildes y las mayúsculas no cuentan.

Subreto 2

Mismo programa que antes pero ahora imprime por pantalla el mayor palíndromo que pueda extraer desde el comienzo de la cadena de texto.

Ale, a currelar.

Comments

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
david.villa's picture

Algún intrépido...

...que lo intente resolver en brainfuck, por lo menos el subreto 1. No tiene porqué ser esta semana. Quizá después de exámenes.

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

magmax's picture

Solucion 2º Reto

Seguramente no sea la más corta, pero creo que es una solución bastante buena.

/* Escriba un programa que permita decidir si una determinada cadena es palíndroma o no. */

#include 
#include 
#include 


#define MAX_SIZE 1000
#define END -1
#define TRUE 1
#define FALSE 0
#define TRANSLATION "Aquí van los 256 caracteres de traducción."
#define DELETE " "

int get_line (char line[]){
  char c;
  int n = 0;

  while ((c = getchar()) != '\n' && c != EOF) {
    if (n < MAX_SIZE) {
      line[n] = c;
      ++n;
    } else {
      fprintf(stderr, "Limit surpassed.");
    }
  }

  if (n == 0 && c == EOF) return END;

  line[n] = '\0';
  return n;
}

int esPalindromoLen(char line[], int length){
  int i = 0;
  while (i < length-i) {
    //    printf("%c == %c\n", line[i], line[length-i-1]);
    if (line[i] != line[length-i-1]) return FALSE;
    i++;
  }
  return TRUE;
}

int esPalindromo (char line[]){
  return esPalindromoLen (line, strlen(line));
}


char* normalizar(char* source, char* translation, char* delete){
  int length = strlen(source);
  char *retval = malloc (length);
  short c;
  int src_cnt = 0;
  int ret_cnt = 0;

  for (src_cnt = 0; src_cnt < length; ++src_cnt){
    c = source[src_cnt];
    
    if (strchr (delete, c) == NULL) {
      retval[ret_cnt] = translation[c];
      ret_cnt++;
    }


  }
  retval[ret_cnt] = '\0';

  printf("Cadena normalizada: _%s_\n", retval); 


  return retval;
}

int main(){
  char line[MAX_SIZE];
  char* normal;
  int length = 0;

  line[0] = '\0';

  while ((length = get_line(line)) != END){
    normal = normalizar(line, TRANSLATION, DELETE);
    if (esPalindromoLen (normal, length))
      printf("SÍ\n");
    else
      printf("NO\n");
    free(normal);
  }
  free(line);
  return 0;
}

La función de normalización hace lo mismo que la que puse en Python. De hecho, recibe hasta los mismos parámetros. Lo único que pasa es que no tuve tiempo para definir la cadena de transformación :-D.

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

david.villa's picture

¿Un requisito del "reto de

¿Un requisito del "reto de la semana" no era que el programa debía tener menos de 50 líneas? Ya se que se puede comprimir. Yo prefiero que sean 50 lineas legibles, en lugar de 12 ofuscadas, pero esto tiene 91!

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

magmax's picture

Cierto: aquí está uno más corto.

Aunque David tiene razón en que el código era demasiado largo, también hay que decir que no hacía lo que se pedía.

Mi código tomaba líneas de la entrada estándar y comprobaba si eran palíndromas o no, cuando lo que debía hacer es tomar una única línea mediante entrada estándar.

Esto lo ha simplificado bastante, y el programita sloccount me dice que tiene 44 líneas. Se podría simplificar aún más, pero, en mi opinión, a costa de la claridad.

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


#define MAX_SIZE 1000
#define END -1
#define TRUE 1
#define FALSE 0
#define TRANSLATION "FIXME:Mapa de 256 caracteres utilizados en la normalización!!"
#define DELETE " "

int esPalindromoLen(char line[], int length){
  int i = 0;
  for ( ; i < length-i; ++i) {
    if (line[i] != line[length-i-1]) return FALSE;
  }
  return TRUE;
}

int esPalindromo (char line[]){
  return esPalindromoLen (line, strlen(line));
}


char* normalizar(char* source, char* translation, char* delete){
  int length = strlen(source);
  char *retval = malloc (length);
  short c;
  int src_cnt = 0;
  int ret_cnt = 0;

  for (src_cnt = 0; src_cnt < length; ++src_cnt){
    c = source[src_cnt];
    
    if (strchr (delete, c) == NULL) {
      retval[ret_cnt] = translation[c];
      ret_cnt++;
    }
  }
  retval[ret_cnt] = '\0';

  return retval;
}

int main(int argc, char* argv[]){
  char* normal;

  if (argc < 2){
	 printf("Debe introducir una cadena a comprobar\n");
	 exit(-1);
  }

  normal = normalizar(argv[1], TRANSLATION, DELETE);
  printf(esPalindromo(normal)?"SÍ\n":"NO\n");

  free(normal);
  return 0;
}

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

brue's picture

SUBRETO 2

No sé cómo será de eficiente, pero yo pongo una primera solución rápida y sin pensar…

Seguro que Paco hace una mucho mucho mucho mejor… pero bueno, algo es algo:


#include
#include
#include

int mayor(char* c, int s){ if (p(c,s) || (s<1) ) {return s;} else return mayor(c,s-1);
}

int p(char* c, int s){ return (s<2) || (c0==c[s-1]) && p(c+1,s-2);
}

main(int a,char* v[]){ char* c;

// Aqui se hace la normalizacion de la cadena c = malloc(strlen(v1)); strncpy(c,v1,strlen(v1)); c[mayor(v1,strlen(v1))]=0; printf(”%s\n”,c); }


La especialización excesiva es una muerte rápida

brue

brue's picture

subreto 2 un poco más pequeño

Se supone que el primer argumento del programa está procesado:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int m(char* c, int s){
  return p(c,s)?s:m(c,s-1);
}
int p(char* c, int s){
  return (s<2) || (c[0]==c[s-1]) && p(c+1,s-2);
}
main(int a,char* v[]){
  char* c = strdup(v[1]);
  c[m(v[1],strlen(v[1]))]=0;
  printf("brue 2006\n=> %s\n",c);
}


La especialización excesiva es una muerte rápida

brue

brue's picture

Más pequeño y superclaro :)

#include <stdio.h>
#include <string.h>
#define X char* c
#define C int
#define F c[1]
C m(X,C s){return p(c,s)?s:m(c,s-1);}
C p(X,C s){return (s<2)||(c[0]==c[s-1])&&p(c+1,s-2);}
main(C s,X[]){char* y= strdup(F);y[m(F,strlen(F))]=0;printf("%s\n",y);}


La especialización excesiva es una muerte rápida

brue

brue's picture

y un poquito más pequeño ...

...ver el de arriba


La especialización excesiva es una muerte rápida

brue

brue's picture

216 Bytes

#define X char* c
#define C int
#define J C s
C m (X,J){return p(c,s)?s:m(c,s-1);}
C p (X,J){return(s<2)||(c[0]==c[s-1])&&p(c+1,s-2);}
main(J,X[]){char* y= strdup(c[1]);y[m(c[1],strlen(c[1]))]=0;printf("%s\n",y);}


La especialización excesiva es una muerte rápida

brue

brue's picture

Eran 214

Pues eso…


La especialización excesiva es una muerte rápida

brue

Ricki's picture

Normalizar la cadena

Estáis hablando de que hay que normalizar la cadena, pero ¿qué es eso exactamente? Supongo que será cambiar las á, à, â, ä por una a, y así con todos los caracteres fuera del ASCII de 7 bits. Si es eso, esta parte va de picar código porque caracteres con tíldes hay para hartarse, y sino mirad en polaco: ŕ, ś, ć, ź, ł.

magmax's picture

Normalizando una cadena (python)

A lo mejor pensáis que el método es un poco cutre, pero la verdad es que es bastante práctico.

Lo primero es definir los 256 caracteres que forman las cadenas que nosotros queremos:

vectorNormal = '\x00\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x0b\x0c\r' +\
	'\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b' +\
	'\x1c\x1d\x1e\x1f !"#$%&\'()*+,-./0123456789:;<=>?@' + \
	'abcdefghijklmnopqrstuvwxyz[\\]^_`' + \
	'abcdefghijklmnopqrstuvwxyz{|}~\x7f\x80\x81\x82\x83\x84\x85\x86\x87' + \
	'\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f\x90\x91\x92\x93\x94\x95' + \
	'\x96\x97\x98\x99\x9a\x9b\x9c\x9d\x9e\x9f\xa0\xa1\xa2\xa3' + \
	'\xa4\xa5\xa6\xa7\xa8\xa9\xaa\xab\xac\xad\xae\xaf\xb0\xb1' + \
	'\xb2\xb3\xb4\xb5\xb6\xb7\xb8\xb9\xba\xbb\xbc\xbd\xbe\xbf' + \
	'aaaaaa\xc6çeeeeiiii\xd0ñooooo\xd7\xd8uuuu\xdd\xde\xdfaaa' + \
	'aaa\xe6çeeeeiiii\xf0\xf1ooooo\xf7\xf8uuuu\xfd\xfe\xff'

Y una vez hecho eso, ya es trivial:

import sys, string
if len(sys.argv) == 1:
	print "debe introducir la cadena a normalizar\n"

print string.translate(sys.argv[1],vectorNormal)

Esto permite modificar los caracteres en cualquier idioma, de una única llamada. A lo mejor nos interesa cambiar los caracteres raros por espacios, o quitar los símbolos de puntuación, ... todo es posible.

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

cleto's picture

Yo he intrepretado...

Que serán caracteres en español. No creo que haya que incluir todos los caracteres raros de otros idiomas.

Que creo yo! Smiling

**"Hay obras de caridad
y obras de sentimiento...
pero las que más duran
son las del Ayuntamiento"**

cleto's picture

De momento....

No puedo cumplir los requisitos. Espero solventar los problemas que PROLOG me pone. Hay que tener en cuenta que el manejo de caracteres es algo escaso y que... bueno... hay que pensar mucho para normalizar la cadena. Aún así, en PROLOG:

palin(X):-delete(X,32,A),reverse(A,A).

El requisito de los espacios lo cumple, pero las tildes y las mayúsculas todavía falta por interpretarlas. ¿Se puede conseguir? Smiling

Un saludo!

**"Hay obras de caridad
y obras de sentimiento...
pero las que más duran
son las del Ayuntamiento"**

cleto's picture

Un poco más...

He conseguido hacer que las mayúsculas se traten bien. Por lo tanto, ahora controla los espacios y las mayúsculas. Lo que veo mucho más raro es que pueda hacerlo para las tildes. El código queda:

palin(X):-delete(X,32,A),string_to_list(C,A),downcase_atom(C,D),string_to_list(D,E),reverse(E,E).

Si no le poneis tildes, la frase palíndroma la detecta sin problemas. ¿Habrá posibilidad para controlar las tildes sin alargar mucho el código?. Ya veremos…

**“Hay obras de caridad
y obras de sentimiento…
pero las que más duran
son las del Ayuntamiento”**

cleto's picture

Sin ningún control

Sin controlar nada de nada...

p(X):-reverse(X,X)

Creo que he encontrado un predicado para Prolog que acepta los parámetros de consola. Lo probaré. Se trata de

unix(argv(Lista_Argumentos)).

Lista_Argumentos toma el valor del argv de toda la vida... lo que pasa es que creo que lo hace atómico. O sea, que debería convertir la frase ya normalizada a lista para que mi programa funcionara.

Investigaremos...

**"Hay obras de caridad
y obras de sentimiento...
pero las que más duran
son las del Ayuntamiento"**

david.villa's picture

Como no has dicho ningún lenguaje

pues a bote pronto se me ocurre una solución en Python para el subreto 1:

def esPalin(cad):
   return len(cad)<2 or cad[0] == cad[-1] and esPalin(cad[1:-1])

Pero conociendote seguro que hay otra solución dolorosamente fácil y corta. También supongo que un lenguaje declarativo (que conozco más bien nada) podría ser útil para este tipo de problema. El subreto 2 tiene más miga. Lo pensaré más despacio cuando tenga más tiempo.

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

david.villa's picture

Un poco más corto

Ya me parecía a mi que era mucho código para ser Python. Ahí va una nueva versión. Ya sé que falta el preprocesado de acentos, mayúsculas y espacios. Eso en la próxima entrega.

def esPalin(cad): return cad == cad[::-1]

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

david.villa's picture

Otro poco más corto

Con las “retorcidas” funciones lambda. Para que luego digan que Python es más legible que Perl… Smiling


lambda x: x == x[::-1]

(lambda x: x == x[::-1])(“abccba”) # ejemplo de uso

aunque se le puede asignar un identicador a la función si se quiere, pero entoces sería más largo. Algo como:


esPalin = lambda x: x == x[::-1]

esPalin(“abccba”) # ejemplo de uso

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

brue's picture

boh ...

¿y los espacios? ¿y las acentuadas?

En c, después de procesar, sería algo como esto… pero seguro que se puede hacer más corto…


int pal(char* p, int s){
  if (s<2) return 1;
  if (p[0]==p[s-1]) return pal(p+1,s-1);
  else return 0;
}


La especialización excesiva es una muerte rápida

brue

brue's picture

otro en C

Gracias a David también:

int p(char* c, int s){
  return (s<2) || (c[0]==c[s-1]) && p(c+1,s-2);
}


La especialización excesiva es una muerte rápida

brue

david.villa's picture

Te has colao

Es Python, ese código funciona incluso con Unicode. De hecho es un vector (de lo que sea). Sirve para encontrar secuencias palíndromas de todo tipo de objetos, no solo carácteres, siempre que se puedan comparar para igualdad.

Además no hacía falta tanto, el enunciado decia:

"Nótese que las tildes y las mayúsculas no cuentan"

Y por cierto, el argumento debe ser "una cadena", no "una cadena y su tamaño".

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

nacho's picture

Tildes y mayúsculas

Bueno, bajo mi punto de vista la función que resuelve si la cadena es un palíndromo o no, debería ser independiente de la comprobación de tildes y tal. Yo haría una función aparte que transformara las mayúsculas en minúsculas y quitara las tildes, y el resultado lo pasaría a la función que se pide...

---
Que la Fuerza os acompañe...

Nacho

brue's picture

je

No cuentan lo he entendido como: "es igual que esté acentuada o no, no cuenta" ... con lo cual, si le metes la frase del ejemplo de Paco a tu programa, no funciona.

Y si no se le pone el tamaño ... ¿cómo se resuelve en C?

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

brue

david.villa's picture

Ya te pillo

Suponía que quería decir que los acentos no cuentan, porque sino tiene mucha tela el invento, y tu programa tampoco valdría.

Y si no se le pone el tamaño … ¿cómo se resuelve en C?

Pues midiendo el tamaño de la cadena, que para eso acaban con un cerito.

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

david.villa's picture

Me colé yo

Tienes razón, aunque me despistó que tu programa no contemplase tampoco los problemas que tenía el mio. Mi suposición era incorrecta. He aquí la importancia de una buena ERS Smiling
Dice Paco que hay que normalizar la cadena... Ya me parecía a mi que era demasiado fácil.

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