Por @Alvy — 19 de Septiembre de 2022

React App

Conrad Barski, médico e ilustrador, ha creado este pequeño juego del que sólo existe un nivel y que se puede resolver en unos minutos pero que resulta entretenido y simpático a la vez: Perros y conejos.

El objetivo es que el perro llegue al hueso y los conejos a las zanahorias. Pero los caminos del grafo que conforma el tablero de juego tienen algunas limitaciones: o bien sólo se pueden mover en un sentido, o bien sólo pueden moverse si se dan ciertas condiciones: que haya un perro/conejo en ciertos vértices o que no haya ninguno.

Yo me lo he pasado bomba resolviéndolo, y creo que puede ser un entretenimiento estupendo incluso para jugar con niños pequeños, de modo que apliquen la lógica antes de hacer los movimientos. Sería genial que tuviera más puzles de dificultad creciente, o incluso que existiera un generador de nuevos puzles y que la gente los pudiera compartir.

Relacionado:

Compartir en Flipboard Tuitear

PUBLICIDAD



Por @Alvy — 12 de Septiembre de 2022

Este curioso vídeo de Polylog es un curioso crossover entre dos de mis temas favoritos: el cubo de Rubik y la criptografía. Explica cómo utilizar la técnica Meet-in-the-Middle («Encontrarse a medio camino») para resolver un cubo de Rubik. Esta técnica se emplea para atacar algunos algoritmos criptográficos, y no es precisamente la ideal para resolver el cubo. Pero sirve para hacerse una idea de cómo funciona este tipo de ataques convirtiendo un ataque imposible por fuerza bruta en otros dos más pequeños que sí son factibles. El vídeo está además estupendamente ilustrado con muy buenas animaciones.

La cuestión es que enseña a ver los movimientos del Cubo como un grafo, algo que puede suceder en otras situaciones, en el que unas posiciones (vértices) llevan a otras con cada giro, en un grafo que podría ser equivalente al de una red social o al de la teoría de los seis grados de separación. Encontrar la solución sería ir de la posición A (mezclado) a la B (resuelto) recorriendo el camino óptimo que tenga menos pasos. Y eso muchas veces puede hacerse, aunque depende de la complejidad y el número de vértices y caminos.

Contamos con una ventaja: para el Cubo de Rubik tradicional de 3×3×3 sabemos que 20 es el número máximo de movimientos necesario para resolverlo de forma óptima. Ojo a los matices, que mucha gente se lía: es el número máximo para resolverlo de forma óptima, que no el mínimo –que pueden ser muchos menos si el cubo está casi resuelto– ni el máximo absoluto –que puede ser infinito si te pones a hacer el tonto girando siempre la misma cara–. El número total de posiciones distintas de un cubo se sabe desde la antigüedad que es 43.252.003.274.489.856.000 (unas 1020).

El problema es que usar la fuerza bruta para llegar a todas las posiciones no sirve porque 1020 es un número un poco inabarcable; que esto es un juguete, no un satélite espía enemigo en el que invertir millones y millones. Pero curiosamente la forma de abordarlo con la técnica Meet-in-the-Middle permite explorar todas las posiciones a las que se pueden llegar con 10 movimientos desde el cubo mezclado (unas 1010) y al mismo tiempo las 1010 posiciones a las que se pueden llegar desde el cubo resuelto. Como está demostrado que el máximo necesario son 20 movimientos, eso quiere decir que si se solapan esos grafos alguna de esas posiciones (que ocupan unos 80 GB, así que se necesita mucha RAM) coincidirá. Se toma un camino del primera grafo, otro del segundo y esa será el camino ideal a la solución. Problema resuelto. Nota: esto solo funciona si el número de posiciones crece de forma suficientemente exponencial.

Incidentalmente, resulta que así es como se atacan criptográficamente sistemas de cifrado como el DES (con una clave única de 56 bits), calculando los dos grupos de 228 bits (algo más abarcable) y solapándolos. Por esta razón se quedó obsoleto y se inventó el Triple DES que usa 168 bits (3×56).

Ya lo hemos dicho antes: este algoritmo Meet-in-the-Middle no es óptimo por poco práctico –muchas veces la fuerza bruta no lo es– pero enseña algunas cosas interesantes. El código puede verse en Github (Rubik MITM Solution) donde se cita a Cube Explorer como sitio en el que encontrar algoritmos mucho más rápidos basados en otras ideas.

En God’s Number is 20 puede leerse algo más sobre cómo se resolvió el problema del número máximo de movimientos y en un vídeo de J Perm se explica lo del conteo de las 4,3 ×1019 posiciones distintas de un cubo 3×3×3.

Relacionado:

Compartir en Flipboard Tuitear

PUBLICIDAD



Por @Alvy — 7 de Agosto de 2022

Figure Puzzle≥

Figure es un juego del estilo de esos que hay miles, en el que el objetivo es limpiar la pantalla de figuras en un máximo de movimientos. Pero sólo se puede hacer clic sobre los de la fila inferior, y el número de piezas que «desaparecen», estilo Tetris, depende de cómo estén conectadas, lo cual está indicado con líneas.

Así que hay que darle al coco e intentar anticipar que es lo que va a suceder, que no suele ser muy complicado, al menos si te vas a por los grandes bloques y te fijas un poco cuando quedan 3-4 movimientos.

