Python

Couldn’t finish the series when it was released but I’m returning to finish it now. The set of free branches of part3 is too large for brute-force but you can exploit the quirk in the input where each free branch only contributes positively or negatively.

from collections import defaultdict
from dataclasses import dataclass
import re

# regex to match numbers in the input data
MATCH_NUMS_PATTERN = re.compile(r"(-?\d+)")

# Plant state class
@dataclass
class Plant:
    id: int
    thickness: int
    # is_free indicates whether the plant has a free branch.
    # it is also used to turn the effect of free branches on or off.
    is_free: bool = False

# Parses the plant input data into a list of Plant objects and a graph representing the connections between plants
# The graph root is the the final plant and the leaves are the free branches. 
def parse_plants(data: str):
    plants: list[Plant] = []
    graph = defaultdict(list)

    # Divide the input into blocks for each plant
    for block in data.split("\n\n"):
        # line iterator to control consumption of lines in the block 
        lines_iter = iter(block.splitlines())

        # get the plant's id and thickness from the first line of the block
        id, thickness = map(int, re.findall(MATCH_NUMS_PATTERN, next(lines_iter)))
        curr_plant = Plant(id, thickness)
        plants.append(curr_plant)

        # parse the remaining lines in the block to get the plant's branches
        for line in lines_iter:
            if line.startswith("- free"):
                curr_plant.is_free = True
            else:
                from_plant, thickness = map(int, re.findall(MATCH_NUMS_PATTERN, line))
                graph[curr_plant.id].append((from_plant, thickness))
    
    return plants, graph

# Recursively calculates the energy for a given plant.
# Naive implementation with no memoization, but enough for the input size.
def get_energy_at(plants: list[Plant], graph: dict[int, list[tuple[int, int]]], plant_id: int):
    plant: Plant = plants[plant_id-1]
    energy = 0

    # if the plant has a free branch, its energy is equal to its thickness.
    # otherwise, its energy is the sum of the incoming energy from its branches, multiplied by the thickness of each branch.
    if plant.is_free:
        energy = plant.thickness
    else:
        for from_plant, thickness in graph[plant_id]:
            energy += thickness * get_energy_at(plants, graph, from_plant)

    # energy only moves through the plant if it is less than or equal to the plant's thickness.
    return energy if plant.thickness <= energy else 0

# Part 1 is simple: just calculate the energy at the final plant with all free branches on.
def part1(data: str) -> int:
    plants, graph = parse_plants(data)
    return get_energy_at(plants, graph, len(plants))

# Part 2: use the boolean data to turn free branches on or off and calculate the energy at the final plant for each configuration.
def part2(data: str) -> int:
    # split the input data into plant data and boolean data
    plant_data, bool_data = data.split("\n\n\n")
    plants, graph = parse_plants(plant_data)

    all_energy = 0
    for line in bool_data.splitlines():
        # transform the boolean string into a list of integers and set the is_free attribute of each plant accordingly
        bools = map(int, line.split(' '))
        for i, b in enumerate(bools):
            plants[i].is_free = b == 1

        all_energy += get_energy_at(plants, graph, len(plants))
    return all_energy

# Part 3: calculate the maximum possible energy at the final plant, 
#   then calculate the cumulative difference in energy between the maximum and each provided configuration of free branches.
# To calculate the maximum possible energy:
#   First, I tried to progressively turn free plants off or on but that doesn't work and the energy stays at 0
#   Since this is a set of constraints, this can be solved by SMT solvers like z3
#   However, there is a quirk in the input data that allows for a simpler solution:
#       Each free branch contributes either positively or negatively ONLY
#       So we can simply turn off all free branches that contribute negatively and get the max energy.
# I don't like this solution because it relies on a quirk in the input data and doesn't work for all inputs,
#   even the sample data
def part3(data: str) -> int:
    # split the input data into plant data and boolean data
    plant_data, bool_data = data.split("\n\n\n")
    plants, graph = parse_plants(plant_data)

    # calculate the contribution of each free branch
    plant_contrib = defaultdict(int)
    for plant in plants:
        # free branches won't have any outgoing edges
        if plant.is_free:
            continue

        # for a non-leaf plant, we cumulate the contribution of each of its free branches
        for from_plant, thickness in graph[plant.id]:
            if not plants[from_plant-1].is_free:
                continue

            # assert our assumption about the input data that 
            #   each free branch contributes either positively or negatively ONLY
            if plant_contrib[from_plant]:
                assert (plant_contrib[from_plant] < 0) == (thickness < 0), (
                    "this approach only works if all free branches contribute "
                    "either positively or negatively ONLY"
                )
            
            plant_contrib[from_plant] += thickness

    # turn off all free branches that contribute negatively
    for id, contrib in plant_contrib.items():
        if contrib >= 0:
            continue
        plants[id-1].is_free = False

    # get max energy for this configuration
    max_energy = get_energy_at(plants, graph, len(plants))

    # calculate the cumulative difference in energy between the maximum and 
    #   each provided configuration of free branches.
    energy_diff = 0
    for line in bool_data.splitlines():
        bools = map(int, line.split(' '))
        for i, b in enumerate(bools):
            plants[i].is_free = b == 1

        dd_energy = get_energy_at(plants, graph, len(plants))
        # we skip configurations that do not activate the final plant
        if dd_energy == 0:
            continue
        energy_diff += max_energy - dd_energy
    
    return energy_diff

