Архив метки: программирование

Advent of Code 2022: Day 10

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

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

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

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

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

Читать далее Advent of Code 2022: Day 10

Advent of Code 2022: Day 9

Вариация на тему змейки – это любопытно. Задачка решилась бы быстро, если бы не моя невнимательность.

Проклятая невнимательность! Она стоила мне пары часов бесплодных поисков ошибок в формулах перемещения узла.

К счастью, решение второй части не потребовало каких-то кардинальных изменений – просто больше узлов, больше хвостов. Но, сколь веревочке ни виться, – ответ будет найден!

Для начала – сделал узелки – “головы” и “хвосты” (и это я не про самогоноварение сейчас).

class RopeKnot {
    public Set<List<Integer>> visited = new HashSet<>();
    public int x;
    public int y;
}

class Head extends RopeKnot {
    public void doStep(String direction) {
        if ("R".equals(direction)) this.x++;
        if ("L".equals(direction)) this.x--;
        if ("U".equals(direction)) this.y++;
        if ("D".equals(direction)) this.y--;
    }
}

class Tail extends RopeKnot {
    private final RopeKnot head;
    public Tail(RopeKnot head) {
        this.head = head;
    }
    public void doFollow() {
        int dX = head.x - this.x;
        int dY = head.y - this.y;
        if (Math.abs(dX) == 2 && dY == 0) {
            this.x += dX > 0 ? 1 : -1;
        } else if (Math.abs(dY) == 2 && dX == 0) {
            this.y += dY > 0 ? 1 : -1;
        } else if (Math.sqrt(Math.pow(dX, 2) + Math.pow(dY, 2)) > 2d) {
            this.x += dX > 0 ? 1 : -1;
            this.y += dY > 0 ? 1 : -1;
        }
        visited.add(List.of(this.x, this.y));
    }
}

Вот где здесь можно ошибиться? Инкремент, декремент, три вида перемещения – положительно – негде! Однако – именно здесь я и пытался безуспешно найти сбой.

Читать далее Advent of Code 2022: Day 9

Advent of Code 2022: Day 8

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

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

Не то, чтобы это всё пригодилось мне в задаче восьмого дня. Но с тех пор, помучившись с отладкой, я крепко запомнил необходимость тщательной проверки границ массивов. Благодаря чему поймал 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

Advent of Code 2022: Day 7

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

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

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

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

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

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
Читать далее Advent of Code 2022: Day 7

Advent of Code 2022: Day 6

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

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

Но оно сработало, что полностью соответствует духу викторины. Для первой части загадки 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

Advent of Code 2022: Day 5

Добрался до пятого дня 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
Читать далее Advent of Code 2022: Day 5

Advent of Code 2022: Day 4

Задачка, предложенная на четвёртом дне, снова показалась проще предыдущей. Если так пойдёт и дальше – можно успеть нагнать календарь и начать двигаться размеренно, по штуке в день.

