Да, “тетрис” был определённо приятней вчерашних “скобочек”. И концептуально, и в реализации. Старые-добрые циклы-в-циклах – что может быть лучше!? 🙂

Только циклы, приправленные щепоткой стримов, конечно! Впрочем, попытки решить вторую часть через стрим – не увенчались успехом, увы. Приступ стримоза отступил и циклы вошли в свои права.

Песок и камни, или – камни и песок

static int drawRock(String scanLine, boolean[][] gameField) {
    int maxY = 0;
    String[] XY = scanLine.split(" -> ");
    for (int i = 0; i < XY.length - 1; i++) {
        int[] rocks = IntStream.rangeClosed(i, i + 1).mapToObj(idx -> XY[idx].split(","))
            .flatMap(Arrays::stream).mapToInt(Integer::parseInt).toArray();
        for (int j = Math.min(rocks[0], rocks[2]); j <= Math.max(rocks[0], rocks[2]); j++) {
            for (int k = Math.min(rocks[1], rocks[3]); k <= Math.max(rocks[1], rocks[3]); k++) {
                gameField[j][k] = true;
            }
        }
        maxY = Math.max(maxY, Math.max(rocks[1], rocks[3]));
    }
    return maxY;
}

static boolean pourSand(int maxY, boolean[][] gameField) {
    if (gameField[500][0]) return false;
    int x = 500;
    int y = 0;
    while (y <= maxY + 3) {
        if (!gameField[x][y + 1]) {
            y++;
            continue;
        } else if (!gameField[x - 1][y + 1]) {
            x--;
            y++;
            continue;
        } else if (!gameField[x + 1][y + 1]) {
            x++;
            y++;
            continue;
        }
        return gameField[x][y] = true;
    }
    return false;
}

Обратная засыпка по самое горлышко

static void day14(String puzzleInputUri) throws IOException, InterruptedException {
    boolean[][] gameField = new boolean[1000][1000];
    var maxY = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
        .body()
        .mapToInt(scanLine -> drawRock(scanLine, gameField))
        .max().orElse(0);

    int answer = 0;
    drawRock( "0," + (maxY + 2) + " -> " + (gameField[0].length - 1) + "," + (maxY + 2), gameField);
    while (pourSand(maxY, gameField)) {
        answer++;
    }
    System.out.println(answer);
}

Зря я сетовал на загадку прошлого дня. Ох, зря! Парсинг вот этих вот дурных скобочек-в-скобочках – это было форменно издевательство, помноженное на бесконечное уныние.

Просто весь интерес убивает. После решения, вместо удовольствия – только облегчение с мыслью “Хоть бы никогда больше не встретить подобного” 🙂

Да будь там, допустим, валидный JSON – я бы, пожалуй, сдался, и подключил либу. Но костыли с JSONArray, навскидку, не выглядели проще кастомного решения. Что ж, вот оно.

По двенадцатому дню – сказать особо нечего. Если дни 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 + '}';
    }
}

С задачкой про Бандар-логов я познакомился (и расстался) непосредственно в день её выхода. И, к стыду своему, уже не очень помню подробности.

Под влиянием пресловутого “И так сойдёт!” – совершил ошибку с BigInteger (вероятно, ожидаемую и типовую для этой задачи). Несколько минут, потраченных на просчет первой тысячи “обезьяньих прыжков”, ясно показали – это ошибочный путь.

А, да – потом зачем-то пробовал пойти путём вычисления GCD, но вовремя присмотрелся к множителям “проверок” и заметил, что все они – простые числа. После этого поиск решения не составил труда.

В формате таблицы заметить этот факт гораздо проще. Ну а “обезьян” я захардкодил, чтобы не парсить ввод. Решение этой загадки запускается на Java 17 (как и решение для Дня 7).

record Monkey(List<Long> items, Worry worry, Test test) {};
record Test(Integer divider, Map<Boolean, Integer> action) {};
record Worry(String arg1, String arg2, BiFunction<Long, Long, Long> op) {};
static BiFunction<Long, Long, Long> mult = (a, b) -> a * b;

