Advent of Code 2024 - Luke 20

Full kode finner du her.

Main metode

For alle oppgavene i 2024 bruker jeg Java, og dette vil være metoden jeg bruker for å hente input for de ulike oppgavene. Input blir lagret i en txt fil og hentes via denne metoden.

Oppgave 1 (og 2)

Ny luke, ny labyrint. Denne gangen er det en labyrint hvor en kan hoppe over vegger. Vi ønsker å finne antallet hopp der vi minker distansen med 100 skritt. For oppgave 1 kan man hoppe over 1 vegg, mens i oppgave 2 kan en hoppe 1 gang, men over opptil 19 vegger. Jeg laget en generell metode for de to ved hjelp av BFS her og, og endret kun på antallet lovlige hopp. Metoden ble slik:

private static void findAllShortcuts(char[][] maze, int[][] distances){
    for (int y = 0; y < maze.length; y++) {
        for (int x = 0; x < maze[0].length; x++) {
            if (distances[y][x] != -1) {
                findShortcut(maze, distances, x, y);
            }
        }
    }
}

private static void findShortcut(char[][] maze, int[][] distances, int baseX, int baseY) {
    for (int deltaRow = -20; deltaRow <= 20; deltaRow++) {
        int row = baseY + deltaRow;
        if (row < 0 || row >= maze.length) continue;

        for (int deltaCol = -20; deltaCol <= 20; deltaCol++) {
            int col = baseX + deltaCol;
            if (col < 0 || col >= maze[0].length) continue;

            int manhattan = Math.abs(deltaRow) + Math.abs(deltaCol);
            if (manhattan == 0 || manhattan > 20) continue;

            if (distances[row][col] == -1) continue;

            int economy = distances[row][col] - distances[baseY][baseX] - manhattan;
            if (economy >= 100) {
                bestShortcuts++;
            }
        }
    }
}


private static int[][] bfs(char[][] maze, int sx, int sy) {
    int[][] distances = new int[maze.length][maze[0].length];
    for (int[] row : distances) Arrays.fill(row, -1);
    distances[sy][sx] = 0;

    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{sy, sx});

    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};

    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int x = current[1];
        int y = current[0];
        int distance = distances[y][x] + 1;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (isValid(maze, ny, nx) && distances[ny][nx] == -1) {
                distances[ny][nx] = distance;
                queue.add(new int[]{ny, nx});
            }
        }
    }
    return distances;
}

private static boolean isValid(char[][] maze, int y, int x) {
    return y >= 0 && y < maze.length && x >= 0 && x < maze[0].length && maze[y][x] != '#';
}