Como los bebés y los ancianos, se apoyan en taca-tacas para reafirmar sus pasos, construyo éste, a modo de diario, para ir dejando, básicamente, temas informáticos.
Por supuesto que, cualquier comentario, duda o crítica que pretenda hacerlo crecer será bienvenida.
viernes, 26 de abril de 2013
La tournée de un caballo por esos tableros de Dios -- en Java -- . (Tour Knight in Java language)
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.
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 ysiempre que, su lado sea mayor o igual que 5.
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
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.
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.
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:
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
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.
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
--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 grafosque vaya
generandotableros 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...
No hay comentarios:
Publicar un comentario