static void day11() {
    Map<Integer, Map.Entry<Monkey, AtomicLong>> bandarLogs = new TreeMap<>(Map.of(
        0, Map.entry(
            new Monkey(new CopyOnWriteArrayList<>(List.of(63L, 57L)), new Worry("old", "11", mult), new Test(7, Map.of(true, 6, false, 2))),
            new AtomicLong(0)
        ),
        1, Map.entry(
            new Monkey(new CopyOnWriteArrayList<>(List.of(82L, 66L, 87L, 78L, 77L, 92L, 83L)), new Worry("old", "1", Long::sum), new Test(11, Map.of(true, 5, false, 0))),
            new AtomicLong(0)
        ),
        2, Map.entry(
            new Monkey(new CopyOnWriteArrayList<>(List.of(97L, 53L, 53L, 85L, 58L, 54L)), new Worry("old", "7", mult), new Test(13, Map.of(true, 4, false, 3))),
            new AtomicLong(0)
        ),
        3, Map.entry(
            new Monkey(new CopyOnWriteArrayList<>(List.of(50L)), new Worry("old", "3", Long::sum), new Test(3, Map.of(true, 1, false, 7))),
            new AtomicLong(0)
        ),
        4, Map.entry(
            new Monkey(new CopyOnWriteArrayList<>(List.of(64L, 69L, 52L, 65L, 73L)), new Worry("old", "6", Long::sum), new Test(17, Map.of(true, 3, false, 7))),
            new AtomicLong(0)
        ),
        5, Map.entry(
            new Monkey(new CopyOnWriteArrayList<>(List.of(57L, 91L, 65L)), new Worry("old", "5", Long::sum), new Test(2, Map.of(true, 0, false, 6))),
            new AtomicLong(0)
        ),
        6, Map.entry(
            new Monkey(new CopyOnWriteArrayList<>(List.of(67L, 91L, 84L, 78L, 60L, 69L, 99L, 83L)), new Worry("old", "old", mult), new Test(5, Map.of(true, 2, false, 4))),
            new AtomicLong(0)
        ),
        7, Map.entry(
            new Monkey(new CopyOnWriteArrayList<>(List.of(58L, 78L, 69L, 65L)), new Worry("old", "7", Long::sum), new Test(19, Map.of(true, 5, false, 1))),
            new AtomicLong(0)
        )
    ));
    int divider = bandarLogs.values().stream().map(Entry::getKey).mapToInt(m -> m.test().divider()).reduce(1, (a, b) -> a * b);

    // int rounds = 20;
    int rounds = 10_000;
    for (int i = 1; i <= rounds; i++) {
        System.out.printf("Round %d\r", i);
        bandarLogs.forEach((monkeyN, monkeyEntry) -> {
            Monkey monkey = monkeyEntry.getKey();
            monkey.items().forEach(item -> {
                var a1 = "old".equals(monkey.worry().arg1()) ? item : Integer.parseInt(monkey.worry().arg1());
                var a2 = "old".equals(monkey.worry().arg2()) ? item :Integer.parseInt(monkey.worry().arg2());
                var newWorryLvl = monkey.worry().op().apply(a1, a2);
                newWorryLvl = rounds == 20 ? newWorryLvl / 3 : newWorryLvl % divider;
                int recipientMonkey = monkey.test().action().get(
                    newWorryLvl % monkey.test().divider() == 0
                );
                bandarLogs.get(recipientMonkey).getKey().items().add(newWorryLvl);
                monkey.items().remove(item);
                monkeyEntry.getValue().incrementAndGet();
            });
        });
    }
    System.out.println();

    var result = bandarLogs.values().stream()
        .map(Entry::getValue)
        .map(AtomicLong::get)
        .sorted(Comparator.reverseOrder())
        .limit(2)
        .reduce((a, b) -> a * b);
    System.out.println("Monkey business = " + result);
}

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

Так вот ты какая – идеальная капча!

