🦆 Everybody.Codes 2025 Quest 19 Solutions 🦆

Syndicated from the fediverse. Read and engage on the original instance.

View original on programming.dev

advent_of_code·Advent Of Codebyhades

🦆 Everybody.Codes 2025 Quest 19 Solutions 🦆

Quest 19: Flappy Quack

Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

Link to participate: https://everybody.codes/

View original on programming.dev

Comments2

2 replies

Pyro

programming.dev

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

hades

programming.dev

Rust

Shortest solution so far.

use std::collections::{BTreeMap};

use interval::{
    IntervalSet,
    ops::Range,
    prelude::{Bounded, Empty, Intersection, Union},
};

pub fn solve_part_1(input: &str) -> String {
    let mut data = BTreeMap::new();
    for v in input.lines().map(|l| {
        l.split(",")
            .map(|v| v.parse().unwrap())
            .collect::<Vec<i64>>()
    }) {
        data.entry(v[0]).or_insert(vec![]).push((v[1], v[2]));
    }
    let mut y_ranges = IntervalSet::new(0, 0);
    let mut x = 0;
    for (wall_x, openings) in data.into_iter() {
        let dx = wall_x - x;
        let mut new_ranges = IntervalSet::empty();
        for interval in y_ranges.into_iter() {
            new_ranges = new_ranges.union(&IntervalSet::new(
                interval.lower() - dx,
                interval.upper() + dx,
            ));
        }
        let mut openings_intervalset = IntervalSet::empty();
        for (opening_start, opening_size) in openings {
            openings_intervalset = openings_intervalset.union(&IntervalSet::new(
                opening_start,
                opening_start + opening_size - 1,
            ));
        }
        y_ranges = new_ranges.intersection(&openings_intervalset);
        x = wall_x;
    }
    let y = y_ranges
        .iter()
        .flat_map(|i| (i.lower()..=i.upper()))
        .find(|y| y % 2 == x % 2)
        .unwrap();
    ((y + x) / 2).to_string()
}

pub fn solve_part_2(input: &str) -> String {
    solve_part_1(input)
}
pub fn solve_part_3(input: &str) -> String {
    solve_part_1(input)
}