viernes, 26 de abril de 2013

La tournée de un caballo por esos tableros de Dios -- en Java -- . (Tour Knight in Java language)



Cómo sobrevivir sin un duro
Algo cuco para no dejar el árbol en los huesos

Comienzos de Diciembre de 2012, me surgió un apañillo.
Un estudiante de ingenería informática en la UNED se vió sorprendido por una de sus asignaturas – en concreto la asignatura más avanzada de programación como tal – “Programación III”, obligada para Ingenierías técnicas informáticas – sistemas y gestión –, como para la Ingeniería superior informática.
 Me pidió, le echara una mano.



Contexto sobre la asignatura “Programación III”


Lo que a continuación detallo es tan real como venenoso. Sufrido en carnes, incluso.
       Al tratarse de algo muy español y muy propio de nuestro sistema y país, no lo voy a traducir   --Dejo a visitantes foranos la opción de traducción por "DIY"--.
       Es más, para no desvirtualizar el contenido de la entrada en sí, voy a empezar a usar botones de expandir.





En el curso academico 2005/2006 también me pasó a mi. Entonces, valía 6 créditos – era el plan anguo del 2000 – . Cada curso tenía dos cuatrimestres. Esta se cursaba en el 2º curso, 1er cuatrimestre.

La consecución exitosa de la asignatura



Desde el año que me intenté enfrentar a ella (por primera y última vez) hasta este año académico – a la vista de lo que la otra parte del acuerdo me demandó –, no ha variado nada.
Consiste en que – si el curso se puede empezar entre el 1 de Octubre y el 1 de Noviembre de un año académico – , a mediados de Febrero, más tardar, te examinaban de “si posees el dominio suficiente para algoritmizar problemas computacionales de la vida real” en concordancia con la teoría de el libro Fundamentos de Algoritmia [G. Brassad y P.Bratley] Ed. Pearson Prentice Hall.
En concreto el examen consistía en resolver, en menos de 120 mínutos, un problema de programación algorítmica por la rama Algoritmos “Voraces”, “Divide y vencerás” o “Exploración de grafos” – que mejor se adecuase – con justificación y análisis de costes computacionales – .

La práctica obligatoria aprobada es requisito previo para examinarse.



Hay un problema añadido y no es, en absoluto, baladí.
Para realizar dicho examen en la asignatura, previamente, tienes que tener aprobada una práctica – supuestamente de similares características al examen pero, además, te piden implementar la solución en Java –.
Práctica cuyo enunciado – varía de año en año – , los profesores títulares de la asignatura dan al alumnado a finales de Noviembre.

¿Cuándo dices Java dices un lenguaje de programación que permita seguir un filosofía de POO (Programación orientada a objetos) como C++ o cualquier otro?
No. Cuando digo Java, digo Java.

Por fortuna, en el enunciado de la práctica, el IDE a utilizar para construir el ejecutable es una recomendación pero, el lenguaje en el que ha de materializarse la implementación, es una Conditio sine qua non

Si no sabes Java, ¿Estás vendido?
Lamentablemente, así es.


¿Y el profesor no te enseña eso?



Normalmente, en los centros asociados, se contrata – a partir de Noviembre – a un profesor para impartir un día a la semana 2 horas de los contenidos del libro referencial de dicha asignatura.
El profesor te dice que, enseñarte Java es imposible. No hay tiempo material.
Teacher
O una cosa o la otra. No hay tiempo para las dos. Me han contratado para los contenidos. Lamentablemente “os tenéis que buscar la vida
Vamos que, a no ser que hayas hecho una FPIII por ejemplo A.S.I. –donde el 2º año y durante 5 meses a hora diaria te formaban en Java – , estás vendido.
No te están pidiendo, en el problema práctico, un pseudocódigo. Lo que te piden entre otras cosas es el jar y probablemente con parámetros de entrada que solucione el problema.


¿Entonces?




Luego, en el caso de una persona sin malicia que, ese cuatimestre curse al menos dos asignaturas de las 12 que consta dicho año, tirará, éste , el dinero de la matrícula y el libro (ninguno de los dos son baratos); habrá jodido su expediente y, probablemente, se habrá dejado algo más de dinero apuntándose a un curso de iniciación de Java de un mes... Eso “a lo legal way”.
Lo sufrí.

