Снова мартышки — те, да не те. Эти позадорней, поживей, поактивней 🙂 Но решение чем-то схожее — соседи, операции, кидают банан чиселку, занимаются эквилибристикой. Для этой загадки обвязка получилась потолще, конечно.

Мартышкины ужимки

enum Action {
    ADD('+', Long::sum),
    SUBTRACT('-', (op1, op2) -> op1 - op2),
    DIVIDE('/', (op1, op2) -> op1 / op2),
    MULTIPLY('*', (op1, op2) -> op1 * op2);
    final char code;
    final BiFunction<Long, Long, Long> func;
    static final Map<Character, Action> OPS = Arrays.stream(Action.values())
        .collect(Collectors.toUnmodifiableMap(it -> it.code, it -> it));
    Action(char code, BiFunction<Long, Long, Long> func) {
        this.code = code;
        this.func = func;
    }
    BiFunction<Long, Long, Long> invert(boolean isPrev) {
        switch (this) {
            case ADD: return (op1, op2) -> op2 - op1;
            case MULTIPLY: return (op1, op2) -> op2 / op1;
            case SUBTRACT: return isPrev ? ADD.func : this.func;
            case DIVIDE: return isPrev ? MULTIPLY.func : this.func;
            default: return null;
        }
    }
}

Настало Появилось время продолжить AoC за, уже оставшийся в прошлом, 2022 год.

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

Упростить решение помогло наличие библиотечного метода Math.floorMod (про который я вычитал в треде на реддите).

Перемешивание координат

static void mix(List<Map.Entry<Integer, Long>> mixed, List<Map.Entry<Integer, Long>> reference) {
    for (var coordinate : reference) {
        int idx = mixed.indexOf(coordinate);
        mixed.remove(idx);
        int newIdx = Math.floorMod(idx + coordinate.getValue(), mixed.size());
        mixed.add(newIdx, coordinate);
    }
}

ЕМНИП, получилось нечто вроде двойного хэширования. Но с ходу приспособить что-то типа LinkedHashMap для хранения координат не удалось, а дольше искать было лень. Так что — остановился на списках.

Вычисление результата

static void day20(String puzzleInputUri) throws IOException, InterruptedException {
    long key = 811589153; // 1 for part 1
    int mixes = 10; // 1 for part 1

    AtomicInteger idx = new AtomicInteger(0);
    var encrypted = client.send(request.uri((URI.create(puzzleInputUri))).build(), BodyHandlers.ofLines())
        .body()
        .map(coord -> Map.entry(idx.getAndIncrement(), Long.parseLong(coord) * key))
        .collect(Collectors.toList());

    var reference = new ArrayList<>(encrypted);
    for (int i = 0; i < mixes; i++) {
        mix(encrypted, reference);
    }

    encrypted.stream()
        .filter(c -> c.getValue() == 0)
        .findAny()
        .map(encrypted::indexOf)
        .map(startIdx -> IntStream.of(startIdx + 1000, startIdx + 2000, startIdx + 3000)
            .map(i -> i % encrypted.size())
            .mapToLong(i -> encrypted.get(i).getValue())
            .sum()
        )
        .ifPresent(System.out::println);
}

Надеюсь, загадки оставшихся дней будут не сильно сложнее 🙂

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

Тяжело дались мне эти игры в Factorio. Хотя, вроде бы, с виду и похожи на слоновьи пляски на вентилях.

В этой задачке тоже пришлось погуглить подсказки, когда нашел варианты отсечек для рекурсии — дело пошло значительно веселее!

Виновница торжества

static int mostGeodes(int ore, int clay, int obsidian, int geode, int oreBot, int clayBot,
                      int obsidianBot, int geodeBot, int time, int maxTime, int[] botsCost) {
    if (time == maxTime) {
        return geode;
    }
    int oreTotal = ore + oreBot;
    int clayTotal = clay + clayBot;
    int obsidianTotal = obsidian + obsidianBot;
    int geodeTotal = geode + geodeBot;

    if (ore >= botsCost[4] && obsidian >= botsCost[5]) {
        return mostGeodes(oreTotal - botsCost[4], clayTotal, obsidianTotal - botsCost[5],
            geodeTotal, oreBot, clayBot, obsidianBot, geodeBot + 1, time + 1, maxTime, botsCost);
    }
    if (clayBot >= botsCost[3] && obsidianBot < botsCost[5] && ore >= botsCost[2] && clay >= botsCost[3]) {
        return mostGeodes(oreTotal - botsCost[2], clayTotal - botsCost[3], obsidianTotal, geodeTotal,
            oreBot, clayBot, obsidianBot + 1, geodeBot, time + 1, maxTime, botsCost);
    }

    int best = 0;
    if (obsidianBot < botsCost[5] && ore >= botsCost[2] && clay >= botsCost[3]) {
        best = Math.max(best, mostGeodes(oreTotal - botsCost[2], clayTotal - botsCost[3], obsidianTotal,
            geodeTotal, oreBot, clayBot, obsidianBot + 1, geodeBot, time + 1, maxTime, botsCost));
    }
    if (clayBot < botsCost[3] && ore >= botsCost[1]) {
        best = Math.max(best, mostGeodes(oreTotal - botsCost[1], clayTotal, obsidianTotal, geodeTotal, oreBot,
            clayBot + 1, obsidianBot, geodeBot, time + 1, maxTime, botsCost));
    }
    if (oreBot < 4 && ore >= botsCost[0]) {
        best = Math.max(best, mostGeodes(oreTotal - botsCost[0], clayTotal, obsidianTotal, geodeTotal,
            oreBot + 1, clayBot, obsidianBot, geodeBot, time + 1, maxTime, botsCost));
    }
    if (ore <= 4) {
        best = Math.max(best, mostGeodes(oreTotal, clayTotal, obsidianTotal, geodeTotal, oreBot, clayBot, obsidianBot,
            geodeBot, time + 1, maxTime, botsCost));
    }
    return best;
}

