Advent of Code 2024 - Queréis problemas?

two pointers, move zeros, pero con "."
ni idea de la optima, me acabo de levantar jaja
edit: entiendo que la optima es no generar el array con "." y trabajar sobre los dos pointers directamente, moviendote

He usado un map para trackear los bloques vacios y llenos, he estado 20 minutos pegandome con un bug tonto, pero al final lo he sacado

with open("input.txt", "r") as f:
    disk_map = f.read()
    blocks = []
    par = True
    count = 0
    empty = {}
    full = {}
    checksum = 0
    for digit in disk_map:
        if par:
            full[len(blocks)] = {"size": int(digit), "stop": len(blocks)+int(digit), "digit": count}
            for i in range(int(digit)):
                blocks.append(count)
            par = False
            count += 1
        else:
            empty[len(blocks)] = {"size": int(digit), "stop": len(blocks)+int(digit)}
            for i in range(int(digit)):
                blocks.append(".")
            par = True
    start = 0
    finish = len(blocks)-1
    for f_start, f in list(full.items())[::-1]:
        for e_start, e in dict(sorted(empty.items())).items():
            if e["size"] >= f["size"] and e_start < f_start:
                blocks[e_start:e_start+f["size"]] = blocks[f_start:f["stop"]]
                empty[e_start]["size"] -= f["size"]
                empty[e_start+f["size"]] = empty[e_start]
                del empty[e_start]
                blocks[f_start:f["stop"]] = ["." for x in  range(f["size"])]
                break
    for i, b in enumerate(blocks):
        if b != ".":
            checksum += int(b)*i
    print(checksum)

de que el input no te llega a mostrar más de 10 ficheros y entonces no ves que el id puede ser un número con más de 1 dígito, y joder, es superobvio, pero como estás focus en el ejemplo y centrado en implementarlo de X manera, no te fijas. Otros días pasa al revés, ves enseguida una trampa en la que otros caen

La primera parte empecé a implementarla inicialmente con un array de chars. Parecía bastante obvio, puesto que solo habría que recorrer el array buscando vacíos para mover los bloques de los ficheros ahí. Tras comerme la trampa de los dígitos y solucionar el problema con arrays, decidí cambiar la implementación basada en array a una cola doblemente enlazada.

En la cola almaceno todos los bloques, sean de ficheros o de espacios vacíos (-1).

La recorro sacando bloques por el principio de la cola:

• Si es un bloque de fichero calculo el checksum de ese bloque y lo sumo al resultado. Aumento el contador del índice.
• Si es un bloque vacío, saco un bloque del final de la cola y lo meto al principio.

La magia es que da igual que el bloque que haya sacado del final de la cola sea un bloque vacío o un bloque de fichero, ya que en la siguiente iteración, si es un bloque vacío, volverá a repetir la operación de sacar uno por el final, y si es un fichero, calculará su checksum.

Se podría meter una pequeña optimización para meter solo al principio de la cola los bloques cuando estos NO sean vacíos, pero a juzgar por los tiempos de ejecución, no ganaría mucho.

public class DiskFragmenter {

private final Deque<Integer> diskDeque = new ArrayDeque<>();

public DiskFragmenter(List<String> inputs) {

    char[] diskMap = inputs.get(0).toCharArray();
    int fileId = 0;
    int lastBlockIndex = 0;

    for(int i = 0; i < diskMap.length; i++) {

        int blockSize = Character.getNumericValue(diskMap[i]);

        for(int blockIndex = lastBlockIndex; blockIndex < lastBlockIndex + blockSize; blockIndex++) {
            if(i % 2 == 0) {
                diskDeque.add(fileId);
            } else {
                diskDeque.add(-1);
            }
        }

        lastBlockIndex += blockSize;
        if(i % 2 == 0) {
            fileId++;
        }
    }

}

public long solve() {

    long result = 0;
    int index = 0;
    while(!diskDeque.isEmpty()) {
        int current = diskDeque.pollFirst();
        if(current != -1) {
            result += (long) index * current;
            index++;
        } else if(diskDeque.peekLast() != null){
            diskDeque.addFirst(diskDeque.pollLast());
        }
    }

    return result;

}

}

Para la parte 2, paré un momento a pensar y me pareció más fácil tratar la solución como si fuese un problema completamente nuevo. Probablemente podría adaptar el código de la primera parte y sacarlo, pero iba a tardar menos haciendo un nuevo código.

Entonces decidí modelar unas clases File y Unallocated para poder abstraer un poco mejor las operaciones que necesitaba hacer:

public class File {

private final int id;
@Getter
private int startBlockIndex;
private int endBlockIndex;
@Getter
private final int size;

public File(int fileId, int startBlockIndex, int size) {
    this.id = fileId;
    this.startBlockIndex = startBlockIndex;
    this.endBlockIndex = startBlockIndex + size - 1;
    this.size = size;
}

public void move(int startBlockIndex) {
    this.startBlockIndex = startBlockIndex;
    this.endBlockIndex = startBlockIndex + size - 1;
}

public long checksum() {
    long result = 0;
    for(int i = startBlockIndex; i <= endBlockIndex; i++) {
        result += (long) id * i;
    }
    return result;
}
}

public class Unallocated {

private int startBlockIndex;
private int size;

public Unallocated(int startBlockIndex, int size) {
    this.startBlockIndex = startBlockIndex;
    this.size = size;
}

public boolean canAllocate(File file) {
    return this.size >= file.getSize() && this.startBlockIndex <= file.getStartBlockIndex();
}

public void allocate(File file) {

    if(canAllocate(file)) {
        file.move(this.startBlockIndex);
        this.startBlockIndex += file.getSize();
        this.size -= file.getSize();
    }
}

}

