Guia Tarea Algoritmos

Tarea Nº2

Diferencias

Alumno: Agustín Matthey

Profesor: Jérémy Barbay

Auxiliares: Bernardo Subercaseaux R.

                    Cristóbal Muñoz V.

1. Descripción del problema: Se nos pide encontrar un método, utilizando herramientas de programación (Java en particular), para generar una lista con los cambios que deben realizarse en un archivo de texto, con tal de que su contenido termine siendo igual al de un segundo archivo (el archivo objetivo). El requerimiento base, es que el número de cambios realizado sea el mínimo posible. En cuanto a la profundidad de los cambios, éstos solo deben realizarse a nivel de líneas de texto (no palabras o letras), y pueden presentarse de tres formas: cambiar, borrar e insertar. El primer caso se trata de tomar la línea y reemplazar su contenido completamente por el de una línea del archivo objetivo. El segundo es simplemente borrar la línea en cuestión (desplazándose una línea todo lo que esté delante de ésta), y finalmente, insertar, consta de agregar una nueva línea en una posición determinada, resultando en un desplazamiento de las líneas posteriores. Para resolver el problema, se intentará un enfoque recursivo, por lo que los casos base deberán estar bien definidos, particularmente ¿qué pasará al comparar un archivo vacío con otro que no lo está? ¿y dos archivos con el mismo contenido?

1. Descripción de la solución: Para comenzar bien encaminados hacia la solución, es fundamental tener información sobre el número de pasos mínimos para realizar la transformación de un archivo en el otro, que es un requisito importante de la tarea. Para ello implementamos la función dist, que calcula precisamente el dato buscado, y lo hace de manera recursiva. Es más fácil entender la implementación de esta función, pensando en cómo se utilizaría para medir la distancia entre dos palabras (la relación con el caso que nos concierne es directa, ya que podemos considerar cada letra de la palabra como si fuera una línea de texto). Podemos calcular el número que buscamos, probando distintas maneras de deconstruir ambas palabras, letra por letra, hasta quedar con nada, y viendo cual es la deconstrucción más rápida posible, considerando que las opciones son: eliminar la letra final de la primera palabra (sumando un paso), eliminar la letra final de la segunda (sumando un paso) y eliminar las letras finales simultáneamente (sumando un paso si son diferentes y sumando cero si son iguales). La función recorrerá todos los posibles caminos, y nos entregará el número de pasos que toma seguir el más corto.

En la porción de código siguiente, se presenta la parte central de la función distancia, que muestra las bifurcaciones que se toman para llegar al resultado final. Los arrays lineas1 y lineas2, contienen la información de los argumentos de la función, y Nuevarg1 y Nuevarg2, son las versiones reducidas de los arrays anteriores (sin el elemento final).

int check = 0;
if (!lineas1[l1 - 1].equals(lineas2[l2 - 1])) {
   check = 1;
}
int a = dist(Nuevarg1, lineas2) + 1;
int b = dist(lineas1, Nuevarg2) + 1;
int c = dist(Nuevarg1, Nuevarg2) + check;
int d = Math.min(Math.min(a, b), c);

return d;

Lo interesante, es que la función distancia puede decirnos más que solo el mínimo de pasos necesarios para transformar un archivo de texto en otro, ya que cada decisión que toma la función puede interpretarse como una modificación en particular (cambiar, borrar o insertar).

Volviendo a la explicación a través del caso con palabras, si buscamos transformar una palabra cualquiera A en otra B, si el camino óptimo que encuentra la función distancia es, por ejemplo, borrar la última letra de la palabra A, borrar las letras finales de ambas palabras (viendo que éstas son diferentes) y borrar las letras de ambas palabras (viendo que éstas son iguales) , ¿qué podemos deducir sobre los cambios a realizar?

En éste caso un par de palabras que cumplirían con lo anterior serían A=ota y B=et. Borrar una letra de la palabra A, significa acercarnos un paso a la palabra B, por lo que es precisamente ese el cambio que debe hacerse. Luego si borramos ambas letras t, significa que estas letras son compartidas, por lo que no hay que hacer cambios. Por último, borrar dos letras diferentes, significa que debemos cambiar la letra borrada de la palabra A, por la letra borrada de la palabra B. Lo que faltaría sería borrar una letra de la palabra B; esto significa que hay una letra que falta en la palabra A, para alcanzar a la palabra B, por lo que se debe insertar esa letra en la palabra A.

int caminoaseguir = Math.min(Math.min(dist(Nuevarg1, lineas2) + 1, dist(lineas1, Nuevarg2) + 1), dist(Nuevarg1, Nuevarg2) + check);

if (caminoaseguir == dist(Nuevarg1, lineas2) + 1) {
   String[] lineas31 = new String[lineas3.length + 1];
   for (int i = 0; i < lineas3.length; ++i) {        //transfiriendo todos los elementos a una lista con un espacio extra
       lineas31[i] = lineas3[i];
   }
   lineas31[lineas3.length] = Integer.toString(l1) + " , d";
   return cambios(Nuevarg1, lineas2, lineas31);
}
if (caminoaseguir == dist(lineas1, Nuevarg2) + 1) {
   String[] lineas31 = new String[lineas3.length + 1];
   for (int i = 0; i < lineas3.length; ++i) {        //transfiriendo todos los elementos a una lista con un espacio extra
       lineas31[i] = lineas3[i];
   }
   lineas31[lineas3.length] = Integer.toString(l2) + " , i , " + lineas2[l2 - 1];
   return cambios(lineas1, Nuevarg2, lineas31);
}
if (caminoaseguir == dist(Nuevarg1, Nuevarg2) + 1) {
   String[] lineas31 = new String[lineas3.length + 1];
   for (int i = 0; i < lineas3.length; ++i) {        //transfiriendo todos los elementos a una lista con un espacio extra
       lineas31[i] = lineas3[i];
   }
   lineas31[lineas3.length] = Integer.toString(l2) + " , c , " + lineas2[l2 - 1];
   return cambios(Nuevarg1, Nuevarg2, lineas31);
}
if (caminoaseguir == dist(Nuevarg1, Nuevarg2)) {
   return cambios(Nuevarg1, Nuevarg2, lineas3);
}

...