Сильно сократила решение

static void day19(String puzzleInputUri) throws IOException, InterruptedException {
    var blueprints = client.send(request.uri((URI.create(puzzleInputUri))).build(), BodyHandlers.ofLines())
        .body()
        .map(blueprint -> Arrays.stream(blueprint.split("[^0-9]+")).skip(1).mapToInt(Integer::parseInt).toArray())
        .collect(Collectors.toList());

    int answer1 = 0;
    int answer2 = 1;
    for (int i = 0; i < blueprints.size(); i++) {
        int[] cost = blueprints.get(i);
        answer1 += cost[0] * mostGeodes(0, 0, 0, 0, 1, 0, 0, 0, 0, 24, Arrays.copyOfRange(cost, 1, cost.length));
        if (i < 3) {
            answer2 *= mostGeodes(0, 0, 0, 0, 1, 0, 0, 0, 0, 32, Arrays.copyOfRange(cost, 1, cost.length));
        }
    }
    System.out.printf("Answer 1: %d %nAnswer 2: %d", answer1, answer2);
}

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

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

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

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

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

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)));
}

Тетрис, больше тетриса! Этот тетрис оказался поголоволомней прошлого. Общая идея была понятна сразу, но «на местности» постоянно вылезали какие-то подводные камешки 🙂

Сначала думал пойти через byte[][], выставляя нужные биты в единицу (на что намекала ширина поля), но закопался в сдвигах (жаль, что ввод не оказался набором сдвиговых операций, или я не разгадал его).

Ну, хотя бы с идеей движения «окном» не промахнулся — во второй части она пригодилась.

Подготовительная работа

enum Move {
    LEFT,
    RIGHT;
    private static final Map<Character, Move> cache = Map.of('<', LEFT, '>', RIGHT);
    static Move of(char code) {
        return cache.get(code);
    }
}

class Triple {
    public int left;
    public int middle;
    public List<Integer> right;
    public Triple(int left, int middle, List<Integer> right) {
        this.left = left;
        this.middle = middle;
        this.right = right;
    }
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        } else if (!(obj instanceof Triple)) {
            return false;
        } else {
            Triple other = (Triple) obj;
            return Objects.equals(left, other.left)
                && Objects.equals(middle, other.middle)
                && Objects.equals(right, other.right);
        }
    }
    public int hashCode() {
        return Objects.hashCode(left) ^ Objects.hashCode(middle)
            ^ Objects.hashCode(right);
    }
}

static boolean hasMove(boolean[][] shape, int x, int y, Map<Integer, boolean[]> rows) {
    for (int yIdx = 0; yIdx < shape.length; yIdx++) {
        int currentY = y + (shape.length - yIdx);
        if (rows.containsKey(currentY)) {
            boolean[] shapeRow = shape[yIdx];
            boolean[] fieldRow = rows.get(currentY);
            for (int xIdx = 0; xIdx < shapeRow.length; xIdx++) {
                if (fieldRow[x + xIdx] && shapeRow[xIdx]) return false;
            }
        }
    }
    return true;
}

Triple позаимствовал в Apache Commons, чтобы не изгаляться с импортом в консольный скрипт.

Пропустил пятнадцатый день. Не осилил… Пока что! Что ж, настало время дня шестнадцатого.

Правда, здесь тоже не обошлось без «помощи зала» — часть решения пришлось подсмотреть в интернете. Иначе упорно не желала разгадываться вторая половина загадки.

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

Следить за котлом!

record Valve(String name, long flow, List<String> linked) {}
record State(Map<String, Long> openValves, Valve player, Valve elephant, long totalFlow) {}

static List<State> openValve(Valve v1, Valve v2, boolean both, Map<String, Valve> valves, State s, long flow) {
    if(v1.flow() > 0 && !s.openValves().containsKey(v1.name()) && (!both || (v2.flow() > 0 && !s.openValves().containsKey(v2.name())))) {
        Map<String, Long> newOpen = new HashMap<>(s.openValves());
        newOpen.put(v1.name(), v1.flow());
        if (both) {
            newOpen.put(v2.name(), v2.flow());
            return List.of(new State(newOpen, v1, v2, flow));
        }
        return v2.linked().stream().map(name -> new State(newOpen, v1, valves.get(name), flow)).collect(Collectors.toList());
    }
    return List.of();
}

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

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

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

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