Advent of Code 2024 - Queréis problemas?

cambia los % por hacer el modulo tu
pasa todo a doubles/floats y haz el modulo a mano, multiplica, floor, luego castea a int
deberia ir 1000 a 10_000 veces mas rapido 500ms 50ms...
quizas en python no te hace SIMD automatico, pero vamos, tip: nunca usar %
quizas en python también al ser bigints depende del interpreter/jit

usar % es varias ordenes de magnitud mas lento que no... nunca hay que usarlo **con valores que no conoces, se me habia olvidado, si en tiempo de compilacion lo sabes esta OK

depende de como leas o setteas, da igual el lenguaje, es cuestion de arquitectura de CPU y que vas a hacer 10 veces mas instrucciones en serial VS 1 instrucciones en SIMD

yo lo estuve probando como en el video y pasaba de segundos a ms en varios tests que hice jaja

un topological sort no te sirve? veo que el problema es parecido al de puertas logicas de hace tiempo, en ese problema no hizo falta ordenar

En realidad... es un puzzle fácil, pero que me ha dado mucho trabajo.
Más que poner el código, voy a comentar un poco mis aventuras con el puzzle y los aprendizajes que he sacado al respecto.

Aprendizajes de este puzzle:

• He recordado de la universidad los conceptos de half-adder y full-adder.
• He aprendido lo que es una representación DOT de grafos y a exportar en dicho formato con JGraphT.
• He conocido dos herramientas para hacer las representaciones visuales: graphviz y graphviz2drawio (la primera para solo visualizar, la segunda, si además quiero editar el grafo en draw.io).

La parte 1 la hice con un dijkstra modificado. La única diferencia respecto al dijkstra real es que a la hora de moverme a un adyacente, tenía en cuenta si estaba moviéndome en la misma dirección o girando 90º para así sumar un score de 1 o de 1001 puntos respectivamente.

La parte 2 fue la que se me atascó. Inicialmente planteé hacerla así:
Cojo el camino de coste mínimo y busco todas las interseciones. Para todas las intersecciones e intento ver desde las mismas si hay un camino mínimo.
El problema es que lo anterior me parecía recursivo: a su vez en un subcamino, puede que a su vez hubiese más intersecciones que diesen caminos óptimos. Me quedé algo bloqueado en como implementarlo porque siempre perdía algún subcamino en el proceso.

Al llegar al día 20, di con una nueva idea: calcular las distancias parciales.
Esto es, si en una intersección B hay un adyacente A, entonces para que haya un camino por dicho adyacente debe ocurrir que la distancia d(S,E) = d(S,A)+d(A,B)+d(B,E)

Conozco todos los parámetros excepto d(A,B), que puede variar, en algunos casos sería 1 y en otros 1001.
Más esta solución tampoco me funcionó, a veces me pasaban cosas raras con la suma, e igualmente había que tener en cuenta las intersecciones nuevas del nuevo camino óptimo.

Finalmente, tuve una idea final aún mejor:
Aplicar un Dijkstra a la inversa, esto es, en realidad, un BFS desde la casilla de fin. Esto es:

• Añado la celda de fin en la cola.
• Mientras queden elementos en la cola voy sacando.
• Para cada elemento que saco, lo marco como visitado, lo marco con un booleano para indicar que es un elemento que debería tener asiento y obtengo sus adyacentes.
• Para cada adyacente no visitado hago un cálculo de score estimado (aquí reutilicé la anterior idea que tuve): d(S,E) = estimated score = d(S,A,E) = d(S,A) + d(A,B) + d(B,E)
• La condición para añadir un elemento a la cola, por lo tanto, en lugar de ser mejorar su mejor coste, pasa a ser que el coste estimado para ese nodo sea exactamente el mismo que el del nodo final, esto significaría que es posible encontrar un camino por ese lado.

De esta forma, voy recorriendo del final al principio con BFS, y en cada intersección, verifico si es posible alcanzar un camino mínimo.
Ahora bien, me costó un HUEVAZO debuggear los problemas de desplazamientos de 1000 y me pasé mucho rato verificando la fórmula anterior.

