Problemilla interesante

[Windgate]

Yo me riiindooo...

[SplinterGU]

no, eso no cuenta... porque aca hay frames, y no es la misma iteraccion... por mas frames que hayan, estan disparando en distinto orden... la idea seria que la comunicacion sea 1 soldado por frame...

la verdad HaCkZJuaNN que no lei tu solucion, demasiado larga y rebuscada... pero aun asi, por lo poco que lei, no me suena que sincronicen todos los soldados... si los soldados no saben contar, no saben contar ni hasta 1000000000 ni tampoco hasta 1 o 2...

creo que es hora de googlear....

[SplinterGU]

ya tengo la solucion!

el que da la orden grita fuerte o usa un altoparlante... y listo, todos reciben la orden a la vez...

ahora hablando en serio, asi como lo planteas, no le veo solucion... si pones una solucion efectiva y con prueba, simple y que se vea la solucion clara (si haces un ejemplo en bennu, cada soldado debe comunicarse con otro a razon de 1 comunicacion por frame... y con las mismas condiciones que planteas, sin contar y sin tomar tiempos...), te doy 10 karmas...

[HaCkZJuaNN]

no, eso no cuenta... porque aca hay frames, y no es la misma iteraccion... por mas frames que hayan, estan disparando en distinto orden... la idea seria que la comunicacion sea 1 soldado por frame...

la verdad HaCkZJuaNN que no lei tu solucion, demasiado larga y rebuscada... pero aun asi, por lo poco que lei, no me suena que sincronicen todos los soldados... si los soldados no saben contar, no saben contar ni hasta 1000000000 ni tampoco hasta 1 o 2...

creo que es hora de googlear....

No, sí que saben contar, PERO EL NÚMERO HASTA EL QUE SABEN CONTAR DEBE SER INDEPENDIENTE DEL NÚMERO DE SOLDADOS Y VÁLIDO PARA CUALQUIERA DE ÉSTOS. Esa es la condición.

Splinter, parece que quieras boicotearme apost o algo :P

En mi solución sólo cuentan hasta 2, o mejor dicho, la entrada que más posibilidades tiene sólo tiene 3, y eso vale para cualquier número de soldados.

Este fin de semana si encuentro un rato lo escribo en bennu para que se vea.

Cuando digo a la vez, me refiero al mismo frame. Creo que la solución de dcelso van disparando uno en cada frame, empezando por el último. Al menos eso es lo que me parece viendo la lógica del algoritmo.

[HaCkZJuaNN]

Siendo mas exaustivos quizas en el mismo frame cuando estan todos a 4, uno sea antes que otro, dependiendo el orden de creación.
Quizas se me haya escapado algún detalle, a mi mi lógica también me dice lo mismo que a ti, pero en la práctica pasa esto que te digo.

Intenta implementar tu método en mi ejemplo para poder ver el resultado, a ver que tal, si quieres , claro.

EDIT: creo que tienes razón, este métido si lo pasamos a máquinas de estados controladas por un reloj no funcionaría ya que el cambio al estado 4 sería progresivo uno a uno en cada golpe de reloj.

Claro, creo que el tema es que en bennu funciona porque los procesos se van ejecutando uno a uno y ahí te da la casualidad de que cuando se ejecuta uno, el siguiente ya se ha ejecutado y por lo tanto confirman todos en el mismo frame, pero eso no pasaría si la ejecución de los frames de todos los procesos ocurriera a la vez. Básicamente es como si en cada turno, cada soldado pensara lo que tiene que decir, y cuando dieran la orden, todos dijeran lo que tienen que decir y que ya no depende de lo que les vayan a decir en este turno, eso se lo guardan para el siguiente.

[Windgate]

Yo espero ver el programa en Bennu, debe de ser uno de los algoritmos de sincronización más premiados de la historia o algo así, ¿Tu amigo lo estudió en sistemas operativos?

Había una serie de problemas típicos, mucho más simples que el tuyo, recuerdo el problema de "los filósofos comiendo spaghetti" por ejemplo, que era un problema acceso a recursos, pero muuucho más sencillo que lo que hablas.