¿Y la opción Septiembre?



La opción "Septiembre" pasa porque, en el verano, el tutor del centro asociado al que te matriculaste – Ese que fue contratado hasta la última semana de Enero para impartirte en unas 20 horas el contenido de 320 páginas de teoría pura y dura y además dar el visto bueno inicial a tu práctica –, trabaje sin ser remunerado.
Quiero decir que, en vez de piscinear sus chancletas, se dedique a pasar calor en su cuarto de casa para dar el visto bueno inicial a tus códigos fuentes y contacte con Madrid a decirselo -- Suponiendo que en Madrid también les guste trabajar en veranito -- .
Todos --y todo-- de forma altruista, atendiendo tu “no-capacidad para hacerlo en el plazo en que su trabajo es remunerado”...
Así que, la “opción de Septiembre” la reescribo como “la casualidad de que des con un mercenario altruista de la enseñanaza”.
Recuerdo que en la cultura Española a Quijote lo querían recluir por loco y a Jesucristo nos lo cargamos.
Además, esta – !Y remuneradamente! – , es la España del: “Mariquita el último”, el “A ver si voy a ser yo el único tonto de trabajar, cuando los demás están de cervecitas” o el “primero, hazlo tú; luego ya, si eso, yo”.
Así que de forma gratis no es que sea graciable. Es un milagro.

¿Entonces?



Todo queda reducido pués, para alguien que nunca ha programado en un lenguaje POO como Java y que se presupone sabe lo que es un TDA (Tipo de Dato Abstracto) -- e implementarlo en Modula-2-- y también se le presuponen nociones de formulación matemática de recursividades, a opciones no tan legales.
Éstas pasan por: desde tener un "amigo" que te “ayude” con alguna "indicación" y "corrección", hasta contratar un tutor particular que te haga la práctica -- "OR/AND" explique --.
Estando la opción tabién de buscarla por internet y copiarla – Si no te pillan, te la juegas al examen (que es por lo que en teoría has pagado) –.
Evidentemente, el tutor da el visto bueno inicial a la solución. Por tanto, "copy&paste" -- sin leer detenidamente ,entender y corroborar -- , a la hora de defender el trabajo, revelará la ausencia de esté.
Cualquier opción es práctica cuando el tutor de apoyo contratado por el centro te dice que es your business y que él aún no sabe como componerselas para explicar en 20 horas --o menos--, 320 páginas de chicha tan apretada.
Gracias a ello, me ví requerido a este apañillo -- a cambio de unas t-shirts para correr por las mañanas-- que en esta entrada os relataré.



La práctica 2012/2013:

          .jar para KNIGHT's TOUR o el problema del caballo, básicamente.


  Aquí está la práctica a realizar:

   Como se ve en el pdf , de forma resumida, piden un jar (Archivo java ejecutable) que se pueda invocar basándose en 4 propiedades distintas:
  •  Lado del tablero
  •  Posición inicial de salida del caballo
  •  El programa se ejecuta hasta alcanzar una solución o hasta hallar todas las existentes para la posición de partida 
  •  Dame la traza de cada movimiento



     Queremos pués que, un caballo de ajedrez haga caminos hamiltonianos (pase una y sólo una vez por cada casilla) en un tablero cuadrado y siempre que, su lado sea mayor o igual que 5.

A trotar por el tablero
Noria, carrusel y ahora tablero. No podían elegir al cocodrilo, no.
  El programa admitirá que demos longitud al lado del tablero.
  También permitirá que establezcamos una posicion incial (x,y) para el caballo.    Obligada la casilla inferior izquierda como 0,0.
   Permitirá la opción de detenerse cuando encuentre un camino o de mostrar todos los posibles.
 Permitirá la opción de mostrar la traza a cada  “intento de moviento“ o no.

