Advent of code

Día 14

HashMap y Recursividad

Advent of code

El Advent of Code es una página web donde cada día del mes de diciembre van descubriendo un problema para que la gente haga un algoritmo que lo resuelva.

14 de diciembre de 2020

El de este día mezcla HashMaps y recursividad

Parte 1

Dan una serie de direcciones y unos valores a escribir en ellas.

Los valores sufren una transformación y se almacenan, al final hay que hacer la suma de los valores almacenados en la memoria.

Escrituras repetidas

Se puede escribir varias veces en una posición de memoria y solo nos interesa el último valor escrito → No podemos ir sumando conforme leemos.

2^36 posiciones de memoria

Para que no usemos la fuerza bruta y hagamos un array con todas las posiciones de memoria nos dicen que éstas son de 36 bits.

Es imposible que hagamos un array de 68.719.476.736 posiciones (68 gigas).

hashmap

Tenemos pocos valores en un espacio de direccionamiento muy amplio.

El caso ideal para usar un hashmap.

Haremos un put(posición, valor) y al final sumaremos los valores recorriendo todo el hashmap.

Parte 2

Múltiples escrituras

Las direcciones de memoria no están definidas del todo.

Si nos dan una direccion como 01010xc01010x000xx11 que tiene 4 x significa que tendremos que escribir en 2^4 = 16 posiciones de memoria diferentes, con todas las combinaciones de 1s y 0s para cada x.

En alguna dirección tenemos que cambiar hasta 10 x, eso son 2^10 = 1024 escrituras.

ejemplo con 2x

Estrategia

Buscar una X
Si no hay estamos ya en una posición final → escribir en hashmap
Si la hay dividimos en dos fragmentos hacemos dos llamadas recursivas una con la X cambiada por 0 y otra con la X cambiada por 1
Repetir hasta que no queden X