Problemilla interesante

[DjSonyk]

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é.

[Windgate]

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

[DjSonyk]

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

[SplinterGU]

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...

[HaCkZJuaNN]

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...

[HaCkZJuaNN]

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).

[HaCkZJuaNN]

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".

[SplinterGU]

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...

[SplinterGU]

bueno, dale, adelante con ese programa... te tengo fe...

[Windgate]

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

[HaCkZJuaNN]

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

Code Select Expand


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.

[Windgate]

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

[HaCkZJuaNN]

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 :)

[SplinterGU]

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...

[HaCkZJuaNN]

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.