Por defecto, si no añadimos ningún parámetro el programa entiende que:
-El tablero es 8*8
- La posición inicial de caballo es la casilla situada en el vertice inferior izquierdo (en un tablero visual). La llameremos casilla 1 y la podríamos etiquetar como a un par ordenado (x,y) correspondiente (0,0).
- El programa se detendrá al encontrar un camino y lo mostrará.
- No hay traza.


Observaciones al enunciado de la práctica



Precisemos para evitar disgustos
Google: Odiseo Troya

Efectivamente, observaciones y objeciones.
 Quien haya leído el enunciado y guía exigida del pdf , teniendo algo de sentido común, habrá observado dos condiciónes que, por absurdas, dañan la vista.
Quien sepa construir programas en Java, quizás piense como yo, 3. 
Digo 3 por cómo exigen invocar el jar. "A gusto se quedo, la madre que los parió". (En los comentarios podemos discutir esto).

Así que, antes de que se nos desboque nuestro Rocinante o nos amargue la fiesta Odiseo, con el fin de no extenderme demasiado, voy aprecisar:



Por un lado, no voy a hacer ni puñetero caso a la exigencia "fichero jar que muestre en consola traza", cuando están pidiendo , también y previamente, ficheros de salida.


¿El motivo? En mi opinión, ya han emperifollado demasiado el programa con la forma de invocación de parámetros.
 Crear otro parámetro, más, para decir si se quiere la salida por consola o por fichero – Recuerdo: no te han dado ni una sola hora de implementación en Java – me parece que es tocar mucho los cojones al personal.
 Esa la opción del parámetro.
La otra solución sería, hacer un programa y luego borrar partes...
Para quien no sepa programar, es como si alguien te dice "Anda, cávate una piscina. Al lado, cávate otra igual. Una vez cavada la segunda , la llenas de agua y le sacas un par de fotos; tras ello, la vacías y cubres de nuevo el agujero;  por último,  me enseñas las fotos y me llenas la primera de agua que, me bañaré". (Mola esta españa tan cañí, ¿Qué no?)

El día que, en el Senado, les de por preguntar a la UNED sobre esto, a más de un "teacher" de Madrid me gustaría verlo responder jugándose el sueldo la carrera y el prestigio. Pero vamos, esto es "Es-paña" y tengo mis dudas de si, en algún siglo, ocurrirá.
Así que, el programa que os colgaré --con su código fuente-- procedera, en su invocación, a dar salida por ficheros.



Leevas trazas de peirme traza... Por otro lado, a mi entender y dado que piden: análisis, diseño, fuentes y ejecutable,es absurdo en ejecución dibujar cada ensayo --e incluso es absurdo dibujar el tablero ensayo si este es factible, puesto que cada tablero solución final muestra una colección de pasos válidos--.
Esto de la traza, para cualquier intento –resulte conduzca a solución o no -- , es lo que durante las dos asignaturas anteriores de programación se ha vilipendiado. Insistiendo en que, una programación diseñada formalmente tiene completamente controlado lo que ocurre en cada iteración de los bucles programados y el uso de trazas desprestigia al programador.
Así que, a mi modo de ver, la petición de la traza es una tonteria , máxime cuando , repito , cada tablero solución debe que contener el acceso a sus casillas secuenciado.
No veo justificada la petición. Dibujar, a cada intento de salto, un tablero sí que ralentiza algo el programa.
Un caballo siempre tiene 8 movimiento posibles pero, imaginaros en tablero de 100 casillas de lado (10000 casillas en total), andar dibujando a cada salto que se computa 10000 casillas......
Es mi objeción. En este caso, quien aportó las camisetas le pareció que era contravenir demasiado el enuncaido. No me dejó. Por tanto, el programa, sí que dibujará --en modo traza-- un tablero en el archivo por cada movimiento que compute. Amén que, cada tablero, siempre portará la secuencia de sus pasos en las casillas.