Si lo veo resuelto para mí será "almost magic".

[SplinterGU]

no, eso no cuenta... porque aca hay frames, y no es la misma iteraccion... por mas frames que hayan, estan disparando en distinto orden... la idea seria que la comunicacion sea 1 soldado por frame...

la verdad HaCkZJuaNN que no lei tu solucion, demasiado larga y rebuscada... pero aun asi, por lo poco que lei, no me suena que sincronicen todos los soldados... si los soldados no saben contar, no saben contar ni hasta 1000000000 ni tampoco hasta 1 o 2...

creo que es hora de googlear....

No, sí que saben contar, PERO EL NÚMERO HASTA EL QUE SABEN CONTAR DEBE SER INDEPENDIENTE DEL NÚMERO DE SOLDADOS Y VÁLIDO PARA CUALQUIERA DE ÉSTOS. Esa es la condición.

Splinter, parece que quieras boicotearme apost o algo :P

En mi solución sólo cuentan hasta 2, o mejor dicho, la entrada que más posibilidades tiene sólo tiene 3, y eso vale para cualquier número de soldados.

Este fin de semana si encuentro un rato lo escribo en bennu para que se vea.

Cuando digo a la vez, me refiero al mismo frame. Creo que la solución de dcelso van disparando uno en cada frame, empezando por el último. Al menos eso es lo que me parece viendo la lógica del algoritmo.

no, no quiero boicotearte ni nada...

wait... pero no sirve que todos disparen al mismo frame porque recibieron la notificacion en ese frame... porque bennu es engañoso en eso... porque con ese criterio, yo puedo asegurar que en 2 iteraciones (2 frames) todos los solados disparan al mismo tiempo... y eso es engañoso totalmente... para hacerlo correcto, hay que hacer que solo 1 soldado pueda comunicarse en cada frame... y con esta primisa y sabiendo que cada soldado solo puede ver y escuchar a la distancia de sus extremos mas proximos... hacer que todos disparen a la vez...

pone facilmente el caso para 3 soldados o 4... cuando 1 soldado le dice al otro dispara, llega al ultimo, el ultimo dice, ROGER o entendido y se prepara a disparar, mientras el otro solado le dice al otro lo mismo, el primero en cofirmar ya disparo... yo, sencillamente si vos decis que ningun soldado puede contar (salvo hasta 3) ni tampoco puede cronometrar nada, no veo forma de sincronizacion...

explicalo de forma reducida, y "for dummy"... asi nos da ganas de leer...

[SplinterGU]

Yo espero ver el programa en Bennu, debe de ser uno de los algoritmos de sincronización más premiados de la historia o algo así, ¿Tu amigo lo estudió en sistemas operativos?

Había una serie de problemas típicos, mucho más simples que el tuyo, recuerdo el problema de "los filósofos comiendo spaghetti" por ejemplo, que era un problema acceso a recursos, pero muuucho más sencillo que lo que hablas.

Si lo veo resuelto para mí será "almost magic".

segun entendi dijo "HaCkZJuaNN", es una de esas incognitas que nadie resolvio... pregunta directa a HaCkZJuaNN, tu amigo te dio la solucion oficial? te dio una solucion propia?

yo estuve googleando y no encontre nada con soldados en fila disparando a la vez...

por favor HaCkZJuaNN mas informacion...

[HaCkZJuaNN]

no, no quiero boicotearte ni nada...

wait... pero no sirve que todos disparen al mismo frame porque recibieron la notificacion en ese frame... porque bennu es engañoso en eso... porque con ese criterio, yo puedo asegurar que en 2 iteraciones (2 frames) todos los solados disparan al mismo tiempo... y eso es engañoso totalmente... para hacerlo correcto, hay que hacer que solo 1 soldado pueda comunicarse en cada frame... y con esta primisa y sabiendo que cada soldado solo puede ver y escuchar a la distancia de sus extremos mas proximos... hacer que todos disparen a la vez...

