Spyke
advent_of_code·Advent Of Codebyhades

🦆 Everybody.Codes 2025 Quest 11 Solutions 🦆

Quest 11: The Scout Duck Protocol

  • 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
4
Comments2
Pyro
programming.dev

Python

Since, an optimized phase 2 is enough to solve p2 and p3, I did not optimize any further.

import math

# Brute-force phase one
#   Simulate all phase one rounds until no more moves can be made or max rounds reached
def phase_one(ducks: list[int], max_rounds: int) -> int:
    n = len(ducks)
    round = 1

    while round <= max_rounds:
        moved = False
        for i in range(n - 1):
            if ducks[i] > ducks[i + 1]:
                ducks[i] -= 1
                ducks[i + 1] += 1
                moved = True
        if not moved:
            break
        round += 1
    return round - 1

# Brute-force phase two
#   Simulate all phase two rounds until no more moves can be made or max rounds reached
def phase_two(ducks: list[int], max_rounds: int) -> int:
    n = len(ducks)
    round = 1

    while round <= max_rounds:
        moved = False
        for i in range(n - 1):
            if ducks[i] < ducks[i + 1]:
                ducks[i] += 1
                ducks[i + 1] -= 1
                moved = True
        if not moved:
            break
        round += 1
    return round - 1

# Optimized phase two for limitless rounds
#   Every round will move one duck from every duck above average to below average
#   So the resulting number of rounds is simply the total number of ducks above average
#   Inversely, you can also total the number of ducks below average
def phase_two_limitless(ducks: list[int]) -> int:
    avg = 0
    for i, d in enumerate(ducks):
        avg += (d - avg) / (i + 1)
    avg = round(avg)

    rounds = sum(x - avg for x in ducks if x > avg)
    return rounds

# Balance ducks through both phases, respecting max rounds
def balance_ducks(ducks: list[int], max_rounds: int) -> int:
    rounds1 = phase_one(ducks, max_rounds)
    # if the number of rounds is unbounded, use the optimized phase two
    if max_rounds < math.inf:
        rounds2 = phase_two(ducks, max_rounds - rounds1)
    else:
        rounds2 = phase_two_limitless(ducks)
    return rounds1 + rounds2

# Calculate checksum of the ducks
def calculate_checksum(ducks: list[int]) -> int:
    n = len(ducks)
    checksum = sum((i + 1) * ducks[i] for i in range(n))
    return checksum

# Brute-force both phases
def part1(data: str):
    ducks = [int(d) for d in data.splitlines()]
    balance_ducks(ducks, 10)
    return calculate_checksum(ducks)

# <asserts snipped>

# Brute-force phase one, use optimized phase two
def part2(data: str):
    ducks = [int(d) for d in data.splitlines()]
    rounds = balance_ducks(ducks, math.inf)  # type: ignore
    return rounds

# <asserts snipped>

# You can use the same function for p2 and p3
part3 = part2
2
hades
programming.dev

Rust

I hate when you need to look at the data to solve a simpler subclass of the problem.

use num::Integer;

fn one_round(columns: &mut [i64], forward: bool) -> bool {
    let mut modified = false;
    for i in 1..columns.len() {
        if forward {
            if columns[i - 1] > columns[i] {
                columns[i - 1] -= 1;
                columns[i] += 1;
                modified = true;
            }
        } else if columns[i - 1] < columns[i] {
            columns[i - 1] += 1;
            columns[i] -= 1;
            modified = true;
        }
    }
    modified
}

pub fn solve_part_1(input: &str) -> String {
    let mut columns = input
        .lines()
        .map(|l| l.parse().unwrap())
        .collect::<Vec<i64>>();
    let mut rounds_remaining = 10;
    while rounds_remaining > 0 {
        if one_round(&mut columns, true) {
            rounds_remaining -= 1;
        } else {
            break;
        }
    }
    while rounds_remaining > 0 {
        if one_round(&mut columns, false) {
            rounds_remaining -= 1;
        } else {
            break;
        }
    }
    columns
        .iter()
        .enumerate()
        .map(|(column_idx, count)| (column_idx + 1) as i64 * *count)
        .sum::<i64>()
        .to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let mut columns = input
        .lines()
        .map(|l| l.parse().unwrap())
        .collect::<Vec<i64>>();
    let mut total_rounds = 0;
    loop {
        if one_round(&mut columns, true) {
            total_rounds += 1;
        } else {
            break;
        }
    }
    loop {
        if one_round(&mut columns, false) {
            total_rounds += 1;
        } else {
            break;
        }
    }
    total_rounds.to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let mut columns = input
        .lines()
        .map(|l| l.parse().unwrap())
        .collect::<Vec<i64>>();
    let invariant_sum = columns.iter().sum::<i64>();
    let mut total_rounds = 0i64;
    loop {
        let first_gap = (0..columns.len() - 1).find(|&i| columns[i].abs_diff(columns[i + 1]) > 1);
        let last_gap = (0..columns.len() - 1)
            .filter(|&i| columns[i].abs_diff(columns[i + 1]) > 1)
            .next_back();
        if let (Some(first_gap), Some(last_gap)) = (first_gap, last_gap)
            && (last_gap > first_gap)
        {
            let amount_to_fill: i64 = columns
                .iter()
                .take(first_gap + 1)
                .map(|&x| columns[first_gap + 1] - x)
                .sum();
            let amount_available: i64 = columns
                .iter()
                .skip(last_gap + 1)
                .map(|&x| x - columns[last_gap])
                .sum();
            let amount_to_transfer = amount_to_fill.min(amount_available);
            let new_amount_left: i64 =
                columns.iter().take(first_gap + 1).sum::<i64>() + amount_to_transfer;
            let (left_base, remainder) = new_amount_left.div_rem(&((first_gap + 1) as i64));
            for (i, new_value) in columns.iter_mut().enumerate().take(first_gap + 1) {
                *new_value = left_base
                    + if first_gap - i < remainder as usize {
                        1
                    } else {
                        0
                    };
            }
            let new_amount_right: i64 =
                columns.iter().skip(last_gap + 1).sum::<i64>() - amount_to_transfer;
            let (right_base, remainder) =
                new_amount_right.div_rem(&((columns.len() - last_gap - 1) as i64));
            for i in last_gap + 1..columns.len() {
                columns[i] = right_base
                    + if columns.len() - i <= remainder as usize {
                        1
                    } else {
                        0
                    };
            }
            assert_eq!(invariant_sum, columns.iter().sum::<i64>());
            total_rounds += amount_to_transfer;
        } else {
            break;
        }
    }
    loop {
        if one_round(&mut columns, false) {
            total_rounds += 1;
        } else {
            break;
        }
    }
    total_rounds.to_string()
}
1

You reached the end