Aprovechando la segunda objeción, quiero hacer una observación: el programa lo empecé a implentar con mi Ubuntu. Algunos días de implementación – coincidiendo con festividades Navideñas – lo continué implementando en Windows, concluí la implementación de nuevo en mi casa con mi Ubuntu.
Todos pinzas de madera pero, cada uno las suyas El par de días que lo fuí probando en Windows observé que los ficheros .txt solución generados en mi Ubuntu no se visualizaban correctamente con el Notepad de windows. La visualización era perfecta usando Wordpad.
Quizás este problema se deba a algo que no sabía: cuando se genera un fichero de texto en Ubuntu existen 3 formas de guardarlo y por defecto emplea una tal que los saltos de linea no son interpetables en Windows.
Así que, si usáis Windows para ver los ficheros solución, recordad: Notepad no, Worpad sí.




La última observación antes de empezar:
No confundir con Crepúsculo.... Joer con la LOGSE    Indican en la guía que, el equipo docente recomienda BlueJ como entorno de desarrollo. 
  Yo no he seguido esta recomendación.
 He utilizado el IDE Eclipse en las versiones Indigo para Ubuntu y Juno  para Windows.
  En comentarios, si hay dudas, aclararé como ejecutar con parámetros. Así como problemas  y soluciones al migrar proyectos entre estas versiones desde “pepinos Quores” hasta equipos más humildes como el mío.





Se acabó tanta chachara. Empezamos la chicha.


 ANÁLISIS: elección de algoritmo y costes.



No se ajusta , no se ajustaNo hay criterio de selección de candidatos dentro de las n2 casillas y una ruta sin solución hará que "algoritmo vóraz" finalice. Ergo, planteamiento bajo la directriz de algoritmos voraces descartado.

no hay tiempo 
En esta primera versión , debido a premuras de tiempo, no tomaremos los estudios matemáticos formales ya realizados sobre este problema desde hace unos siglos. Luego, no iremos por la linea de algoritmos "divide y vencerás". Línea que sí podríamos seguir en otras versiones posteriores.


Hablamos de un caballo que parte de una posicion en el tablero (“estado”) y puede
quien mejor
--en caso mejor – saltar a 8 casillas (“nuevos estados”). Parece pues que se ajusta bastante bien a la idea de grafo y árbol. El grado de ramificación en hijos es de 8.
Hablamos, pues, de un algoritmo de exploración de grafos que vaya generando tableros y que nos permita la vuelta atrás si no agotamos los n2 nodos pero si las casillas posibles para un nuevo tablero desde una posición.


   Estudio de costes:

 

Supongamos que, queremos rellenar las n2 casillas del tablero con números entre 1 y n2 (sin repetir) con independencia de las reglas del movimiento de caballo. Las maneras posibles serían (n2)! . Sí , el factorial del cuadrado de n.


Al saber el número de ramificaciones podemos acotar el tamaño del arbol a una mantisa de 8 y un exponente de n2 . Es más, podemos incluso precisar que, no siempre son 8 las ramificaciones posibles pues en ciertas casillas este número merma -- por su ubicación -- y conforme vamos llenando el tablero disminuyen las alternativas.


Tirando de los conocimientos de fundamentos de Inteligencia Artificial en búsqueda y exploración de grafos usaré un algoritmo de busqueda en profundidad con retroceso cronológico.
Por supuesto que, se podría emplear heurística. Reduciendo todavía más las cotas pero como he dicho para desechar divide y vencerás vamos a “no – documentarnos “ y dejarlo para sucesivas versiones.
Concluyo pues que, con este algoritmo y sin heurística alguna, podemos hablar de una cota superior en complejidad temporal de θ (8 n*n )   y de una cota espacial de     θ (n2).





DISEÑO



              
He diseñado el módulo en 4 clases: 'saltocaballo', 'Tablero', 'Secretario' y 'Exploradora'.
 No sé hasta que punto es conveniente mostrar el esquema de cada clase, puesto que aquí ya hay detalles que pertencen al campo de la implementación. Pero, por si a alguien le sirve para tomar confianza, aquí van.


La clase 'Secretario' se encarga de pasar los tableros a ficheros. Podría, inicialmente, considerarse innecesaria como clase y suplirla por un método dentro de la clase Exploradora. Podría. Sin embargo, me ha parecido más claro establecerla como clase e instanciarla en una 'topisto' (elegante telefonista) por si, para futuras versiones, se le requirieran más cosas.