Задача десятого дня далась неожиданно просто. Ну, не совсем неожиданно и не совсем просто, будем честны. Но, по сравнению с проклятым “древом седьмого дня” – это было совсем не больно 🙂

Поначалу думал, что получится всё запихать в один длинный и страшный стрим, с кучей таинственных мутаций внутри.

Как-то я делал сервис, реализующий развесистую логику подбора уже не помню чего по куче разных условий – и вот там было именно так. Мапы перетекали в мапы, всё это бесконечно упаковывалось и распаковывалось, подвергалось преобразованиям Шварца (да, корни где-то в Лиспе), и, в качестве вишенки на торте, венчалось самосборным коллектором.

В общем, для такого лучше подошел бы Perl. Или, например, JS. И уже через минуту я бы точно забыл, как это работает.

После седьмого дня – решение восьмого было, в некотором роде, отдыхом. Хотя “усладой для глаз” его точно не назовёшь – вид оно имеет весьма портяночный.

Когда-то развлекался – делал “крестики-нолики” с полем свободного размера. И для среднего уровня сложности позиция следующего хода компьютера вычислялась сканированием этого самого поля.

Не то, чтобы это всё пригодилось мне в задаче восьмого дня. Но с тех пор, помучившись с отладкой, я крепко запомнил необходимость тщательной проверки границ массивов. Благодаря чему поймал ArrayIndexOutOfBoundsException лишь единожды ¯\_(ツ)_/¯.

static void day8(String puzzleInputUri) throws IOException, InterruptedException {
    int[][] forest = client.send(
        request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()
        ).body()
        .map(line -> line.chars().map(cCode -> cCode - '0').toArray())
        .toArray(int[][]::new);
    int mapHeight = forest.length;
    int mapWidth = forest[0].length;

    AtomicInteger visibilityCount = new AtomicInteger(mapWidth * mapHeight);
    TreeSet<Integer> scenicScores = new TreeSet<>();
    for (int j = 1; j < mapHeight - 1; j++) { //j down
        for (int i = 1; i < mapWidth - 1; i++) { //i ->
            List<Boolean> visibilities = new ArrayList<>();
            int scenicScore = 1;
            //look left
            for (int k = i - 1; k >= 0; k--) {
                if (forest[j][k] >= forest[j][i]) {
                    visibilities.add(false);
                    scenicScore *= (i - k);
                    break;
                } else if (k == 0) {
                    visibilities.add(true);
                    scenicScore *= i;
                }
            }
            //look right
            for (int k = i + 1; k < mapWidth; k++) {
                if (forest[j][k] >= forest[j][i]) {
                    visibilities.add(false);
                    scenicScore *= (k - i);
                    break;
                } else if (k == mapWidth - 1) {
                    visibilities.add(true);
                    scenicScore *= (mapWidth - 1) - i;
                }
            }
            //look top
            for (int k = j - 1; k >= 0; k--) {
                if (forest[k][i] >= forest[j][i]) {
                    visibilities.add(false);
                    scenicScore *= (j - k);
                    break;
                } else if (k == 0) {
                    visibilities.add(true);
                    scenicScore *= j;
                }
            }
            //look bottom
            for (int k = j + 1; k < mapHeight; k++) {
                if (forest[k][i] >= forest[j][i]) {
                    visibilities.add(false);
                    scenicScore *= (k - j);
                    break;
                } else if (k == (mapHeight - 1)) {
                    visibilities.add(true);
                    scenicScore *= (mapHeight - 1) - j;
                }
            }
            visibilities.stream().reduce(Boolean::logicalOr).ifPresent(isVisible -> {
                if (!isVisible) visibilityCount.decrementAndGet();
            });
            scenicScores.add(scenicScore);
        }
    }

    System.out.println(visibilityCount);
    System.out.println(scenicScores.last());
}

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

Мои взаимоотношения с этой загадкой можно описать примерно такой фразой (по мотивам анекдотов):

– Дерево – подумал Штирлиц
– Дерево – поняло дерево

Всё началось с того, что мне совершенно не хотелось строить это дерево (забегая вперёд – всё же пришлось).

