antigravity Problema 244 de Project Euler

Prompt

El **Problema 244 de Project Euler ("Sliders")** se plantea formalmente de la siguiente manera: Se tiene un tablero de 4x4 que contiene 15 fichas de colores (rojas y azules) y un espacio en blanco. Las fichas se pueden deslizar hacia el espacio en blanco de la misma forma que en el clásico rompecabezas de 15 números. Se define una configuración inicial **S** y una configuración objetivo **T**. Cada movimiento se registra anotando la dirección en la que se desplaza el **espacio en blanco**: * **L** (Izquierda) - Valor ASCII: 76 * **R** (Derecha) - Valor ASCII: 82 * **U** (Arriba) - Valor ASCII: 85 * **D** (Abajo) - Valor ASCII: 68 Para cualquier camino (una secuencia de movimientos que lleva el tablero desde la configuración inicial **S** hasta la configuración objetivo **T**), se forma una cadena de caracteres con las direcciones. A partir de esta cadena, se calcula un *checksum* (suma de verificación) iterativo. Si la secuencia de movimientos tiene una longitud $n$, denotada como $m_1, m_2, \dots, m_n$, el checksum $C_k$ se calcula paso a paso mediante la siguiente fórmula: $$C_0 = 0$$ $$C_k = (C_{k-1} \times 243 + m_k) \pmod{100000007}$$ Donde $m_k$ es el valor ASCII del $k$-ésimo movimiento. > **El objetivo del problema:** > Encuentra la suma de los *checksums* de **todos** los caminos válidos que logren resolver el rompecabezas (llegar de S a T) en la **menor cantidad de movimientos posibles**. ### Las configuraciones exactas Aunque las letras pueden variar en la traducción, el problema original define los estados exactos mediante una distribución de fichas Rojas (R) y Azules (B) con un espacio en blanco (`_`): **Configuración Inicial (S):** El espacio en blanco está en la esquina superior izquierda, seguido de una distribución específica de fichas rojas y azules. **Configuración Objetivo (T):** El espacio en blanco sigue en la esquina superior izquierda, pero las fichas deben formar un patrón de tablero de ajedrez alternado entre rojo y azul. Para resolverlo, el algoritmo debe ser capaz de encontrar la longitud mínima para alcanzar el patrón de tablero de ajedrez y luego rastrear matemáticamente cada una de las ramificaciones que logran ese objetivo en el mismo número exacto de pasos.