ChooChooLoco

Advent of Code 2022: Day 16

Пропустил пятнадцатый день. Не осилил… Пока что! Что ж, настало время дня шестнадцатого.
Правда, здесь тоже не обошлось без «помощи зала» — часть решения пришлось подсмотреть в интернете. Иначе упорно не желала разгадываться вторая половина загадки.
В целом — задачи становятся интересней (и парсинг ввода не причиняет неудобств, как бывало). Но и времени занимают ощутимо больше, чем первая десятка.
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 void day16(String puzzleInputUri) throws IOException, InterruptedException {
final Pattern vName = Pattern.compile("([A-Z]{2})");
final Pattern vFlow = Pattern.compile("\\d+");

var valves = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines()).body()
.map(line -> {
List<String> linkedValves = new ArrayList<>();
var nameMatcher = vName.matcher(line);
nameMatcher.find();
String name = nameMatcher.group();
while (nameMatcher.find()) {
linkedValves.add(nameMatcher.group());
}
var flowMatcher = vFlow.matcher(line);
flowMatcher.find();
int flow = Integer.parseInt(flowMatcher.group());
return new Valve(name, flow, linkedValves);
})
.collect(Collectors.toMap(v -> v.name(), v -> v));

// Part 1
Set<State> states = new HashSet<>();
states.add(new State(new HashMap<>(), valves.get("AA"), null, 0));
for (int minutes = 0; minutes < 30; minutes++) {
Set<State> newStates = new HashSet<>();
for(State s : states) {
long flow = s.openValves().values().stream().mapToLong(f -> f).sum() + s.totalFlow();
if(s.player().flow() > 0 && !s.openValves().containsKey(s.player().name())) {
Map<String, Long> newOpen = new HashMap<>(s.openValves());
newOpen.put(s.player().name(), s.player().flow());
newStates.add(new State(newOpen, s.player(), null, flow));
}
s.player().linked().forEach(name -> newStates.add(new State(s.openValves(), valves.get(name), null, flow)));
}
states = newStates;
}
var answer1 = states.stream().mapToLong(State::totalFlow).max().orElseThrow();
System.out.println("Answer 1: " + answer1);
}

#adventofcode #adventofcode_2022 #программирование

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-16.html

Advent of Code 2022: Day 14

Да, «тетрис» был определённо приятней вчерашних «скобочек». И концептуально, и в реализации. Старые-добрые циклы-в-циклах — что может быть лучше!? 🙂
Только циклы, приправленные щепоткой стримов, конечно! Впрочем, попытки решить вторую часть через стрим — не увенчались успехом, увы. Приступ стримоза отступил и циклы вошли в свои права.
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);
}

Капля стримоза
Первая часть загадки через стрим решилась без особых проблем, и даже выглядела не слишком страшно:
var sandCnt = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.mapToInt(scanLine -> drawRock(scanLine, gameField))
.max()
.stream().mapToObj(mY ->
IntStream.rangeClosed(0, gameField.length)
.mapToObj(i -> pourSand(mY, gameField))
.takeWhile(Boolean.TRUE::equals)
.count()
)
.findAny()
.orElseThrow();
System.out.println(sandCnt);
А вот со второй — возникли проблемы. Попытки подсунуть в стрим «пол пещеры» в таком виде:
.peek(maxY -> drawRock( "0," + (maxY + 2) + " -> " + (gameField[0].length - 1) + "," + (maxY + 2), gameField))
не приводили к успеху — ответ никак не сходился. Пришлось вернуться к циклам.

#adventofcode #adventofcode_2022 #программирование

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-14.html

Advent of Code 2022: Day 13

