Autor Tema: ¿Este puzzle en 21 movimientos?

0 Usuarios y 1 Visitante están viendo este tema.

25 Noviembre, 2024, 04:14 pm
Leído 4771 veces

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola!

Curioseando un poco con distintos puzzles he encontrado uno de tubos y ordenar colores.

El puzzle en cuestión consiste en ordenar el agua coloreada dispuesta en tubos. El que les presento debe poder lograrse en 21 movimientos o menos:



He encontrado que muchos lo resuelven pero en más de 21 movimientos:



Y este me ha hecho gracia sus comentarios:




Indagando un poco encontré un artículo en arXiv que asegura que este tipo de problemas son NP-complete.

También encontré diferentes solucionadores de estos puzzles:

https://elfin.cc/en/water-sort-solver

https://water-puzzle-solver.vercel.app/

Sin embargo, en todas esas páginas ninguna ha podido lograrlo en 21 movimientos.

¿Existe alguna configuración válida para lograrlo en esos movimientos (sin usar comodines)? Y si no, ¿por qué la página dice que se puede hacer en 21 movimientos?

Gracias!!
Saludos

04 Diciembre, 2024, 02:32 am
Respuesta #1

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

¿Nadie se anima a domar a la bestia o al menos plantearlo en términos matemáticos para atacarlo desde una perspectiva más formal? ¿O quizás (me inclino más por esta opción) no he visto que la imposibilidad de los 21 movimientos es una verdad de Perogrullo que no tiene sentido contestar el problema? :-\

Saludos

04 Diciembre, 2024, 11:48 am
Respuesta #2

Tachikomaia

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,297
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
No me había enterado.

Cuando pregunté qué programa les gustaría que haga, me hubieras dicho uno que busque cómo resolver eso en la menor cantidad de movimientos posibles.

Lo intentaré.

Para empezar, a ver si entendí bien las reglas.
Se tienen 9 tubos con líquidos de distinta densidad y color, o bien podrían ser pelotas de distinto color, la cuestión es que uno queda encima del otro. Y están entreverados de cierto modo. Hay:
1- Rojo.
2- Rosa.
3- Naranja.
4- Violeta.
5- Verde cyan.
6- Celeste.
7- Marrón.

Yo no distingo bien, al menos en este monitor, el rojo del rosa, y el violeta del marrón.

Y los líquidos se pueden mover a otros tubos. Bah, diferente densidad no tienen porque sino se unirían al mezclarlos ¿no? Pero el que se pone arriba siempre queda arriba.

Bueno, eso ¿y un mismo nivel qué tanto puede variar? Porque con ciertos desórdenes puede que se requieran menos movimientos o más.

Intento el de la 1era imagen. No voy a terminar ahora, aviso, ni pronto, quizá deba dejarlo.
// J=Rojo, S=Rosa.
InicialTubo1 = "JSSJ";
// L=Violeta, D=Verde.
InicialTubo2 = "CJLJ";
InicialTubo3 = "NNDN";
InicialTubo4 = "MLMD";
InicialTubo5 = "DCMN";
InicialTubo6 = "CMSC";
InicialTubo7 = "SLLD";
InicialTubo8 = "";
InicialTubo9 = "";

¿Está bien?

Otro punto relevante es que si al pasar el líquido de un tubo a otro hay colores seguidos en él, se mueven todos y sólo cuenta como 1 movimiento ¿no?

Bueno...

