Advent of Code 2024 - Luke 16

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

Luke 16 i Advent of Code tok meg tilbake til da jeg tok bachelor på OsloMet. Høsten 2022 tok jeg faget Algoritmer og Datastrukturer hvor vi da lærte om Djikstra, som er korteste vei til et punkt. Vi lærte derimot ikke om implementasjonen av Djikstra, så i denne luken fikk jeg prøve meg på hvordan det gjøres. Oppgave 1 går ut på å finne korteste vei fra S (start) til E (end). Haken er at det koster 1 for å gå fremover, og 1000 for hver gang man velger å snu 90 eller 180 grader. Jeg endte opp med å lage en metode for å finne hvor start og slutt var, og en metode som gjennomførte Djikstras algoritmen, som kommer godt med når vi har forskjellig kostnad for ulike felt/retninger. Metodene ble slik:

private static int[] findPoint(char[][] maze, char target) {
    for (int i = 0; i < maze.length; i++) {
        for (int j = 0; j < maze[i].length; j++) {
            if (maze[i][j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}

private static int dijkstra(char[][] maze, int[] start, int[] end) {
    int rows = maze.length;
    int cols = maze[0].length;

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

    costArray = new int[rows][cols][4];
    for (int[][] layer : costArray) {
        for (int[] row : layer) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
    }

    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));

    for (int d = 0; d < 4; d++) {
        costArray[start[0]][start[1]][1] = 0;
        pq.offer(new int[]{start[0], start[1], 0, 1});
    }

    int minCostToEnd = -1;

    while (!pq.isEmpty()) {
        int[] current = pq.poll();
        int x = current[0];
        int y = current[1];
        int currentCost = current[2];
        int currentDir = current[3];

        if (x == end[0] && y == end[1]) {
            minCostToEnd = currentCost;
            break;
        }

        if (currentCost > costArray[x][y][currentDir]) continue;

        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (!isValid(maze, nx, ny)) continue;

            int turnCost = (dir == currentDir) ? 1 : 1001;
            int newCost = currentCost + turnCost;

            if (newCost < costArray[nx][ny][dir]) {
                costArray[nx][ny][dir] = newCost;
                pq.offer(new int[]{nx, ny, newCost, dir});
            }
        }
    }

    return minCostToEnd;
}

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

Oppgave 2

For oppgave 2 er det samme konsept som oppgave 1, men finne alle unike felt som er med på veier tilsvarende laveste kostnad. For dette opprettet jeg en ny metode som istedenfor å bryte av ved laveste funnet heller legger til alle veier i et Set for å unngå duplikat. Metoden blir da slik:

 private static Set<String> getAllBestPathTiles(char[][] maze, int[] start, int[] end, int minCost) {
    Set<String> bestPathTiles = new HashSet<>();
    if (minCost < 0) return bestPathTiles;

    int rows = maze.length;
    int cols = maze[0].length;

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

    Queue<int[]> queue = new LinkedList<>();
    boolean[][][] visited = new boolean[rows][cols][4];

    for (int d = 0; d < 4; d++) {
        if (costArray[end[0]][end[1]][d] == minCost) {
            queue.offer(new int[]{end[0], end[1], d});
            visited[end[0]][end[1]][d] = true;
            bestPathTiles.add(end[0] + "," + end[1]);
        }
    }

    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int x = current[0];
        int y = current[1];
        int dir = current[2];

        int currentCost = costArray[x][y][dir];

        int nx = x - dx[dir];
        int ny = y - dy[dir];

        for (int ndir = 0; ndir < 4; ndir++) {
            if (!isValid(maze, nx, ny)) continue;

            int prevCost = costArray[nx][ny][ndir];
            if (prevCost == Integer.MAX_VALUE) continue;

            int turnCost = (ndir == dir) ? 1 : 1001;
            if (prevCost + turnCost == currentCost) {
                String tileKey = nx + "," + ny;
                bestPathTiles.add(tileKey);

                if (!visited[nx][ny][ndir]) {
                    visited[nx][ny][ndir] = true;
                    queue.offer(new int[]{nx, ny, ndir});
                }
            }
        }
    }

    return bestPathTiles;
}