Пропустил пятнадцатый день. Не осилил… Пока что! Что ж, настало время дня шестнадцатого.

Правда, здесь тоже не обошлось без “помощи зала” – часть решения пришлось подсмотреть в интернете. Иначе упорно не желала разгадываться вторая половина загадки.

В целом – задачи становятся интересней (и парсинг ввода не причиняет неудобств, как бывало). Но и времени занимают ощутимо больше, чем первая десятка.

Следить за котлом!

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.

Исходные данные: https://adventofcode.com/2022/day/16/input