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);
// Part 2
Set<String> useful = valves.values().stream().filter(valve -> valve.flow() > 0).map(Valve::name).collect(Collectors.toSet());
states.clear();
states.add(new State(new HashMap<>(), valves.get("AA"), valves.get("AA"), 0));
Map<Integer, Long> kpis = Map.of(5, 25L, 10, 50L, 15, 100L, 20, 140L, 25, 160L);
for(int minutes = 0; minutes < 26; minutes++) {
Set<State> newStates = new HashSet<>();
for(State s : states) {
long flow = s.openValves().values().stream().mapToLong(f -> f).sum() + s.totalFlow();
if(s.openValves().size() == useful.size()) {
newStates.add(new State(s.openValves(), valves.get("AA"), valves.get("AA"), flow));
}
int openedValves = newStates.size();
newStates.addAll(openValve(s.player(), s.elephant(), false, valves, s, flow));
newStates.addAll(openValve(s.elephant(), s.player(), false, valves, s, flow));
newStates.addAll(openValve(s.player(), s.elephant(), true, valves, s, flow));
if(openedValves == newStates.size()) {
IntStream.range(0, s.player().linked().size()).boxed()
.flatMap(i -> s.elephant().linked().stream()
.map(l -> Map.entry(s.player().linked().get(i), l))
).forEach(valvesPair -> newStates.add(
new State(s.openValves(), valves.get(valvesPair.getKey()), valves.get(valvesPair.getValue()), flow)
));
}
}
states = newStates;
if (kpis.containsKey(minutes)){
long kpi = kpis.get(minutes);
states = states.stream().filter(
s -> s.openValves().values().stream().mapToLong(f -> f).sum() >= kpi
).collect(Collectors.toSet());
}
}
var answer2 = states.stream().mapToLong(State::totalFlow).max().orElseThrow();
System.out.println("Answer 2: " + answer2);
}
Особенно выручила позаимствованная идея с Map<Integer, Long> kpis — с ней вторая часть загадки считалась примерно за 3 минуты, а без неё — падала с OOM минут через 12
Начать дискуссию