La clase que resuelve el problema ahora maneja una cola para los ficheros y una lista para los huecos disponibles:

1. Saca un fichero por el final de la cola.
2. Intenta reubicar el fichero en el primer espacio vacío que encuentre.
3. Si encuentra un espacio vacío, se actualiza el espacio disponible en dicho espacio vacío,
4. Independientemente de que el fichero se reubique o no, se calcula su checksum en ese mismo momento (al fin y al cabo, los ficheros se mueven una y solo una vez, o no se mueven en absoluto, pero en ambos casos, su índice de bloque inicial ya no se modifica).

public class DiskDefragmenter {

private final Deque<File> files = new ArrayDeque<>();
private final List<Unallocated> unallocateds = new ArrayList<>();

public DiskDefragmenter(List<String> inputs){

    char[] diskMap = inputs.get(0).toCharArray();
    int fileId = 0;
    int blockIndex = 0;

    for(int i = 0; i < diskMap.length; i++) {

        int blockSize = Character.getNumericValue(diskMap[i]);

        if(i % 2 == 0) {
            files.add(new File(fileId++, blockIndex, blockSize));
        } else {
            unallocateds.add(new Unallocated(blockIndex, blockSize));
        }

        blockIndex += blockSize;

    }

}

public long solve() {
    long result = 0;
    while(!files.isEmpty()) {
        File file = files.pollLast();
        result += reallocate(file);

    }
    return result;
}

private long reallocate(File file) {

    for(Unallocated unallocated : unallocateds) {
        if(unallocated.canAllocate(file)) {
            unallocated.allocate(file);
            break;
        }
    }

    return file.checksum();
}
}

No es muy eficiente... pero me ha hecho el apaño para poder sacar la parte 2 sin rayarme demasiado en adaptar la primera parte.

Dia 10, otro search, hoy con backtracking.

hoy he probado una tecnica nueva para generar los neighbours:

fn count_trailheads(grid: &[Vec<u8>], starting_coords: (usize, usize)) -> usize {
    let mut trailheads = 0;
    let mut stack = VecDeque::new();
    let mut visited = HashSet::new();

stack.push_back(starting_coords);
while let Some((i, j)) = stack.pop_front() {
    if !visited.insert((i, j)) {
        continue;
    }

    if grid[i][j] == 9 {
        trailheads += 1;
        continue;
    }

    let neighbors = [
        (i.checked_sub(1).map(|x| (x, j))),
        (i.checked_add(1).map(|x| (x, j))),
        (j.checked_sub(1).map(|y| (i, y))),
        (j.checked_add(1).map(|y| (i, y))),
    ];
    for next_pos in neighbors.into_iter().flatten() {
        let (ni, nj) = next_pos;
        if ni >= grid.len() || nj >= grid[0].len() {
            continue;
        }
        if grid[ni][nj] != grid[i][j] + 1 {
            continue;
        }

        stack.push_back((ni, nj));
    }
}

trailheads
}

Creo que a eso le ha pasado a mazo de gente hoy, yo incluido!
Ha sido brutal, porque luego cuando he visto que el resultado de ejemplo de la segunda parte era lo que me daba la primera al principio, me he puesto a deshacer código como un cabrón. XD

Ha sido leer el enunciado y revisar el input, que en mi mente ha resonado un pensamiento: Lantern Fish

Aún así, he ido primero con una aproximación naive a la primera parte, puesto que era suficiente, y ya en la segunda parte, readaptaría el código.

Efectivamente, tras ver que la segunda parte petaba la memoria, decidí remodelarlo como un mapa de recuento con cada número y sus apariciones.
He cometido un pequeño fallo al codificarlo que me ha tenido un ratito debugeando a ver por que fallaba.

Aún así, mi solución es mejorable: he visto gente por reddit que ha añadido funciones de caché (memoization), cosa que en Java no es tan sencillo como Python, y también gente que lo ha resuelto de manera recursiva/como un árbol.

public class PlutonianPebbles {

private Map<Long, Long> rocksPerNumber;

public PlutonianPebbles(List<String> inputs) {
    rocksPerNumber = Arrays.stream(inputs.getFirst().split(StringUtils.SPACE)).map(Long::valueOf)
                           .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}


public long solve(int blinks) {

    for(int i = 0; i < blinks; i++) {
        blink();
    }

    return rocksPerNumber.values().stream().reduce(0L, Long::sum);
}

private void blink() {

    Map<Long,Long> processedRocks = new HashMap<>();

    for(Map.Entry<Long,Long> rock : rocksPerNumber.entrySet()) {
        long number = rock.getKey();
        long rockCount = rock.getValue();
        long digits = String.valueOf(number).length();

        if(number == 0) {
            updateNumber(1L, rockCount, processedRocks);
        } else if(digits % 2 == 0) {
            String strNumber = String.valueOf(number);
            
            String strNumberLeft = strNumber.substring(0, strNumber.length() / 2);
            updateNumber(Long.parseLong(strNumberLeft), rockCount, processedRocks);

            String strNumberRight = strNumber.substring(strNumber.length() / 2);
            updateNumber(Long.parseLong(strNumberRight), rockCount, processedRocks);
        } else {
            updateNumber(number*2024L, rockCount, processedRocks);
        }
    }

    rocksPerNumber = processedRocks;
}

private void updateNumber(long number, long rockCount, Map<Long,Long> processedRocks) {
    rockCount += processedRocks.getOrDefault(number, 0L);
    processedRocks.put(number, rockCount);
}

}

Que envidia me dáis con el functools cache xD

Tengo que investigar más en profundidad una forma parecida de hacer cache en Java. He visto cosillas, pero no son ni de lejos tan sencillas como esa anotación, casi siempre requiere, pues eso, definir manualmente una estructura de datos para la memoization.