Получилось так, что решается она практически целиком – копипастом решения первой половины во вторую (за исключением последнего .map. На циклах можно и не копипастить, пожалуй, но уже сделано так.

Главное – есть верный ответ!

static void day4(String puzzleInputUri) throws IOException, InterruptedException {
    var resultPartOne = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
        .map(pair -> pair.split(","))
        .map(tasks -> {
            String[] taskOneBounds = tasks[0].split("-");
            String[] taskTwoBounds = tasks[1].split("-");
            return Map.entry(
                Map.entry(Integer.parseInt(taskOneBounds[0]), Integer.parseInt(taskOneBounds[1])),
                Map.entry(Integer.parseInt(taskTwoBounds[0]), Integer.parseInt(taskTwoBounds[1]))
            );
        })
        .map(tasks -> Map.entry(
            IntStream.rangeClosed(tasks.getKey().getKey(), tasks.getKey().getValue()).boxed().collect(Collectors.toSet()),
            IntStream.rangeClosed(tasks.getValue().getKey(), tasks.getValue().getValue()).boxed().collect(Collectors.toSet())
        ))
        .map(tasks -> {
            var task1 = new HashSet<>(tasks.getKey());
            var task2 = new HashSet<>(tasks.getValue());
            task1.removeAll(task2);
            tasks.getValue().removeAll(tasks.getKey());
            return task1.isEmpty() || tasks.getValue().isEmpty();
        })
        .filter(included -> included)
        .count();
    System.out.println(resultPartOne);

    var resultPartTwo = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
        .map(pair -> pair.split(","))
        .map(tasks -> {
            String[] taskOneBounds = tasks[0].split("-");
            String[] taskTwoBounds = tasks[1].split("-");
            return Map.entry(
                Map.entry(Integer.parseInt(taskOneBounds[0]), Integer.parseInt(taskOneBounds[1])),
                Map.entry(Integer.parseInt(taskTwoBounds[0]), Integer.parseInt(taskTwoBounds[1]))
            );
        })
        .map(tasks -> Map.entry(
            IntStream.rangeClosed(tasks.getKey().getKey(), tasks.getKey().getValue()).boxed().collect(Collectors.toSet()),
            IntStream.rangeClosed(tasks.getValue().getKey(), tasks.getValue().getValue()).boxed().collect(Collectors.toSet())
        ))
        .map(tasks -> tasks.getKey().stream().anyMatch(taskN -> tasks.getValue().contains(taskN))
            || tasks.getValue().stream().anyMatch(taskN -> tasks.getKey().contains(taskN))
        )
        .filter(cross -> cross)
        .count();
    System.out.println(resultPartTwo);
}
Исходные данные: https://adventofcode.com/2022/day/4/input

Advent of Code 2022: Day 3

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

А вот во второй пришлось вернуться к корням 🙂 Через стрим получался этакий монстроузорный коллектор для группировки по три строки, что ну его на фиг. Через циклы тоже не конфетка, но тут этого и не нужно. Ответ – есть!

static void day3(String puzzleInputUri) throws IOException, InterruptedException {
    int lowerCaseOffset = 96;
    int upperCaseOffset = 38;

    var resultPartOne = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
        .body()
        .map(backpack -> Map.entry(
            Arrays.stream(backpack.substring(0, backpack.length() / 2)
                .split("")).collect(Collectors.toSet()),
            Arrays.stream(backpack.substring(backpack.length() / 2)
                .split("")).collect(Collectors.toSet())
        ))
        .map(pockets -> {
            pockets.getKey().retainAll(pockets.getValue());
            return pockets.getKey();
        })
        .flatMap(Collection::stream)
        .mapToInt(item -> {
            int charCode = item.codePointAt(0);
            return Character.isUpperCase(charCode)
                ? charCode - upperCaseOffset
                : charCode - lowerCaseOffset;
        })
        .sum();
    System.out.println(resultPartOne);

    List<String> src = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
        .body().collect(Collectors.toList());
    Integer resultPartTwo = 0;
    Map<String, Integer> groupOfThree = new HashMap<>();
    for (String backpack : src) {
        if (!groupOfThree.containsValue(3)) {
            for (String item : Arrays.stream(backpack.split("")).collect(Collectors.toSet())) {
                groupOfThree.merge(item, 1, Integer::sum);
            }
        }
        if (groupOfThree.containsValue(3)) {
            resultPartTwo += groupOfThree.entrySet().stream()
                .filter(e -> e.getValue() == 3)
                .map(Entry::getKey)
                .mapToInt(item -> {
                    int charCode = item.codePointAt(0);
                    return Character.isUpperCase(charCode)
                        ? charCode - upperCaseOffset
                        : charCode - lowerCaseOffset;
                })
                .sum();
            groupOfThree = new HashMap<>();
        }
    }
    System.out.println(resultPartTwo);
}
Исходные данные: https://adventofcode.com/2022/day/3/input

Advent of Code 2022: Day 2

Задачка второго дня оказалась повариативней, пришлось искать отдельные решения для первой и второй частей.

Тем не менее – они были найдены, а ответы – получены. Как обычно – решение в виде функции запускается в jshell.

static void day2(String puzzleInputUri) throws IOException, InterruptedException {
/*
rock: A, X
scissors: C, Z
paper:  B, Y
*/
    Map<String, Integer> choiceCosts = Map.of("X", 1, "Y", 2, "Z", 3);
    Map<Integer, Set<String>> strategyCosts = Map.of(
        6, Set.of("A Y", "C X", "B Z"), //win
        3, Set.of("A X", "C Z", "B Y"), //draw
        0, Set.of("A Z", "C Y", "B X") //lose
    );
    Map<String, Set<String>> strategyMappingPartTwo = Map.of(
        "X", strategyCosts.get(0), //lose
        "Y", strategyCosts.get(3), //draw
        "Z", strategyCosts.get(6) //win
    );

    int totalPartOne = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
        .map(round -> Map.entry(round,
            strategyCosts.entrySet().stream().mapToInt(entry -> entry.getValue().contains(round) ? entry.getKey() : 0).sum())
        )
        .mapToInt(roundWithCost -> {
            String choice = roundWithCost.getKey().split(" ")[1];
            return roundWithCost.getValue() + choiceCosts.get(choice);
        })
        .sum();
    System.out.println(totalPartOne);

    int totalPartTwo = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
        .map(round -> round.split(" "))
        .map(choiceAndStrategy -> strategyMappingPartTwo.get(choiceAndStrategy[1]).stream()
            .filter(strategies -> strategies.contains(choiceAndStrategy[0]))
            .findAny()
        )
        .flatMap(Optional::stream)
        .mapToInt(round -> {
            int cost = strategyCosts.entrySet().stream().mapToInt(entry -> entry.getValue().contains(round) ? entry.getKey() : 0).sum();
            return cost + choiceCosts.get(round.split(" ")[1]);
        })
        .sum();
    System.out.println(totalPartTwo);
}
Исходные данные: https://adventofcode.com/2022/day/2/input

P.S. Как же, оказывается, тяжело воспринимается “на слух” непривычный порядок – вместо “камень/ножницы/бумага” в условиях описывается Rock Paper Scissors​ – несколько раз путался при мапинге стратегий, пока комментарий в “правильном” порядке не написал 😀

Advent of Code 2022: Day 1

Итак, простое решение для первого дня Advent of Code 2022 года. Запускается из консоли jshell.

Т.к. лень было что-то специальное изобретать для работы с данными задачи (да и формат AoC этого не предполагает) – сразу решил сложить всё в сортированную коллекцию.

Это пригодилось для второй части задачи – оказалось достаточным просто просуммировать три наибольшие цифры на калькуляторе – и ответ готов!

static void day1(String problemUri) throws IOException, InterruptedException {
    List<List<String>> initial = new ArrayList<>();
    initial.add(new ArrayList<>());
    var result = client.send(request.uri((URI.create(problemUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
        .reduce(initial, (sublist, element) -> {
            if (element.isBlank()) {
                sublist.add(new ArrayList<>());
            } else {
                sublist.get(sublist.size() - 1).add(element);
            }
            return sublist;
        }, (list1, list2) -> emptyList());

    TreeSet<Integer> calories = new TreeSet<>();
    for (var stringList : result) {
        calories.add(stringList.stream()
            .mapToInt(Integer::parseInt)
            .sum()
        );
    }

    System.out.println(calories);
}
Исходные данные: https://adventofcode.com/2022/day/1/input