Problemilla interesante

[SplinterGU]

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

[SplinterGU]

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

[DCelso]

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.

[Windgate]

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

[DCelso]

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.

[HaCkZJuaNN]

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.

[Windgate]

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.

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.

[HaCkZJuaNN]

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.

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.

[FreeYourMind]

Te creo.
Aunque todavia no he leido el problema ni las soluciones en condiciones para saber de que va en su totalidad  ;D

[Windgate]

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.

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

[SplinterGU]

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.

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.

[SplinterGU]

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

Code Select Expand


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!

[Windgate]

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!

[DjSonyk]

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

[SplinterGU]

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