Зря я сетовал на загадку прошлого дня. Ох, зря! Парсинг вот этих вот дурных скобочек-в-скобочках — это было форменно издевательство, помноженное на бесконечное уныние.
Просто весь интерес убивает. После решения, вместо удовольствия — только облегчение с мыслью «Хоть бы никогда больше не встретить подобного» 🙂
Да будь там, допустим, валидный JSON — я бы, пожалуй, сдался, и подключил либу. Но костыли с JSONArray, навскидку, не выглядели проще кастомного решения. Что ж, вот оно.
class PDU implements Comparable<PDU> {
private final List<PDU> child = new ArrayList<>();
private int val = -1;
private boolean isNum = true;
private final String rawValue;
public PDU(String input) {
this.rawValue = input;
if (!input.startsWith("[")) {
val = Integer.parseInt(input);
} else {
input = input.substring(1, input.length() - 1);
int level = 0;
StringBuilder tmp = new StringBuilder();
for (char c : input.toCharArray()) {
if (c == ',' && level == 0) {
child.add(new PDU(tmp.toString()));
tmp = new StringBuilder();
} else {
level += (c == '[') ? 1 : (c == ']') ? -1 : 0;
tmp.append(c);
}
}
if (!tmp.toString().equals("")) {
child.add(new PDU(tmp.toString()));
}
isNum = false;
}
}
@Override
public int compareTo(PDU other) {
if (isNum && other.isNum) {
return Integer.compare(other.val, val);
}
if (!isNum && !other.isNum) {
for (int i = 0; i < Math.min(child.size(), other.child.size()); i++) {
int val = child.get(i).compareTo(other.child.get(i));
if (val != 0) {
return val;
}
}
return other.child.size() - child.size();
}
PDU pdu1 = isNum ? new PDU("[" + val + "]") : this;
PDU pdu2 = other.isNum ? new PDU("[" + other.val + "]") : other;
return pdu1.compareTo(pdu2);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
PDU that = (PDU) o;
return rawValue.equals(that.rawValue);
}
@Override
public int hashCode() {
return Objects.hashCode(rawValue);
}
}
static void day13(String puzzleInputUri) throws IOException, InterruptedException {
String[] packets = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.filter(line -> line.startsWith("["))
.toArray(String[]::new);

int answerPartOne = 0;
List<PDU> broadcast = new ArrayList<>();
for (int i = 0, pairIdx = 1; i < packets.length - 1; i += 2, pairIdx++) {
PDU left = new PDU(packets[i]);
PDU right = new PDU(packets[i+1]);
broadcast.addAll(List.of(left, right));
answerPartOne += left.compareTo(right) > 0 ? pairIdx : 0;
}
System.out.println(answerPartOne);

PDU separator1 = new PDU("[[2]]");
PDU separator2 = new PDU("[[6]]");
broadcast.addAll(List.of(separator1, separator2));
broadcast.sort(Comparator.reverseOrder());
int answerPartTwo = (broadcast.indexOf(separator1) + 1) * (broadcast.indexOf(separator2) + 1);
System.out.println(answerPartTwo);
}
Ладно, спишу это на «несчастливый номер» задачки. Вариация на тему тетриса (из задачи следующего дня) обещает быть интересней.

#adventofcode #adventofcode_2022 #программирование

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-13.html

Advent of Code 2022: Day 12

По двенадцатому дню — сказать особо нечего. Если дни 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 + '}';
}
}
static Vertex findEndPoint(Vertex from, char[][] map) {
Set<Vertex> visited = new HashSet<>();
char endMark = 'E';
char nextTraversableMarkAfter_z = '{';
int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int mapHeight = map.length;
int mapWidth = map[0].length;

Vertex start = new Vertex(from.x, from.y, from.dist, from.height);
Queue<Vertex> queue = new ArrayDeque<>();
queue.add(start);
visited.add(start);

while (!queue.isEmpty()) {
Vertex current = queue.poll();
for (int[] direction : directions) {
int nextX = Math.max(current.x + direction[1], 0);
int nextY = Math.max(current.y + direction[0], 0);
if (nextX < mapWidth && nextY < mapHeight) {
Vertex next = new Vertex(nextX, nextY, current.dist + 1, map[nextY][nextX]);
if (!visited.contains(next) && (next.height - current.height <= 1 || current.height == 'S')) {
if (next.height == endMark) {
map[next.y][next.x] = nextTraversableMarkAfter_z;
continue;
}
if (next.height == nextTraversableMarkAfter_z) {
map[next.y][next.x] = endMark;
return next;
}
queue.add(next);
visited.add(next);
}
}
}
}
return new Vertex(from.x, from.y, from.dist, '#');
}
static void day12(String puzzleInputUri) throws IOException, InterruptedException {
char[][] mapArray = client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.map(String::toCharArray)
.toArray(char[][]::new);

System.out.println("Answer 1: " + findEndPoint(new Vertex(0,20,0, 'S'), mapArray));

Vertex answer2 = IntStream.range(0, mapArray.length)
.mapToObj(y -> Map.entry(y, mapArray[y]))
.flatMap(row -> IntStream.range(0, row.getValue().length)
.mapToObj(x -> Stream.of(new Vertex(x, row.getKey(), 0, row.getValue()[x])))
)
.flatMap(Function.identity())
.filter(vertex ->
Set.of('a', 'S').contains(vertex.height)
&& (
(vertex.x == 0 || vertex.x == mapArray[0].length - 1)
|| (vertex.y == 0 || vertex.y == mapArray.length - 1)
)
)
.map(entrance -> findEndPoint(entrance, mapArray))
.filter(v -> v.height != '#')
.min(Comparator.comparingInt(v -> v.dist))
.orElseThrow();
System.out.println("Answer 2: " + answer2);
}