pone facilmente el caso para 3 soldados o 4... cuando 1 soldado le dice al otro dispara, llega al ultimo, el ultimo dice, ROGER o entendido y se prepara a disparar, mientras el otro solado le dice al otro lo mismo, el primero en cofirmar ya disparo... yo, sencillamente si vos decis que ningun soldado puede contar (salvo hasta 3) ni tampoco puede cronometrar nada, no veo forma de sincronizacion...

explicalo de forma reducida, y "for dummy"... asi nos da ganas de leer...

Con esas condiciones es absolutamente imposible, obviamente. La idea es que todos los soldados transmiten instrucciones a la vez sincronizados. Vale que en bennu lo de los frames es engañoso, pero se me ha ocurrido una forma de implementarlo en bennu para que eso no de problemas. Cada "iteración" la subdivido en 2 frames de bennu. En el primero los soldados "piensan" que es lo que van a transmitir, y en el segundo únicamente lo transmiten. De esa forma me ahorro esos problemillas. Ya lo haré el sábado o el domingo...

Básicamente les digo: "Hora de comunicarse", todos se comunican, sin hacer razonamientos sino meramente comunicar y apuntar lo que les dicen los de sus lados. Entonces digo "hora de pensar", y todos hacen los razonamientos con los datos que han recibido en la "hora de comunicarse" y lo que ya tenían apuntado de antes. De esa forma me ahorro problemas de que si éste soldado ha actuado antes que éste o lo que sea, dado que cuando se comunican me aseguro que todos ya han actuado, y cuando actuan me aseguro que todos ya se han comunicado.

Mi solución explicada rápido se basa en que mando una señal que va avanzando de soldado a soldado hasta llegar al último, donde "rebota" y vuelve para atrás. Al mismo tiempo que mando esa señal, mando otra por otra entrada/salida de cada soldado que va avanzando 2 soldados y retrocediendo 1, de forma que de media avance 1 soldado cada 3 turnos. El punto en el que la señal "rebotada" y la señal lenta se juntan es justamente el soldado que está en medio. Entonces ese soldado vuelve a enviar esas dos señales, DUPLICADAS hacia sus dos lados, de forma que acabo encontrando los soldados que se sitúan en los cuartos. Y repite, repite, repite... De esta forma, voy subdividiendo a los soldados en grupos iguales, hasta que todos los soldados intentan enviar señales al mismo tiempo, y es cuando disparan. Un soldado dispara cuando tanto él, como su siguiente como su anterior ya han sido soldados "de en medio" en algún momento, que se produce en todos al mismo tiempo siempre. Si queréis pruebas mejor explicadas y fiaros más leer la solución bien explicada.

Y ya escribiré el programilla... sin prisa ;)

[HaCkZJuaNN]

segun entendi dijo "HaCkZJuaNN", es una de esas incognitas que nadie resolvio... pregunta directa a HaCkZJuaNN, tu amigo te dio la solucion oficial? te dio una solucion propia?

yo estuve googleando y no encontre nada con soldados en fila disparando a la vez...

por favor HaCkZJuaNN mas informacion...

Nono, está resuelto, y no sólo resuleto sino DEMOSTRADO(matemáticamente) que es imposible encontrar una solución de orden menor a 2n-2. Mi amigo no me ha dado la solución oficial 2n-2, pero realmente no me interesa tanto, él tampoco la sabe, sabe que existe y sabe dónde encontrarla, pero está intentando encontrarla él mismo.

Se llama el problema del "pelotón de fusilamiento" o algo así, al menos eso me dijo. Un profesor también charla con nosotros sobre esto, te aseguro que es un problema conocido.

[SplinterGU]

no, no quiero boicotearte ni nada...

wait... pero no sirve que todos disparen al mismo frame porque recibieron la notificacion en ese frame... porque bennu es engañoso en eso... porque con ese criterio, yo puedo asegurar que en 2 iteraciones (2 frames) todos los solados disparan al mismo tiempo... y eso es engañoso totalmente... para hacerlo correcto, hay que hacer que solo 1 soldado pueda comunicarse en cada frame... y con esta primisa y sabiendo que cada soldado solo puede ver y escuchar a la distancia de sus extremos mas proximos... hacer que todos disparen a la vez...

pone facilmente el caso para 3 soldados o 4... cuando 1 soldado le dice al otro dispara, llega al ultimo, el ultimo dice, ROGER o entendido y se prepara a disparar, mientras el otro solado le dice al otro lo mismo, el primero en cofirmar ya disparo... yo, sencillamente si vos decis que ningun soldado puede contar (salvo hasta 3) ni tampoco puede cronometrar nada, no veo forma de sincronizacion...

explicalo de forma reducida, y "for dummy"... asi nos da ganas de leer...

Con esas condiciones es absolutamente imposible, obviamente. La idea es que todos los soldados transmiten instrucciones a la vez sincronizados. Vale que en bennu lo de los frames es engañoso, pero se me ha ocurrido una forma de implementarlo en bennu para que eso no de problemas. Cada "iteración" la subdivido en 2 frames de bennu. En el primero los soldados "piensan" que es lo que van a transmitir, y en el segundo únicamente lo transmiten. De esa forma me ahorro esos problemillas. Ya lo haré el sábado o el domingo...

Básicamente les digo: "Hora de comunicarse", todos se comunican, sin hacer razonamientos sino meramente comunicar y apuntar lo que les dicen los de sus lados. Entonces digo "hora de pensar", y todos hacen los razonamientos con los datos que han recibido en la "hora de comunicarse" y lo que ya tenían apuntado de antes. De esa forma me ahorro problemas de que si éste soldado ha actuado antes que éste o lo que sea, dado que cuando se comunican me aseguro que todos ya han actuado, y cuando actuan me aseguro que todos ya se han comunicado.

Mi solución explicada rápido se basa en que mando una señal que va avanzando de soldado a soldado hasta llegar al último, donde "rebota" y vuelve para atrás. Al mismo tiempo que mando esa señal, mando otra por otra entrada/salida de cada soldado que va avanzando 2 soldados y retrocediendo 1, de forma que de media avance 1 soldado cada 3 turnos. El punto en el que la señal "rebotada" y la señal lenta se juntan es justamente el soldado que está en medio. Entonces ese soldado vuelve a enviar esas dos señales, DUPLICADAS hacia sus dos lados, de forma que acabo encontrando los soldados que se sitúan en los cuartos. Y repite, repite, repite... De esta forma, voy subdividiendo a los soldados en grupos iguales, hasta que todos los soldados intentan enviar señales al mismo tiempo, y es cuando disparan. Un soldado dispara cuando tanto él, como su siguiente como su anterior ya han sido soldados "de en medio" en algún momento, que se produce en todos al mismo tiempo siempre. Si queréis pruebas mejor explicadas y fiaros más leer la solución bien explicada.

Y ya escribiré el programilla... sin prisa ;)

entiendo lo que decis, eso podria funcionar... pero me da la sensacion que llevara mas de 2n - 2... a menos que 2n - 2 te refieras a la cantidad de veces que interactua cada soldado...

ya me imagine que ni tu amigo ni tu sabian la solucion... ya es hora de la solucion oficial... a googlear...

[HaCkZJuaNN]

entiendo lo que decis, eso podria funcionar... pero me da la sensacion que llevara mas de 2n - 2... a menos que 2n - 2 te refieras a la cantidad de veces que interactua cada soldado...

ya me imagine que ni tu amigo ni tu sabian la solucion... ya es hora de la solucion oficial... a googlear...

No claro, desde el principio dije que mi solución es de orden 3n.

Mi amigo sabe dónde está escrita la solución, pero prefier intentarllo él primero ;)

[SplinterGU]

si alguien encuentra en google la solucion oficial... adelante... quiero verla... :D

a mi no me interesa intentarlo, esto es como hacer tu propio codigo para todo o reusar uno existente... como perder tiempo en inventar la rueda que ya hace tiempo que existe... si tenes donde sacar la solucion pasalo please... gracias...

[Windgate]

Yo no la encontré...

[DCelso]

Yo también creo que voy a desistir, a mi parece faltan datos :(