Problemilla interesante

[SplinterGU]

bien, empezamos a aclarar la cuestion...

los papers aclaran un poco mas el problema y dan los datos que faltaban... paso a comentar:

1) no es una fila, es un anillo... esto quiere decir, que el primero se enlaza con el ultimo y a la inversa

No, ese es otro tercer problema distinto. En ese, mi algoritmo funciona y además es de orden 2n-2, y se puede iniciar sobre cualquier soldado. Con una fila también se puede solucionar, y de hecho el mio lo soluciona. Es básicamente lo mismo pero más fácil :P

por otro lado, hay otro metodo que no es nada optimo que trabaja sobre el peloton en forma de array, y va dividiendo al mismo de 2 en 2, de forma recursiva... en este caso se arranca con un solo iniciador que debe ser ubicado al final del array (para saber la cantidad de automatas o soldados)... por ende, se cuentan...

Creo que esa es la solución mia, pero o bien no lo es o la has entendido mal como la mía :P porque en la mía no se cuenta. Pero la mía se basa en ir dividiendo la fila por la mitad sucesivas veces.

Por favor, me encantaría que entendierais mi solución a parte de las "oficiales". Además estoy seguro de que la mía es una de las oficiales, aunque no la mejor.

nop, no es lo mismo de tu solucion, son cosas totalmente diferentes... la solucion mas optima es la de ir creando iniciadores (quienes envian señales) y se hace en N... estas son simetricas, lo que indique no se envian 2 señales hacia el mismo sentido, se envian 2 señales en sentidos opuestos, cuando estas señales chocan (por coincidir celdas o por estar a distancia 1, una de otra) entonces ahi se crean 2 iniciadores, con limites posicion inicial del iniciador padre y punto de colision, y asi sucesivamente, como se ve en esta explicacion se cuentan posiciones, es necesario saber las posicion inicial, para ubicar los limites de los iniciadores hijos creados. El sistema se resuelve cuando todos los automatas son iniciadores.

Tanto la solucion de mitades, como la de señales multiples difiere mucho de tu solucion que sigo sin entender... ya partamos con que la 3) no fue lo que pregunte... no pregunte que, sino "como" y de forma simple, no mas de 1 parrafo. Disculpa, en serio, pero sigo sin entenderte.

Ostras tu, que revelador el ejemplo extraido de su autor y es exactamente este,

http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem

Pues sí, he leído varias veces tu solución y creo que es una implementación de la solución que llaman General  (de orden 3n). En la wiki se entiende muy bien es cuestion de mandar dos señales una la mitad mas lenta que la otra (asi que algo de temporización hace, aqui está el truco :D ) por lo que vas encontrando la mitad y volviendo a plantear el problema para las dos mitades creadas, aunque dice que se resuelve con 15 estados, (cosa que en tu ejemplo no veo).
Esta creo que se podría programar facilmente y verla visualmente :D.

En cuanto a la solución óptima en tiempo (orden 2n-2), no pillo ni papa, aparecen "i" señales y pone que van distintas velocidades a cada una, es como la general pero intentando encontrar en vez de mitades , i particiones, por lo que llegas a acotar antes y portanto disparar antes. Por cierto, No se lo que vale i ni de qué depende :D.

He leido que también hay optimizaciones de este código propuestas por estudiantes pero todas consisten en cambiar el enunciado :D, haciendo el anillo del que habla splinter, o haciendo conexiones en cubo o noseque historias :), vamos ahí guarreando un poco las reglas.

No, no es lo mismo que dice Hackzjuann, hackzjuan envia varias señales a la vez con sobre el mismo sentido y a misma velocidad... no es el ejemplo, y necesita de 4 ciclos para que matchee... no es para nada lo mismo... por eso es que no entiendo como dice que enviando 3 señales en 1 todos lo pueden decodificar...

imaginemos el problema como lo siguiente... soldados en fila, pasando uno a otro el mensaje de fuego, como si tuvieran 2 vasos conectados con un cable... tienen 2, 1 para el oido izq y otro para el derecho... solo se puede escuchar 1 mensaje por cada oido, no 10, el mensaje a escuchar es "fuego"... no es "preparate para disparar que vamos a atacar"... solo 1 palabra, "fuego"...

