ChooChooLoco

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

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

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

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

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

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

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>> wareHouse = new TreeMap<>(Map.of(
1, stack1, 2, stack2, 3, stack3, 4, stack4,
5, stack5, 6, stack6, 7, stack7, 8, stack8,
9, stack9
));

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 = wareHouse.get(fromStack).pop();
wareHouse.get(toStack).push(crate);
}
});
StringBuilder upperCrates = new StringBuilder();
wareHouse.values().forEach(stack -> upperCrates.append(stack.pop()));
System.out.println(upperCrates);
}
Для второй части задачи — поменять строки 45-48 на такие:
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));

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

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

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

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

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

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://dimio.org/advent-of-code-2022-day-3.html

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

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

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

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

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

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