После пары неудачных попыток (о которых ниже) – решил хранить эту псевдо-ФС в избыточном виде – получились этакие “мангровые заросли”.

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

record File(String name, long size, List<File> files) {}
static Map<String, File> flattenFs = new HashMap<>();

static void day7(String puzzleInputUri) throws IOException, InterruptedException {
    List<String[]> commands = client.send(
            request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()
        ).body()
        .skip(1)
        .filter(line -> !line.equals("$ ls"))
        .map(line -> line.replace("$ ", ""))
        .map(line -> line.split(" "))
        .toList();

    String currentDirKey = "/";
    flattenFs.put(currentDirKey, new File("/", 0L, new ArrayList<>()));
    for (var commandLine : commands) {
        String command = commandLine[0];
        String arg = commandLine[1];
        if ("dir".equals(command)) {
            String newDirKey = currentDirKey + "/" + arg;
            flattenFs.putIfAbsent(newDirKey, new File(newDirKey, 0L, new ArrayList<>()));
            flattenFs.get(currentDirKey).files().add(flattenFs.get(newDirKey));
        } else if ("cd".equals(command)) {
            if ("..".equals(arg)) {
                String parentDir = currentDirKey.substring(0, currentDirKey.lastIndexOf("/"));
                currentDirKey = flattenFs.keySet().stream()
                    .filter(dir -> dir.equals(parentDir))
                    .findAny().orElseThrow();
            } else {
                currentDirKey += "/" + arg;
            }
        } else {
            flattenFs.get(currentDirKey).files().add(new File(arg, Long.parseLong(command), new ArrayList<>()));
        }
    }

    long resultPartOne = flattenFs.values().stream()
        .mapToLong(dir -> getTotalSize(dir, 0L))
        .filter(size -> size <= 100_000L)
        .sum();
    System.out.println(resultPartOne);

    long usedSpace = getTotalSize(flattenFs.get("/"), 0L);
    long freeSpace = 70_000_000L - usedSpace;
    long needForUpdateSpace = 30_000_000L - freeSpace;
    long resultPartTwo = flattenFs.values().stream()
        .mapToLong(dir -> getTotalSize(dir, 0L))
        .filter(size -> size >= needForUpdateSpace)
        .min()
        .orElseThrow();
    System.out.println(resultPartTwo);
}

static long getTotalSize(File dir, long totalSize) {
    List<File> files = dir.files();
    for (File file : files) {
        totalSize += file.size() > 0L
            ? file.size()
            : getTotalSize(flattenFs.get(file.name()), 0L);
    }
    return totalSize;
}

Этот пример запускал на Java 17, на традиционно используемой в прошлых задачах одиннадцатой версии Java он не заработает.

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

Решение для шестого дня получилось коротким, простым, универсальным (применительно к загадке).

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

Но оно сработало, что полностью соответствует духу викторины. Для первой части загадки markerSize = 4, для части два – markerSize = 14.

static void day6(String puzzleInputUri) throws IOException, InterruptedException {
    int markerSize = 14;
    Set<Byte> buffer = new HashSet<>();
    byte[] message = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofByteArray()).body();
    for (int i = 0; i < message.length - markerSize; i++) {
        for (int j = i; j < i + markerSize; j++) {
            buffer.add(message[j]);
        }
        if (buffer.size() == markerSize) {
            System.out.println(i + markerSize);
            break;
        }
        buffer.clear();
    }
}

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

Добрался до пятого дня AoC. Вообще, по ощущениям, сами алгоритмы пока становятся проще от задачи к задаче. А вот пред-обработка исходных данных начинает требовать времени.

Начальное состояние склада просто захардкодил, слегка покрутив в Calc (для бо́льшего удобства копипаста). В конце заметки приведу некоторые подробности.

Поскольку мутируются стеки ящиков “на месте” – для корректного решения второй части приходится использовать копию начального состояния склада.

