Desafio : Laberinto

[IngProd]

Iniciado por nicolaspar

Claro, visualmente está mucho mejor, pero el proceso es mayor, ya que estas haciendo varios caminos. De todas maneras me gusta :)

Gracias. Todo es cuestión de qué queramos conseguir... el enlace que puse al principio busca un camino, el de ahora busca el más corto, en realidad son dos cosas distintas. De todas formas, podemos tener dos caso:

1) El primer camino que encuentra es corto -> Entonces, tal como yo tengo el algoritmo el resto de los caminos los cortará rápido, ya que no recorre un camino que supere al mejor encontrado

2) El primer camino que encuentra es el más largo -> Buscar otros será despreciable en tiempo

Por proponer, se me ocurre que midamos el tiempo de ejecución de nuestros algoritmos (sin contar el tiempo necesario para mostrar, ya que depende de lo bonito que cada uno lo quiera dejar) y al final colocarlos todos en un mismo servidor (ofrezco el mio) y así poder hacer comparaciones... Si al final todos o casi todos permitimos situar en un determinado lugar el queso y el ratón, se podrán comparar bien los algoritmos. ¿Qué les parece?

[DeeR]

Iniciado por IngProd

Gracias. Todo es cuestión de qué queramos conseguir... el enlace que puse al principio busca un camino, el de ahora busca el más corto, en realidad son dos cosas distintas. De todas formas, podemos tener dos caso:

1) El primer camino que encuentra es corto -> Entonces, tal como yo tengo el algoritmo el resto de los caminos los cortará rápido, ya que no recorre un camino que supere al mejor encontrado

2) El primer camino que encuentra es el más largo -> Buscar otros será despreciable en tiempo

Por proponer, se me ocurre que midamos el tiempo de ejecución de nuestros algoritmos (sin contar el tiempo necesario para mostrar, ya que depende de lo bonito que cada uno lo quiera dejar) y al final colocarlos todos en un mismo servidor (ofrezco el mio) y así poder hacer comparaciones... Si al final todos o casi todos permitimos situar en un determinado lugar el queso y el ratón, se podrán comparar bien los algoritmos. ¿Qué les parece?

Dips es lo mejor para comparar el rendimiento de los Algoritmos. Lo otro, seria bueno que los usuarios del foro tambien pusieran nota a los algoritmos, esto lo podriamos hacer en una encuesta, en un post con la recopilacion de todos las soluciones.

Saludos

[IngProd]

Iniciado por DeeR

Dips es lo mejor para comparar el rendimiento de los Algoritmos.

Hola,

A qué te refieres con Dips ¿?, la verdad es que no lo había visto antes... creo.

[DeeR]

Iniciado por IngProd

Hola,

A qué te refieres con Dips ¿?, la verdad es que no lo había visto antes... creo.

Es un modismo cybernetico chileno de la afirmacion SI

XD

[Falhor]

Ah xD Yo busqué en Google y apareció una comida o algo asi, jeje.

Yo ofrezco mi servidor si quieren también, igual ahora no creo hacer algo en el script hasta el fin de semana...

Saludos.

[oso96_2000]

Vi el tema en la mañana y me estoy animando a hacer algo xD
Ahorita lo unico que me falta es lo que me parece mas complicado: indicar el camino del raton hacia el queso, pero por lo demas de momento mi clase permite especificar la posicion tanto del raton como el queso, asi como crear el laberinto, ya sea de un arreglo (como el de DeeR) o un archivo con la estructura que el propuso:
http://stuff.otaku-anime.com/maze.txt

Me parecio buena idea para darle mas variedad a los laberintos xD.. en cuanto complete el reto, posteare la url del ejemplo o.o

Edito unas horas despues: No se si sea la hora y el sueño, pero no consigo recorrer el laberinto hasta encontrar el queso, tengo la idea pero no consigo plasmarla, espero al despertar y estar descansado algo salga =_=

[caricatos]

Hola:

Fuera de concurso (es que está en javascript) : Laberinto

Tal vez pueda servir la idea... y la forma de mostrar el desarrollo.

Si me da tiempo paso el código a php.

Saludos

[fatherjuan]

Lo que estaría realmente retador sería que el laberinto se construyera tambien aleatoriamente.

Saludos

[sergiold]