En principio tenía todo esto:

• El score de inicio a fin, es decir, d(S,A) en teoría, estaría calculado por la primera vuelta del bucle. Esto es, si el nodo tiene un coste mínimo X, ese debería ser el coste mínimo a sumar.
• El score del tile adyacente A a su tile previa B, es decir, d(A,B), sería 1 si la dirección de ambas era la misma, y 1001 en caso contrario.
• El score de la tile previa B al final, es decir, d(B,E) estaría calculado por su score hasta el final en la anterior vez que hubiese salido a la cola.
• Finalmente, el score de la tile final, es decir, d(S,E) estaría calculado por la primera vuelta de dijkstra.

En mi, caso por ejemplo, la tile del final tenía un coste de 7036, y el algoritmo funcionaba bien hasta después de hacer algunos giros. En ocasiones me dejaba con 1000 de menos (6036) o con 1000 de más (8036) y casi me vuelvo loco ajustando las anteriores fórmulas. Básicamente era un off-by-1 error pero en formato 1000 xD

Después de muchos intentos adaptando las fórmulas a lo que me parecía lógico en mi cabeza y faileando vilmente, decidí volver a la vieja confiable de papel. Fue entonces donde me di cuenta donde estaba mi off-by-1000 error:

• En todas mis tiles guardé, además de lo típico de dijkstra (score, visitado y demás), guardé la dirección de dicha casilla.
• La dirección se guardaba en relación a la anterior casilla, de tal forma que si hay un giro justamente en esa casilla, no se guarda la dirección del giro, eso se guarda en la siguiente. En otras palabras, guardaba las direcciones así:

####
#^>>
#^##

Y no así:

####
#>>>
#^##

El problema que tiene esto es que cuando haces el camino a la inversa, tienes que tenerlo en cuenta y hacerlo igual, es decir, así:

####
#<<<
#v##

Y no así:

####
#v<<
#v##

Total, que me enrollo, supongo que había muchas formas de arreglar esto, pero tras mucha prueba y error, lo que me funcionó primero fue sumar 1000 adicionales a la casilla si su dirección de vuelta invertida (multiplicada por 1) es igual que la dirección de ida de la casilla adyacente.

Esto es, supongamos que estoy evaluando la casilla X:

####
#<<<  // La esquina tiene una dirección de ida de (0,-1) y de vuelta (-1,0)
#X## // La X tiene una dirección de ida de (0,-1) y de vuelta (0,1)

Entonces veo que su nueva dirección del camino de vuelta es (0,1). Si miro la dirección de la casilla anterior (la que está justo encima), su dirección de ida es (0,-1), por lo tanto (0,1)*-1 == (0,1) -> sumo 1000 adicionales.

Es una ñapa como una casa, imagino que había una forma mas simple hacerlo, pero casi me vuelvo loco haciéndolo y pasaba de tocarlo maás:

    long scoreAdjacentTile = adjacentTile.getScore();

    // If there is a corner, adjacent tile must modify its score
    Vector2 reversedNewDirection = Vector2.multiply(newDirection,-1);
    if(!reversedNewDirection.equals(adjacentTile.getDirection())) {
        scoreAdjacentTile += 1000;
    }

    return scoreAdjacentTile;
}

private long calculateAdjacentTileToTileScore(Tile tile, Vector2 newDirection) {
    long scoreAdjacentToTile;
    if(tile == endTile) {
        scoreAdjacentToTile = 1;
    } else {
        scoreAdjacentToTile = newDirection.equals(tile.getDirectionReverse()) ? 1 : 1001;
    }

    return scoreAdjacentToTile;
}

Con esto, por fin conseguí sacar un resultado que tuviera sentido:

• Clase Reindeer Maze
• Clase Tile

Lo complicado de este era la parte 2.
Haciendo pruebas, vi que había ciertos patrones que se repetían en el output al ir probando números. También noté que cada X cambios de números, el listado de números se incrementaba:

