Spyke

Replies

Comment on

🦆 Everybody.Codes 2025 Quest 19 Solutions 🦆

Python

The DP solution to go column by column and compute the min flaps for each cell is correct but too slow. Fortunately this problem can be solved using MATH

# Uses math to calculate the minimum number of flaps needed to reach the last passage at any height.
# This solution relies on a couple of facts:
#   1. The number of flaps needed to reach a passage at (x, y) is ceil((x + y) / 2).
#       Proof:
#       - Each flap increases your height by 1 and each glide decreases it by 1
#       - Suppose you flapped f times and covered a horizontal distance of x
#       - So your final height would be y = f - (x - f) = 2f - x
#       - Now suppose a passage at position p_x begins at height p_y. To enter it, your height must be, y >= p_y
#       - Substituting y, 2f - x >= p_y => 2f - p_x >= p_y
#       - Solving for f, f >= (p_x + p_y) / 2
#       - Since f is an integer, f = ceil((p_x + p_y) / 2)
#   2. For each wall, the lowest opening gives the smallest lower bound on the cumulative number of flaps.
#      The maximum of these bounds is necessary because an earlier high wall may require more flaps than the last wall.
#   3. For this input, that maximum lower bound is attainable through all the walls, so it is the optimal answer.
#      This is not true in general: an opening's upper edge or the distance between walls can make the lowest opening unreachable.
def flapsMath(data: str):
    flaps = 0

    passages = [[int(p) for p in passage.split(',')] for passage in data.splitlines()]
    passages.sort(key=lambda p: (p[0], p[1]))  # Sort passages so that we always have the lowest opening first
    last_seen_x = 0

    for x, y, _ in passages:
        if x != last_seen_x:
            last_seen_x = x
            # calculate the minimum number of flaps needed to cross this passage at its lowest opening
            # (x + y + 1) // 2 is equivalent to ceil((x + y) / 2) for integers
            flaps = max(flaps, (x + y + 1) // 2)

    return flaps

Comment on

🦆 Everybody.Codes 2025 Quest 18 Solutions 🦆

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