Código: [Seleccionar]
function ObtenerSituacionInicial () {
  SituacionInicial = "S"+InicialTubo1;
  TuboaAgregar = 1;
  do {
    TuboaAgregar++;
    SituacionInicial = SituacionInicial+"_"+eval("InicialTubo"+TuboaAgregar);
  } while (TuboaAgregar < 9);
}
function ObtenerSituacion () {
  Situacion = "S"+Tubo1;
  TuboaAgregar = 1;
  do {
    TuboaAgregar++;
    Situacion = Situacion+"_"+eval("Tubo"+TuboaAgregar);
  } while (TuboaAgregar < 9);
}
// Guardar situación inicial y cómo se produjo
// (eso se usa para saber que es la inicial):
// Parte inicial del nombre de los datos (en este caso SJSSJ_CJLJ_NNDN_MLMD_DCMN_CMSC_SLLD__):
SitID = ObtenerSituacionInicial();
// Acción realizada en la situación anterior (en este caso ninguna):
set (SitID+"ActionAnteriorP1", "Ninguna");
// En este caso la variable es SJSSJ_CJLJ_NNDN_MLMD_DCMN_CMSC_SLLD__ActionAnteriorP1 y su valor es "Ninguna".
// Nunca cree una variable de nombre tan largo, espero funcione.
// P1 significa parte 1, ya que las acciones se componen de 2 partes en este juego.
// Acción que será usada 1ero:
TuboaVertir = 1;
TuboaVertirle = 2;
// Variables sobre situaciones anotadas:
// Total de situaciones anotadas:
SAs = 0;
// Situación anotada que será investigada 1ero:
SiguienteSAaInvestigar = 0;
// Mensaje que se mostrará en pantalla:
Respuesta = "";
function BuscandoSolucion () {
// Reset de la situación:
        TuboaResetear = 0;
        do {
          TuboaResetear++;
          Resumen = "Tubo"+TuboaResetear;
          set (Resumen, eval("Inicial"+Resumen));
        } while (TuboaResetear < 9);
        // Aplicación de la acción:
        // Acá va lo de vertir un tubo en otro, no lo haré en este momento.
// ¿Se logró el objetivo?
        // Acá hay que especificar qué condiciones deben ocurrir para que se logre. Idem.
if (---logrado---) {
// Sí, iniciando proceso para mostrar cómo causarla:
Serie = Action;
gotoAndPlay (3);
} else {
// No ¿la situación producida está anotada?
                ObtenerSituacion ();
if (eval("Situacion"+"ActionAnterior") == undefined) {
// No, se anotará y cómo se logró;
set (Situacion+"SituacionAnterior", SituacionInicial);
set (Situacion+"ActionAnteriorP1", TuboaVertir);
set (Situacion+"ActionAnteriorP2", TuboaVertirle);
// También se agrega como situación a investigar y se anota en qué consiste:
SAs = SAs+1;
SitID = "SA"+SAs;
                        TuboaAgregar = 0;
                        do {
                           TuboaAgregar++;
                           Resumen = "Tubo"+TuboaAgregar;
                           set (SitID+Resumen, eval(Resumen));
                         } while (TuboaAgregar < 9);
}
// Sino sí está anotada, no se hace algo en particular.
// ¿Modificar acción es posible?
                // acá hay que especificar cómo se pueden variar las acciones, básicamente si TuboaVertir<9 y TuboaVertirle<9.
if (---sí---) {
// Sí, modificarla (especificar qué parte):
// Repetir este proceso (esta función).
} else if (SiguienteSAaInvestigar<SAs) {
// No ¿aún hay situaciones anotadas sin investigar?
// Sí, investigar una:
// (lo ideal sería investigar la más diferente a las investigadas, pero me es difícil programar eso).
SiguienteSAaInvestigar = SiguienteSAaInvestigar+1;
                        TuboaUsar = 0;
                        do {
                           TuboaUsar++;
                           Resumen = "Tubo"+TuboaUsar;
                           set ("Inicial"+Resumen, eval("SA"+SiguienteSAaInvestigar+Resumen));
                         } while (TuboaAgregar < 9);
// Reset de la acción a usar:
                       TuboaVertir = 1;
                          TuboaVertirle = 2;
// Repetir este proceso.
} else {
// No hay situaciones anotadas sin investigar:
Respuesta = Respuesta+" Ninguna, no es posible lograr el objetivo.";
stop ();
}
}
}
function RecordandoSolucion () {
// Obtener acción anterior:
ActionAnterior = eval("S"+----------+"ActionAnteriorP1");
        // ahí hay que poner cómo están los tubos, debo pensarlo.
// ¿Hubo?
if (ActionAnterior != "Ninguna") {
// Sí, agregarla en la lista:
Serie = ActionAnteriorP1+" en "+ActionAnteriorP2+", "+Serie;
// Averiguar cual fue la situación anterior:
                     // también me falta esto.
// Repetir este proceso.
} else {
// No hubo una acción anterior, mostrar la serie:
Respuesta = Respuesta+Serie;
gotoAndStop (4);
}
}

Ese código se basa en uno para un problema más simple, por eso le faltan cosas, hay que ajustarlo. Lo recomendable es intentar resolver algo más simple, o sea, lo que yo resolvía era quitar puntos de vida a un personaje, en este caso me refiero a que sean 3 tubos nada más, menos espacios y menos colores, o quizá sólo 2 tubos para empezar. Una vez que se logre que el programa funcione, se iría aumentando la complejidad.

Si puedo haré eso.

05 Diciembre, 2024, 10:24 pm
Respuesta #3

ani_pascual

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,221
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • שמע ישראל יהוה אלהינו יהוה אחד
    • Kepler_Ck
Hola:
...
¿Nadie se anima a domar a la bestia o al menos plantearlo en términos matemáticos para atacarlo desde una perspectiva más formal? ¿O quizás (me inclino más por esta opción) no he visto que la imposibilidad de los 21 movimientos es una verdad de Perogrullo que no tiene sentido contestar el problema? :-\
...
¡No he podido hacerlo en menos de 24 movimientos!  ;D







Saludos

05 Diciembre, 2024, 11:24 pm
Respuesta #4

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Acabo de intentarlo UN MINUTO DESPUÉS de ver tu mensaje y CREO que lo he podido resolver, estoy shockeado ;D ;D ;D

Menos mal que lo grabé para ver la secuencia de movimientos. Lo edito y lo subo.

Saludos

05 Diciembre, 2024, 11:50 pm
Respuesta #5

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Aquí está:



Versión un poco más rápida:

Spoiler
[cerrar]

Imagen de la victoria del nivel 16 :laugh::



Es correcto lo que hice?? Encima cuando vi tu mensaje dije "voy a intentar algo parecido a lo que hizo ani_pascual" y salió a la primera literalmente ja ja (ya habiendo intentado en su momento más de 10 u 11 veces).

Si está bien, ¿por qué todos los resolvedores que probamos ninguno ha podido conseguirlo en 21 movimientos? ¡No me lo puedo creer!

El nivel 17 creo recordar era más difícil...

Saludos

EDITADO

06 Diciembre, 2024, 09:44 am
Respuesta #6

ani_pascual

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,221
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • שמע ישראל יהוה אלהינו יהוה אחד
    • Kepler_Ck
Hola:
...
Acabo de intentarlo UN MINUTO DESPUÉS de ver tu mensaje y CREO que lo he podido resolver, estoy shockeado ;D ;D ;D
...
:aplauso: :aplauso: ¡Cuidado con la dosis de juego, que engancha!  ;D
Saludos