style="display:inline-block;width:728px;height:90px"
data-ad-client="ca-pub-5164839828746352"
data-ad-slot="7563230308">

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

  val words = List("racecar", "icicv", "dar")     //> words  : List[String] = List(racecar, icicv, dar)

  words.map(_.permutations).foreach(permutations => {

    val palindromes = permutations.filter(permutation => {
      permutation.reverse == permutation
    }).toList

    palindromes.headOption match {

      case Some(palindrome) => println(palindrome)
      case None => println(-1)

    }

  })                                              //> racecar
                                                  //| icvci
                                                  //| -1

Ahora, si examinan el código anterior se pueden dar cuenta que:

  1. Tenemos una lista de palabras "words" con las palabras del ejemplo.
  2. Convertimos cada uno de los elementos en un iterador que nos dara las permutaciones usando la función de alto orden map(_.permutations)
  3. 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.
  4. 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:

  val words = List("racecar", "icicv", "dar")     //> words  : List[String] = List(racecar, icicv, dar)

  words foreach (word => {

    val permutations = word.permutations.toStream

    permutations.collectFirst({

      case x if x.reverse == x => x

    }) match {
      case Some(palindrome) => println(palindrome)
      case None => println(-1)
    }

  })                                              //> racecar
                                                  //| icvci
                                                  //| -1

Básicamente hicimos lo siguiente:

  1. Tenemos la misma lista de palabras "words"
  2. 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.
  3. Por cada Stream de permutaciones, obtenemos solo el primer elemento el cual al ser invertido es igual a si mismo i.e. un palindromo.
  4. 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.

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 ezamudio

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.

Imagen de ezamudio

En Ceylon

En Ceylon es así:

String palindrome(String s) {
  "Devuelve la cadena recibida pero sin la letra en la posición indicada"
  function remove(String s, Integer i) => i==0 then s else s.initial(i)+s[i+1...];
  "Indica si una cadena (de longitud par) tiene exactamente 2 veces cada una de sus letras"
  function epal(String z) => z.every((c) => z.count((d) => d==c) == 2);
  "Reordena las letras de la cadena"
  function makepal(Integer i) {
    value sb = StringBuilder();
    for (c in s[0:i]) {
      if (!c in sb) {
        sb.appendCharacter(c);
      }
    }
    return sb.string+(i==s.size then "" else s[i:1])+sb.string.reversed;
  }
  if (s.size % 2 == 1) {
    for (i in 0..s.size-1) {
      if (epal(remove(s,i))) {
        return makepal(i);
      }
    }
    return "-1";
  }
  return epal(s) then makepal(s.size) else "-1";
}

Un algoritmo mucho más

Un algoritmo mucho más sencillo es:

- Iterar cada letra y guardarla en un buffer temporal
- Si la letra ya existe sacarla del buffer y ponerla en buffer de palindromo potencial

-Si al final el buffer esta vacío (porque hubo duplicados y se movieron al buffer del palíndromo) o tiene una sola letra,
entonces tenemos un palindromo.

-Si tiene más de 2 letras quiere decir que ninguna combinación formaría el palíndromo.

Escrito en Java:

import java.util.List;
import java.util.ArrayList;

import static java.util.Arrays.asList;
import static java.lang.System.out;

class Palindrome {
    public static void main( String ... args ) {
        asList("rececar", "icicv", "dar", "anita lava la tina", "anitalavalatina").forEach( Palindrome::print );
    }
    private static void print(String word) {
        List<Character> buff = new ArrayList<>(word.length());
        List<Character> pal  = new ArrayList<>(word.length()/2+1);

        for ( Character c : word.toCharArray() ) {
            if ( buff.contains(c) ) {
                buff.remove(c);
                pal.add(c);
            } else {
                buff.add(c);
            }
        }
        if ( buff.size() > 1 ) {
            out.println(-1);
            return;
        }
        //print the palindrome buffer
        int i = 0;
        while( i < pal.size() ) {
            out.print(pal.get(i++));  
        }
        if ( buff.size() == 1 ) {
            out.print(buff.get(0));
        }
        while ( i > 0 ) {
            out.print(pal.get(--i));
       }
        out.println();
    }
}

Salida:

java Palindrome
ecrarce
icvci
-1
-1
aaltinavanitlaa

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: http://bizarrocomics.com/2013/10/24/shame-on-me/

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:

public class Test1 {
               
        public static void main(String[] argsv) {
                String[] arrayWords = {"racecar", "icicv", "dar"};
               
                for(String word : arrayWords){
                        validateWord(word);
                }
               
        }
       
        public static void validateWord(String word){
                for(int i=0; i<=(word.length()/2); i++){
                        if(!String.valueOf(word.charAt(i)).equals(String.valueOf(word.charAt(word.length()-1-i)))){
                                System.out.println("-1");
                                return;
                        }
                }
                System.out.println("Es palindrome");
        }

}

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)

Imagen de ezamudio

no

Ese último algoritmo está mal; si le pasas algo como "vciic" te va a dar -1.

Imagen de echan

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:

 val words = List("racecar", "icicv", "dar", "nono")
 val pal  =  words.map( _.permutations.toSeq.find{w => w.equals(w.reverse)}.getOrElse("-1"))
 println(pal)   // List(racecar, icvci, -1, noon)

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

Imagen de ezamudio

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:

Es palindrome
-1
-1

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

Imagen de echan

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

Imagen de ElderMael

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:

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.

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.

Imagen de diegoeva

La primera ves que lo intente solucionar.

Hace ya un tiempo lo solucione de la siguiente manera:

public static void main(String[] args) {
        Scanner leer = new Scanner(System.in);
       
        String cad, invertido="";
       
        char original[];
        char copia[];
        char intento[];
       
       
        System.out.println("Ingresa el palindromo");
       
        cad=leer.nextLine();
       
        //quitando los espacios de la cadena
        intento=cad.toCharArray();
        String sinesp="";
        for (int i = 0; i < intento.length; i++) {
            if(intento[i]!=' '){
                sinesp+=intento[i];
            }
        }
       
        original = sinesp.toCharArray();        
       
        //Invertir el arreglo original
        copia=new char[original.length];
       
        for (int i = copia.length-1,j=0; j < original.length; i--,j++) {
            copia[j]=original[i];
        }
        //concatenando arreglo copiado a nueva cadena
        for (int i = 0; i < copia.length; i++) {
            invertido+=copia[i];
        }
       
        //comparando las cadenas
       
        if(sinesp.equals(invertido)){
            System.out.println("Es palindromo!!");
        }else{
            System.out.println("No es palindromo");
        }      
    }
   
}

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.

style="display:inline-block;width:728px;height:90px"
data-ad-client="ca-pub-5164839828746352"
data-ad-slot="7563230308">