26
π¨οΈ - 2024 DAY 5 SOLUTIONS - π¨οΈ
(programming.dev)
Java
Part 2 was an interesting one and my solution kinda feels like cheating. What I did I only changed the validation method from part 1 to return the indexes of incorrectly placed pages and then randomly swapped those around in a loop until the validation passed. I was expecting this to not work at all or take forever to run but surprisingly it only takes three to five seconds to complete.
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.stream.Collectors;
public class Day05 {
private static final Random random = new Random();
public static void main(final String[] args) throws IOException {
final String input = Files.readString(Path.of("2024\\05\\input.txt"), StandardCharsets.UTF_8);
final String[] inputSplit = input.split("[\r\n]{4,}");
final List<PageOrderingRule> rules = Arrays.stream(inputSplit[0].split("[\r\n]+"))
.map(row -> row.split("\\|"))
.map(row -> new PageOrderingRule(Integer.parseInt(row[0]), Integer.parseInt(row[1])))
.toList();
final List<ArrayList<Integer>> updates = Arrays.stream(inputSplit[1].split("[\r\n]+"))
.map(row -> row.split(","))
.map(row -> Arrays.stream(row).map(Integer::parseInt).collect(Collectors.toCollection(ArrayList::new)))
.toList();
System.out.println("Part 1: " + updates.stream()
.filter(update -> validate(update, rules).isEmpty())
.mapToInt(update -> update.get(update.size() / 2))
.sum()
);
System.out.println("Part 2: " + updates.stream()
.filter(update -> !validate(update, rules).isEmpty())
.map(update -> fixOrder(update, rules))
.mapToInt(update -> update.get(update.size() / 2))
.sum()
);
}
private static Set<Integer> validate(final List<Integer> update, final List<PageOrderingRule> rules) {
final Set<Integer> invalidIndexes = new HashSet<>();
for (int i = 0; i < update.size(); i++) {
final Integer integer = update.get(i);
for (final PageOrderingRule rule : rules) {
if (rule.x == integer && update.contains(rule.y) && i > update.indexOf(rule.y)) {
invalidIndexes.add(i);
}
else if (rule.y == integer && update.contains(rule.x) && i < update.indexOf(rule.x)) {
invalidIndexes.add(i);
}
}
}
return invalidIndexes;
}
private static List<Integer> fixOrder(final List<Integer> update, final List<PageOrderingRule> rules) {
List<Integer> invalidIndexesList = new ArrayList<>(validate(update, rules));
// Swap randomly until the validation passes
while (!invalidIndexesList.isEmpty()) {
Collections.swap(update, random.nextInt(invalidIndexesList.size()), random.nextInt(invalidIndexesList.size()));
invalidIndexesList = new ArrayList<>(validate(update, rules));
}
return update;
}
private static record PageOrderingRule(int x, int y) {}
}