По двенадцатому дню – сказать особо нечего. Если дни 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, но вовремя присмотрелся к множителям “проверок” и заметил, что все они – простые числа. После этого поиск решения не составил труда.
Источник: Wikipedia
В формате таблицы заметить этот факт гораздо проще. Ну а “обезьян” я захардкодил, чтобы не парсить ввод. Решение этой загадки запускается на 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);
}
Задача десятого дня далась неожиданно просто. Ну, не совсем неожиданно и не совсем просто, будем честны. Но, по сравнению с проклятым “древом седьмого дня” – это было совсем не больно 🙂
Поначалу думал, что получится всё запихать в один длинный и страшный стрим, с кучей таинственных мутаций внутри.
Как-то я делал сервис, реализующий развесистую логику подбора уже не помню чего по куче разных условий – и вот там было именно так. Мапы перетекали в мапы, всё это бесконечно упаковывалось и распаковывалось, подвергалось преобразованиям Шварца (да, корни где-то в Лиспе), и, в качестве вишенки на торте, венчалось самосборным коллектором.
В общем, для такого лучше подошел бы Perl. Или, например, JS. И уже через минуту я бы точно забыл, как это работает.
Вариация на тему змейки – это любопытно. Задачка решилась бы быстро, если бы не моя невнимательность.
Проклятая невнимательность! Она стоила мне пары часов бесплодных поисков ошибок в формулах перемещения узла.
К счастью, решение второй части не потребовало каких-то кардинальных изменений – просто больше узлов, больше хвостов. Но, сколь веревочке ни виться, – ответ будет найден!
Для начала – сделал узелки – “головы” и “хвосты” (и это я не про самогоноварение сейчас).
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));
}
}
Вот где здесь можно ошибиться? Инкремент, декремент, три вида перемещения – положительно – негде! Однако – именно здесь я и пытался безуспешно найти сбой.
После седьмого дня – решение восьмого было, в некотором роде, отдыхом. Хотя “усладой для глаз” его точно не назовёшь – вид оно имеет весьма портяночный.
Когда-то развлекался – делал “крестики-нолики” с полем свободного размера. И для среднего уровня сложности позиция следующего хода компьютера вычислялась сканированием этого самого поля.
Не то, чтобы это всё пригодилось мне в задаче восьмого дня. Но с тех пор, помучившись с отладкой, я крепко запомнил необходимость тщательной проверки границ массивов. Благодаря чему поймал 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());
}
Всё началось с того, что мне совершенно не хотелось строить это дерево (забегая вперёд – всё же пришлось).
После пары неудачных попыток (о которых ниже) – решил хранить эту псевдо-ФС в избыточном виде – получились этакие “мангровые заросли”.
Директории, помимо вложенности в свои родительские каталоги, дублируются на корневом уровне. Таким образом получается без лишних усилий посчитать результат по условиям загадки.
Добрался до пятого дня 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));
Задачка, предложенная на четвёртом дне, снова показалась проще предыдущей. Если так пойдёт и дальше – можно успеть нагнать календарь и начать двигаться размеренно, по штуке в день.
Получилось так, что решается она практически целиком – копипастом решения первой половины во вторую (за исключением последнего .map. На циклах можно и не копипастить, пожалуй, но уже сделано так.
Первая часть задачки из третьего дня оказалась неожиданно простой в решении. По ощущениям – проще заданий дня второго.
А вот во второй пришлось вернуться к корням 🙂 Через стрим получался этакий монстроузорный коллектор для группировки по три строки, что ну его на фиг. Через циклы тоже не конфетка, но тут этого и не нужно. Ответ – есть!
