Resolviendo el #TuentiContest: Problema 7 – The tile game

Saludos de nuevo ¿Qué tal te ha ido? He desaparecido por unos días. El viernes fue feriado en Barcelona por San Juan y no tenía planeado escribir durante el fin de semana. Llegamos al problema 7, en el que nos piden calcular la cantidad mínima de cambios que deben realizarse para pasar de una lista de elementos a otra. Luego de una pequeña aventura en C++, con este problema vuelvo a mis raíces y lo resuelvo en Java. Recuerda que también tengo publicadas mis soluciones a los otros problemas del evento. Con la finalidad de “complicar” un poco la situación, este es el primer problema en que nos mencionan la codificación de la entrada. Ahora, los datos vendrían en UTF-8 y tendríamos que tomar las precauciones al respecto. Curiosamente, para la mayoría de los lenguajes la codificación es bastante automática. En el caso de Java, simplemente hay que indicar UTF-8 al momento de crear nuestro objeto de lectura. Del resto, que se encargue el bajo nivel. Lo más curioso aún es que sabiendo esto desde hace mil años, me empeciné en que el bug que tenía mi algoritmo, luego de implementarlo, estaba en la entrada de datos. Afortunadamente, luego de un tiempo (más del que me gustaría admitir) decidí que el error no podría estar allí y cuando revisé el algoritmo, lo corregí adecuadamente. Análisis del problema Luego de cubrir la extensa descripción del problema, nos encontramos con que es un caso muy conocido en computación llamado Distancia de Edición o más específicamente, la distancia de Levenshtein, que es la más conocida. La distancia de Levenshtein es muy conocida no solo por ser un buen ejemplo de programación dinámica y recursión, sino por su vigente funcionalidad. Por ejemplo, existen varias medidas de calidad en traducción automática y reconocimiento de voz derivadas de la distancia de edición (WER, TER) y las sugerencias de los correctores ortográficos también se inspiran en la medida. Si bien es cierto que con un poco de Wikipedia podemos resolver el asunto en un dos por tres, dedicaré un momento a explicar en qué consiste la solución. Al igual que en el problema de las vacas y el de las tareas, nuestra mejor amiga aquí será la recursión. Supongamos que queremos calcular la distancia entre dos conjuntos ordenados a y b y que, estando en la fase media del cálculo nos toca comparar las piezas en las posiciones i y j de cada conjuntos  (a(i) y b(j)). Puede que sean iguales o puede que no. Si lo son, entonces no tenemos que hacer ningún cambio, por lo tanto la distancia mínima será la misma que tengamos hasta ese momento d(i,j) = d(i-1,j-1). Si por otro lado las piezas son distintas, entonces tenemos tres opciones: reemplazar a(i) por b(j), con lo cual d(i,j) = d(i-1, j-1) + reemplazo; eliminar a(i), entonces d(i,j) = d(i-1,j) + borrar; o añadir b(j), para que quede d(i,j) = d(i,j-1) + añadir. La idea es elegir la mejor de las tres opciones. Por último, debemos notar que los estados iniciales son d(i,0) = del*i (borrar i palabras) y d(0,j) = add*j (añadir j palabras). Les ofrezco un poco de ayuda extra con la siguiente imagen:

Recursión en la distancia de Levenshtein

Explicada la solución, dejamos pautada la recursión de la siguiente manera: d(i,j) = (a(i) == b(j)) ? d(i-1,j-1) : min(d(i-1,j-1)+rep, d(i-1,j)+del, d(i,j-1)+add) Con lo cual, solo nos queda implementar la solución con nuestra estrategia favorita, bottom-up o top-down con memoización. En mi caso, me incliné por la primera opción. Solución enviada Como mencioné al principio, mi solución está implementada en Java. Las primera líneas resaltadas muestran una “trampa” que suelo hacer para no jugar con los índices, mientras que las últimas representan la recursión planteada anteriormente.

import java.util.*;

public class Tile {

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in, "UTF-8");
    while(scan.hasNext()){
      String s1 = scan.next(); s1 = "0"+s1;
      String s2 = scan.next(); s2 = "0"+s2;
      String costos = scan.next();
      Scanner scanCostos = new Scanner(costos);
      scanCostos.useDelimiter(",");
      int add = scanCostos.nextInt();
      int del = scanCostos.nextInt();
      int swap = scanCostos.nextInt();

      int result = editDistance(s1.toCharArray(),s2.toCharArray(),add,del,swap);
      System.out.println(result);
    }
  }

  private static int editDistance(char[] s1, char[] s2, int add, int del, int swap) {
    int[][] cost = new int[s1.length][s2.length];
    for(int i=0;i
      cost[0][i] = add*i;
    }
    for(int i=0;i
      cost[i][0] = del*i;
    }
    for(int i=1;i
      for(int j=1;j
        if(s1[i] == s2[j]) {
          cost[i][j] = cost[i-1][j-1];
        }else{
          cost[i][j] = Math.min(cost[i-1][j-1]+swap,
              Math.min(cost[i-1][j]+del, cost[i][j-1]+add));
        }
      }
    }
    return cost[s1.length-1][s2.length-1];
  }

}

Con respecto a la “trampa” de las líneas 8 y 9: la recursión asume que los conjuntos ordenados se enumeran desde el 1, al contrario de la enumeración de todo informático que se aprecie. Esto es porque la recursión contempla las soluciones desde cero, es decir, un conjunto vacío. De no hacer ese inocente cambio, la comparación de la línea 32 sería

if(s1[i-1] == s2[j-1]) {

Solución mejorada Personalmente creo que esta implementación es bastante limpia y a la vez legible. Si se quiere ahorrar un poco de espacio, es posible implementarla utilizando dos vectores en vez de una matriz, pues solo hacemos uso de la fila anterior durante la recursión. Otra opción, aunque no de mejora sino simplemente una alternativa diferente, es utilizar la estrategia top-down con memoización en cuyo caso la función se escribiría explícitamente como una recursión,  almacenando los resultados previos cuando corresponda para no calcular dos veces los mismos números. Me ha gustado mucho este problema, en particular porque los ejemplos estaban puestos de manera tal que aún cometiendo errores en la solución, ciertos casos de prueba daban la solución correcta, con lo cual podíamos confundirnos al momento de buscar el error (al principio tenía el peso de agregar y el de eliminar cambiados y no me daba cuenta).  Solo implementándolo correctamente obteníamos el visto bueno en todos los casos de prueba. Y tú ¿cómo lo resolviste?

6 thoughts on “Resolviendo el #TuentiContest: Problema 7 – The tile game

    1. Hola Ricardo. Pues ahora no recuerdo. La competencia creo que duró una semana en total y cada quien se administraba el tiempo como quisiera. Este problema es un clásico en este tipo de competencias.

Deja un comentario