La clase 'saltocaballo' es la clase que lleva el main y gestiona la parametrización de la invocación y computa el problema pidendo, se guarden los resultados de la prueba en un fichero indentificable de acceso secuencial. 






  La clase 'Tablero' intancia tableros. Cada tablero instanciado contiene una secuencia de pasos por sus casillas siendo estas ordenadas. También, entre sus atributos, tiene el de “en que jugada me hallo” y otro atributo que nos permita la vuelta atrás cronológica. La he dotado de un método que nos devuelve un boleano si una posición (x,y) está o no dentro del tablero y adremás es usable. Tiene un contructor para el tablero inicial.


 

La clase 'Exploradora' es la más compleja.
 Hace instancias de 'Tablero' y genera saltos de caballo.
 A la hora de explorar el método trabajará con tipo de datos dinámico, 3.
 Uno lo uso para almacenar las soluciones que vaya encontrando en la invocación. Otro me sirve de rastro o huella y el tercero lo uso para comprobar si he llegado a la solución y si no generar hijo factible. Al generar hijo factible el padre pasa a la “pila” de rastro de mi exploración. Si no llego a solución cada vez que no hay paso factible el método toma la cima de rastro y busca el siguiente salto en la cronología.




Una clase de exploradora
Tablero por defecto
Si las imagines anteriores han servido para perderos, no preocuparse.
 Pongo un par, por ejemplo, de la clase exploradora y otra de la clase tablero y nos vamos a la implementación que es donde de verdad se destapa toda la chicha  y hay que leer y comentar detenidamente. ;-)











IMPLEMENTACIÓN

Voy con los fuentes de menor a mayor complejidad:


Source secretario class





Source Tablero class




Sí, implemento la clase tablero como "serializable". El motivo es que la hora de "explorar" un tablero dado en busca de la solución  voy creando  clones y modificándolos respecto al tablero que examino.


La clase 'saltocaballo'  la paso a odt y os la pego en dos fotos :



Foto 1 de 2


Foto 2 de 2












El último fuente es la clase "Exploradora" que instancio en salto caballo como 'dora'.
Expongo el archivo .java en él, como veis, bastantes métodos son auxiliares:










Foto Exploradora.java 1 de 7


Foto Exploradora.java 2 de 7


Foto de Exploradora.java 3 de 7


Foto de Exploradora.java 4 de 7


Foto de Exploradora.java 5 de 7


Foto de Exploradora.java 6 de 7

Foto Exploradora.java 7 de 7







PROBAR EN ECLIPSE Y HACER EL .JAR




   Con estos 4 fuentes ya todo se reduce a probarlo una vez en el entorno eclipse y construir el programa ejecutable saltocaballo.jar

Ese que, creo yo y no como dice la guía,  debería de invocarse como:
             $> java jar saltocaballo.jar
Y, si se quiere, darle parámetros de entrada.





Entregar el programa y ...
 !A probar las camisetas! ;-)





 No quiero alagar a entrada mucho más. De por sí es técnica y larga.
 Os subiré un enlace para que os descarguéis el .jar y hagáis vuestras probatinas.

 Recordad el coste temporal. Da igual que tengáis un "pepino" de equipo  con tropecientos "quad cores". Como le pongáis lados de tablero por encima de 20,  lo mismo disminuye el paro en España del 25 %  y aún no tenéis solución... !Nah!
    Sí que os agradecería si me haceis llegar los costes de los ficheros con busqueda exhaustiva que por probatinas genereís. Así me daré cuenta de cuanto de desfasado tengo el hardware de mi equipo. (lo ideal sería me mandeis el nombre del fichero generado , procesador de vuestro equipo , memoria ram, sistema operativo y tiempo que ha tardado en generarse el fichero una vez invocado el .jar ;-)


    Respecto a algunas dudas que ya me han ido llegado por correo,  daré mi opinión o cómo lo hice en comentarios.
 !En cuánto tenga algo de tiempo!
Mientras ya sabéis, salida 3,2,1...


SED BUENOS!

No hay comentarios: