Resulta que un amigo de la universidad me ha contado esto, que por lo visto es un problema famoso, relacionado con informática.
La forma intuitiva de verlo es la siguiente:
Tienes una fila de soldados. Todos los soldados son exactamente iguales. Cada soldado puede hablar con el que tiene delante y con el que tiene detrás. Se trata de que tú en un momento dado le digas al último soldado: "Dispara", y los soldados se comuniquen unos con otros, SIGUIENDO UN ALGORITMO IGUAL EN TODOS, de forma que en un momento dado todos los soldados disparen al mismo tiempo.
Forma un poco más rigurosa:
Se trata de máquinas de estados finitos. El número de soldados que tienes es finito PERO NO LO CONOCES DE ANTEMANO!!!! No vale contar los soldados porque los soldados(como máquinas que son) tienen un límite de hasta dónde pueden contar, y ese límite puede ser más pequeño que el número de soldados que hay. Los soldados sólo pueden estar en un número finito predeterminado no dependiente del número de soldados de estados(por ejemplo, 5), y dar un número finito predeterminado no dependiente del número de soldados de instrucciones distintas.
Las entradas/salidas de cada soldado pueden ser todas las que quieras porque al fin y al cabo se podrían codificar todas en una sola(potencias de 2, etc...), pero un número finito(esto nos gusta mucho decirlo) ;)
Los soldados no pueden disparar antes de tiempo, se trata de que cuando disparen todos a la vez ninguno haya disparado todavía(menuda tontería si no xD).
Pues hala. Si tenéis preguntas decídmelo.
Por cierto, por si no queda claro, el problema trata de escribir el algoritmo de los soldados.
Este problema está resuelto y aparentemente era muy complicado(aunque yo lo he resuelto y no me parecía tan complicado), y se ha demostrado que el mejor algoritmo que lo resuleve es de orden 2n-2(n = número de soldados). Mi solución es un poco más larga :P, pero funciona.
Además, esto se puede perfectamente implementar en bennu, basta con crear un proceso "soldado" que tenga el algoritmo dentro y que sea capaz de comunicarse con el soldado "anterior" y el "siguiente".
PS: Se me olvidaba, el primer soldado y el último soldado SABEN QUE SON EL PRIMERO Y EL ÚLTIMO. Y podéis declarar todas las variables que os hagan falta(finitas y predeterminadas ;) )
Al primer soldado le pasas un N = 1
En cada "FRAME" el soldado pasa al siguiente su N + 1
Así que al final cada soldado queda con un valor igual a su posición en la fila
El último soldado recibe un valor que almacena en M
El último soldado pasa al anterior un valor M - 1
En cada "FRAME" el soldado pasa al siguiente anterior M - 1 y además suma 1 en un contador K inicializado a 0
Cuando el valor del contador K coincide con la M que reciben disparan
Espero que me se haya entendido... ::)
Quote from: Windgate on November 10, 2009, 09:20:17 PM
Al primer soldado le pasas un N = 1
En cada "FRAME" el soldado pasa al siguiente su N + 1
Así que al final cada soldado queda con un valor igual a su posición en la fila
El último soldado recibe un valor que almacena en M
El último soldado pasa al anterior un valor M - 1
En cada "FRAME" el soldado pasa al siguiente anterior M - 1 y además suma 1 en un contador K inicializado a 0
Cuando el valor del contador K coincide con la M que reciben disparan
Espero que me se haya entendido... ::)
Esa es la idea fácil, pero no vale.
Si no conoces el número de soldados que hay, N podría llegar a valer cualquier cosa(finita, pero cualquier cosa), y tú tienes que saber desde el principio hasta cuánto saben contar los soldados; sin depender del número de soldados que haya.
Así que tú me dices que saben contar hasta 5000? Y si hay 5001 soldados??? Saben contar hasta 5000000000000000000000 y si hay 5000000000000000000001 soldados? etc... Se puede resolver sin tener que utilizar eso.
Entiendo... Tiene que ser a prueba de límites de overflow, sigo meditando.
Quote from: HaCkZJuaNN on November 10, 2009, 07:29:12 PM
Resulta que un amigo de la universidad me ha contado esto, que por lo visto es un problema famoso, relacionado con informática.
La forma intuitiva de verlo es la siguiente:
Tienes una fila de soldados. Todos los soldados son exactamente iguales. Cada soldado puede hablar con el que tiene delante y con el que tiene detrás. Se trata de que tú en un momento dado le digas al último soldado: "Dispara", y los soldados se comuniquen unos con otros, SIGUIENDO UN ALGORITMO IGUAL EN TODOS, de forma que en un momento dado todos los soldados disparen al mismo tiempo.
Forma un poco más rigurosa:
Se trata de máquinas de estados finitos. El número de soldados que tienes es finito PERO NO LO CONOCES DE ANTEMANO!!!! No vale contar los soldados porque los soldados(como máquinas que son) tienen un límite de hasta dónde pueden contar, y ese límite puede ser más pequeño que el número de soldados que hay. Los soldados sólo pueden estar en un número finito predeterminado no dependiente del número de soldados de estados(por ejemplo, 5), y dar un número finito predeterminado no dependiente del número de soldados de instrucciones distintas.
Las entradas/salidas de cada soldado pueden ser todas las que quieras porque al fin y al cabo se podrían codificar todas en una sola(potencias de 2, etc...), pero un número finito(esto nos gusta mucho decirlo) ;)
Los soldados no pueden disparar antes de tiempo, se trata de que cuando disparen todos a la vez ninguno haya disparado todavía(menuda tontería si no xD).
Pues hala. Si tenéis preguntas decídmelo.
Por cierto, por si no queda claro, el problema trata de escribir el algoritmo de los soldados.
Este problema está resuelto y aparentemente era muy complicado(aunque yo lo he resuelto y no me parecía tan complicado), y se ha demostrado que el mejor algoritmo que lo resuleve es de orden 2n-2(n = número de soldados). Mi solución es un poco más larga :P, pero funciona.
Además, esto se puede perfectamente implementar en bennu, basta con crear un proceso "soldado" que tenga el algoritmo dentro y que sea capaz de comunicarse con el soldado "anterior" y el "siguiente".
PS: Se me olvidaba, el primer soldado y el último soldado SABEN QUE SON EL PRIMERO Y EL ÚLTIMO. Y podéis declarar todas las variables que os hagan falta(finitias ;) )
o lei muy por arriba o te falto decir que es lo que se busca o representa tu "2n-2(n = número de soldados)"...
y creo que windgate te esta explicando como implementarlo en bennu, que creo no es lo que vos estas planteando...
por otro lado, el disparar al mismo tiempo dependera del tiempo que tarda cada uno en pasar la voz al otro y en el tiempo que todos tardan en recibir la orden, pero aun asi, mas si los soldados de mas atras no pueden contar la cantidad que tienen delante, y no pueden verlos ni escucharlos mas alla de sus vecinos cercanos (1 soldado delante y 1 detras), nunca sabra cuando el ultimo recibio la señal, y solo hasta que el del frente (o detras segun el sentido) le informe de tal situacion... y esto aca entra en un ciclo sin fin... ya que el de delante debera saber cuando el ultimo sabe que el (el de adelante) sabe que tiene la orden de disparar... puff...
a mi me parece el planteo un poco ridiculo e ilogico... si los soldados no pueden recibir la orden de una unica fuente en comun, hacer la sincronizacion es imposible...
quizas vos preguntas otra cosa, pero te falta aclarar mejor tu planteo...
Hombre, la solución sencilla es que le demos la orden al último soldado, y este guarda una variable propia i=1, y al siguiente le pasa i++, que lo guarda y le pasa i++ al siguiente. Así el último sabe cuantos soldados hay en la cadena.
Entonces le pasa al anterior una señal y espera "numero de soldados" (su propia i) ciclos para disparar, que es el tiempo que tardará la señal del último en llegar al primero, que al tener un valor i==1 esperará un ciclo.
Pero planteas la posibilidad de haber overflow en el tipo de la variable i, por lo que necesitamos algo contable que no provoque overflow... y es demasiado de noche para pensar en ello ;D
O bien buscar la forma de que el primer y el último soldado se comuniquen a traves de la fila de forma que dos señales lleguen simultáneamente al primero y al último.
En bennu es muy facil.
ordenas a todos a disparar al mismo tiempo. ;D
Yo creo que se basa en pasarse un 1 o un 0 hasta que de alguna mágica manera al final todos reciban un 2 a la vez... Por supuesto con coste 2n-2 no se me ocurre nada, se me ocurren soluciones con coste n!
Podría empezarse así:
- El primero pasa un 0 al segundo, el segundo pasa un 1 al tercero, así se alternan 1s y 0s hasta llegar al último. (Coste n)
...pero no se me ocurre como seguir...
@Splinter: Asumía que en el coste que n es el número de soldados y que existe un tiempo de comunicación 1 de forma que el tiempo total de resolver el problema sea T = 2n - 2
2n-2 significa lo siguiente:
el primer soldado llama al que tiene a su lado, este nuevo llama al siguiente, asi hasta llegar al último, y vuelta hacia atras
el último solidado llama al qui tiene a su lado, este nuevo llama al siguie, así hasta llegar al primero,
justo aqui dispararían todos a la vez.
Una representación gráfica con cuatro soldados sería (2*4-2 = 6). O: soldado, _:iteración
1 2 3
_ _ _
O1_O2_O3_O4
6 5 4
Sí, tiene pinta de ser así DCelso, es como pasarse la patata caliente.
Pero en cada "turno" supongo que no sólo se comunicará un soldado con el siguiente, si no que habrá comunicación al mismo tiempo entre varios. Si no no le veo solución...
Pero, probasteis mi ejemplo?
Quote from: SplinterGU on November 11, 2009, 12:58:09 AM
o lei muy por arriba o te falto decir que es lo que se busca o representa tu "2n-2(n = número de soldados)"..
Es el orden del algoritmo más rápido que resuelve el problema. Si hay 10 soldados, el algoritmo tarda 18 instrucciones en funcionar. Eso es lo que quiere decir(es aproximado, 2n-2 es sólo cuando el número de soldados es muy muy grande). Yo no pido la solución óptima, yo ni la sé; la solución que yo encontré es de orden 3n(si hay 5000 soldados, tarda 15000 instrucciones en funcionar, aproximadamente).
Quote
y creo que windgate te esta explicando como implementarlo en bennu, que creo no es lo que vos estas planteando...
No, implementarlo en bennu sin restricciones es relativamente fácil, me refiero a resolver el problema con las condiciones que he impuesto(es la definición de máquina de estados finitos según tengo entendido), y que una vez resuelto, se puede comprobar que funciona en bennu(lo cual no quiere decir que en bennu haya soluciones más fáciles)
Quote
por otro lado, el disparar al mismo tiempo dependera del tiempo que tarda cada uno en pasar la voz al otro y en el tiempo que todos tardan en recibir la orden, pero aun asi, mas si los soldados de mas atras no pueden contar la cantidad que tienen delante, y no pueden verlos ni escucharlos mas alla de sus vecinos cercanos (1 soldado delante y 1 detras), nunca sabra cuando el ultimo recibio la señal, y solo hasta que el del frente (o detras segun el sentido) le informe de tal situacion... y esto aca entra en un ciclo sin fin... ya que el de delante debera saber cuando el ultimo sabe que el (el de adelante) sabe que tiene la orden de disparar... puff...
a mi me parece el planteo un poco ridiculo e ilogico... si los soldados no pueden recibir la orden de una unica fuente en comun, hacer la sincronizacion es imposible...
quizas vos preguntas otra cosa, pero te falta aclarar mejor tu planteo...
Nono, lo entendiste perfectamente, y ahí está la gracia, que es treméndamente complicado hacer que todos se comuniquen sin comunicarse. Pero se puede hacer, lo juro por mi vida. El truco está en hacer que se sincronicen sin tener que comunicarse... de alguna manera...
Quote from: Windgate on November 11, 2009, 01:32:52 PM
Sí, tiene pinta de ser así DCelso, es como pasarse la patata caliente.
Pero en cada "turno" supongo que no sólo se comunicará un soldado con el siguiente, si no que habrá comunicación al mismo tiempo entre varios. Si no no le veo solución...
Obviamente tiene que haberla ;)
Quote from: DCelso on November 11, 2009, 12:27:55 PM
2n-2 significa lo siguiente:
el primer soldado llama al que tiene a su lado, este nuevo llama al siguiente, asi hasta llegar al último, y vuelta hacia atras
el último solidado llama al qui tiene a su lado, este nuevo llama al siguie, así hasta llegar al primero,
justo aqui dispararían todos a la vez.
Una representación gráfica con cuatro soldados sería (2*4-2 = 6). O: soldado, _:iteración
1 2 3
_ _ _
O1_O2_O3_O4
6 5 4
Pero el tema es que el último no tiene ni idea de cuándo llegas al primero, ya que él sólo se comunica con el anterior a él, así que cómo le dices que dispare cuando llegues al primero, si él no sabe cuándo llegas??? Y si le pasas la información a través de todos los de en medio, para cuando le llegue la orden, el primer ha disparado hace 3 horas. Se trata de que disparen A LA VEZ.
Por cierto, se supone que las instrucciones tardan todas el mismo tiempo y se sincronizan..., todos los soldados deciden que van a comunicar y cuando se les da la orden se lo comunican al siguiente y al anterior lo que le tengan comunicar. Como los FRAMES en bennu. Un sistema de "turnos".
No se pueden poner spoilers en este foro?? Lo digo para poner mi solución y que sólo la lean los que quieran.
Los spoilers los odio >:(
Esas veces que buscas algo y te pone que tienes que registrarte en un foro que versa sobre chino mandarín para descargar el capítulo 237 de tu ánime preferido... Es una opinión.
Yo creo que nos has dejado a todos sorprendidos conjeturando, incluido DCelso y Splinter que son programadores obesos y con mucho vello... Por mí puedes soltarlo :P
Bueno, ya digo que no conozco la solución óptima, pero aquí está la que yo saqué, de orden 3n(cuando el número de soldados es grande, el algoritmo tarda 3 x el número de soldados "frames" en terminar):
No voy a escribir el algoritmo porque es un poco largo y pesado y no se entendería, así que lo voy a explicar.
En primer lugar defino 4 clasificaciones que se pueden aplicar a cada soldado
-Primero ABSOLUTO: Esto se lo pongo solamente al primero de todos(en la primera instrucción del algoritmo pongo if(soy_primero) then primero_absoluto = 1; Ya dije que el primero y el último saben que lo son.
-Último ABSOLUTO: Idem, pero al último.
-Primero relativo: Esto lo voy a utilizar más, pero en la primera instrucción hago que el primero y el último absolutos se autoasignen esto.
-Último relativo: Idem.
Ahora bien, el problema es igual si hay 1 sola entrada/salida entre cada 2 o varias, ya que varias entradas/salidas se pueden codificar en una sola, así que hablaré como si hubiera varias entradas.
Hay 2 "flujos". Ambos empiezan por el primer soldado, que al ser el primero lo "suelta". El primer "flujo" funciona así:
El primer soldado le manda al siguiente un 1 por la entrada/salida1. Cada soldado, si recibe un 1 por la entrada/salida1, manda un 1 al siguiente soldado por la misma entrada si no es un último relativo. Si es un último relativo, entonces le manda un -1 al soldado anterior por la misma entrada. Cada soldado, si recibe un -1 por esa entrada/salida del soldado siguiente, manda un -1 al soldado anterior.
Por otro lado, el otro flujo, que va por otra entrada/salida, empieza con un 1 que manda el primer soldado al segundo. Cada soldado, si recibe un 1 por esta entrada/salida2 desde el anterior, manda un -1 al mismo que se lo ha mandado(al anterior). Si recibe un -1 del SIGUIENTE, entonces le manda un 2 al SIGUIENTE. Si recibe un 2 del anterior, le manda un 1 al siguiente. Básicamente este flujo/señal lo que va haciendo es avanzar 2 soldados y retroceder 1. 1,-1,2,1,-1,2,1,-1,2,1,-1,2,1,-1...
Bien, pues como se puede ver que la primera señal va hasta el final y "rebota", y que la segunda tarda 3 turnos en recorrer 1 espacio, se puede ver(lo podéis comprobar en un papel) que el punto en el que la señal "de vuelta" del primer flujo entra al mismo soldado(por la derecha obviamente) que la señal que va avanzando cada 3 turnos es justamente el soldado de en medio si el número de soldados es impar o si es par, de los dos que están en medio, el de la derecha(el último está a la derecha del todo, para orientaros).
Además, si el número de soldados es impar, la señal que le llega por entrada/salida2 al soldado de en medio del soldado anterior en ese instante es siempre 2, mientras que si el número de soldados es par, la señal que le llega al de la derecha de los dos de en medio es 1. De modo que ese soldado "sabe" si el número de soldados es par o es impar.
Si es impar(sólo hay 1 en medio), entonces ese se autoasigna a sí mismo primero_relativo = 1 y ultimo_relativo = 1. Si es par, se autoasigna a sí mmismo primero_relativo = 1 y le dice al anterior(el otro que está en medio) que se asigne ultimo_relativo = 1.
De esta forma, quedaría un esquema tal que así:
si n = 8(cada - separa dos soldados)
prim - 0 - 0 - ult - prim - 0 - 0 - ult
si n = 7
prim - 0 - 0 - ult/prim - 0 - 0 - ult
Pues bien, ahora la cuestión es repetir, si es impar, el de en medio vuelve a enviar el mismo par de señales hacia la izquierda Y hacia la derecha al mismo tiempo. Si es par pues el de la derecha la manda hacia la derecha y el de la izquierda la manda hacia la izquierda. Así, cuando rebote y vuelvan a encontrarse las señales, tenemos los que estén situados en los "cuartos".
Por ejemplo, supongamos n un poco más grande, n = 18, tras dos iteraciones del recorrido de las señales, tenemos:
prim - 0 - 0 - 0 - ult/prim - 0 - 0 - 0 - ult - prim - 0 - 0 - 0 - ult/prim - 0 - 0 - 0 - ult
Y por supuesto, ahora se mandarían 4 nuevos pares de señales en los 4 sentidos. De este modo, voy subdividiendo a los soldados en grupos iguales(siempre iguales, pues si es impar cojo 1 en medio y si es par cojo 2, de manera que los que restan sean pares).
Tras la siguiente señal el resultado sería:
prim - 0 - ult/prim - 0 - ult/prim - 0 - ult/prim - 0 - ult - prim - 0 - ult/prim - 0 - ult/prim - 0 - ult/prim - 0 - ult
Al mismo tiempo, en cada "frame", cada soldado le pasa a su anterior y su siguiente el valor de su variable primero_relativo y ultimo_relativo. En el caso del PRIMERO_ABSOLUTO y el ULTIMO_ABSOLUTO, sólo comprueban por uno de los lados.
La condición de disparo de cada soldado es que tanto él mismo, como su anterior, como su siguiente sean o bien un primero o un último(cada uno puede ser cada una de las 2 cosas). Esto se produce en todos los soldados AL MISMO TIEMPO(pues voy subdividiéndolos en grupos iguales, hasta que los grupos son de 1). En el caso del PRIMERO_ABSOLUTO y el ULTIMO_ABSOLUTO sólo comprueban uno de los lados, pero el algoritmo sigue funcionando en estos casos.
El orden de este algoritmo es 3n porque si tomamos un n muy grande, n -> infinito; el número de "frames" que tienen que pasar es de 3n/2 para el primer bucle, n/2*3/2 para el segundo, n/4*3/2 para el tercero, etc...
3n/2+3n/4+3n/8+3n/16... = 3n(1/2+1/4+1/8+1/16...) = 3n*1 = 3n.
Sin embargo, acabo de darme cuenta de que el algoritmo se puede reducir fácilmente a 2n empezando la señal de la derecha del PRIMER bucle desde el último(solamente del primero), encontrando el de en medio mucho antes. Pero el caso es que funciona.
a ver... no hay soldados en los costados, solo adelante y atras... es 1 fila...
bien... la solucion se puede implementar asi en 2 recorridas...
recorrida 1, cada soldado avisa al de adelante que se prepare para disparar, y a su vez le dice cual es el tiempo/hora que se dio la orden y este soldado toma nota del tiempo/hora que recibio la orden... cuando un soldado no tiene a quien pasar la orden ya que es el ultimo...
y se inicia la recorrida 2, y cada soldado le indica al soldado anterior que ya recibio la orden... en este caso, cada soldado de la fila ya conoce (desde su posicion) cuando tiempo tardara la confirmacion en llegar al primer soldado, por ende, empieza a contar hacia atras su reloj, y cuando de 0, ya puede disparar y todos dispararan a la vez....
obviamente se supone que todos los solados son iguales y tienen la misma velocidad de respuesta y comunicacion...
entonces la cantidad de iteracciones sera (2 x N) - 1... demasiado estupido el asunto...
Ni siquiera importa saber cuantos soldados hay...
Dejo la lectura de HackzJuaNN para mañana, me puede a estas horas, pero:
Splinter, propuse lo mismo. Para un número finito "pequeño" de soldados sirve, pero si hay un número de soldados mayor que la capacidad de representación de un int la solución no vale, ya que puede haber overflow del int, se trata de resolverlo sin utilizar números grandes.
Conjeturé que podría haber una solución usando sólo 0 , 1 y 2, pero la solución que propone HackzJuaNN usa -1 , 0 , 1 , 2
Mañana la estudio :P
PD: Sorry, estoy cansado para semejante problema xD
acabo de leer el tuyo, no es lo mismo, es parecido, aca no tenes que contar soldados... solo es tiempo, lo que haces es cuando recibir tu orden seteas un cronometro de cuenta regresiva con el valor resultante (T - Ti), donde T es tiempo actual y Ti tiempo inicial, y cuando recibis la confirmacion arrancas el cronometro... cuando el cronometro da cero ya esta... nadie tiene que contar nada, nadie tiene por que saber contar hasta 5000000000001 ni nada... solo es tiempo...
no me puse a analizar la solucion de HackzJuaNN, demasiado rebuscada, me gustan las cosas simples y efectivas.
Sí Splinter, pero el primer soldado puede llevar tanto tiempo contando que tenga overflow en el contador, lo que propone HackzJuan es resolverlo sin contadores grandes, él propone una solución basada en números "no mayores que 2".
Vamos, que contar el tiempo o contar soldados termina siendo un número "grande" si tenemos en cuenta que el número de soldados puede ser mayor que la capacidad de representación de long long int.
PD: No sé que hago despierto, sigo sin haber leido a fondo la solución de HackzJuan, mañana...
no, en tiempo no hay overflow... vamos que se pueden contar años sin problemas... no creo que un soldado tarde mas de 100 años en disparar, seguramente si pasan 100 años ya este muerto antes de que el ultimo reciba la orden...
bueno, como quieran... demasiado larga la solucion de HackzJuan... pero si funciona y es mas rapido bien...
Eso sí que es cierto, en tiempo no hay overflow, pero HackzJuann no se refiere a un PC sino a una máquina de estados, por eso ahí no podemos asumir que haya tan siquiera "algo" capaz de contar el timepo (HackzJuann lo confirmará mejor, yo hace años que no toco una máquina de estados).
Tú solución por supuesto que sirve, es similar a la que propuse y son soluciones que hoy en día nos valdrían, pero el problema que propone HackzJuann es de los típicos problemas matemáticos/informáticos de cuando la informática se basaba en cintas perforadas y necesitaban ser funcionales para N elementos asumiendo que las variables debían ocupar un par de bits a lo sumo.
Sigo diciendo que a pesar de seguir por aquí a estas horas (Qué vergüenza) no he interpretado todavía la solución de HackzJuann, lo que es seguro es que la resolvió alguien que ganó algún premio xD
yo hice maquinas de estados, maquinas de estados es una rutina que tiene estados asociados a un codigo, un estado pasa a otro estado una vez que concluye la logica del estado actual...
por ejemplo, seria algo asi como un switch metido dentro de un while... cada case de ese switch es un estado de la maquina y tiene un codigo asociado que ejecuta y hace que al terminar la ejecucion pase a otro estado...
creo que lo de juan es una propuesta... no se si es la solucion... es demasiado para leer... yo paso...
Sí que es demasiado para leer lo que nos dice :o, pero me pica la curiosidad conocer una solución que no dependa de la capacidad de representación numérica.
HackzJuann, ¿Es la verdadera solución al problema lo que propones?, a simple vista no entiendo nada más que una carambola de números, estoy por mirar en la Wikipedia :P
Insisto, una solución con coste 2n-2 es para premio nobel
PD: Ahora recuerdo la teoría sobre los problemas NP-completos, problemas que no son resolubles en un tiempo ni tan siquiera exponencial, esto es, tiempos del orden n! que es lo que se me ocurrió en un principio... No quise meterme a pensar sobre tan endiablado asunto pero me has enganchado, cabronazo >:(
EDIT: Joder, releo la solución de HackzJuann con propuesta de mejora y lo dejo para mañana, en serio, me pillas con 8 horas encima programando droides y no estoy para algoritmia.
Splinter... Los soldados no pueden saber el tiempo ni nada. No es un problema real no son ordenadores, hay unas limitaciones muy claras. No es un problema "auténtico". Por supuesto para hacerlo en la realidad es muy fácil, es un problema teórico donde la gracia está en pensar soluciones para un problema muy limitado, no se trata más que de pensar. No es ninguna tontería, es un problema conocido generalmente.
La gracia es que me di cuenta de que mi solución se puede hacer en 2n-2 ajustando una pequeña cosa(lo pone al final de mi solución), así que supongo que será la buena. De todas formas a mi aún no me han contado cuál se supone que es la solución "buena". Así que no la sé.
A ver esta otra solu.
Consiste en disparar cuando todos tengan confirmación de haber recibido la orden.
En el ejemplo he puesto variables en pantalla para ir viendo resultados, es bastante didáctico.
Aqui os dejo el proceso para que lo debatais, las iteraciones son 2n-2 exactamente.
Decir tiene que no he leido ninguna de vuestras soluciones aún, me lo tomé como reto personal :D.
Process soldado(x,y,graph)
public
soldado izquierda;
soldado derecha;
estado = 0;
begin
write_var(0,x+20,y-20,0,id);
write_var(0,x+20,y-10,0,estado);
write_var(0,x+20,y,0,izquierda);
write_var(0,x+20,y+10,0,derecha);
while (!key(_esc) )
switch (estado)
case PARADO:
end
case ORDEN_RECIBIDA:
if (derecha != 0)
derecha.estado = ORDEN_RECIBIDA;
estado = ORDEN_ENVIADA;
else
estado = ORDEN_CONFIRMADA;
end
end
case ORDEN_ENVIADA:
end
case ORDEN_CONFIRMADA:
if (izquierda !=0)
izquierda.estado = ORDEN_CONFIRMADA;
end
if (izquierda == 0 OR (izquierda !=0 AND izquierda.estado == ORDEN_CONFIRMADA))
estado = DISPARAR;
end
end
case DISPARAR:
fire(imagenes[1]);
estado = PARADO;
end
end
frame(2000);
end
end
Quote from: DCelso on November 12, 2009, 11:47:37 AM
A ver esta otra solu.
Consiste en disparar cuando todos tengan confirmación de haber recibido la orden.
En el ejemplo he puesto variables en pantalla para ir viendo resultados, es bastante didáctico.
Aqui os dejo el proceso para que lo debatais, las iteraciones son 2n-2 exactamente.
Decir tiene que no he leido ninguna de vuestras soluciones aún, me lo tomé como reto personal :D.
Process soldado(x,y,graph)
public
soldado izquierda;
soldado derecha;
estado = 0;
begin
write_var(0,x+20,y-20,0,id);
write_var(0,x+20,y-10,0,estado);
write_var(0,x+20,y,0,izquierda);
write_var(0,x+20,y+10,0,derecha);
while (!key(_esc) )
switch (estado)
case PARADO:
end
case ORDEN_RECIBIDA:
if (derecha != 0)
derecha.estado = ORDEN_RECIBIDA;
estado = ORDEN_ENVIADA;
else
estado = ORDEN_CONFIRMADA;
end
end
case ORDEN_ENVIADA:
end
case ORDEN_CONFIRMADA:
if (izquierda !=0)
izquierda.estado = ORDEN_CONFIRMADA;
end
if (izquierda == 0 OR (izquierda !=0 AND izquierda.estado == ORDEN_CONFIRMADA))
estado = DISPARAR;
end
end
case DISPARAR:
fire(imagenes[1]);
estado = PARADO;
end
end
frame(2000);
end
end
Hmm, pero entonces dispara primero el último no?
Quizá parece que disparan a la vez por la velocida de los frames o algo así, pero la lógica me dice que eso hace que dispare primero el último.
Si ves la ejecución, se ponen a la vez todos al estado 4 en el mismo frame y al siguiente disparan.
¿No es esto lo que se buscaba?
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.
Yo me riiindooo...
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....
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...
Quote from: SplinterGU on November 12, 2009, 01:45:09 PM
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.
Quote from: DCelso on November 12, 2009, 12:24:14 PM
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.
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".
Quote from: HaCkZJuaNN on November 12, 2009, 06:39:52 PM
Quote from: SplinterGU on November 12, 2009, 01:45:09 PM
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...
Quote from: Windgate on November 12, 2009, 07:30:46 PM
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...
Quote from: SplinterGU on November 12, 2009, 08:15:38 PM
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 ;)
Quote from: SplinterGU on November 12, 2009, 08:19:17 PM
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.
Quote from: HaCkZJuaNN on November 12, 2009, 08:40:36 PM
Quote from: SplinterGU on November 12, 2009, 08:15:38 PM
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...
Quote from: SplinterGU on November 12, 2009, 11:13:38 PM
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 ;)
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...
Yo no la encontré...
Yo también creo que voy a desistir, a mi parece faltan datos :(
Quote from: HaCkZJuaNN on November 10, 2009, 07:29:12 PM
Tienes una fila de soldados. Todos los soldados son exactamente iguales. Cada soldado puede hablar con el que tiene delante y con el que tiene detrás. Se trata de que tú en un momento dado le digas al último soldado: "Dispara", y los soldados se comuniquen unos con otros, SIGUIENDO UN ALGORITMO IGUAL EN TODOS, de forma que en un momento dado todos los soldados disparen al mismo tiempo.
Creo que en tu difinición falla algo...
En "SIGUIENDO UN ALGORITMO IGUAL EN TODOS",se supone que el primero y el ultimo se comunican con el de alante y detras con lo que algo falla,o que no he acabado de entender.
Sin llegar a comprobarlo yo creo que es parecido al tipico puzzle en que pisas una casillas y se encienden/apagan las de alrededor y seguramente con un XOR bit a bit,seria la solucion...Cuando tenga un rato lo comprobaré.
Gran deducción lo que dices de las casillas DJSonyk xD
Pero hay un problema, en el tablero de casillas del que hablas hay sólo 2 colores, aquí necesitamos un "tercer color" que es al que llegan TODOS a la vez para disparar.
Vamos, que no sirve que uno de ellos pase por ese tercer color hasta el final
Lo siento no me explique bien ^^....Sabiendo que el primero y el ultimo saben que los son....
1 0 0 0 0 1 ---> Fila de soldados 1 para el primero y el ultimo.El ultimo dice "Disparar".
1 0 0 0 1 0 siguiente paso 1 0 0 1 0 1 siguiente 1 0 1 0 1 0 siguente 1 1 0 1 0 1 en el siguiente al ver que el estado ya esta cambiado hace el rebote... y quedaria 0 0 1 0 1 0 ...ect algo asi me referia..
Lo que es lo mismo al comunicarse con el anterior posterior cambiaria el bit con un XOR y al tener todos 1,osea 1 1 1 1 1 1 ,dispararian....me explicado mejor? de ahi que alla puesto el ejemplo de las casillas ,pisas una y cambian el valor las del alrededor pero aplicado a este problema matematico,en la cual solo le ve de utilidad para sincronizar robots,maquinas,ect no para la programación ,al menos hasta que se me muestre un buen ejemplo,creo haber leido hace tiempo algo parecido,pero para aplicaciones cuanticas,en las que para por ejemplo abrir un agujero de gusano,lanzar desde varias posiciones un rayo sincronizado, es un ejemplo heee,no creais lo que digo... :P
se entiende lo que dices, pero me parece que tampoco va por ahi... y la solucion de HackZJuan me parece que tampoco va... porque al pegar la señal la vuelta o cerca del ultimo se daria el caso de que el soldado recibe y quiere enviar y asumiria que tiene que disparar cuando los otros ni enterados...
Quote from: DjSonyk on November 13, 2009, 05:04:02 PM
Quote from: HaCkZJuaNN on November 10, 2009, 07:29:12 PM
Tienes una fila de soldados. Todos los soldados son exactamente iguales. Cada soldado puede hablar con el que tiene delante y con el que tiene detrás. Se trata de que tú en un momento dado le digas al último soldado: "Dispara", y los soldados se comuniquen unos con otros, SIGUIENDO UN ALGORITMO IGUAL EN TODOS, de forma que en un momento dado todos los soldados disparen al mismo tiempo.
Creo que en tu difinición falla algo...
En "SIGUIENDO UN ALGORITMO IGUAL EN TODOS",se supone que el primero y el ultimo se comunican con el de alante y detras con lo que algo falla,o que no he acabado de entender.
Sin llegar a comprobarlo yo creo que es parecido al tipico puzzle en que pisas una casillas y se encienden/apagan las de alrededor y seguramente con un XOR bit a bit,seria la solucion...Cuando tenga un rato lo comprobaré.
Ya dije que el primero y el último saben que lo son, así que el algoritmo es exactamente el mismo pero ese algoritmo tiene que si es el primero absoluto, se olvide de su anterior, y que si es el último absoluto se olvide de su siguiente. Pero eso está en TODOS, lo que pasa que como sólo el primero y sólo el último son primeros absolutos.
La idea de las casillas es buena, aunque no creo que funcione porque como ha dicho windgate, te hace falta un tercer estado, y tal como lo has descrito, es difícil que todos pasen a ese estado a la vez...
Quote from: SplinterGU on November 13, 2009, 11:16:28 PM
se entiende lo que dices, pero me parece que tampoco va por ahi... y la solucion de HackZJuan me parece que tampoco va... porque al pegar la señal la vuelta o cerca del ultimo se daria el caso de que el soldado recibe y quiere enviar y asumiria que tiene que disparar cuando los otros ni enterados...
Nono, mi solución funciona 99.9% seguro. Tengo que escribir el programa, creo que lo voy a escribir ahora mismo... Eso que dices no ocurre, y aunque ocurriera, la condición de disparo no es que les lleguen esas señales, sino que tanto él como su anterior como su siguiente(si tienen) sean primero o último al mismo tiempo. Voy a escribir sólo el proceso y lo voy a comprobar de otras maneras, pero no me apetece ponerme a hacer gráficos y demás ahora... Vosotros podéis ponerle gráficos a lo que ponga si os parece, pero yo voy a comprobar que funciona haciendo un say del turno para ver si todos lo hacen a la vez(deberían, y debería ser en el turno ~3n).
Por cierto, me he dado cuenta de que en realidad hacen falta 3 frames por "turno", uno para asignar las salidas, otro para recibir las entradas y otro para "pensar".
Quote from: HaCkZJuaNN on November 13, 2009, 11:35:04 PM
Por cierto, me he dado cuenta de que en realidad hacen falta 3 frames por "turno", uno para asignar las salidas, otro para recibir las entradas y otro para "pensar".
ja... no vale acomodarte los turnos a tu antojo... por que no nos das la solucion oficial o donde obtenerla... yo la verdad google y no aparece en ningun lado...
bueno, dale, adelante con ese programa... te tengo fe...
DJsonik, no sirve
Asumes que todos disparan cuando todos están a 1, pero eso implica que todos son capaces de ver el estado de todos... Para nada sirve, recuerda que sólo son capaces de mirar a izquierda y derecha.
Yo como Splinter sigo a la espera de la solución real, y reitero que es algoritmo de premio novel/nobel.
Desisto de seguir pensando, espero una solución real y soy tan cabezota que digo que no la hay :P
Que me resten karma si me equivoco :o
Soy un vago de narices y paso de subir el archivo, así que os copio aquí el código de 500 líneas y que os cunda xD
import "mod_say";
import "mod_proc";
import "mod_time";
import "mod_video";
import "mod_key";
#define N 150
global
int turno;
soldado soldado_actual;
soldado soldado_anterior;
int s_terminado[N];
int terminado_total;
int i;
end
declare process soldado(int num) //La variable num SOLAMENTE SE UTILIZA EN EL SAY PARA SABER DE QUÉ SOLDADO ESTOY HABLANDO
private
//Entradas/salidas, la versión privada que utilizan para hacer los cálculos, para que no se mezcle con la pública
int e_ultprim_i_p = 0;
int e_ultprim_d_p = 0;
int s_ultprim_i_p = 0;
int s_ultprim_d_p = 0;
int e1_i_p = 0;
int s1_d_p = 0;
int e1_d_p = 0;
int s1_i_p = 0;
int e2_i_p = 0;
int s2_d_p = 0;
int e2_d_p = 0;
int s2_i_p = 0;
//Espejo de las otras entradas/salidas(para recorrerlo en sentido inverso)
int e3_d_p = 0;
int s3_i_p = 0;
int e3_i_p = 0;
int s3_d_p = 0;
int e4_d_p = 0;
int s4_i_p = 0;
int e4_i_p = 0;
int s4_d_p = 0;
int s_se_primero_p = 0;
int s_se_ultimo_p = 0;
int e_se_primero_p = 0;
int e_se_ultimo_p = 0;
int me_hago_ultimo = 0;
int me_hago_primero = 0;
int iniciado = 0;
int reiniciado_derecha = 0;
int reiniciado_izquierda = 0;
int terminado = 0;
end
public
soldado siguiente;
soldado anterior;
//Estados
int primero_relativo = 0;
int ultimo_relativo = 0;
int primero_absoluto = 0;
int ultimo_absoluto = 0;
int e_ultprim_i_l = 0;
int e_ultprim_d_l = 0;
int s_ultprim_i_l = 0;
int s_ultprim_d_l = 0;
int e1_i_l = 0;
int s1_d_l = 0;
int e1_d_l = 0;
int s1_i_l = 0;
int e2_i_l = 0;
int s2_d_l = 0;
int e2_d_l = 0;
int s2_i_l = 0;
//Espejo de las otras entradas/salidas(para recorrerlo en sentido inverso)
int e3_d_l = 0;
int s3_i_l = 0;
int e3_i_l = 0;
int s3_d_l = 0;
int e4_d_l = 0;
int s4_i_l = 0;
int e4_i_l = 0;
int s4_d_l = 0;
int s_se_primero_l = 0;
int s_se_ultimo_l = 0;
int e_se_primero_l = 0;
int e_se_ultimo_l = 0;
end
end
begin
set_fps(30,0);
turno = 1;
for(i = 1; i <= N; i++)
s_terminado[i] = 0;
end
//Crear los soldados
//Primer soldado
soldado_actual = soldado(1);
soldado_actual.primero_absoluto = 1;
//Soldados de en medio
for(i = 2; i <= N-1; i++)
soldado_anterior = soldado_actual;
soldado_actual = soldado(i);
soldado_actual.anterior = soldado_anterior;
soldado_anterior.siguiente = soldado_actual;
end
//Último soldado
soldado_anterior = soldado_actual;
soldado_actual = soldado(N);
soldado_actual.anterior = soldado_anterior;
soldado_anterior.siguiente = soldado_actual;
soldado_actual.ultimo_absoluto = 1;
while(!terminado_total)
terminado_total = 1;
for(i = 1; i <= N and terminado_total; i++)
terminado_total*=s_terminado[i];
end
turno++;
say("***"+turno+"***");
/*while(!key(_enter))
if(key(_esc))
exit();
end
frame;
end
while(key(_enter))
frame;
end*/
frame;
frame;
frame;
frame;
end
end
process soldado(int num)
begin
//Aquí el main le dice al soldado quién es su anterior y su siguiente
frame;
e_ultprim_i_p = 0;
e_ultprim_d_p = 0;
while(!terminado)
//Frame de "pensar"
//CONDICIÓN DE DISPARO
if((primero_relativo or ultimo_relativo) and (e_ultprim_i_p or primero_absoluto) and (e_ultprim_d_p or ultimo_absoluto))
say("Soldado "+num+": Disparo en turno = "+turno+",tiempo = "+get_timer());
terminado = 1;
end
if(ultimo_absoluto) ultimo_relativo = 1; end
if(primero_absoluto) primero_relativo = 1; end
if(e_se_primero_p)
primero_relativo = 1;
end
if(e_se_ultimo_p)
ultimo_relativo = 1;
end
if(me_hago_primero)
primero_relativo = 1;
me_hago_primero = 0;
end
if(me_hago_ultimo)
ultimo_relativo = 1;
me_hago_ultimo = 0;
end
if(!iniciado and primero_absoluto) //Si es el primero y aún no ha iniciado, inicia, disparador del algoritmo...
s1_d_p = 1;
s2_d_p = 1;
iniciado = 1;
end
//Si acaba de convertirse en un primero relativo manda señal hacia la derecha
if(primero_relativo and !reiniciado_derecha and !primero_absoluto)
s1_d_p = 1;
s2_d_p = 1;
reiniciado_derecha = 1;
end
//Si acaba de convertirse en un último relativo manda señal hacia la izquierda(señal invertida)
if(ultimo_relativo and !reiniciado_izquierda and !ultimo_absoluto)
s3_i_p = 1;
s4_i_p = 1;
reiniciado_izquierda = 1;
end
//"Pasar" las señales
if(e1_i_p == 1)
if(ultimo_relativo)
s1_i_p = -1;
else
s1_d_p = 1;
end
end
if(e1_d_p == -1 and e2_i_p == 0)
s1_i_p = -1;
end
if(e2_i_p == 1 and e1_d_p == 0)
s2_i_p = -1;
end
if(e2_d_p == -1)
s2_d_p = 2;
end
if(e2_i_p == 2 and e1_d_p == 0)
s2_d_p = 1;
end
//Uno de en medio
//Son impares
if(e1_d_p == -1 and e2_i_p == 2)
primero_relativo = 1;
ultimo_relativo = 1;
end
//Son pares
if(e1_d_p == -1 and e2_i_p == 1)
me_hago_primero = 1;
s_se_ultimo_p = 1;
end
//Entradas "al revés"
if(e3_d_p == 1)
if(primero_relativo)
s3_d_p = -1;
else
s3_i_p = 1;
end
end
if(e3_i_p == -1 and e4_d_p == 0)
s3_d_p = -1;
end
if(e4_d_p == 1 and e3_i_p == 0)
s4_d_p = -1;
end
if(e4_i_p == -1)
s4_i_p = 2;
end
if(e4_d_p == 2 and e1_i_p == 0)
s4_i_p = 1;
end
//Uno de en medio
//Son impares
if(e3_i_p == -1 and e4_d_p == 2)
primero_relativo = 1;
ultimo_relativo = 1;
end
//Son pares
if(e3_i_p == -1 and e4_d_p == 1)
me_hago_ultimo = 1;
s_se_primero_p = 1;
end
//Decirle a los de los lados si es primero o último
if(primero_relativo)
s_ultprim_i_p = 1;
s_ultprim_d_p = 1;
end
if(ultimo_relativo)
s_ultprim_i_p = 1;
s_ultprim_d_p = 1;
end
/////////////////////////////////////////////////////////////
frame;
/////////////////////////////////////////////////////////////
//Frame de asignar salidas
s1_i_l = s1_i_p;
s1_d_l = s1_d_p;
s2_i_l = s2_i_p;
s2_d_l = s2_d_p;
s3_i_l = s3_i_p;
s3_d_l = s3_d_p;
s4_i_l = s4_i_p;
s4_d_l = s4_d_p;
s_ultprim_i_l = s_ultprim_i_p;
s_ultprim_d_l = s_ultprim_d_p;
s_se_primero_l = s_se_primero_p;
s_se_ultimo_l = s_se_ultimo_p;
s1_i_p = 0;
s1_d_p = 0;
s2_i_p = 0;
s2_d_p = 0;
s3_i_p = 0;
s3_d_p = 0;
s4_i_p = 0;
s4_d_p = 0;
s_ultprim_i_p = 0;
s_ultprim_d_p = 0;
s_se_primero_p = 0;
s_se_ultimo_p = 0;
///////////////////////////////////////////////////////////////
frame;
///////////////////////////////////////////////////////////////
//Frame de asignar entradas a salidas
if(!primero_absoluto)
e1_i_l = anterior.s1_d_l;
e2_i_l = anterior.s2_d_l;
e3_i_l = anterior.s3_d_l;
e4_i_l = anterior.s4_d_l;
e_ultprim_i_l = anterior.s_ultprim_d_l;
e_se_primero_l = anterior.s_se_primero_l;
end
if(!ultimo_absoluto)
e1_d_l = siguiente.s1_i_l;
e2_d_l = siguiente.s2_i_l;
e3_d_l = siguiente.s3_i_l;
e4_d_l = siguiente.s4_i_l;
e_ultprim_d_l = siguiente.s_ultprim_i_l;
e_se_ultimo_l = siguiente.s_se_ultimo_l;
end
/*say(num+":");
say(" Pr:"+primero_relativo+",Ult:"+ultimo_relativo);
say(" e1_i_l:"+e1_i_l);
say(" e1_d_l:"+e1_d_l);
say(" e2_i_l:"+e2_i_l);
say(" e2_d_l:"+e2_d_l);
say(" e3_i_l:"+e3_i_l);
say(" e3_d_l:"+e3_d_l);
say(" e4_i_l:"+e4_i_l);
say(" e4_d_l:"+e4_d_l);
say(" s1_i_l:"+s1_i_l);
say(" s1_d_l:"+s1_d_l);
say(" s2_i_l:"+s2_i_l);
say(" s2_d_l:"+s2_d_l);
say(" s3_i_l:"+s3_i_l);
say(" s3_d_l:"+s3_d_l);
say(" s4_i_l:"+s4_i_l);
say(" s4_d_l:"+s4_d_l);
say(" e_ultprim_i_l:"+e_ultprim_i_l);
say(" e_ultprim_d_l:"+e_ultprim_d_l);
say(" s_ultprim_i_l:"+s_ultprim_i_l);
say(" s_ultprim_d_l:"+s_ultprim_d_l);*/
////////////////////////////////////////////////////////////////
frame;
////////////////////////////////////////////////////////////////
//Frame de asignar entradas
e1_i_p = e1_i_l;
e1_d_p = e1_d_l;
e2_i_p = e2_i_l;
e2_d_p = e2_d_l;
e3_i_p = e3_i_l;
e3_d_p = e3_d_l;
e4_i_p = e4_i_l;
e4_d_p = e4_d_l;
e_ultprim_i_p = e_ultprim_i_l;
e_ultprim_d_p = e_ultprim_d_l;
e_se_primero_p = e_se_primero_l;
e_se_ultimo_p = e_se_ultimo_l;
e1_i_l = 0;
e1_d_l = 0;
e2_i_l = 0;
e2_d_l = 0;
e3_i_l = 0;
e3_d_l = 0;
e4_i_l = 0;
e4_d_l = 0;
e_ultprim_i_l = 0;
e_ultprim_d_l = 0;
e_se_primero_l = 0;
e_se_ultimo_l = 0;
frame;
/*while(!key(_enter))
frame;
end
while(key(_enter))
frame;
end*/
end
s_terminado[num] = 1;
end
Funciona perfectamente EXCEPTO cuando el número de soldados es un múltiplo de 8 más 1 o más 2, excepto el 9 y el 10. Esto es, a mi me ha fallado en 17, 18, 25, 26, 33, 34. Son las 2:30 y no tengo ninguna gana de ver por qué falla en eso ahora mismo... llevo dos horas con esto... parece que el segundo no se coordina con los demás, y luego eso causa catástrofes varias. De todas formas, estoy 99% seguro de que el fallo está en la implementación en bennu y no en el propio algoritmo teórico...
En cualquier caso, si probáis para valores que no sean múltiplos de 8 más 1 o más 2, funciona perfectamente, también podéis probar para valores muy altos y asombraros ;). Yo he probado hasta para 250 y disparan todos en el turno 744 ;) Como véis, no siempre tarda 3n, pero cuanto mayor es el número de soldados, más se aproxima el número de turnos a 3n.
Por cierto splinter, lo de subdividir los turnos es por loos problemillas del propio bennu de que los procesos se ejecutan uno detrás de el otro, pero cada turno es cada turno, únicamente lo divido en 4 frames para poder primmero calcular, luego asignar salidas, asignar entradas a salidas y asignar entradas.
A ver si os lo creéis de una vez...
PS: El archivo no tiene gráficos ni nada... Simplemente copiad y pegad en un .prg, compilad y ejecutad. Debería funcionar. Pero tenéis que ver la salida por say(), ahí es donde está el tema.
Cagonlaleche, yo ya lo pruebo mañana que es tarde y tengo novia, has tocado la moral de más de uno con este tema xD
Acepto el Karma-- si es correcto.
...Y el karma++ para tí lo contrarrestará, por supuesto.
PD: Eso del say me tira para atrás pero vale, bueno :P
PD2: Si tiene que haber karma-- en este foro que sea para mí, por incrédulo
Quote from: Windgate on November 14, 2009, 01:42:56 AM
Cagonlaleche, yo ya lo pruebo mañana que es tarde y tengo novia, has tocado la moral de más de uno con este tema xD
Acepto el Karma-- si es correcto.
...Y el karma++ para tí lo contrarrestará, por supuesto.
PD: Eso del say me tira para atrás pero vale, bueno :P
PD2: Si tiene que haber karma-- en este foro que sea para mí, por incrédulo
Los says están puestos. Sólo digo que os fijéis en ellos.
No tenéis que poner los says vosotros, están puestos :)
tiene que funcionar 100% en todos los casos... por otro lado, si la señal es 1 sola (caso inicial) solo vale 1 comunicacion por frame entre todos los soldados... se supone que el frame es un instante, no una secuencia de instantes... con esto quiero decir... que no es valido que en un frame, se pase la señal desde el soldado 1 hasta el ultimo... si el algoritmo hace eso esta mal... o sea, el objeto es señal/aviso/orden... cada 1 de estos objetos debe pasar solo a 1 soldado en cada frame... si lo hiciste asi, y funciona entonces esta bien... ahora si tu objeto pasa a mas de 1 soldado por frame no vale...
si tenes mas de 1 señal/objeto/orden circulando por la fila de soldados, entonces ahi pueden haber mas de 1 soldado afectado a la vez, pero solo 1 objeto por soldado por frame... si no es asi, no vale, estas haciendo trampas...
Quote from: SplinterGU on November 14, 2009, 02:41:07 AM
tiene que funcionar 100% en todos los casos... por otro lado, si la señal es 1 sola (caso inicial) solo vale 1 comunicacion por frame entre todos los soldados... se supone que el frame es un instante, no una secuencia de instantes... con esto quiero decir... que no es valido que en un frame, se pase la señal desde el soldado 1 hasta el ultimo... si el algoritmo hace eso esta mal... o sea, el objeto es señal/aviso/orden... cada 1 de estos objetos debe pasar solo a 1 soldado en cada frame... si lo hiciste asi, y funciona entonces esta bien... ahora si tu objeto pasa a mas de 1 soldado por frame no vale...
si tenes mas de 1 señal/objeto/orden circulando por la fila de soldados, entonces ahi pueden haber mas de 1 soldado afectado a la vez, pero solo 1 objeto por soldado por frame... si no es asi, no vale, estas haciendo trampas...
Mira el código o lee la explicación, cada señal solo pasa de un soldado a otro cada frame, el tema es, como dices, que a part de cierto punto la señal se va duplicando hasta que está en todos los soldados a la vez...
La señal no pasa del 1 al último en un frame, sino en N turnos(que por problemas de bennu son 4N frames, pero eso es sólo por la forma de funcionar de bennu).
Y puede haber varias señales en el mismo soldado, ya que como dije, varias entradas/salidas se pueden codificar como una sola muy fácilmente. No hay una diferencia cualitativa entre tener 1 señal por soldado y un número finito determinado no dependiente del número de soldados de señales por soldado.
Lo he probado y sólo veo que cuenta y cuenta, es como un:
LOOP
say ( x++ );
END
Llega a 250 y sigue, pero hay 150 soldados, mi no entendel ???
Pobre Hackzjuan, que no nos creemos que haya solución, qué malos que somos ;D
EDIT: Vale, ya ha terminado, veo que todos tienen el mismo turno, pero al lado sale el tiempo y hay 6 valores distintos... Al menos pone el mismo turno eso sí... Ah, vale, el tiempo ese es un timer, ok.
EDIT 2: Veo el código y veo la lógica, pero hay algo que no me convence, los soldados se comunican uno a uno, no va en paralelo, por tanto en una de las comunicaciones el último soldado podría dar a toda la fila la orden de disparar, la orden recorre la fila y en el siguiente FRAME disparan, vamos, que no me termina de convencer la solución (No estoy diciendo que esté mal, pero no me convence). ¿No hay algún link donde alguien explique el problema lujosamente con dibujos y cosas así? Es que soy un poco retarded y aquí no es que nos expliquemos muy bien en general :)
EDIT 3: Cagondio, ahora con 200 soldados me da error de ejecución y me terminan en turnos distintos algunos antes de reventar.
EDIT 4: Hay 8 variables privadas por soldado, suficientes para codificar el número de soldado hasta 256, tendría que funcionar para números mayores que 256 con el mismo número de variables.
Qué cabrón que soy, no te enfades Hackzjuan, no es que sea incrédulo, simplemente le estoy dando vueltas a tu "problemita interesante", está peludo xD
Quote from: Windgate on November 14, 2009, 12:05:40 PM
Lo he probado y sólo veo que cuenta y cuenta, es como un:
LOOP
say ( x++ );
END
Llega a 250 y sigue, pero hay 150 soldados, mi no entendel ???
Pobre Hackzjuan, que no nos creemos que haya solución, qué malos que somos ;D
EDIT: Vale, ya ha terminado, veo que todos tienen el mismo turno, pero al lado sale el tiempo y hay 6 valores distintos... Al menos pone el mismo turno eso sí... Ah, vale, el tiempo ese es un timer, ok.
EDIT 2: Veo el código y veo la lógica, pero hay algo que no me convence, los soldados se comunican uno a uno, no va en paralelo, por tanto en una de las comunicaciones el último soldado podría dar a toda la fila la orden de disparar, la orden recorre la fila y en el siguiente FRAME disparan, vamos, que no me termina de convencer la solución (No estoy diciendo que esté mal, pero no me convence). ¿No hay algún link donde alguien explique el problema lujosamente con dibujos y cosas así? Es que soy un poco retarded y aquí no es que nos expliquemos muy bien en general :)
EDIT 3: Cagondio, ahora con 200 soldados me da error de ejecución y me terminan en turnos distintos algunos antes de reventar.
EDIT 4: Hay 8 variables privadas por soldado, suficientes para codificar el número de soldado hasta 256, tendría que funcionar para números mayores que 256 con el mismo número de variables.
Qué cabrón que soy, no te enfades Hackzjuan, no es que sea incrédulo, simplemente le estoy dando vueltas a tu "problemita interesante", está peludo xD
Tengo que probar lo del 200. 200 es propiamente múltiplo de 8 así que debería funcionar...
Respecto a lo de que se comunique uno con todos, por eso divido en 4 frames y si te fijas las variables las tengo duplicadas, privadas y locales. Así estoy seguro de que se respeta eso. En la fase de "pensar" los soldados ÚNICA Y EXCLUSIVAMENTE UTILIZAN LAS VERSIONES PRIVADAS DE LAS VARIABLES. En la siguiente fase, cada soldado asigna cada salida privada a su versión pública, Y HAY UN FRAME JUSTAMENTE DESPUÉS DE ESTO, ASÍ QUE HASTA QUE NO TERMINAN DE HACER ESTO TODOS LOS SOLDADOS NO CONTINÚA. En la siguiente fase, cada soldado copia las salidas de los de sus lados en sus entradas, pero durante esta fase esas variables NO SE MODIFICAN, únicamente se asignan de uno a otro. Por último, en la última fase del turno, los soldados copian sus entradas públicas sobre sus entradas privadas, para poder trabajar con ellas. De este modo, si no te das cuenta, no hay posibilidad de que ocurra eso que dices, ya que siempre me aseguro de que todos los soldados hayan acabado con cada parte antes de empezar a mezclar las cosas.
Hay una ristra enorme de says comentada por ahí con todas las entradas/salidas. Descomentadla y descomentad también la parte del "while(!key(_enter)), etc..."(que está tanto en el main como en el proceso soldado, hay que descomentarlo 2 veces). Así es como lo debugeé y así podéis ver turno a turno que es lo que va haciendo cada soldado. Hasta que no le dáis a enter no pasa al siguiente turno. Así a lo mejor os queda más claro cómo funciona el algoritmo.
Efectivamente con 200 también peta, que raro... pero estoy del todo seguro de que tiene que ser un problema al escribirlo. Intentad entender la lógica del algoritmo y daros cuenta de que no hay lugar a fallo. No me apetece nada ponerme a rebuscar donde está el fallo en el programa. Si tuviera una pizarra os lo explicaría con dibujitos, pero me da pereza hacer los dibujitos en paint...
Estoy probando con 1000 para dejarte contento... pero fíjate en el código del procesos soldado y date cuenta de que EN NINGÚN MOMENTO UTILIZA LA CONSTANTE N DENTRO DEL CÓDIGO, y los únicos momentos en los que utiliza la variable num es para imprimir los resultados y para conseguir que el programa termine cuando ya hayan disparado, en cualquier otro momento, prescinde totalmente de esto y únicamente se comunica con su siguiente y con su anterior.
Quote from: Windgate on November 14, 2009, 12:05:40 PM
Lo he probado y sólo veo que cuenta y cuenta, es como un:
LOOP
say ( x++ );
END
Llega a 250 y sigue, pero hay 150 soldados, mi no entendel ???
Espero que hayas entendido que eso es porque si hay 150, deberá acabar más o menos en el 450... 3n.
Probé con 1000 y tras casi 10 minutos en el turno 2992 dispararon los 1000 a la vez.
He probado el caso 17 a mano y funciona perfectamente, hay algún problema en el código con este caso, y eso afecta a todos los demás múltiplos de 8 más 1 o más 2. Pero como ya he dicho, no tengo ninguuuuuuuna gana de arreglarlo.
el codigo es bastante largo como para con solo verlo leer claramente lo que quisiste hacer (o realmente no le dedique tiempo) ... no entiendo por que decis que se necesitan varias entradas y salidas por soldado, deberia haber 1 sola entrada y 1 sola salida por soldado, y lo de 4 frames no entiendo porque, deberia ser 1 solo frame... por que dice wind que hay un "x++" ? no es que los soldados no cuentan? (aclaro que no mire el codigo, demasiado largo)
si la solucion es correcta matematicamente debe funcionar en todos los casos, si no funciona y necesita parches para casos especificos, entonces a mi entender no es una solucion matematica...
por favor, no te lo tomes a mal, sabemos todos que eres un crack en las matematicas, pero danos la solucion real, publicada y oficial...
ja! ya veo lo que hace... eso es totalmente trucho... asi no vale... ahora veo por que los 4 frames... no, esa solucion no sirve... la idea no es que cada 4 frames chequees si todos terminaron... ademas 4 frames te da tiempo que los soldados coincidan en 4 instancias de tiempo diferente... es como decir... disparen todos a la vez, pero la vez significa rangos de 4 horas...
perdon, pero la solucion asi no es solucion...
Quote from: SplinterGU on November 14, 2009, 02:48:42 PM
ja! ya veo lo que hace... eso es totalmente trucho... asi no vale... ahora veo por que los 4 frames... no, esa solucion no sirve... la idea no es que cada 4 frames chequees si todos terminaron... ademas 4 frames te da tiempo que los soldados coincidan en 4 instancias de tiempo diferente... es como decir... disparen todos a la vez, pero la vez significa rangos de 4 horas...
perdon, pero la solucion asi no es solucion...
Splinter, empiezo a pensar seriamente que tienes algo en contra mío.
Lo de comprobar si ha terminado es para que el programa no siga corriendo eternamente. Quítalo y siguen disparando todos al mismo tiempo, solo que el programa sigue corriendo después de que hayan disparado.
Los 4 frames, como ya te he explicado 50 veces, son para que las entradas no se solapen con las salidas en el mismo turno. Es por el funcionamiento de bennu, si bennu fuera totalmente sincronizado(todos los procesos corrieran exactamente a la vez y las entradas y salidas fueran actualizadas únicamente al final de los turnos), no haría falta. Y todos terminan en la misma instancia de tiempo, porque el if de la condición de disparo está en el mismo sitio.
Lo del x++ es porque es la impresión que le dio cuando lo ejecutó. Hay un turno++ que sirve para contar los turnos y ver en qué turno disparan, pero eso es meramente para ver las entradas y salidas y comprobar que disparan a la vez, quítalo y seguirán disparando al mismo tiempo, excepto que no sabrás en qué turno es.
La solución es correcta, ahora mismo estoy 100% seguro, funciona en todos los casos, no necesita parches para casos específicos, no tiene ninguno. Ahora mismo falla en algunos casos muy concretos POR UN ERROR EN EL CÓDIGO ESCRITO EN BENNU, que no tengo ninguna gana de buscar porque parece sumamente complicado de encontrar, pero he probado esos casos que fallan haciendo el algoritmo manualmente y funciona perfectamente.
No hay una "solución real". Hay una "solución ÓPTIMA", que no me sé pero que utiliza funciones matemáticas y cosas de modo que en realidad no da el algoritmo, sino demuestra que se puede obtener un algoritmo que haga eso en 2n-2.
No sé si lo sabes pero en matemáticas incontables veces se puede demostrar que algo que cumple unas determinadas propiedades existe sin encontrarlo explícitamente. Creo que eso es lo que ocurre en este caso, la solución 2n-2 se demuestra que es posible obtenerla y que es la óptima, pero no se conoce realmente(al menos eso es lo que tengo entendido).
Por favor splinter, puedes dejar de tratar de demostrar que me equivoco??? Si no te apetece, no entiendas la solución, pero entonces no intentes demostrar que está mal sin entenderla... La solución se la comenté a un profesor de mi universidad dedicado a este tipo de temas y me dijo que era perfectamente correcta, pero que, obviamente, no era la mejor. Si tuviera una pizarra y estuviera en persona creo que sería bastante más fácil explicarosla, pero la solución estar está bien.
Hombre yo no creo que Splinter tenga nada contra ti,y tampoco intenta demostrar que te equivocas,solo que no le convence o no le parece la solución correcta,aun asi yo he mirado por ahi en google y no sale nada respecto al problema del peloton aun asi si que he visto salidas/entradas de maquinas infinitas con muchas ecuacciones que no creo que sean la solución pero pienso que si realmente no existe la solicion real puede que pase como le paso a Arquitas de Tarento que trato de solucinar el problema de la duplicación del cubo : " Dado un cubo de arista conocida¿se puede multiplicar a esta por alguna fracción ,de modo que el volumen del cubo se duplique?" ,la respuesta hoy es evidente ,NO....Hay cosas que no se pueden conseguir ,aunque si como dices hay una optima ahora me pica la curiosidad de conocerla.....De todas formas me huele a una operación matematica-cientifica ,y como sabemos los cientificos ,primero plantean una teoria y luego intentan demostrarla,y hasta que no se demuestre..... pues eso.
No HackzJuan, que no tenemos nada en contra tuyo hombre, es que estamos incrédulos ante semejante problema tranki ;)
Tú defiende tu postura ante Splinter que es muy "cabezota", a mí me ha quitado la razón miles de veces 8) pero no te enfades :P
Yo sigo pidiendo un link de wikipedia o similar, porque el código es complejo de entender... Mucho
Quote from: DjSonyk on November 14, 2009, 04:54:47 PM
Hombre yo no creo que Splinter tenga nada contra ti,y tampoco intenta demostrar que te equivocas,solo que no le convence o no le parece la solución correcta,aun asi yo he mirado por ahi en google y no sale nada respecto al problema del peloton aun asi si que he visto salidas/entradas de maquinas infinitas con muchas ecuacciones que no creo que sean la solución pero pienso que si realmente no existe la solicion real puede que pase como le paso a Arquitas de Tarento que trato de solucinar el problema de la duplicación del cubo : " Dado un cubo de arista conocida¿se puede multiplicar a esta por alguna fracción ,de modo que el volumen del cubo se duplique?" ,la respuesta hoy es evidente ,NO....Hay cosas que no se pueden conseguir ,aunque si como dices hay una optima ahora me pica la curiosidad de conocerla.....De todas formas me huele a una operación matematica-cientifica ,y como sabemos los cientificos ,primero plantean una teoria y luego intentan demostrarla,y hasta que no se demuestre..... pues eso.
Ya he dicho que el problema está demostrado que existe una solución 2n-2 y está demostrado que es imposible encontrar una mejor(demostración matemática). Yo no conozco la solución, y me suena que la solución no se conoce, aunque se sabe que existe. Algo así. Como ya dije, matemáticamente es posible probar la existencia de algo sin conocerlo.
Quote from: Windgate on November 14, 2009, 04:57:48 PM
No HackzJuan, que no tenemos nada en contra tuyo hombre, es que estamos incrédulos ante semejante problema tranki ;)
Tú defiende tu postura ante Splinter que es muy "cabezota", a mí me ha quitado la razón miles de veces 8) pero no te enfades :P
Yo sigo pidiendo un link de wikipedia o similar, porque el código es complejo de entender... Mucho
Lo he buscado pero no encuentro nada.
A ver, dandole mucho al coco no hay forma de hacerlo sin que los soldados no tengan espacio para guardar el número de soldados que hay. A ver:
Una solucion: mandas una variable a 0 al último soldado, este la manda incrementada en 1 al siguiente, así uno a uno hasta el primero, este primero cuando la recibe la incrementa en uno y ya conoce el número exacto de soldados (N) y ahora inicia un contador para disparar después de N saltos, y manda N-1 al siguiente soldado, este iniciará un contador para disparar justo después de la variable pasada de saltos N-1, y la decrementa y la pasa al siguiente así hasta el último que recibirá un 0 y al siguiente golpe de reloj disparará y coinicidirá con todos para disparar.
Claro esta solucion supone que puedes guardar el número de soldados en una variable, así que si tienes una variable de 16 bits no podrás tener más de 65535 soldados, se produciría oveflow,
También supones que los soldados pueden decrementar en cada golpe de reloj una variable internta.
Quote from: DCelso on November 14, 2009, 05:43:00 PM
También supones que los soldados pueden decrementar en cada golpe de reloj una variable internta.
Eso se puede hacer, lo otro no.
Otra forma, todos los soldados tienen una variable, cuando ordendes disparar al último, manda su id cuo, y lo va pasando uno a uno encolando su id, cuando el primero reciba todos los ids, este empieza a mandar por otro lado uno a uno los ids encolados, cuando todas las variables de todos los soldados tengan su id igual a la variable disparan, mientras que el primero disparará cuando se vacíe su cola.
si se hizo bien todos los soldados deben recibir su id a la vez ya que lo encolaron en orden en la primera vuelta.
Esta solucion presupone que puedes mandar una variable de tipo cola (o lista) y que el primer soldado es un poco especial y sabe repartir ids los ids.
Tambien presupones que puedes tener variables capaces de guardar ids únicos.
Quote from: HaCkZJuaNN on November 14, 2009, 05:48:07 PM
Quote from: DCelso on November 14, 2009, 05:43:00 PM
También supones que los soldados pueden decrementar en cada golpe de reloj una variable internta.
Eso se puede hacer, lo otro no.
Entonces es imposible, casi 100%
Por eso dije que faltan datos al enunciado.
Quote from: HaCkZJuaNN on November 14, 2009, 03:58:44 PM
Quote from: SplinterGU on November 14, 2009, 02:48:42 PM
ja! ya veo lo que hace... eso es totalmente trucho... asi no vale... ahora veo por que los 4 frames... no, esa solucion no sirve... la idea no es que cada 4 frames chequees si todos terminaron... ademas 4 frames te da tiempo que los soldados coincidan en 4 instancias de tiempo diferente... es como decir... disparen todos a la vez, pero la vez significa rangos de 4 horas...
perdon, pero la solucion asi no es solucion...
Splinter, empiezo a pensar seriamente que tienes algo en contra mío.
Lo de comprobar si ha terminado es para que el programa no siga corriendo eternamente. Quítalo y siguen disparando todos al mismo tiempo, solo que el programa sigue corriendo después de que hayan disparado.
Los 4 frames, como ya te he explicado 50 veces, son para que las entradas no se solapen con las salidas en el mismo turno. Es por el funcionamiento de bennu, si bennu fuera totalmente sincronizado(todos los procesos corrieran exactamente a la vez y las entradas y salidas fueran actualizadas únicamente al final de los turnos), no haría falta. Y todos terminan en la misma instancia de tiempo, porque el if de la condición de disparo está en el mismo sitio.
Lo del x++ es porque es la impresión que le dio cuando lo ejecutó. Hay un turno++ que sirve para contar los turnos y ver en qué turno disparan, pero eso es meramente para ver las entradas y salidas y comprobar que disparan a la vez, quítalo y seguirán disparando al mismo tiempo, excepto que no sabrás en qué turno es.
La solución es correcta, ahora mismo estoy 100% seguro, funciona en todos los casos, no necesita parches para casos específicos, no tiene ninguno. Ahora mismo falla en algunos casos muy concretos POR UN ERROR EN EL CÓDIGO ESCRITO EN BENNU, que no tengo ninguna gana de buscar porque parece sumamente complicado de encontrar, pero he probado esos casos que fallan haciendo el algoritmo manualmente y funciona perfectamente.
No hay una "solución real". Hay una "solución ÓPTIMA", que no me sé pero que utiliza funciones matemáticas y cosas de modo que en realidad no da el algoritmo, sino demuestra que se puede obtener un algoritmo que haga eso en 2n-2.
No sé si lo sabes pero en matemáticas incontables veces se puede demostrar que algo que cumple unas determinadas propiedades existe sin encontrarlo explícitamente. Creo que eso es lo que ocurre en este caso, la solución 2n-2 se demuestra que es posible obtenerla y que es la óptima, pero no se conoce realmente(al menos eso es lo que tengo entendido).
Por favor splinter, puedes dejar de tratar de demostrar que me equivoco??? Si no te apetece, no entiendas la solución, pero entonces no intentes demostrar que está mal sin entenderla... La solución se la comenté a un profesor de mi universidad dedicado a este tipo de temas y me dijo que era perfectamente correcta, pero que, obviamente, no era la mejor. Si tuviera una pizarra y estuviera en persona creo que sería bastante más fácil explicarosla, pero la solución estar está bien.
si no podes suministrar ese lugar que dijiste existia donde daban la solucion real, entonces no importa... a mi no me convence... pero como te lo tomas como algo personal paso ya de opinar... pero quiero aclarar que no estoy intentando demostrar que te equivocas, sino estoy diciendo que la solucion inventando frames de 4, o comos sea, segun se acomode a tu realidad a mi no me convence para nada... solo eso, desde ahora paso de opinar sobre este tema... felicitaciones pues por tu solucion... si a ti te convence y tu ego esta satisfecho al escuchar que tienes la razon, te lo digo y ya "tienes la razon, es la solucion perfecta, sos un crack..." me alegro...
saludos... pasemos a otros temas que no se sepanos no puedan transformarse en algo personal...
Quote from: HaCkZJuaNN on November 14, 2009, 05:48:07 PM
Quote from: DCelso on November 14, 2009, 05:43:00 PM
También supones que los soldados pueden decrementar en cada golpe de reloj una variable internta.
Eso se puede hacer, lo otro no.
puf, si bien dije que no iba a opinar, esta es la misma solucion que dio windgate y que di yo... y tu has dicho que eso no servia... ahora si sirve... puf, evidentemente hay algo personal pero es algo personal de tu parte... vamos hombre...
y ahora dices que no se conoce solucion? post atras habias dicho que existia una solucion matematica... no es que uno se tome las cosas personales, pero no puedes tirar algo asi, nos haces perder tiempo, y luego dices que no se conoce solucion...
ahora si paso de opinar...
Yo por mi parte he intentado hacer todo lo posible por resolverlo, pero ya te digo, algo falla en el enunciado, o el profesor busca que os comais el coco para ver los motivos por los que no se puede resolver, o no lo entiendo.
Yo extrapolaría mis dos posibles soluciones al profesor o quien propusiera el ejemplo a ver en que dicen que fallan, porque la única forma de sincronizar un sistema es poder identificar de forma única a cada soldado, eso es un id, y el id más pequeño y óptimo sería un número de 0 al número de soldados, así que si no podemos guardar el número de soldados la llevamos clara, otra cosa sería poder introducir un mismo dato a todos a la vez.
Matemáticamente habrá algún método que demuestre que hay solución, pero al fin y al cabo no somos matemáticos... Supongo que habréis leído algo sobre los problemas NP-Completos, hay algoritmos sobre los que matemáticamente se puede conjeturar, pero la parte de programación queda pendiente...
Haya paz amiguitos, estamos discutiendo como en un verdadero foro ;D pero no nos enfademos ni pensemos que es algo personal demostrar que hay o que no hay solución, al fin y al cabo son matemáticas, y nosotros somos programadores.
(Y al fin y al cabo hace décadas que la capacidad de representación no es un problema)
Es como si nos pusiésemos a discutir sobre la política en el siglo pasado xDDD
Pues eso, paz amiguitos :-*
A ver, yo por mi parte quiero ver la solución, matemática o programada para ver cual es el truco, porque tiene que haberlo.
A mi me suena esto al típico error de demostración de que (2 = 3) dos es igual a tres donde en el proceso de demotración te das cuenta que hacen una reducción "relativamente falsa" y es la que conlleva al resultado final :D.
Quote from: DCelso on November 14, 2009, 05:52:19 PM
Otra forma, todos los soldados tienen una variable, cuando ordendes disparar al último, manda su id cuo, y lo va pasando uno a uno encolando su id, cuando el primero reciba todos los ids, este empieza a mandar por otro lado uno a uno los ids encolados, cuando todas las variables de todos los soldados tengan su id igual a la variable disparan, mientras que el primero disparará cuando se vacíe su cola.
si se hizo bien todos los soldados deben recibir su id a la vez ya que lo encolaron en orden en la primera vuelta.
Esta solucion presupone que puedes mandar una variable de tipo cola (o lista) y que el primer soldado es un poco especial y sabe repartir ids los ids.
Tambien presupones que puedes tener variables capaces de guardar ids únicos.
Eso es igual que lo de contar, si tienes N soldados, necesitas al menos N ids únicos, y los soldados no saben contar hasta cualquier N.
Pero sí se puede hacer, y de hecho le he hecho, porque no leéis mi explicación??? No es demasiado complicada. Lo único que hago es irlos dividiendo por la mitad con un sistema que me permite saber cuál es el de en medio sin saber cuántos son.
QuoteLo único que hago es irlos dividiendo por la mitad con un sistema que me permite saber cuál es el de en medio sin saber cuántos son.
Oh, es un aporte al algoritmo.
En cualquier caso, conocer el del medio no es ninguna ventaja a priori... Conocer el del centro puede servir para lanzar una orden a izquierda y derecha para que todos disparen, pero si hay "retraso" para esa orden no funcionaría.
Lo que dije al principio, resolver el problema es conseguir que la carambola de valores X valga 1 para todos al mismo tiempo.
Ahora recuerdo, un coste del tipo 2N-2 es coste lineal... Mucho pedir para este problema... Un coste 2^N exponencial me lo podría creer, pero apuesto por un coste exponencial N!... El límite de representación es un handicap enooorme.
No he podido encontrar nada en Google, lo que está claro es que debe ser un problema de sincronización, de la rama de sistemas operativos.
Quote from: Windgate on November 14, 2009, 08:51:29 PM
QuoteLo único que hago es irlos dividiendo por la mitad con un sistema que me permite saber cuál es el de en medio sin saber cuántos son.
Oh, es un aporte al algoritmo.
En cualquier caso, conocer el del medio no es ninguna ventaja a priori... Conocer el del centro puede servir para lanzar una orden a izquierda y derecha para que todos disparen, pero si hay "retraso" para esa orden no funcionaría.
Lo que dije al principio, resolver el problema es conseguir que la carambola de valores X valga 1 para todos al mismo tiempo.
Ahora recuerdo, un coste del tipo 2N-2 es coste lineal... Mucho pedir para este problema... Un coste 2^N exponencial me lo podría creer, pero apuesto por un coste exponencial N!... El límite de representación es un handicap enooorme.
No he podido encontrar nada en Google, lo que está claro es que debe ser un problema de sincronización, de la rama de sistemas operativos.
Joder es que no os lo creéis. Ya he explicado mi algoritmo de 2 maneras y lo he implementado y aún no os lo creéis. Mi algoritmo es 3N, lineal también, y funciona.
Lo que hago es dividirlos por la mitad, y entonces el del centro manda una señal para los dos lados como has dicho tú, pero claro, yo puedo volver a dividir por la mitad las dos mitades, y luego dividir por la mitad los cuatro cuartos, y así sucesivamente hasta que están de 1 en 1 y entonces disparan. En eso es en lo que se basa mi algoritmo. Tiene un sistema para que cuando sean impares funcione de una manera y cuando sean pares de otra(cada división que hace), y esto lo sabe por la señal que le llega, si son impares es una y si son pares otra... por la manera en que funciona el algoritmo. De este modo los divido y divido hasta que están todos separados, que ocurre en todos al mismo tiempo.
Te creo.
Aunque todavia no he leido el problema ni las soluciones en condiciones para saber de que va en su totalidad ;D
QuoteLo que hago es dividirlos por la mitad, y entonces el del centro manda una señal para los dos lados como has dicho tú, pero claro, yo puedo volver a dividir por la mitad las dos mitades, y luego dividir por la mitad los cuatro cuartos, y así sucesivamente hasta que están de 1 en 1 y entonces disparan. En eso es en lo que se basa mi algoritmo. Tiene un sistema para que cuando sean impares funcione de una manera y cuando sean pares de otra(cada división que hace), y esto lo sabe por la señal que le llega, si son impares es una y si son pares otra... por la manera en que funciona el algoritmo. De este modo los divido y divido hasta que están todos separados, que ocurre en todos al mismo tiempo.
Entiendo la idea, eso sería una solución, lo que no entiendo es cómo son capaces de detectar varios soldados que son "centros" de esa división. Pero ciertamente me huele bien esa solución :)
Tranki HackzJuan, no es que no creamos en tí ni mucho menos, discute con nosotros e imponte, this... is... a forum...!!!
Quote from: HaCkZJuaNN on November 14, 2009, 09:56:21 PM
Quote from: Windgate on November 14, 2009, 08:51:29 PM
QuoteLo único que hago es irlos dividiendo por la mitad con un sistema que me permite saber cuál es el de en medio sin saber cuántos son.
Oh, es un aporte al algoritmo.
En cualquier caso, conocer el del medio no es ninguna ventaja a priori... Conocer el del centro puede servir para lanzar una orden a izquierda y derecha para que todos disparen, pero si hay "retraso" para esa orden no funcionaría.
Lo que dije al principio, resolver el problema es conseguir que la carambola de valores X valga 1 para todos al mismo tiempo.
Ahora recuerdo, un coste del tipo 2N-2 es coste lineal... Mucho pedir para este problema... Un coste 2^N exponencial me lo podría creer, pero apuesto por un coste exponencial N!... El límite de representación es un handicap enooorme.
No he podido encontrar nada en Google, lo que está claro es que debe ser un problema de sincronización, de la rama de sistemas operativos.
Joder es que no os lo creéis. Ya he explicado mi algoritmo de 2 maneras y lo he implementado y aún no os lo creéis. Mi algoritmo es 3N, lineal también, y funciona.
Lo que hago es dividirlos por la mitad, y entonces el del centro manda una señal para los dos lados como has dicho tú, pero claro, yo puedo volver a dividir por la mitad las dos mitades, y luego dividir por la mitad los cuatro cuartos, y así sucesivamente hasta que están de 1 en 1 y entonces disparan. En eso es en lo que se basa mi algoritmo. Tiene un sistema para que cuando sean impares funcione de una manera y cuando sean pares de otra(cada división que hace), y esto lo sabe por la señal que le llega, si son impares es una y si son pares otra... por la manera en que funciona el algoritmo. De este modo los divido y divido hasta que están todos separados, que ocurre en todos al mismo tiempo.
disculpa pero la solucion no puede ser... y creo que ya te estaras dando cuenta que todos te estamos diciendo que la solucion es genial para que no te lo tomes a personal... lo mismo me suena a tu profesor, ya he escuchado a muchos que por no entender algo y no quedar mal te dicen "si, es una buena opcion, pero no la mejor...", asi que si tu profesor no te dio la solucion a tu pregunta, no cuenta...
lamentablemente no puedo no participar... te hemos leido, pero tu solucion no cierra, y te has puesto un poco cabezotas en que la solucion de nadie sirve, salvo la tuya... desvalorizando la opinion de los demas e incluso te ofendes y dices que es algo personal contra ti... y aun asi no tienes forma de demostrar innequivocamente que tu solucion es la que vale... no tienes referencias con que apoyarlas, solo lo que tu piensas que funciona... no pensaste en que quizas no te estas explicando correctamente y/o estes omitiendo algunos detalles?
a ver... vamos por partes... y tratemos de verificar si lo que dices es correcto, seria realmente interesante encontrar una solucion...
por favor, todo lo que te pregunto no lo expliques con programas que puedan, por "fallas" del lenguaje, no hacer las cosas como tu dices que deben hacerse..., explicalo conceptualmente... y bien clarito, y pregunta a pregunta... solo limitate a responder eso, no te vayas por las ramas en largas explicaciones o ejemplos rebuscados... a ver si asi podamos ver la logica real en tu solucion... o en caso contrario puedas ver lo que te decimos no cierra...
1) como sabes cual es la mitad, si los soldados no cuenta? (como puedes decir que los soldados cuentan en un caso y en otro no? cuentan o no cuenta...)
2) por otro lado, como obtienes un centro cuando la cantidad de soldados es par? si es impar ok... en 3 el centro es el del medio, pero en 4 soldados?
3) partiendo de que el primer soldado envia una señal inicial, en que momento la señal en circulacion pasa de ser 1 señal a ser 2? y cuando pasa a ser mas de 2?
saludos.
mas alla de las preguntas, este codigo es el concepto que han dicho varios del foro y a mi parecer cierra mas que la otra propuesta, que aun no termina de ser logica...
en este codigo:
- se usa 1 solo frame (como entiendo debe ser)
- la comunicacion es 1 por soldado por frame
- se resuelve en 2xN + 5 (esos 5 frames son por como esta armada la maquina de estados)
- usa una maquina de estados (esto es una maquina de estados, pasar de un estado a otro y ejecutar codigo en consecuencia)
- 100% efectivo
- se resuelve en menos frames
import "mod_say";
#define N 150
global
int turno;
soldado soldado_actual;
soldado soldado_anterior;
soldado soldado_primero;
int i;
int soldados_que_dispararon = 0;
comunicacion_para_este_turno_consumida = 0;
end
#define STATE_WAIT_ORDER 0
#define STATE_WAIT_CONFIRM 1
#define STATE_COUNTDOWN 2
#define STATE_FIRE 3
process soldado(int num)
public
fire;
soldado snext;
soldado sprev;
private
state = STATE_WAIT_ORDER;
counter = 0;
ready_to_fire = 0;
begin
while(!ready_to_fire)
switch ( state )
case STATE_WAIT_ORDER:
if ( !comunicacion_para_este_turno_consumida )
if ( fire )
if ( snext )
snext.fire = 1;
state = STATE_WAIT_CONFIRM;
else
sprev.fire = 1;
state = STATE_COUNTDOWN; /* Me autoconfirmo, soy el ultimo */
end
counter = turno;
fire = 0;
comunicacion_para_este_turno_consumida = 1;
end
end
end
case STATE_WAIT_CONFIRM:
if ( !comunicacion_para_este_turno_consumida )
if ( fire )
if ( sprev )
sprev.fire = 1;
end
fire = 0;
state = STATE_COUNTDOWN;
comunicacion_para_este_turno_consumida = 1;
end
end
end
case STATE_COUNTDOWN:
counter--;
if ( counter < 0 )
state = STATE_FIRE;
end
end
case STATE_FIRE:
ready_to_fire = 1;
end
end
frame;
end
say ( "turno: " + turno + " soldado "+ num + " fire!");
soldados_que_dispararon++;
end
begin
//Crear los soldados
soldado_anterior = 0;
// crea soldados y los linkea
for(i = 0; i < N; i++)
soldado_actual = soldado(i);
if ( soldado_primero == 0 )
soldado_primero = soldado_actual;
end
soldado_actual.sprev = soldado_anterior;
soldado_actual.snext = 0;
if ( soldado_anterior )
soldado_anterior.snext = soldado_actual;
end
soldado_anterior = soldado_actual;
end
// doy la orden de disparar
soldado_primero.fire = 1;
// espero que todos hayan completado, solo por mantener el contador de turnos
while( soldados_que_dispararon < N )
comunicacion_para_este_turno_consumida = 0;
turno++;
frame;
end
say( "total de soldados en la fila = " + N );
say( "total de soldados que dispararon = " + soldados_que_dispararon );
end
por favor, espero tus respuestas, para aclarar todos los puntos grises de tu solucion...
saludos, animo!
lol aquí tenemos código de Splinter, es como degustar algo directamente del puño y letra de Miguel de Cervantes :o
Ahora en serio: Es bueno que intercambiemos opiniones y mantengamos posturas e incluso nos enojemos, pero no entremos en el bando del karma negativo, en serio Splinter y HackzJuan, hagan las paces o les bajo el Karma :-[
Por tu parte HackzJuan mantén tu postura y por tu parte Splinter mantén la tuya, pero tomadlo como un juego, estoy viendo más fluctuación de karma negativo que cuando se habla de la oxidada historia del salto de Fenix a Bennu (Bella historia de Bennu, no hay bella historia sin "batalla" xD).
Y tu solución propuesta, aunque más breve y sencilla de leer, tampoco me convence Splinter, pero en mi país es "demasiado" tarde, mañana la chequeo.
This... Is... Bennu... Be pleasant!
Quote from: Windgate on November 14, 2009, 06:36:56 PM
Haya paz amiguitos, estamos discutiendo como en un verdadero foro ;D pero no nos enfademos ni pensemos que es algo personal demostrar que hay o que no hay solución, al fin y al cabo son matemáticas, y nosotros somos programadores.
Humm... Wild las mates y la programacción se llevan muy bien o lo que es lo mismo estan relacionadas y yo me atreveria a decir que muy relacionadas ,tampoco quiero decir que si no se sabe de matematicas no se puede programar,pero te hace la vida mucho mas sencilla,sobre todo si conoces trigonometria en fin ,solo un apunte... ^^
Humm creo que puedo sacar la solución de un libro,que me parerio que venia,aunque habla de TORTUGA,?alguien al menos a oido hablar de el?yo la verdad ni que me acordaba xD
pero si yo no estoy enojado, solo he expresado mi opinion y que no me cierra el tema, no con esas condiciones "flexibles" para posturas segun conviene... hackzjuann ha dicho que yo tenia algo personal con el, solo por cuestionar su solucion... pero acaso no es que por los cuestionamientos el mundo avanza tecnologicamente?
che, windgate, como que no te convence si es lo que vos propusiste, incluso no he usado lo de time que yo decia, sino que use tu concepto de turnos como cronometro???!!!
edit: igualmente, probalo, funciona en todos los casos...
Por cierto el libro en cuestion se llama The Pattern on the Stone.
en el capitulo trata del tema
En el capítulo 2, Hillis nos muestra como con las puertas lógicas Y, O y NO, un conjunto de construcción universal, puede implementarse cualquier secuencia de reglas. Cualquier función representable como una tabla entrada-salida de ceros y unos puede implementarse a través de este reducido conjunto de operadores lógicos. El autor diserta sobre números binarios, código ASCII, coma flotante y unidades aritméticas. A través de las máquinas de estado finito nos introduce a las memorias, a los bloques lógicos denominados registros. Para acabar hablando de la velocidad de reloj, los límites de las "máquinas de estado finito y el problema del pelotón de fusilamiento que le propuso su mentor Marvin Minsky al que dedica el libro".
Quote from: DjSonyk on November 15, 2009, 03:12:55 AM
Por cierto el libro en cuestion se llama The Pattern on the Stone.
en el capitulo trata del tema
En el capítulo 2, Hillis nos muestra como con las puertas lógicas Y, O y NO, un conjunto de construcción universal, puede implementarse cualquier secuencia de reglas. Cualquier función representable como una tabla entrada-salida de ceros y unos puede implementarse a través de este reducido conjunto de operadores lógicos. El autor diserta sobre números binarios, código ASCII, coma flotante y unidades aritméticas. A través de las máquinas de estado finito nos introduce a las memorias, a los bloques lógicos denominados registros. Para acabar hablando de la velocidad de reloj, los límites de las "máquinas de estado finito y el problema del pelotón de fusilamiento que le propuso su mentor Marvin Minsky al que dedica el libro".
eso si tiene buena pinta, lastima que no encuentro mas textos que el que enuncias... a ver si aparece algo en ingles...
Yo creo que queda claro que el enunciado debe decir algo como que los soldados no conocen a priori el número de soldados que son, es decir no vale usar n como variable que todos conocen, esto es la forma de independizar el sistema del número de soldados, (pero sí que la pueden calcular preguntándose).
Además veo un poco contradictorio que no puedan calcular el número de soldados y que sí puedan pasarse infinitas entradas ( ya que dice el enunciado que pueden reducirse a una), pues entonces mandamos tantas entradas como necesitemos para enviar n una vez calculada por el último soldado ¿no?
De todas formas si no pueden contar, la otra solución es la de mandarse los ids que deben ser únicos y para ello este id debe de ser capaz como mínimo de alvergar N (número de soldados) ids diferentes así que dependencia con N por narizes debe de haber directa o indirectamente.
Así mismo el contar la mitad, ya vuelve a hacer el sistema dependiente de N, N/2 es relación directa con N. Veo un tanto en cuanto raro que seamos capaces de guardar N/2 y no N, es decir, N puede ser lo grande que quieras así que si produces overflow con N el doble de éste porducirá con N/2 el overflow. Hablando con números si n = 10, y no puedes guardarlo entonces que pasa si n = 20, n/2 es 10 y no puedes guardarlo.
En cuanto a la solución de splinter, no entendí el truco de los frames, a ver un sistema real de biestables síncronos, contadores, y demás cosas, dependen de un reloj en golpes ascendentes, es decir, tienen una patilla por la que le llega una señal cuadrada y cuando pasa del valor más bajo al mas alto, se produce el cambio en estos, es justo el momento en el que hacen lo que tienen que hacer, leer entradas, calcular cosas que consuman un tiempo y cambiar datos. Así que eso es justo lo que es un frame, no veo el porqué tener que hacer un sistema en que cada frame solo responda uno, en la realidad todos los soldados son independientes y deben de hacer lo que deban justo cuando se los dice el reloj así que esto debe ser ejecución en paralelo, además sino a ver como haces que disparen todos a la vez en el mismo frame si cada uno va respondiendo frame a frame. Irian al final todos los disparos desfasados en un frame, de ahí el tener que hacer un "raro"(por no decir otra cosa más fea :D) bucle de sincronización que salta las reglas del enunciado :)
aqui podemos sacar algo en conclusion sobre todo quien sepa bastante de ingles http://portal.acm.org/citation.cfm?id=568278
el problema:
In this paper we improve the bounds on the complexity of solutions to the firing squad problem, also known as the firing synchronization problem. In the firing synchronization problem we consider a one-dimensional array of n identical finite automata. Initially all automata are in the same state except for one automaton designated as the initiator for the synchronization. Our results hold for the original problem, where the initiator may be located at either endpoint, and for the variant where any one of the automata may be the initiator, called the generalized problem. In both cases, the goal is to define the set of states and transition rules for the automata so that all machines enter a special fire state simultaneously and for the first time during the final round of the computation. In our work we improve the construction for the best known minimal-time solution to the generalized problem by reducing the number of states needed and give non-minimal-time solutions to the original and generalized problem that use fewer states than the corresponding minimal-time solutions.
el frame representa un instante... varios soldados no pueden recibir la orden en 1 unico instante (o ciclo de reloj), por eso es que es 1 por frame... esto es como que en cada ciclo de reloj se ejecuta la operacion de comunicar a 1 soldado, pensa que le esta diciendo al oido uno a otro "dispara"... esto es solo en el caso de transmitir el mensaje, en todo otro caso, no hay esta limitacion... sin esta limitacion, la señal se transmitiria en 1 solo ciclo a todos los soldados y todos dispararian en el primer turno, y no seria necesario ningun tipo de sincronizacion... adjunto ejemplo (nota adicional, se agrega prioridad, para indicar el orden de ejecucion de los soldados, ya que segun como bennu ordena en memoria los procesos no seria posible hacer una comunicacion en fila).
import "mod_say";
#define N 150
global
int turno;
soldado soldado_actual;
soldado soldado_anterior;
soldado soldado_primero;
int i;
int soldados_que_dispararon = 0;
comunicacion_para_este_turno_consumida = 0;
end
#define STATE_WAIT_ORDER 0
#define STATE_WAIT_CONFIRM 1
#define STATE_COUNTDOWN 2
#define STATE_FIRE 3
process soldado(int num)
public
fire;
soldado snext;
soldado sprev;
private
state = STATE_WAIT_ORDER;
counter = 0;
ready_to_fire = 0;
begin
priority = ( N + 1 ) - i ;
while(!ready_to_fire)
switch ( state )
case STATE_WAIT_ORDER:
// if ( !comunicacion_para_este_turno_consumida )
if ( fire )
if ( snext )
snext.fire = 1;
state = STATE_WAIT_CONFIRM;
else
sprev.fire = 1;
state = STATE_COUNTDOWN; /* Me autoconfirmo, soy el ultimo */
end
counter = turno;
fire = 0;
comunicacion_para_este_turno_consumida = 1;
state = STATE_FIRE;
end
// end
end
case STATE_WAIT_CONFIRM:
if ( !comunicacion_para_este_turno_consumida )
if ( fire )
if ( sprev )
sprev.fire = 1;
end
fire = 0;
state = STATE_COUNTDOWN;
comunicacion_para_este_turno_consumida = 1;
end
end
end
case STATE_COUNTDOWN:
counter--;
if ( counter < 0 )
state = STATE_FIRE;
end
end
case STATE_FIRE:
ready_to_fire = 1;
end
end
frame;
end
say ( "turno: " + turno + " soldado "+ num + " fire!");
soldados_que_dispararon++;
end
begin
//Crear los soldados
soldado_anterior = 0;
// crea soldados y los linkea
for(i = 0; i < N; i++)
soldado_actual = soldado(i);
if ( soldado_primero == 0 )
soldado_primero = soldado_actual;
end
soldado_actual.sprev = soldado_anterior;
soldado_actual.snext = 0;
if ( soldado_anterior )
soldado_anterior.snext = soldado_actual;
end
soldado_anterior = soldado_actual;
end
// doy la orden de disparar
soldado_primero.fire = 1;
// espero que todos hayan completado, solo por mantener el contador de turnos
while( soldados_que_dispararon < N )
comunicacion_para_este_turno_consumida = 0;
turno++;
frame;
end
say( "total de soldados en la fila = " + N );
say( "total de soldados que dispararon = " + soldados_que_dispararon );
end
prestar atencion en que en este caso cuando recibe la señal de fuego, se pasa directo al estado disparar, y todos los soldados lo hacen sincronizados en el mismo ciclo, esto se debe a que no tiene la limitacion de 1 mensaje por ciclo de reloj/instante de tiempo.
Saludos.
agrego que en este ejemplo, no se conoce la cantidad de soldados.
Aqui podeis bajaros el libro en ingles y PDF,yo en este ordenador no me deja intalar el acroba reader por no tener el pack2 ya me contareis se supone que esta en el capitulo 2
www.cs.rutgers.edu/~mdstone/class/503/readings/hillis-pattern.pdf
aca va la solucion real... hay que leer, esta en ingles, y pesado...
http://facweb.cs.depaul.edu/asettle/research/papers/sirocco02.pdf
aca menciona 2 soluciones, una es dividiendo el array por 2, en sucesivas llamadas, pero parece que aca se conoce la cantidad de elementos en el anillo, igual hay que leerlo bien... es un poco largo, si alguien lo lee, y da una explicacion esta interesante...
saludos.
otra cosa, hay varios iniciadores, 2 por lo menos...
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
2) se arranca con 2 señales que van circulando 1 para un lado y otra para el otro y ahi es como al colicionar se detectan medios... pero nada que ver con pares e impares.
si es necesario, luego hare un ejemplo...
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...
hay otro caso donde el iniciador empieza en 1, y va sumandose (se cuenta tambien)... bueno, hay varios, lo lei un poco por arriba los ultimos... la primera me parece la mejor... un anillo con 2 señales iniciales que luego se van incrementando a medida que colisionan...
gracias DjSonyk por la informacion!
Quote from: SplinterGU on November 15, 2009, 01:12:26 AM
disculpa pero la solucion no puede ser... y creo que ya te estaras dando cuenta que todos te estamos diciendo que la solucion es genial para que no te lo tomes a personal... lo mismo me suena a tu profesor, ya he escuchado a muchos que por no entender algo y no quedar mal te dicen "si, es una buena opcion, pero no la mejor...", asi que si tu profesor no te dio la solucion a tu pregunta, no cuenta...
Nono, mi profesor conocía este problema de antes, y si la solución oficial se conoce(está demostrado que existe, pero como ya expliqué puede ser que aunque exista, no se conozca), seguramente él la conozca. El lunes le pregunto.
Quote
1) como sabes cual es la mitad, si los soldados no cuenta? (como puedes decir que los soldados cuentan en un caso y en otro no? cuentan o no cuenta...)
2) por otro lado, como obtienes un centro cuando la cantidad de soldados es par? si es impar ok... en 3 el centro es el del medio, pero en 4 soldados?
3) partiendo de que el primer soldado envia una señal inicial, en que momento la señal en circulacion pasa de ser 1 señal a ser 2? y cuando pasa a ser mas de 2?
saludos.
Así es más fácil de explicar ;) Gracias por plantearlo así.
Voy a empezar respondiendo a la pregunta 3, porque afecta a las otras 2.
3) Te voy a demostrar que si los soldados se pueden comunicar de manera finita y predeterminada(NO DEPENDIENTE DEL NÚMERO DE SOLDADOS), es exactamente lo mismo decir que pueden enviarse 1 señal a que pueden enviarse 2 a que pueden enviarse todas las que quieran, siempre y cuando el número de señales que manden no dependa del número de soldados.
Supongamos que sólo pueden enviarse 1 señal de uno a otro. Pues bien, si yo quiero hacer que se manden 2 señales, que supongamos tienen 20 posibles valores cada una(0..19 por ejemplo), lo único que tengo que hacer es combinarlas en una sola, de forma que el valor de la señal que mandan es 20*s1+s2. Así, para cada valor que le llega, el soldado lo vuelve a descomponer, tomando la división entera por 20 y el resto por 20 como las 2 señales que el otro soldado intentaba mandarle.
Lo que quiero decir es que si me puedo comunicar, te puedo comunicar cualquier número de cosas como una sola. Qué más me da a mi decirte: "hola" y después "splinter" que decirte "hola splinter" todo seguido. Si los dos conocemos el modo de codificarlo y la codificación es exacta(cada señal única está asociada a una pareja de señales única), entonces no hay problema.
Por tanto,
da igual si hay una señal o varias, porque son equivalentes, siempre que no dependa del número de soldados. Por tanto, pienso con varias señales y si después el hardware me exige hacerlo con 1 sola, pues la codifico. Conceptualmente son equivalentes1) Esa es la gracia del algoritmo y donde está toda la chicha. El tema es que, ya habiéndote explicado que varias señales son equivalentes a una sola, vamos a pensarlo con varias señales(es mucho más fácil de entender), y ya luego lo codificaríamos como fuera.
El primer soldado manda 2 señales.
La primera señal funciona así:
Tiene 2 valores: 1 y -1(y 0 que significa que no hay señal, si esa entrada es 0 el soldado no hace nada).
El primer soldado manda un 1 al siguiente para empezar el algoritmo.
Cada soldado, si NO es UN último(voy asignando varios soldados como últimos a lo largo del algoritmo, para dividir los subgrupos), si recibe un 1 del anterior, manda un 1 al siguiente al siguiente turno. Básicamente, la señal va avanzando un soldado cada turno. Además, si recibe un -1 del siguiente, manda un -1 al anterior. Los soldados de en medio solamente van retransmitiendo lo que les llega cada turno
Si el soldado ES un último, entonces si le llega un 1 del anterior, como no tiene siguiente, "REBOTA" la señal y manda un -1 al anterior.
De este modo(dibújaroslo en un papel si queréis), la señal va avanzando un soldado cada turno hasta que llega al último y rebota, retrocediendo un soldado cada turno también.
La segunda señal funciona así:
Tiene 3 valores: 1, -1 y 2(y 0 que significa que no hay señal, los soldados no hacen caso de esta)
El primer soldado manda un 1 al siguiente para empezar el algoritmo.
Cada turno, si el soldado NO es UN último, hace esto:
-Si le llega un 1 del anterior, al siguiente turno manda un -1 a ese mismo anterior.
-Si le llega un -1 del siguiente, manda un 2 a ese mismo siguiente.
-Si le llega un 2 del anterior, manda un 1 al siguiente.
De esta forma, la señal va avanzando 2 y retrocediendo 1, de media avanzando 1 cada 3 turnos.
Esta señal nunca llega hasta un último. Luego veréis por qué. No es que yo lo defina, es que en la manera en que funciona el algoritmo es imposible que llegue hasta un último. Por tanto siempre va hacia la derecha además.
Ahora, por supuesto, el primero en el segundo turno ya no manda nada por la primera señal(manda un 0), ni por la segunda(otro 0). Así que, a menos que les halla llegado una señal en el turno anterior, ellos no mandarán nada en el turno que corresponde. Lo cual quiere decir que en principio hay tantas señales "activas" como se hallan iniciado en esta "ronda". La primera ronda es 2 porque el primero manda 2 señales, en la segunda serán 4 porque el de/los de en medio mandan 2 para cada lado. En la tercera 8, etc...
Pues bien, probad a ir ejecutando las 2 señales al mismo tiempo en un papel(dibujaros cajitas conectadas en fila e ir haciéndolo, veréis cómo funciona), cada soldado, en cada turno, ve lo que le ha llegado, y decide lo que va a hacer en el siguiente, entonces lo mandan todos a la vez, y se pasa al siguiente turno.
El resultado es(SE VE EN EL PAPEL, HACEDLO EN EL PAPEL PARA VERLO), que si son impares, el punto en el que la primera señal "de vuelta" entra por la derecha en un soldado al que al mismo tiempo le llega por la izquierda un 1 ó un 2 de la segunda señal(que siempre ocurre en alguno), es justamente el soldado de en medio. ADEMÁS(de nuevo, se ve en el papel), la señal que le entra por la izquierda a éste es un 2.
Si son pares, el punto en el que ocurre esto mismo es, de los 2 que están en medio, el de la derecha(se ve en el papel). Además, a este la señal que le llega por la izquierda es un 1(se ve en el papel).
Entonces, si a un soldado le entra un 2 por la izquierda al mismo tiempo que le entra un -1 por la derecha, significa que es el de en medio y que son impares, luego lo que hace es asignarse a si mismo la propiedad de último Y de primero, y a continuación manda, AL MISMO TIEMPO, el mismo para de señales hacia la derecha, y el mismo par de señales hacia la izquierda, SIMÉTRICAS(lo cual quiere decir, hacemos 2 nuevas señales que funcionan igual que las anteriores pero donde pone siguiente lo cambias por anterior y donde pone último lo cambias por primero).
Si a un soldado le entra un 1 por la izquierda(por la segunda señal, 1 en la primera señal es distinto que 1 en la segunda) al mismo tiempo que le entra un -1 por la derecha, sabe que son pares y que es el de la derecha de los 2 de en medio, así que lo que hace es asignarse a si mismo una variable auxiliar: me_hago_primero y mandarle a su anterior una señal especial que significa "hazte_ultimo"(por una entrada nueva, que tiene 2 posibles valores: 0(no hagas nada), y 1(hazte ultimo). En cada turno, cada soldado revisa su propia variable me_hago_primero, ANTES DE LA PARTE PRINCIPAL DEL ALGORITMO, y si le dice que se haga primero, se hace primero y pone su variable me_hago_primero a 1. Así mismo, cada soldado, revisa su entrada "hazte_ultimo" que le viene del de la derecha, y si le dice 1 pues se hace último. De este modo consigo que estos 2 soldados se hagan uno primero y el otro último a la vez(el de la derecha consigue simular un retraso utilizando una variable auxiliar que setea más tarde en el algoritmo de lo que la comprueba, con lo que hasta el siguiente turno no la comprueba, y logra un retraso). A continuación, el de la derecha manda el par de señales hacia la derecha de nuevo y el de la izquierda manda el par de señales simétricas hacia la izquierda. Y repetir.
De este modo, si son impares los divido en 2 grupos iguales donde el primero de 1 es el último del otro(pero siguen siendo grupos en los que sus señales no se van a mezclar), y si son pares los divido en 2 grupos iguales y separados.
Hacedlo en el papel que es donde se ve bien. Probad con números de soldados distintos y veréis que siempre funciona.
Recordad que la condición de disparo es que él, su anterior(si no es el primero del todo), y su último(si no es el último del todo), sean o bien primeros o bien últimos o las 2 a la vez, posiblemente unos diferentes de otros, pero todos son al menos una, y esto siempre se produce en todos los soldados al mismo tiempo. Para saber esto cada turno se mandan señales hacia los dos lados con su valor de primero y de último. Así que en realidad disparan al turno siguiente a que ya son todos primeros o últimos, pero en cualquier caso es en todos a la vez.
La 2) ya la he respondido aquí. Lo mejor es que dibujéis la ristra de soldados en un papel y lo comprobéis.
Quote from: SplinterGU on November 15, 2009, 02:37:17 AM
counter = turno;
Ese es el problema de ese algoritmo. Que no sabes cuántos turnos va a haber, y por lo tanto eso podría dar overflow. Yo no utilizo la variable turno como parte del PROPIO algoritmo, sino meramente para indicar los resultados, pero los soldados no la conocen, la conozco yo que soy el que está probando el algoritmo.
Quote from: DCelso on November 15, 2009, 03:44:14 AM
Yo creo que queda claro que el enunciado debe decir algo como que los soldados no conocen a priori el número de soldados que son, es decir no vale usar n como variable que todos conocen, esto es la forma de independizar el sistema del número de soldados,
Exactamente. El algoritmo es fijo, y da igual cuantos soldados pongas juntos, sigue funcionando.
Quote
Además veo un poco contradictorio que no puedan calcular el número de soldados y que sí puedan pasarse infinitas entradas ( ya que dice el enunciado que pueden reducirse a una), pues entonces mandamos tantas entradas como necesitemos para enviar n una vez calculada por el último soldado ¿no?
No, perdon si no me expliqué bien. No se pueden hacer infinitas entradas. Tampoco se pueden hacer finitas entradas pero que el número de entradas sea dependiente del número de soldados. Si el número de entradas es fijo y funciona para cualquier número de soldados, entonces se pueden condificar como una sola. Obviamente lo que tú dices es así, eso sería hacer trampas, pero si el número de entradas es un número predeterminado(por ejemplo, 14), sí que vale y sí que se puede codificar en 1 sola.
Quote
De todas formas si no pueden contar, la otra solución es la de mandarse los ids que deben ser únicos y para ello este id debe de ser capaz como mínimo de alvergar N (número de soldados) ids diferentes así que dependencia con N por narizes debe de haber directa o indirectamente.
Así mismo el contar la mitad, ya vuelve a hacer el sistema dependiente de N, N/2 es relación directa con N. Veo un tanto en cuanto raro que seamos capaces de guardar N/2 y no N, es decir, N puede ser lo grande que quieras así que si produces overflow con N el doble de éste porducirá con N/2 el overflow. Hablando con números si n = 10, y no puedes guardarlo entonces que pasa si n = 20, n/2 es 10 y no puedes guardarlo.
Nono, yo no sé cuántos hay en la mitad, yo sé QUÉ SOLDADO ES EL DE EN MEDIO. Hay una diferencia. Saber que un soldado es el de en medio es simplemente ponerle un booleano a 1 a ese soldado. Saber cuántos hay en la mitad queda fuera de las reglas del enunciado.
Quote from: DjSonyk on November 15, 2009, 03:50:52 AM
aqui podemos sacar algo en conclusion sobre todo quien sepa bastante de ingles http://portal.acm.org/citation.cfm?id=568278
el problema:
In this paper we improve the bounds on the complexity of solutions to the firing squad problem, also known as the firing synchronization problem. In the firing synchronization problem we consider a one-dimensional array of n identical finite automata. Initially all automata are in the same state except for one automaton designated as the initiator for the synchronization. Our results hold for the original problem, where the initiator may be located at either endpoint, and for the variant where any one of the automata may be the initiator, called the generalized problem. In both cases, the goal is to define the set of states and transition rules for the automata so that all machines enter a special fire state simultaneously and for the first time during the final round of the computation. In our work we improve the construction for the best known minimal-time solution to the generalized problem by reducing the number of states needed and give non-minimal-time solutions to the original and generalized problem that use fewer states than the corresponding minimal-time solutions.
Ese es. Aunque en mi caso siempre la señal se le da al primero. Si se le puede dar a cualquiera(lo que llama ahí generalized problem), mi algoritmo obviamente no funciona :(
Quote from: SplinterGU on November 15, 2009, 07:42:12 AM
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
Quote
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.
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.
Si Dcelso yo al igual que tu ,he visto unas cuantas formulas para lo mismo que no quieren decir que sean mas optimas ,anillos ,arrays dimensionales,... un ect hasta esquaciones....bueno yo creo que ya mas no me voy a comer el tarro,hasta una solucion final eso si me quedo con la mia xD.... De todas formas si huviera por ejemplo 1000 soldados no podria una maquina enviar la sentencia de todas a la vez,ya que las maquinas no son multitareas y abria un espacio de tiempo entre 1 disparo y otro vamos como en la vida real ,el jefe de formación dice "Fuego!!" y segun el tiempo de reaccion de cada soldado dispara antes que otros... en fin por cierto por mas que mire en la wiki ni vi nada de eso DCelso ,buen descubrimiento.
Quote from: HaCkZJuaNN on November 15, 2009, 10:25:13 AM
Quote from: SplinterGU on November 15, 2009, 07:42:12 AM
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
Quote
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.
Quote from: DCelso on November 15, 2009, 11:34:24 AM
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.
Quote from: SplinterGU on November 15, 2009, 04:45:42 PM
Quote from: HaCkZJuaNN on November 15, 2009, 10:25:13 AM
Quote from: SplinterGU on November 15, 2009, 07:42:12 AM
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
Quote
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.
Quote from: DCelso on November 15, 2009, 11:34:24 AM
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.
Quote
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.
Quote from: SplinterGU on November 15, 2009, 07:28:40 PM
Quote
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.
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.
Quote from: SplinterGU on November 15, 2009, 10:29:27 PM
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.
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.
Quote from: SplinterGU on November 15, 2009, 11:23:13 PM
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".
lo revisare ni bien tenga tiempo... gracias... saludos.
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
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