static void day5(String puzzleInputUri) throws IOException, InterruptedException {
/*
                [V]     [C]     [M]
[V]     [J]     [N]     [H]     [V]
[R] [F] [N]     [W]     [Z]     [N]
[H] [R] [D]     [Q] [M] [L]     [B]
[B] [C] [H] [V] [R] [C] [G]     [R]
[G] [G] [F] [S] [D] [H] [B] [R] [S]
[D] [N] [S] [D] [H] [G] [J] [J] [G]
[W] [J] [L] [J] [S] [P] [F] [S] [L]
 1   2   3   4   5   6   7   8   9
*/
    Stack<String> stack1 = new Stack<>();
    stack1.addAll(List.of("W","D","G","B","H","R","V"));
    Stack<String> stack2 = new Stack<>();
    stack2.addAll(List.of("J","N","G","C","R","F"));
    Stack<String> stack3 = new Stack<>();
    stack3.addAll(List.of("L","S","F","H","D","N","J"));
    Stack<String> stack4 = new Stack<>();
    stack4.addAll(List.of("J","D","S","V"));
    Stack<String> stack5 = new Stack<>();
    stack5.addAll(List.of("V","S","H","D","R","Q","W","N","V"));
    Stack<String> stack6 = new Stack<>();
    stack6.addAll(List.of("P","G","H","C","M"));
    Stack<String> stack7 = new Stack<>();
    stack7.addAll(List.of("C","F","J","B","G","L","Z","H","C"));
    Stack<String> stack8 = new Stack<>();
    stack8.addAll(List.of("S","J","R"));
    Stack<String> stack9 = new Stack<>();
    stack9.addAll(List.of("M","L","G","S","R","B","N","V","M"));

    Map<Integer, Stack<String>> wareHousePartOne = new TreeMap<>(Map.of(
        1, stack1, 2, stack2, 3, stack3, 4, stack4,
        5, stack5, 6, stack6, 7, stack7, 8, stack8,
        9, stack9
    ));

    Map<Integer, Stack<String>> wareHousePartTwo = new TreeMap<>();
    wareHousePartOne.forEach((stackN, stack) -> {
        var wh2Stack = new Stack<String>();
        wh2Stack.addAll(stack);
        wareHousePartTwo.put(stackN, wh2Stack);
    });

    client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
        .dropWhile(s -> !s.contains("move"))
        .map(s -> s.split(" "))
        .forEach(action -> {
            int count = Integer.parseInt(action[1]);
            int fromStack = Integer.parseInt(action[3]);
            int toStack = Integer.parseInt(action[5]);
            for (int i = 0; i < count; i++) {
                String crate = wareHousePartOne.get(fromStack).pop();
                wareHousePartOne.get(toStack).push(crate);
            }
        });
    StringBuilder upperCrates = new StringBuilder();
    wareHousePartOne.values().forEach(stack -> upperCrates.append(stack.pop()));
    System.out.println(upperCrates);

    client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
        .dropWhile(s -> !s.contains("move"))
        .map(s -> s.split(" "))
        .forEach(action -> {
            int count = Integer.parseInt(action[1]);
            int fromStack = Integer.parseInt(action[3]);
            int toStack = Integer.parseInt(action[5]);
            List<String> cratesBuffer = new ArrayList<>();
            for (int i = 0; i < count; i++) {
                cratesBuffer.add(wareHousePartTwo.get(fromStack).pop());
            }
            Collections.reverse(cratesBuffer);
            cratesBuffer.forEach(crate -> wareHousePartTwo.get(toStack).push(crate));
        });
    StringBuilder upperCratesPartTwo = new StringBuilder();
    wareHousePartTwo.values().forEach(stack -> upperCratesPartTwo.append(stack.pop()));
    System.out.println(upperCratesPartTwo);
}

Либо – просто между вызовами для решения разных частей – поменять внутрянку перестановки ящиков:

List<String> cratesBuffer = new ArrayList<>();
for (int i = 0; i < count; i++) {
    cratesBuffer.add(wareHouse.get(fromStack).pop());
}
Collections.reverse(cratesBuffer);
cratesBuffer.forEach(crate -> wareHouse.get(toStack).push(crate));

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