#adventofcode #adventofcode_2022 #программирование
https://dimio.org/advent-of-code-2022-day-12.html

Advent of Code 2022: Day 11

С задачкой про Бандар-логов я познакомился (и расстался) непосредственно в день её выхода. И, к стыду своему, уже не очень помню подробности.
Под влиянием пресловутого «И так сойдёт!» — совершил ошибку с BigInteger (вероятно, ожидаемую и типовую для этой задачи). Несколько минут, потраченных на просчет первой тысячи «обезьяньих прыжков», ясно показали — это ошибочный путь. Пока не заметил, что множители проверок - простые числа. Ну а «обезьян» я захардкодил, чтобы не парсить ввод. Решение этой загадки запускается на 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)
) // и так далее
));
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);
}

#adventofcode #adventofcode_2022 #программирование

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-11.html

Так вот ты какая — идеальная капча!
Задача десятого дня далась неожиданно просто. Ну, не совсем неожиданно и не совсем просто, будем честны. Но, по сравнению с проклятым «древом седьмого дня» — это было совсем не больно 🙂
Поначалу думал, что получится всё запихать в один длинный и страшный стрим, с кучей таинственных мутаций внутри.
Для такого лучше подошел бы Perl. Или, например, JS. И уже через минуту я бы точно забыл, как это работает.
На джаве всё получилось достаточно стройненько (но очень даже длинненько), не смотря на использование только консоли jshell. Кучка сущностей с описанием системы:

interface SignalTracker {
void track(int rX, int cycle);
}

static class SignalStrengthCounter implements SignalTracker {
private final Set<Integer> cycleToCheck = Set.of(20, 60, 100, 140, 180, 220);
public int strength = 0;
@override
public void track(int rX, int cycle) {
if (cycleToCheck.contains(cycle)) this.strength += rX * cycle;
}
}

static class CRT implements SignalTracker {
private static final int SCREEN_WIDTH = 40;
public final StringBuilder screen = new StringBuilder(System.lineSeparator());
@override
public void track(int ra, int cycle) {
var symbol = cycle % SCREEN_WIDTH;
screen.append(symbol >= ra && symbol <= ra + 2 ? "#" : " ");
if (cycle != 0 && symbol % SCREEN_WIDTH == 0) screen.append(System.lineSeparator());
}
}

enum Operation {
noop(1),
addx(2);
final int busyTime;
Operation(int busyTime) {
this.busyTime = busyTime;
}
}

static class Instruction {
public Operation operation;
int value;
private Instruction(Operation operation, int value) {
this.operation = operation;
this.value = value;
}
static public Instruction parseCommand(String input) {
String[] split = input.split(" ");
int v = split.length > 1 ? Integer.parseInt(split[1]) : 0;
return new Instruction(Operation.valueOf(split[0]), v);
}
}

static class CPU {
private final SignalTracker counter;
private int rX = 1;
private int cycle = 0;
public CPU(SignalTracker c) {
this.counter = c;
}
public void exec(Instruction instruction) {
Operation o = instruction.operation;
this.updateCycle(o);
if (o == Operation.addx) {
rX += instruction.value;
}
}
private void updateCycle(Operation op) {
for (int i = 0; i < op.busyTime; i++) {
cycle++;
counter.track(rX, cycle);
}
}
}

Черту под которыми подводит достаточно простая логика обработки входа:

static void day10(String puzzleInputUri) throws IOException, InterruptedException {
SignalStrengthCounter sigStrength = new SignalStrengthCounter();
CPU cpu = new CPU(sigStrength);
CRT crt = new CRT();
CPU gpu = new CPU(crt);
client.send(request.uri((URI.create(puzzleInputUri))).build(), HttpResponse.BodyHandlers.ofLines())
.body()
.map(Instruction::parseCommand)
.peek(cpu::exec)
.peek(gpu::exec)
.count();

System.out.println(sigStrength.strength);
System.out.println(crt.screen);
}

В итоге получилось заветное слово АБЫРВАЛГ. Шучу — получилось (не менее странное) RZHFGJCB.
С точками в качестве «пустых символов» это выглядело абсолютно нечитаемо, подчеркивания чуть исправили картину, но наилучший эффект и белоснежную улыбку обеспечили самые обыкновенные пробелы!

Кто-нибудь знает, что это может означать? Я тоже понятия не имею 🙂 Наверное, можно было бы поколдовать с escape-символами консоли, но наш девиз — «И так сойдёт!».

#adventofcode #adventofcode_2022 #программирование

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-10.html

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 #adventofcode_2022 #программирование

--- Ссылка на запись ---
https://dimio.org/advent-of-code-2022-day-9.html