Advent of Code 2022: Day 12

По двенадцатому дню — сказать особо нечего. Если дни 7 и 10 запомнились (первый — неожиданными сложностями, второй — интересной в решении загадкой), то день 12 — совершенно безликий какой-то.

Тут изначально понятно, что именно придется делать для решения, и также понятно, что делать это будут довольно скучно.

Ну да ладно, BFS — так BFS. Разве что — не «тру-ООП» — без хранения вершиной своего состояния. Работает — и хорошо.

Что полезного отсюда вынес — обратное преобразование матрицы в стрим элементов, позволяющее отказаться от вложенных циклов.

class Vertex {
    public final int x;
    public final int y;
    public final int dist;
    public final char height;
    public Vertex(int x, int y, int dist, char height) {
        this.x = x;
        this.y = y;
        this.dist = dist;
        this.height = height;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Vertex that = (Vertex) o;
        return x == that.x && y == that.y;
    }
    @Override
    public int hashCode() {
        return x + y;
    }
    @Override
    public String toString() {
        return "Vertex{x=" + x + ", y=" + y + ", dist=" + dist + '}';
    }
}

static Vertex findEndPoint(Vertex from, char[][] map) {
    Set<Vertex> visited = new HashSet<>();
    char endMark = 'E';
    char nextTraversableMarkAfter_z = '{';
    int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int mapHeight = map.length;
    int mapWidth = map[0].length;

    Vertex start = new Vertex(from.x, from.y, from.dist, from.height);
    Queue<Vertex> queue = new ArrayDeque<>();
    queue.add(start);
    visited.add(start);

    while (!queue.isEmpty()) {
        Vertex current = queue.poll();
        for (int[] direction : directions) {
            int nextX = Math.max(current.x + direction[1], 0);
            int nextY = Math.max(current.y + direction[0], 0);
            if (nextX < mapWidth && nextY < mapHeight) {
                Vertex next = new Vertex(nextX, nextY, current.dist + 1, map[nextY][nextX]);
                if (!visited.contains(next) && (next.height - current.height <= 1 || current.height == 'S')) {
                    if (next.height == endMark) {
                        map[next.y][next.x] = nextTraversableMarkAfter_z;
                        continue;
                    }
                    if (next.height == nextTraversableMarkAfter_z) {
                        map[next.y][next.x] = endMark;
                        return next;
                    }
                    queue.add(next);
                    visited.add(next);
                }
            }
        }
    }
    return new Vertex(from.x, from.y, from.dist, '#');
}

static void day12(String puzzleInputUri) throws IOException, InterruptedException {
    char[][] mapArray = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
        .body()
        .map(String::toCharArray)
        .toArray(char[][]::new);

    System.out.println("Answer 1: " + findEndPoint(new Vertex(0,20,0, 'S'), mapArray));

    Vertex answer2 = IntStream.range(0, mapArray.length)
        .mapToObj(y -> Map.entry(y, mapArray[y]))
        .flatMap(row -> IntStream.range(0, row.getValue().length)
            .mapToObj(x -> Stream.of(new Vertex(x, row.getKey(), 0, row.getValue()[x])))
        )
        .flatMap(Function.identity())
        .filter(vertex ->
            Set.of('a', 'S').contains(vertex.height)
            && (
                (vertex.x == 0 || vertex.x == mapArray[0].length - 1)
                || (vertex.y == 0 || vertex.y == mapArray.length - 1)
            )
        )
        .map(entrance -> findEndPoint(entrance, mapArray))
        .filter(v -> v.height != '#')
        .min(Comparator.comparingInt(v -> v.dist))
        .orElseThrow();
    System.out.println("Answer 2: " + answer2);
}

Для решения второй части — была мысль пойти от E в направлении ближайших a, но всё равно пришлось бы перебрать их все, чтобы сравнить длину пройденного пути.

#adventofcode #adventofcode2022