en el caso es simple, supongamos que todos estan conectados de izq a derecha y el ultimo con el primero... uno cualquiera dice a la izq y a la derecha "fuego"... cuando uno escucha fuego lo repite al "telefono" del costado opuesto... cuando un soldado escucha que le entran 2 "fuego" por ambos oidos o cuando 2 soldados se avisan al mismo tiempo "fuego", dichos soldados se transforman en iniciadores, y empiezan a gritar fuego en el sentido inverso (aca hay algo que dejaria de transformarse en algo practico a nivel humano, ya que el iniador necesita enviar 2 señales, en los limites del subanillo, o sea, dar la vuelta en su rango de accion)... y esto se repite hasta cuando tanto nosotros como nuestros vecinos son iniciadores... momento en que todo esta sincronizado...

esa es la mejor solucion, pero cualquier solucion propuesta en los papers difiere mucho de lo que plantea Hackzjuann que me encantaria entender... no entiendo porque el quiere meter 4 canales de entrada/salida, cuando solo hay 2 (uno izq y otro der)

Saludos.

[HaCkZJuaNN]

bien, empezamos a aclarar la cuestion...

los papers aclaran un poco mas el problema y dan los datos que faltaban... paso a comentar:

1) no es una fila, es un anillo... esto quiere decir, que el primero se enlaza con el ultimo y a la inversa

No, ese es otro tercer problema distinto. En ese, mi algoritmo funciona y además es de orden 2n-2, y se puede iniciar sobre cualquier soldado. Con una fila también se puede solucionar, y de hecho el mio lo soluciona. Es básicamente lo mismo pero más fácil :P

por otro lado, hay otro metodo que no es nada optimo que trabaja sobre el peloton en forma de array, y va dividiendo al mismo de 2 en 2, de forma recursiva... en este caso se arranca con un solo iniciador que debe ser ubicado al final del array (para saber la cantidad de automatas o soldados)... por ende, se cuentan...

Creo que esa es la solución mia, pero o bien no lo es o la has entendido mal como la mía :P porque en la mía no se cuenta. Pero la mía se basa en ir dividiendo la fila por la mitad sucesivas veces.

Por favor, me encantaría que entendierais mi solución a parte de las "oficiales". Además estoy seguro de que la mía es una de las oficiales, aunque no la mejor.

nop, no es lo mismo de tu solucion, son cosas totalmente diferentes... la solucion mas optima es la de ir creando iniciadores (quienes envian señales) y se hace en N... estas son simetricas, lo que indique no se envian 2 señales hacia el mismo sentido, se envian 2 señales en sentidos opuestos, cuando estas señales chocan (por coincidir celdas o por estar a distancia 1, una de otra) entonces ahi se crean 2 iniciadores, con limites posicion inicial del iniciador padre y punto de colision, y asi sucesivamente, como se ve en esta explicacion se cuentan posiciones, es necesario saber las posicion inicial, para ubicar los limites de los iniciadores hijos creados. El sistema se resuelve cuando todos los automatas son iniciadores.

Tanto la solucion de mitades, como la de señales multiples difiere mucho de tu solucion que sigo sin entender... ya partamos con que la 3) no fue lo que pregunte... no pregunte que, sino "como" y de forma simple, no mas de 1 parrafo. Disculpa, en serio, pero sigo sin entenderte.

Ostras tu, que revelador el ejemplo extraido de su autor y es exactamente este,

http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem

Pues sí, he leído varias veces tu solución y creo que es una implementación de la solución que llaman General  (de orden 3n). En la wiki se entiende muy bien es cuestion de mandar dos señales una la mitad mas lenta que la otra (asi que algo de temporización hace, aqui está el truco :D ) por lo que vas encontrando la mitad y volviendo a plantear el problema para las dos mitades creadas, aunque dice que se resuelve con 15 estados, (cosa que en tu ejemplo no veo).
Esta creo que se podría programar facilmente y verla visualmente :D.

En cuanto a la solución óptima en tiempo (orden 2n-2), no pillo ni papa, aparecen "i" señales y pone que van distintas velocidades a cada una, es como la general pero intentando encontrar en vez de mitades , i particiones, por lo que llegas a acotar antes y portanto disparar antes. Por cierto, No se lo que vale i ni de qué depende :D.

He leido que también hay optimizaciones de este código propuestas por estudiantes pero todas consisten en cambiar el enunciado :D, haciendo el anillo del que habla splinter, o haciendo conexiones en cubo o noseque historias :), vamos ahí guarreando un poco las reglas.

No, no es lo mismo que dice Hackzjuann, hackzjuan envia varias señales a la vez con sobre el mismo sentido y a misma velocidad... no es el ejemplo, y necesita de 4 ciclos para que matchee... no es para nada lo mismo... por eso es que no entiendo como dice que enviando 3 señales en 1 todos lo pueden decodificar...