Rust

use regex::Regex;
use z3::{
    Optimize, Params,
    ast::{Bool, Int},
};

#[derive(Default)]
struct Plant {
    thickness: i64,
    free: Option<i64>,
    connected: Vec<(usize, i64)>,
}

fn parse_plant_spec(input: &str) -> Plant {
    let mut result = Plant::default();
    let first_re = Regex::new(r"Plant \d+ with thickness (\d+):").unwrap();
    let free_re = Regex::new(r"- free branch with thickness (\d+)").unwrap();
    let branch_re = Regex::new(r"- branch to Plant (\d+) with thickness (-?\d+)").unwrap();
    for line in input.lines() {
        if let Some((_, [thickness])) = first_re.captures(line).map(|c| c.extract()) {
            result.thickness = thickness.parse().unwrap();
        } else if let Some((_, [thickness])) = free_re.captures(line).map(|c| c.extract()) {
            result.free = Some(thickness.parse().unwrap());
        } else if let Some((_, [plant, thickness])) = branch_re.captures(line).map(|c| c.extract())
        {
            result
                .connected
                .push((plant.parse().unwrap(), thickness.parse().unwrap()));
        } else {
            panic!("cannot parse line: {line}");
        }
    }
    result
}

fn eval_plant(plants: &[Plant], number: usize, free_branches: &[i64]) -> i64 {
    let plant = &plants[number - 1];
    if plant.free.is_some() {
        assert_eq!(1, plant.thickness);
        assert_eq!(1, plant.free.unwrap());
        free_branches[number - 1]
    } else {
        let incoming = plant
            .connected
            .iter()
            .map(|&(plant_number, branch_thickness)| {
                eval_plant(plants, plant_number, free_branches) * branch_thickness
            })
            .sum::<i64>();
        if incoming >= plant.thickness {
            incoming
        } else {
            0
        }
    }
}

pub fn solve_part_1(input: &str) -> String {
    let plants = input
        .split("\n\n")
        .map(parse_plant_spec)
        .collect::<Vec<_>>();
    eval_plant(&plants, plants.len(), &vec![1; plants.len()]).to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let (plants, tests) = input.split_once("\n\n\n").unwrap();
    let plants = plants
        .split("\n\n")
        .map(parse_plant_spec)
        .collect::<Vec<_>>();
    tests
        .lines()
        .map(|test| {
            eval_plant(
                &plants,
                plants.len(),
                &test
                    .split(" ")
                    .map(|v| v.parse().unwrap())
                    .collect::<Vec<i64>>(),
            )
        })
        .sum::<i64>()
        .to_string()
}

fn eval_plant_z3(plants: &[Plant], number: usize, free_branches: &[Option<Bool>]) -> Int {
    let plant = &plants[number - 1];
    if plant.free.is_some() {
        assert_eq!(1, plant.thickness);
        assert_eq!(1, plant.free.unwrap());
        free_branches[number - 1]
            .as_ref()
            .unwrap()
            .ite(&Int::from_i64(1), &Int::from_i64(0))
    } else {
        let incoming = plant
            .connected
            .iter()
            .map(|&(plant_number, branch_thickness)| {
                eval_plant_z3(plants, plant_number, free_branches) * Int::from_i64(branch_thickness)
            })
            .reduce(|a, b| a + b);
        let incoming = incoming.unwrap_or_else(|| Int::from_i64(0));
        incoming
            .ge(Int::from_i64(plant.thickness))
            .ite(&incoming, &Int::from_i64(0))
    }
}

fn maximum_achievable_brightness(plants: &[Plant]) -> i64 {
    let mut free_branches = vec![None; plants.len()];
    plants.iter().enumerate().for_each(|(i, p)| {
        if p.free.is_some() {
            free_branches[i] = Some(Bool::fresh_const("free"));
        }
    });
    let solver = Optimize::new();
    let mut params = Params::new();
    params.set_symbol("opt.maxsat_engine", "wmax");
    solver.set_params(&params);
    let brightness = eval_plant_z3(plants, plants.len(), &free_branches);
    solver.maximize(&brightness);
    match solver.check(&[]) {
        z3::SatResult::Sat => solver
            .get_model()
            .unwrap()
            .eval(&brightness, true)
            .unwrap()
            .as_i64()
            .unwrap(),
        _ => panic!("unsat"),
    }
}

pub fn solve_part_3(input: &str) -> String {
    let (plants, tests) = input.split_once("\n\n\n").unwrap();
    let plants = plants
        .split("\n\n")
        .map(parse_plant_spec)
        .collect::<Vec<_>>();
    let maximum = maximum_achievable_brightness(&plants);
    tests
        .lines()
        .map(|test| {
            eval_plant(
                &plants,
                plants.len(),
                &test
                    .split(" ")
                    .map(|v| v.parse().unwrap())
                    .collect::<Vec<i64>>(),
            )
        })
        .map(|v| if v > 0 { maximum - v } else { 0 })
        .sum::<i64>()
        .to_string()
}