El juego no requiere registro, pero recuerda tus partidas anteriores, te guarda estadísticas y tiene las habituales funciones «estilo Wordle» de compartir resultados una vez has terminado y demás. Sólo hay uno cada día, así que tampoco perderá demasiado tiempo con él. Tan sencillo como relajante.

Actualización (10 de septiembre de 2022) – Hemos echado una mano a Sumul, su creador, para traducirlo. Ya está disponible aquí: Figure en español.

Relacionado:

Compartir en Flipboard Tuitear

PUBLICIDAD



Por @Alvy — 25 de Julio de 2022

El canal Blend the Rules parece haberse creado con un único objetivo, pues tiene solo un vídeo: sugerir una forma alternativa de calcular los tiempos en las competiciones del Cubo de Rubik de modo que se beneficie a quien resuelve el cubo más rápido, no quien lo resuelve más rápido en la competición.

Captar los matices y la diferencia entre una cosa y la otra no es trivial, y por eso el vídeo explica cómo se cronometra en las competiciones de speedcubing con todo detalle. Haciéndolo de este modo quizá el récord del mundo estuviera más bien entre 6 y 9 segundos que en los 3,47 segundos actuales que ostenta Yusheng Du muy meritoriamente.

Dejando aparte variantes de promedios, eliminación de mejores y peores cubos, etcétera, en la competición tradicional para el cubo más rápido el tiempo se cronometra en dos fases:

  • Primero hay hasta 15 segundos de tiempo de inspección del cubo, en los cuales –delante quien hace el papel de juez, que ha desordenado* el cubo antes– se puede mirar sin girar las caras. Este tiempo no se tiene en cuenta porque…
  • … Luego está el tiempo de resolución, que comienza a contar cuando se ponen las manos en los sensores del cronómetro, se resuelve el cubo y finaliza cuando se vuelven a pulsar los sensores con las manos.

En otras palabras: si el participante A emplea 14 segundos en inspeccionar el cubo y luego lo resuelve en 5 segundos (total: 19 segundos) y el participante B emplea 2 segundos en la inspección pero lo resuelve en 5,01 segundos (total: 7,01 segundos), el ganador es A. El tiempo de inspección simplemente se descarta y no se registra ni se tiene en cuenta, sea mucho o poco, porque así son las reglas.

El autor del vídeo examina de este modo los vídeos conocidos del Top 10 y luego el Top 100 de los récords del Cubo de Rubik 3×3×3 para mostrar las diferencias: situaciones y speedcubers que inspeccionan poco (o mucho) y resuelven luego más rápido o más despacio. Es muy meticuloso e incluso hay una hoja de cálculo con todos los datos. Gran trabajo por su parte.

La propuesta final es crear una nueva competición en la que se sumen ambos tiempos, de modo que se valore en ella a quien resuelva el cubo más rápido desde que lo ve por primera vez, y no tanto a quien ejecute más rápido sus algoritmos una vez examinada la posición (que tiene mucho mérito, pero no es lo mismo). Yo por ejemplo soy más bien de los primeros, porque examinar el cubo no me aporta gran cosa dado lo lento que soy resolviéndolo, ~50 seg (mi récord personal es 40,21 seg desde 2005, pero tampoco he competido desde entonces).

Todo esto en cierto modo me recordó a la inagotable insistencia de Ramón Trecet, el mítico periodista deportivo, acerca de que la marca en la prueba de salto de longitud debería medirse desde el punto de batida –que para eso hay cámaras y rayos láser en el siglo XXI– y no desde el «cero» teórico que marca la tabla. Esta medida integral significaría que si alguien salta 8,85 pero además se ha «dejado» 15 cm antes de la tabla, su salto real o salto de longitud real se validaría como 9,00 metros. ¡Nuevo récord del mundo!

A mi en general me parece una buenísima propuesta: en las competiciones de speedcubing, como en el atletismo o el ajedrez, hay que innovar de vez en cuando. E igual que hay variantes con promedios, a ciegas, con una mano, etcétera, podría popularizarse esta de «tiempo total, sin inspección». Sería un cambio nimio que daría lugar a marcas más realistas, de alrededor de 9 segundos según han calculado. Aunque por cierto hay algún vídeo de Max Park marcándose un 3 segundos de inspección + 3 segundos de resolución –no en competición– que indicaría que a ese nuevo récord se podría llegar en alrededor de 6 segundos.

_____
* El tema de la desordenación de los cubos es también complejo, pero está bien resuelto en la actualidad: se sabe que se puede resolver cualquier cubo desordenado en un máximo de 20 movimientos. Por eso hay software que genera una secuencia para desordenarlo desde el estado inicial de entre 20 y 25 movimientos; los participantes no lo ven ni conocen esas secuencias, que son básicamente aleatorias y ejecutadas por los jueces antes de la competición. Aun así, puede suceder que por azar resulten cubos que se pueden resolver en menos pasos de los habituales (lo cual depende de los algoritmos que utilice cada participante) y quizá algunos puedan suponer por puro azar una pequeña ventaja. En competición se suele intentar compensar con las pruebas del tipo «promedio de 3 cubos», «5 cubos», «eliminando el mejor y peor cubo», etcétera.

Compartir en Flipboard Tuitear

PUBLICIDAD




PUBLICIDAD




Un libro de @Alvy y @Wicho

Se suponía que esto era el futuro | un libro de Microsiervos, por Alvy y Wicho

Se suponía que esto era el futuro
Ciencia, tecnología y mucho más
www.microsiervos.com/libro