Caricatos, muy buena la forma de mostrar el procedimiento para llegar a la solución. Así da gusto!

Saludos,

[oso96_2000]

x_x.. el raton ya encuentra el queso, pero el algoritmo es muy ineficiente y colorea muchas casillas de mas.. pero bueno, al menos por mientras q se vea un pequeño resultado xD

Posicion del raton y queso aleatoria.
Indicando la posicion del raton.
Indicando la posicion del queso.
Indicando ambas posiciones.

Las coordenadas para posicionar son coordenadas reales en el laberinto, no las posiciones del arreglo.

A veces la pagina no muestra nada, y no se porque sea.. me refiero visualmente, porque viendo el codigo html ahi esta todo.. no se si sea cosa del servidor o algo asi (pq ni en el log de errores aparece alguno).. pero con actualizar se genera de nuevo xD

Tendre que trabajarle mas en la busqueda que visite las menos casillas posibles x_x

Edito: Se queda asi, es la conducta mas apegada a lo que haria un raton: andar por el laberinto hasta encontrar el queso, sin saber donde esta este.

[rickgonza]

hola yo soy novato en esto del php y me realmente no se como realizar el desafio me gustaria si se pudiese que alguien amable explicara como lo hizo o por ultimo solo comentando su codigo
desde ya gracias

saludos de rickgonza

[jam1138]

Iniciado por rickgonza

hola yo soy novato en esto del php y me realmente no se como realizar el desafio me gustaria si se pudiese que alguien amable explicara como lo hizo o por ultimo solo comentando su codigo
desde ya gracias

Inténtalo, es la mejor manera de aprender. Aún tienes tiempo.

Hasta ahora solo se han mostrado scripts trabajando sin código (PHP), obviamente para no interferir con los demás participantes. Los códigos se mostrarán, comentarán y discutirán después. Está en la convocatoria.

Iniciado por DeeR

Las soluciones la pueden postear apartir del dia Domingo 25 Marzo 2007 (Para que todos tengan la Oportunidad de Participar)

[caricatos]

Hola:

Bueno, ya tengo la versión php: Laberinto

Quería mejorar la presentación, pero me lié con un errorcillo que me hizo perder más tiempo del que quería.

Saludos

[AlvaroG]

Pues este problema parece demasiado interesante como para no participar
Mi 'algoritmo de media hora' (porque en ese tiempo lo hice ) es bastante pobre, simplemente recorre el laberinto intentando no pasar más de una vez por la misma casilla (aunque no lo logro, ya que no supe cómo equilibrar el "no pases más de 1 vez" con el "si me estanco tengo que volver").

En definitiva, el ratón siempre encuentra el queso. Y al contrario del ratón de Caricatos, el mío no tiene visión de rayos X para ver todo el laberinto hasta encontrar el queso...

Estuve viendo problemas similares, un amigo me sugirió buscar Backtracking... aún no sé si fue un algoritmo así el que usó caricatos, pero lo que sí se es que voy a leer esa página hasta entenderlo

http://www.tallerwebmaster.com/alvli.../laberinto.php

Saludos.

[caricatos]

Hola:

alvlin : Supongo que cuando termine el plazo (me parece que mañana), soltaremos el código y creo que será el tema más interesante, comentando y debatiendo sobre nuestros códigos.
El backtracking creo que es la forma de resolver laberintos más conocida y usada, pero en teoría no busca el camino más corto.
Cuando estudié en las aulas estas técnicas recursivas, se me ocurrió el algoritmo que he usado, y ver este mensaje me animó a desarrollarlo (seguro que ya estaba hecho antes y mucho más mejorado)... también lo hice en relativamente poco tiempo (cuando ya se tiene la idea ), aunque más tiempo tardé en pasarlo a php (no sabía pasar variables por referencia, entre otras cosas)

Por cierto, la evolución solo la ví con opera, y al terminar me saltó la consola de errores... tanto en firefox como en explorer no se ven los pasos (la verdad es que ya no es cosa php, pero tal vez sea mejor que revises el código)...

Esta línea:
celda.style = "background-color : blue";
debería ser:
celda.style.backgroundColor = "blue";

Y el bucle creo que la condición de recursividad hace que se pase de rango la variable i... prueba así:

Código:

	if (++i < pasoX.length)
	{
		//i++;
		setTimeout("mostrarPaso("+i+")", 100);
	}

