Kata de palíndromos con Streams (en Scala)
Pues resulta y pasa que para una entrevista tuve que resolver un problema cuya definición (a lo que recuerdo) era:
Dada una lista de palabras, por cada elemento hacer lo siguiente:
- Obtener una combinación de las letras de la palabra las cuales sea un palíndromo, i.e. una palabra que se lee indistinguiblemente al derecho o al revés; imprimirla en consola.
- Si no se encuentra dicha combinación, imprimir "-1" en la consola.
E.g., teniendo la lista de palabras "racecar", "icicv", "dar", deberia de imprimirse algo como "racecar", "civic", -1.
Primera iteración
Ahora, yo hice una primera implementación simplemente creando las permutaciones de las letras de cada palabra y entonces filtrando los palíndromos. Esto lo hice con Scala y me quedo algo así:
Ahora, si examinan el código anterior se pueden dar cuenta que:
- Tenemos una lista de palabras "words" con las palabras del ejemplo.
- Convertimos cada uno de los elementos en un iterador que nos dara las permutaciones usando la función de alto orden map(_.permutations)
- Por cada iterador, filtramos aquellos elementos que al invertirse son iguales a si mismos (permutation.reverse == permutation); esto lo convertimos en una lista de palindromos.
- Ahora, por cada lista de palíndromos, obtenemos el primer elemento (head) y verificamos: si existe, lo imprimimos; de otro modo (i.e. no hay algo) imprimimos -1
Esto no es necesario del todo, ¿Para que generar toda la lista de permutaciones? Esto haría que tuviéramos que generar hasta k*n! elementos; donde k es el numero de palabras que tenemos y n es la longitud de la palabra mas grande (el ! junto a la n significa factorial).
Despues de muchas iteraciones
Entonces, ¿Como hacemos para no generar tantos elementos? ¿Y para no filtrar todos los elementos sino solo llegar hasta el primero que cumple alguna condición (ser palíndromo)?
Aqui es donde entran los Streams. Primero el código:
Básicamente hicimos lo siguiente:
- Tenemos la misma lista de palabras "words"
- Generamos un Stream de las permutaciones de las letras de cada palabra. He aquí lo interesante, este Stream es un iterador que ira generando elementos según se le sean pedidos (no todos a la vez). Es decir, que si viéramos el contenido del Stream al crearse, seria algo así: "Stream(rraacce, ?)". Esto lo explico después.
- Por cada Stream de permutaciones, obtenemos solo el primer elemento el cual al ser invertido es igual a si mismo i.e. un palindromo.
- Si este primer elemento existe, lo imprimimos; en el caso contrario imprimimos -1.
La teoría
Un Stream es una estructura de datos cuyos elementos se van calculando conforme estos son accesados; las implementaciones de esta estructura suelen memorizar los elementos ya materializados para no recalcularlos subsecuentemente. A esto se le llama evaluación tardía (lazy evaluation) y memoización (memoization), respectivamente.
¿Cual es la ventaja de esto? Pues que se pueden procesar sucesiones de datos muy grandes; potencialmente infinitas.
En nuestro caso particular, el generar las permutaciones de las letras de una palabra es una operación muy costosa ya que generamos al menos n! de posibles combinaciones e.g. si tuviéramos una palabra con tan solo 6 letras hay que generar ¡720 combinaciones!.
Ahora, al crear un Stream, solo se tiene el primer elemento y después se computan los subsecuentes. Es por esto que si ustedes crean un Stream en Scala y lo imprimen a consola obtienen algo como "Stream(rraacce, ?)". Esto significa que el primer elemento, la cadena "rraacce", esta listo para obtenerse; el resto, representado por el signo ?, aun no esta materializado i.e. aun no se han calculado ni están en memoria.
Regresando a la kata, aunque nuestro peor caso sigue siendo de k*n!, ya no tenemos que generar todas las permutaciones excepto en el caso en el que no existan palindromos a crear con dicha palabra. Un algoritmo mas inteligente podría inspeccionar las letras y la longitud de la palabra para saber si es posible generar palindromos e.g. si la palabra solo tiene 1 letra, pues se descarta inmediatamente.
En fin, reprobé la entrevista puesto que tarde bastante mas del limite previsto y como ven no mejore mucho el algoritmo final.
- ElderMael's blog
- Inicie sesión o regístrese para enviar comentarios
palíndromos
Para evaluar si una palabra es un posible palíndromo reordenando sus letras:
Si tiene un número par de letras, evaluar que tenga exactamente 2 veces cada letra.
Si tiene un número impar de letras, quitarle una y evaluar el resto con la condición anterior (que tenga exactamente 2 veces cada letra). Hacer esto quitando la primera, luego la segunda, etc hasta que se cumpla con alguna, o no es palíndromo.
Si resulta que sí es un palíndromo, tomar las letras únicas, ordenarlas de cualquier forma (alfabético o lo que sea), poner la letra faltante (en caso de que fuera impar) y luego poner otra vez las letras pero en reversa.
En Ceylon
En Ceylon es así:
Un algoritmo mucho más
Un algoritmo mucho más sencillo es:
Escrito en Java:
Salida:
La ventaja que tiene este procedimiento es que solo itera la cadena una vez y no la vuelve a recorrer más. En el buffer solo hay letras que no se han visto, en el caso de que sea un palindromo salen del buffer. En el peor de los casos ( una palabra muy larga que no es palindrome ) la complejidad es O(n)
The Palindrome Family
▲ Mi pequeña contribución de palíndromos. :D
Fuente:
Hola.No me quede sin las
Hola.
No me quede sin las ganas de realizar mi aporte. No sé si no estamos complicando mucho, pero creo que se puede hacer algo más eficiente en Java. Aqui va mi código:
Es O(n/2) cuando la cantidad de datos (longitud de la cadena) es par y es O floor((n/2)+1) para la cantidad de datos es impar.
Salu2 desde Colombia.
Corrijo mi apunte sobre el algoritmo
El algoritmo es O (floor(n/2)+1)
no
Ese último algoritmo está mal; si le pasas algo como "vciic" te va a dar -1.
Entonces, ¿Como hacemos para
Entonces, ¿Como hacemos para no generar tantos elementos? ¿Y para no filtrar todos los elementos sino solo llegar hasta el primero que cumple alguna condición (ser palíndromo)?
Bueno en Scala la funcion toSeq sobre un Iterator de texto nos da un Stream y la funcion find hace precisamente ubicar el primer elemento que cumple una condicion, entonces podriamos hacer:
Pregunta
Buena tarde.
Leo y leo el problema y entiendo que el algoritmo debe estar en capacidad de recibir una cadena e imprimir -1 cuando no es palindrome o imprimir "es palindrome" si lo es. Si yo tomo la cadena que tu indicas ezamudio "vciic", al reversarla quedará como ciicv es es diferente de vciic. Con esa condición, veo que mi algoritmo funciona correctamente.
Si hay algo que no alcance a entender, me podrías por favor explicar cual es mi error.
Salu2!!!!!
permutaciones
La descripción original del problema claramente dice que el algoritmo debe detectar si cualquier combinación de letras en la cadena puede dar un palíndromo. vciic no es un palíndromo, pero si reordenadas las letras, puedes tener civic o icvci; por lo tanto vciic es un palíndromo (y te debe mostrar al menos uno de los posibles palíndromos formados con esas letras).
Por eso hemos estado diciendo definiciones de lo que debe tener una palabra para ser un posible palíndromo. Mi definición fue que todas sus letras deben tener un número par de ocurrencias dentro de la cadena, si su longitud es par; si su longitud es non, entonces adicionalmente debe tener una letra que ocurre una sola vez.
@jvrlo Lee el problema original, la
Lee el problema original, la parte relevante es esta:
Obtener una combinación de las letras [....] [e] imprimirla en consola.
Es decir no necesariamente en el orden en el que están las letras, sino una combinación de ellas e imprimir esa combinación. No dice: imprimir "es palindrome" en ningún lado.
Y en
E.g., teniendo la lista de palabras "racecar", "icicv", "dar", deberia de imprimirse algo como "racecar", "civic", -1.
Tu implementación imprime:
@echan La idea de calcular
@echan La idea de calcular las permutaciones es para empezar muy ineficiente, la solución de usar "find" solo la hace un poquito menos ineficiente en el caso que de la condición se cumpla en las primeras permutaciones, pero si es en las ultimas o peor aún si la palabra no es palindrome se siguen haciendo computaciones innecesarias.
Por ejemplo la frase "anitalavalatinaxyz" ( que no es palindrome ) tiene más de 500 mill millones de permutaciones
No tiene ningún caso optimizar algo que esta mal en principio.
Buen punto, las permutaciones
Buen punto, las permutaciones crecen gigantescamente y el ejemplo se calcula de forma estricta, pero no creo que este mal en principio, es decir, la kata no es explicito en terminos de eficiencia ni tampoco a que se refiere el primer palindromo. Suponiendo que asi fuera y el primer palindromo sea por orden de aparición los ejemplos que han dado funcionan perfectamente, pero si es lexicográficamente no veo de otra que no sea generar permutaciones y lo mas que se podría hacer es hacerlas por demanda.
Por ejemplo de la palabra "tustus" cual es el primer palindromo? "suttus" o "tussut"? por orden de aparición a lo mejor "tussut" pero lexicográficamente es "suttus".
En la entrevista simplemente
En la entrevista simplemente tome el problema y lo trate de ejecutar con lo primero que me llego a la mente. Esto fue generar las permutaciones (puesto que ya había visto que en Scala se podía hacer rápido; con un solo método). Como lo explica @OscarRyz, fue una mala decisión empezar por ahí mas obviamente me preguntaron que si esta seria la mejor implementación y como la mejoraría.
Mis dos respuestas fueron 1) Para la implementación actual, usar un Stream (explicando la estructura de datos) y la 2) fue:
Eso es exactamente de lo que se trataron las demás aportaciones.
A mi se me ocurría un mapa en el cual las llaves fueran las letras y los valores el numero de veces que se repiten; al final solo comprobaría que todas las llaves tuvieran valores pares permitiendo una sola tener un numero impar. Luego iterar el set de tuplas de llaves y valores imprimiendo N veces (donde N es el valor en el mapa) al principio y al final (parecido a la respuesta de @OscarRyz). Pero de todos modos no tenia tiempo para programarlo.
La primera ves que lo intente solucionar.
Hace ya un tiempo lo solucione de la siguiente manera:
Ya se que es una manera muy fea pero que puedo hacer.
@Diego Lee el post original,
@Diego Lee el post original, no se trata de determinar si es o no palíndromo, sino que ver si alguna permutación de la palabra puede formar un palíndromo y e imprimirlo en caso de que si se pueda.