• Los 8 primeros números imprimen un output.
• Los 64 siguientes imprimen 2 outputs.
• Los 512 siguientes imprimen 3 outputs.

Esto son potencias en base 8 (8^1, 8^2, 8^3..). Como el programa de salida tiene 16 dígitos, entonces el número más bajo a partir del cuál puede estar la solución tendrá que ser 8^16. Vale, es algo, pero no conseguía ver la solución.

Finalmente, curioseé algunas pistas por Reddit, y vi que la gente recomendaba convertir los números a octal y ver que pasaba si te fijabas en los últimos dígitos del output. Efectivamente, si nos fijamos en el último dígito, y luego en los 2 últimos dígitos, y luego en los 3 últimos dígitos y así sucesivamente, y convertimos el número decimal a octal, veremos que se van sumando dígitos por la derecha. Por ejemplo, inventándome valores:

6 -> 0
66 -> 1,0
661 -> 3,1,0
6612 -> 5,3,1,0
66120 -> 4,5,3,1,0

Y que estos valores coinciden con el output esperado del programa por el final.

Implementé un algoritmo que cogía la primera aparición (greedy), porque creía que era la que contaba, pero al final resulta que había que evaluar todas las posibles expresiones que pudieran dar dicho output. Así que lo convertí a un algoritmo recursivo de backtracking para evaluar todas las posibles combinaciones de 16 dígitos en octal hasta que encuentra la primera.

Por otro lado, también traduje las instrucciones a un programa más real. Puse el algoritmo de descifrado en ambos, tanto en el programa a bajo nivel como en el de alto nivel, pero por alguna razón, solo me funciona en el de alto nivel, debe de ser algún problema con int vs long:

• Clase ChronospatialComputer
• Clase Program

Más que un puzzle difícil, me pareció laborioso.

Cuando lo vi el primer día, lo primero que pensé es usar grafos para los teclados y usar dijkstra (una vez más, este año ha sido el año de dijkstra) para buscar caminos mínimos entre botones. Tras un poco de esfuerzo conseguí montar el grafo, pero a veces me salían caminos que aunque eran mínimos en el primer robot, no lo eran en el siguiente. Dejé en pausa este puzzle para el final porque vi que iba a ser laborioso, y el día que tocó hacer este puzzle había dormido 3h nada más.

Lo retomé ayer o antes de ayer y decidí atacar el problema por partes.
Lo primero, la construcción del grafo. Aunque había construido el grafo había sido muy manual y laborioso, lo que ensuciaba muchísimo el código y me preocupaba que hubiese algún error. Así que se me ocurrió una idea: generar un fichero en el que estén definidas todas las tuplas de vértice origen, vértice destino y arista.

Primero cogí una excel, y puse en cada columna vértice de origen, arista, vértice de destino (el grafo es dirigido). A continuación hice un join y generé dos ficheros.

El primer fichero es más sencillo, para el grafo del keypad direccional:

U,v,D
U,>,A
A,<,U
A,v,R
L,>,D
D,<,L
D,^,U
D,>,R
R,<,D
R,^,A

Puse las letras L, R, U y D en lugar de <, >, ^ y v porque a JGraphT no le gusta que los vértices se llamen "<" ni ">. Además, esto permitía identificar mejor los vértices respecto a las aristas.

Por ejemplo: U,v,D indica que de la flecha U (^) se puede ir a la flecha D (v) pulsando la tecla v.

Lo mismo con el keypad numérico:

7,>,8
7,v,4
8,<,7
8,>,9
8,v,5
9,<,8
9,v,6
4,^,7
4,>,5
4,v,1
5,<,4
5,^,8
5,>,6
5,v,2
6,<,5
6,^,9
6,v,3
1,>,2
1,^,4
2,<,1
2,^,5
2,>,3
2,v,0
3,<,2
3,^,6
3,v,A
0,>,A
0,^,2
A,<,0
A,^,3

De esta forma, ahora para leer el grafo el algoritmo tenía menos código y no estaba hardcodeado:

public class Keypad {

private static final String FILE_DIRECTIONAL_MAPPINGS = "directional_mappings.txt";
private static final String FILE_NUMPAD_MAPPINGS = "numpad_mappings.txt";

private final Graph<String, LabeledEdge> graph = new DirectedMultigraph<>(LabeledEdge.class);
private final boolean directional;

@Setter
private Keypad nextKeypad;

public Keypad(boolean isDirectional) {
    directional = isDirectional;

    String filename = directional ? FILE_DIRECTIONAL_MAPPINGS : FILE_NUMPAD_MAPPINGS;
    List<String> lines = Input.readStringLines("day21", filename);

    // Create the vertexes and edges described at each line
    for(String line : lines) {

        String[] parts = line.split(",");
        String vertexSource =  parts[0];
        String edgeLabel = parts[1];
        String vertexTarget = parts[2];

        if(!graph.containsVertex(vertexSource)) {
            graph.addVertex(vertexSource);
        }

        if(!graph.containsVertex(vertexTarget)) {
            graph.addVertex(vertexTarget);
        }

        graph.addEdge(vertexSource, vertexTarget, new LabeledEdge(edgeLabel));

    }

}

Como el día 24 aprendí a hacer visualizaciones de grafos, aproveché para visualizarlo y poder ver que las conexiones estuvieran bien puestas antes de proceder con el siguiente paso. Me creé una clase LabeledEdge para poder mostrar etiquetas en las aristas y luego exporté los grafos a representación DOT. Desde los siguientes enlaces podéis ver la visualización online del grafo:

• Grafo keypad numérico
• Grafo keypad direccional

La siguiente parte fue montar el algoritmo.

Para la parte 1 opté por una cola de keypads. Cada keypad calcula usando el método AllDirectedPaths todos los caminos entre 2 botones y me quedo con los más cortos. Una vez obtenidos todos los caminos mas cortos para todos los caracteres de la cadena, apliqué un producto cartesiano para generar todas las combinaciones de caminos, tras esto solo me quedaba ir pasando las cadenas por la cola de keypads y ¡voilá, solución!

Para la segunda parte, esto fue una aproximación muy ingenua. el producto cartesiano crecía y desbordaba el tamaño máximo de una lista en Java (MAX_INTEGER, es decir, 2^31-1, apenas hace falta que 31 caracteres tengan al menos un camino alternativo adicional para que se desborde).
Lo reconvertí a algoritmo recursivo y la cosa no mejoró mucho, ahora tenía un stack overflow.

Así que volví a mi algoritmo iterativo del principio, pero decidí que en lugar de hacer el producto cartesiano, podía ir evaluando los caminos según fueran saliendo. Enlacé los keypads entre si en lugar de usar una cola, de tal forma que cada vez que calculaba la pulsación de una tecla, llamaba a continuación al siguiente keypad, explorando en profundidad (DFS).

Más en concreto apliqué dos técnicas:

• Divide y vencerás: Para cada cadena, la convierto en array de caracteres, para cada carácter, saco sus posibles caminos, y para cada posible camino (para un único carácter), llamo al siguiente keypad. Es decir, ya no me espero a tener una cadena entera antes de pasársela al siguiente robot. Sino que según se van haciendo pulsaciones, el algoritmo va evaluando cada pulsación por separado y en profundidad.
• Programación dinámica (memoization): la apliqué en dos puntos, por un lado para la generación de los caminos de JGraphT usando AllDirectedPaths, y por otro lado, para las llamadas a pulsación de un botón (getMinimumButtonLength(originButton, targetButton))

Tuve un pequeño bug, porque en mi memoización original pensé que el mapa que guardaba las pulsaciones de botones podía ser static y compartido por todos los keypads, pero daba problemas, al parecer porque la memoization no es la misma, puede cambiar según la profundidad del algoritmo (he visto gente en reddit que en su algoritmo recursivo, usan un parámetro adicional de depth, en mi caso no tengo eso porque cada keypad es una instancia independiente).

El resultado final:

• Clase Keypad
• Clase KeypadConundrum
• Record CharacterPress (memoization de pulsación de teclas)