Lo demás creo que está bien
Mis disculpas por poner código javascript en este foro.

Saludos

[AlvaroG]

Tenés toda la razón jejejee detalles que se me pasan
Lo de css en javascript lo sabía, lo que no sé es lo que estaba pensando al ponerlo así
Ahora, lo de la función sí no me había dado cuenta... ¡gracias!

[okram]

Bien, ya vamos llegando al final de este concurso y las soluciones posteadas son todas muy interesantes. No pude entrar mucho durante la semana, y recien acabo de ver las soluciones posteadas por caricatos y alvlin y son bastante buenas .

Yo no pude hacer mayores arreglos a mi script, pero aquí está en su versión final:

Función QueSo

No puedo esperar hasta mañana para ver las soluciones. En mi caso, no sé cual metodo apliqué, pero mi ratón llega al queso usando el camino más corto. Intenté pasarlo a una clase, pero no me resultó, así que el script está hecho en base a varias funciones.

Un saludo, y nos vemos mañana

PD: ¿Los códigos serán publicados en este mismo mensaje, o se abrirá un nuevo tema, o cada usuario publicará su código en sus sitios web?. Propongo que los usuarios que enviamos soluciones publiquemos en nuestros sitios web los códigos, tal vez usando la función PHP highlight_file(), y que en el foro se abra un nuevo tema para discutir las soluciones y comentar los códigos

[Panino5001]

Bueno, aquí dejo mis soluciones, lamentablemente no me da el tiempo para agregarle más detalles:
http://www.disegnocentell.com.ar/ali...into_class.php

[AlvaroG]

Pues yo agregué un par de detalles al mío, además hay algo que noté:
En $array, la primera coordenada es la fila y la segunda es la celda, no? es la forma más sencilla de dibujar la tabla.

Pero en la matriz del laberinto, la fila es Y y la celda es X.
Por lo tanto, la forma genérica de un punto sería $array[COORDENADA_Y][COORDENADA_X]

Al menos caricatos, Panino5001 y yo tenemos, por lo tanto, las coordenadas inversas. okram parece haberse dado cuenta del problema, y tiene las coordenadas correctamente.

Habrá que interpretar la tabla de costado

Si no se entiende lo que quiero decir, miren bien las coordenadas que obtienen, y la forma en que dibujan el laberinto.

Saludos.

[oso96_2000]

Asi es, para colocar el raton/queso, el punto en el arreglo debe tomarse como $array[$y][$x]

Yo me di cuenta mientras hacia la funcion para posicionar el raton xD.. no quedaba donde queria, y me fije que debia ponerlo en ese orden.

Ahorita casi no tengo inet, mi conexion esta fallando mucho, pero aun asi en mi solucion aparecerá el enlace a el codigo fuente.

[caricatos]

Hola:

Posiblemente no me conecte en un par de días, así que muestro Aquí el código fuente... el primer include es un "copy & paste" del laberinto original y el segundo es un fichero txt normal (pensaba enviar directamente el enlace al txt porque no conocía el método highlight_file)

Me ha gustado participar y ver los resultados de otros, y en principio me parece muy buena la forma de resolver el desafío por parte de Andrés (Panino5001)... en proyectos míos me gusta manejar objetos y veo que los ha usado con buen tino.

Esperemos que alvlin con los comentarios y códigos que mostremos, pueda mejorar su laberinto para encontrar mejores soluciones (en ocasiones se resuelve en más de 300 pasos )

Sobre el orden de las coordenadas, me dí cuenta con bastante código escrito, y me dió un poco de pereza volverlo a escribir/modificar, pero también he pensado en proponerlo en esta fase de debate, así que ahora trataré de verlo...

Saludos

[okram]

Hoy es el día amigos foreros.

Arme un tema nuevo para discutir las soluciones. Sugiero ir a:

http://www.forosdelweb.com/showthread.php?p=1943134

Para enviar nuestras soluciones y comentarlas.

Un saludo,

[AlvaroG]

Pues mostraré mis vergüenzas
No creo que lo pueda modificar para hacerlo más eficiente (falta de tiempo, como siempre ), pero me comprometo a estudiar el tema del backtracking y la solución al problema del laberinto

Ya arreglo un poco para dejarlo más prolijo, y subo.


Saludos.