imaginemos el problema como lo siguiente... soldados en fila, pasando uno a otro el mensaje de fuego, como si tuvieran 2 vasos conectados con un cable... tienen 2, 1 para el oido izq y otro para el derecho... solo se puede escuchar 1 mensaje por cada oido, no 10, el mensaje a escuchar es "fuego"... no es "preparate para disparar que vamos a atacar"... solo 1 palabra, "fuego"...

en el caso es simple, supongamos que todos estan conectados de izq a derecha y el ultimo con el primero... uno cualquiera dice a la izq y a la derecha "fuego"... cuando uno escucha fuego lo repite al "telefono" del costado opuesto... cuando un soldado escucha que le entran 2 "fuego" por ambos oidos o cuando 2 soldados se avisan al mismo tiempo "fuego", dichos soldados se transforman en iniciadores, y empiezan a gritar fuego en el sentido inverso (aca hay algo que dejaria de transformarse en algo practico a nivel humano, ya que el iniador necesita enviar 2 señales, en los limites del subanillo, o sea, dar la vuelta en su rango de accion)... y esto se repite hasta cuando tanto nosotros como nuestros vecinos son iniciadores... momento en que todo esta sincronizado...

esa es la mejor solucion, pero cualquier solucion propuesta en los papers difiere mucho de lo que plantea Hackzjuann que me encantaria entender... no entiendo porque el quiere meter 4 canales de entrada/salida, cuando solo hay 2 (uno izq y otro der)

Saludos.

Mira splinter lo siento pero estoy cansado, y me da toda la impresión de que simplemente no lo quieres entender. No lo puedo explicar rápido y al mismo tiempo convenciéndote de que todo está bien. Si lo explico rápido no te lo explico todo y no te lo crees. Si lo explico todo te parece muy largo y no lo entiendes/no lo intentas entender.

YO MANDO UNA SEÑAL QUE AVANZA DE 1 EN 1 Y OTRA QUE AVANZA DE 3 EN 3. LA ÚNICA DIFERENCIA ES QUE PARA HACER QUE AVANCE DE 3 EN 3 YO HAGO QUE AVANCE 2 Y RETROCEDA 1, PERO ES EXACTAMENTE LO MISMO.

Mi solución es EXACTAMENTE la que aparece en el dibujito de colorines en la página de wikipedia:

http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem

El primer dibujo a la derecha, de colores, ESO EXACTAMENTE SIN NINGUNA DIFERENCIA es mi solución al problema. Lo único que ahora que lo veo y tal me doy cuenta de que la mía era un pelín retorcida en algún aspecto que se podría haber hecho más sencillo, pero al final es lo mismo, una avanza 1, otra avanza 3, una va hasta el final y rebota, donde coinciden es el medio.

Y cuando veo el de abajo, el de la solución 2n-2, me quedo flipado. Creo que lo entiendo, y es genial, es básicamente lo mismo solo que en vez de dividirlo de 2 en 2 lo va dividiendo en grupos distintos, o algo así. Mola :P

Así que sí se conocía la 2n-2, en eso me equivocaba :P

No sé por qué dice lo de los 15 estados exactamente, pero seguramente tenga que ver con las posibles combinaciones de las señales.

[SplinterGU]

YO MANDO UNA SEÑAL QUE AVANZA DE 1 EN 1 Y OTRA QUE AVANZA DE 3 EN 3. LA ÚNICA DIFERENCIA ES QUE PARA HACER QUE AVANCE DE 3 EN 3 YO HAGO QUE AVANCE 2 Y RETROCEDA 1, PERO ES EXACTAMENTE LO MISMO.

eso es una respuesta, corta y clara... tan dificil te era decirlo desde el principio?

ahora, si tu esquema avanza 3 y otra avanza 1, como haces para que cuando avanza 3 no se pase de la cantidad de soldados? ahi estas salteando soldados...

por fin lo reconoces que era un poco retorcido tu esquema...

yo tampoco entiendo lo de los 15 estados, pero como sea, hay varias soluciones al problema, unas mas elegantes que otras...

pero te repito, no me parece correcto eso de 4 entradas y 4 frames para que sincronice... eso sigue sin convencerme... y realmente no veo que tu programita sea lo mismo que el dibujo... pero bueno, ya no importa mucho...

