Advent of Code 2022: Day 18

Загадка восемнадцатого дня, на мой вкус, могла бы служить образцом для многих предыдущих загадок.

Минимум возни с парсингом ввода и кодированием очередных обходов графа. Максимум размышлений над поисками решения.

В то же время, само решение — не переусложнённое. Похожей по соотношению интерес/сложность для меня была задачка с обработкой сигналов.

Решение тут получилось компактным

static void day18(String puzzleInputUri) throws IOException, InterruptedException {
    List<Point> points = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
        .body()
        .map(line -> line.split(","))
        .map(xyz -> new Point(Integer.parseInt(xyz[0]), Integer.parseInt(xyz[1]), Integer.parseInt(xyz[2])))
        .collect(Collectors.toUnmodifiableList());
    long area1 = area(points);
    System.out.println("Answer 1: " + area1);
    List<Point> voids = findVoids(new Point(0, 0, 0), makeCube(points));
    System.out.println("Answer 2: " + (area1 - area(voids)));
}

Но только за счет раздутой подготовки

enum Matter {
    AIR, STEAM, LAVA
}

static class Point {
    public final int x, y, z;
    private final Set<BiFunction<Point, Integer, Point>> makeNeighbor = Set.of(
        (p, add) -> new Point(p.x + add, p.y, p.z),
        (p, add) -> new Point(p.x, p.y + add, p.z),
        (p, add) -> new Point(p.x, p.y, p.z + add)
    );
    public Point(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
    public boolean isNeighbor(Point c) {
        return Math.abs(this.x - c.x) + Math.abs(this.y - c.y)
            + Math.abs(this.z - c.z) == 1;
    }
    public List<Point> makeNeighbours() {
        return makeNeighbor.stream()
            .flatMap(f -> IntStream.of(-1, 1).mapToObj(i -> f.apply(this, i)))
            .collect(Collectors.toList());
    }
}

static List<Point> findVoids(Point start, int[][][] cube) {
    Deque<Point> stack = new ArrayDeque<>();
    Set<Point> visited = new HashSet<>();
    stack.push(start);
    while (!stack.isEmpty()) {
        Point cur = stack.pop();
        visited.add(cur);
        if (cube[cur.x][cur.y][cur.z] == Matter.AIR.ordinal()) {
            cube[cur.x][cur.y][cur.z] = Matter.STEAM.ordinal();
            for (Point neighbour : cur.makeNeighbours()) {
                if (!visited.contains(neighbour) && isBelongCube(neighbour, cube)) {
                    stack.push(neighbour);
                }
            }
        }
    }
    return IntStream.range(0, cube.length)
        .mapToObj(x -> IntStream.range(0, cube[x].length)
            .mapToObj(y -> IntStream.range(0, cube[x][y].length)
                .mapToObj(z -> new Point(x, y, z))
            )
        )
        .flatMap(it -> it.flatMap(Function.identity()))
        .filter(p -> cube[p.x][p.y][p.z] == Matter.AIR.ordinal())
        .collect(Collectors.toList());
}

static boolean isBelongCube(Point p, final int[][][] cube) {
    return (p.x >= 0 && p.y >= 0 && p.z >= 0)
        && (p.x < cube.length && p.y < cube[0].length && p.z < cube[0][0].length);
}

static int[][][] makeCube(List<Point> points) {
    int maxCoord = points.stream()
        .flatMapToInt(p -> IntStream.of(p.x, p.y, p.z))
        .summaryStatistics().getMax();
    int[][][] cube = new int[maxCoord + 1][maxCoord + 1][maxCoord + 1];
    points.forEach(p -> cube[p.x][p.y][p.z] = Matter.LAVA.ordinal());
    return cube;
}

static long area(List<Point> points) {
    return (points.size() * 6L) - IntStream.range(0, points.size())
        .mapToObj(i -> IntStream.range(i, points.size())
            .mapToObj(j -> points.get(i).isNeighbor(points.get(j)))
        )
        .flatMap(b -> b)
        .filter(Boolean.TRUE::equals)
        .count() * 2;
}

Возможно, для постоянно имеющих дело играми/графикой (и подобным), эта задачка будет выглядеть скучной. Мне же она понравилась (и с капелькой стримоза!).

Исходные данные: https://adventofcode.com/2022/day/18/input

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *