Problemilla interesante

[Windgate]

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

[HaCkZJuaNN]

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.

[SplinterGU]

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

[Windgate]

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

[SplinterGU]

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.

[Windgate]

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

[SplinterGU]

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

[Windgate]

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

[SplinterGU]

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

[Windgate]

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.

[HaCkZJuaNN]

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

[DCelso]

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.

Code Select Expand


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



[HaCkZJuaNN]

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.

Code Select Expand


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.

[DCelso]

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?

[DCelso]

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.