Advent of Code, día 23

Estructuras de datos: la diferencia entre O(1) y O(n) cuando n = 1.000.000

Advent of Code

Parte 1

La parte 1 se puede resolver mediante una implementación “naive”, es decir sin preocuparse mucho de la eficiencia, ya que tanto el tamaño de n como el número de iteraciones es relativamente pequeño.

def solve(input):
    cups = [int(d) for d in input.strip()]
    min_cup = min(cups)
    max_cup = max(cups)

    for round in range(100):
        current_cup = cups[0]
        pick = cups [1:4]
        cups = [cups[0]] + cups[4:]
        search_for = current_cup - 1
        while search_for not in cups:
            search_for -= 1
            if search_for < min_cup:
                search_for = max_cup
        destination_pos = cups.index(search_for)
        cups = cups[:destination_pos+1] + pick + \
                                          cups[destination_pos+1:]
        cups = cups[1:] + cups[:1]

    start = cups.index(1)
    cups = cups[start+1:] + cups[:start]
    return ''.join(str(cup) for cup in cups)

Es un paso útil hacia la parte 2. Aunque no sea la implementación más eficiente, nos sirve para tener una forma de calcular resultados intermedios y poder así comprobar la corrección de otras soluciones.

Parte 2

La parte 2 cambia tanto el tamaño de la entrada (1.000.000) como el número de iteraciones (10.000.000). Cualquier pequeña ineficiencia hará que el programa sea tan lento que no acabe en un tiempo razonable.

Antes de llegar a una solución practicable, probé varias aproximaciones:

1. cambiar list() por deque(). Las deques pueden servir para implementar listas circulares, y tienen un método rotate() que quita elementos del principio y los añade del final (o viceversa). Podemos ir rotando la lista para que todas las operaciones ocurran al principio… Sin embargo tenemos una operación (buscar el nuevo punto de inserción en cada iteración) que nos requiere ir examinando todos los elementos de uno en uno O(n)
2. resolver con papel y boli: a veces es posible buscar una regla o fórmula para obtener los valores finales… tal vez era posible calcular solo los dos valores que nos piden al final… si en este caso existe dicha fórmula, yo no la encontré .
3. implementar una lista circular doblemente enlazada… también infructuoso pero me puso en la buena dirección: Mientras estaba pensando en la implementación y como resolver las operaciones que necesitaba, me di cuenta de que las inserciones se resolvían bien, pero seguía sin resolver el problema de encontrar rápidamente el punto de inserción. En una lista circular no tienes acceso directo a los elementos… ¿o si?

Y fue en ese momento en el que se me encendió la bombilla… pensé que podía guardar inicialmente un acceso directo a cada nodo en un array indexado por el valor del nodo… En cada nodo necesitaba almacenar su propio valor y un “puntero” al elemento siguiente. Pero si el elemento [15] del array, apunta siempre al nodo que tiene {value: 15, next: ??} en realidad no necesitamos almacenar el 15 dos veces. Así que llegué a la conclusión de que solo necesitaba un único array llamado next con un millón de elementos. El valor de cada nodo no necesita almacenarse, está implícito en la posición en el array. Lo que almacena el array para cada elemento es el valor de la posición siguiente en la lista circular.

Y esto hace que:

a) solo necesitamos un array de 1.000.000 de elementos que permanece estático durante todo el programa (evitamos reservar/liberar memoria dentro del bucle)

b) todas las operaciones en el interior del bucle son O(1): podemos acceder directamente al elemento actual current_cup, al siguiente elemento a uno dado next[cup], y a cualquier elemento por su valor. Además podemos reorganizar la lista simplemente cambiando los next de los elementos (sin necesidad de mover elementos en memoria)

Con esta idea, me puse a implementar la solución, y confieso que lo más difícil fue rellenar el array next inicial:

def solve(input):
    initial_cups = [int(d) for d in input.strip()]
    rest_of_cups = list(
        range(max(initial_cups) + 1, ONE_MILLION + 1)
    )

    next = [None] * (ONE_MILLION + 1)
    for cup, next_cup in zip(
        initial_cups + rest_of_cups,
        initial_cups[1:] + rest_of_cups + [initial_cups[0]]
    ):
        next[cup] = next_cup    
    
    current_cup = initial_cups[0]
    for round in range(10 * ONE_MILLION):
        if round % ONE_MILLION == 0:
            print(round)
        pick = [
            next[current_cup], 
            next[next[current_cup]], 
            next[next[next[current_cup]]]
        ]
        insert_after = current_cup - 1
        while insert_after in pick or insert_after == 0:
            insert_after -= 1
            if insert_after < 1:
                insert_after = ONE_MILLION
        next_insert_after = next[insert_after]
        next[insert_after] = pick[0]
        next[current_cup] = next[pick[-1]]
        next[pick[-1]] = next_insert_after

        current_cup = next[current_cup]

    return next[1] * next[next[1]]

El bucle en sí mismo es bastante más fácil de razonar, ya que sigue — mas o menos — los pasos descritos en el enunciado.

El código completo aquí: https://github.com/jabadia/adventOfCode2020/tree/main/d23