quizas si planteas tu ejemplo, haciendo que las señales sean procesos separados, quizas funciona en 1 frame... y ahi se pueda ver clara tu solucion... si quieres hacerla seria interesante.

Saludos.

[HaCkZJuaNN]

YO MANDO UNA SEÑAL QUE AVANZA DE 1 EN 1 Y OTRA QUE AVANZA DE 3 EN 3. LA ÚNICA DIFERENCIA ES QUE PARA HACER QUE AVANCE DE 3 EN 3 YO HAGO QUE AVANCE 2 Y RETROCEDA 1, PERO ES EXACTAMENTE LO MISMO.

eso es una respuesta, corta y clara... tan dificil te era decirlo desde el principio?

ahora, si tu esquema avanza 3 y otra avanza 1, como haces para que cuando avanza 3 no se pase de la cantidad de soldados? ahi estas salteando soldados...

por fin lo reconoces que era un poco retorcido tu esquema...

yo tampoco entiendo lo de los 15 estados, pero como sea, hay varias soluciones al problema, unas mas elegantes que otras...

pero te repito, no me parece correcto eso de 4 entradas y 4 frames para que sincronice... eso sigue sin convencerme... y realmente no veo que tu programita sea lo mismo que el dibujo... pero bueno, ya no importa mucho...

quizas si planteas tu ejemplo, haciendo que las señales sean procesos separados, quizas funciona en 1 frame... y ahi se pueda ver clara tu solucion... si quieres hacerla seria interesante.

Saludos.

No, en un solo frame con mi sistema es imposible hacerlo, porque haga lo que haga, unos soldados se ejecutan antes que otros. Da igual que guarde los valores al principio, o al final, o lo que sea, siempre se van a sobreponer unos sobre otros.

No es que una avance 3, es que una avanza cada 3 turnos y la otra cada 1 turno.

[SplinterGU]

puedes usar prioridad...

poder hacer con 1 frame se puede...

y no era mas facil explicar esto  que has dicho en los ultimos 2 mensajes en poquitas lineas y claro desde un principio?

saludos.

[HaCkZJuaNN]

puedes usar prioridad...

poder hacer con 1 frame se puede...

y no era mas facil explicar esto  que has dicho en los ultimos 2 mensajes en poquitas lineas y claro desde un principio?

saludos.

Ehm... es que desde mi punto de vista es lo mismo :P

Para hacerlo con un frame, habría que utiilzar variables globales me temo yo. Sino, por mucha prioridad que utilice, entre 2 soldados o bien se ejecuta uno primero o bien se ejecuta el otro primero. En cualquier caso, como ambos tienen que pasarse datos, los datos de uno van a estar desfasados. Si pongo la actualización de datos al final del proceso, entonces el que no estaba desfasado ahora lo estará. No importa como lo ponga, van a estar desfasados por el hecho de que bennu ejecuta primero un proceso y luego otro.

[SplinterGU]

se me ocurre, y si haces procesos señal, y estos son los que van pasando de soldado a soldado los avisos? y los soldados no pasan nada, solo disparan cuando deben o crean señales si hacen falta? o quizas no hacen nada... no se, habria que pensarlo.

[HaCkZJuaNN]

se me ocurre, y si haces procesos señal, y estos son los que van pasando de soldado a soldado los avisos? y los soldados no pasan nada, solo disparan cuando deben o crean señales si hacen falta? o quizas no hacen nada... no se, habria que pensarlo.

Quizás podría funcionar. Pero no me apetece ponerme a programarlo otra vez, y no tengo tiempo :P Sin embargo, si te fijas en como funcionan los 4 frames de mi programa, verás que no alterna para nada el concepto de "turno".

[SplinterGU]

lo revisare ni bien tenga tiempo... gracias... saludos.

[Windgate]

Increíble, entonces es posible resolverlo con capacidad de representación no dependiente del número de soldados... Miré la solución en Wikipedia, no llegué a entenderla, pero bueno es saber que un problema así tiene solución :P

Me será útil para meditar si algún día soy encerrado durante meses en un calabozo oscuro sin nada más que hacer que contemplar la espesa oscuridad que me rodea cada noche ;)

Recibí una lección, al principio dije que no existiría solución para tal cosa :-X

[DjSonyk]

Aqui os dejo el problema en cuestion y la solucion.... ^^

Varios estados en 3n-3 y 2n-2 ,y diferentes solodados en la formacion.

http://www-cs-faculty.stanford.edu/~eroberts/courses/soco/projects/2004-05/automata-theory/problem.html