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

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

Сам алгоритм плетения узлов тоже не поражает сложностью:

static void day9(String puzzleInputUri) throws IOException, InterruptedException { Head h = new Head(); Tail t1 = new Tail(h); List<Tail> knots = new ArrayList<>(List.of(t1)); for (int i = 1; i < 9; i++) { knots.add(new Tail(knots.get(i-1))); } client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body() .map(line -> line.split(" ")) .forEachOrdered(command -> { for (int i = 0; i < Integer.parseInt(command[1]); i++) { h.doStep(command[0]); knots.forEach(tail -> tail.doFollow()); } }); System.out.println(knots.get(0).visited.size()); System.out.println(knots.get(knots.size() - 1).visited.size()); }

Но именно в нём крылась досадная ошибка! Парсинг количества перемещений я скопипастил с решения восьмого дня, и он представлял собой такую конструкцию: command[1].charAt(0) - '0'. Всё это прекрасно работало на тестовом примере и ни в какую не хотело выдавать верный ответ на рабочем наборе данных :(

Проверил на бумажке в клетку несколько перемещений. Распечатал историю движения хвоста. Всё совпадает, всё верно! Уже было думал переписать на вложенных циклах и двигать не «точки по карте», а «карту под точками». К счастью — не пришлось.

Бесплодные мучения продолжались до тех пор, пока я не пролистал весь входной набор и не заметил, наконец (как индеец «Зоркий глаз»), что шаги бывают заданы двузначными числами.

«Эврика!» — воскликнул Архимед. А я воскликнул — «Идиот!». Быстренько поправил парсинг и, с глубоким облегчением, отправил верные ответы на загадку!

#adventofcode #adventofcode2022

4 комментария

import xgboost as xgb

15.12.2022

На самом деле, это мой первый AoC и я разочарован. Задачи не на поиск идеи, а на душный парсинг инпута и обработку кучи случаев (те же задачи на 2д сетке постоянно)

Ответить

Dimio

Автор

У меня тоже первый, пока увлекает. На счет поиска идеи - мне сложно представить задачи подобного содержания при условии сохранения формата AoC.
Ну в смысле - относительно короткие алгоритмические задачки (что тут, что, допустим, литкод/хакеранг и т.п.) - базово уже решены и описаны в учебниках.
Чем мне, кстати, в этом отношении АоС - не надо задрачивать на оптимизацию и можно более творчески подходить к процессу, чем "перепечатка" Кормена/Сэджвика etc.
PS Поисков идей "как из г сделать конфетку за двукратно меньший срок" хватает на работе :)