Spyke
advent_of_code·Advent Of Codebyhades

🦆 Everybody.Codes 2025 Quest 16 Solutions 🦆

Quest 16: Harmonics of Stone

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

Python

def part1(data: str):
    elements = map(int, data.split(','))
    total = 0
    for ele in elements:
        # a spell element will add (90 // number) bricks for 90 columns
        total += 90 // ele
    return total

assert part1("1,2,3,5,9") == 193

# Gets all spell elements needed to build a wall
# Useful for part 2 and part 3
def get_elements(data: str):
    wall = map(int, data.split(','))
    elements = []   # spell elements

    for col_idx, fragments in enumerate(wall):
        # fix for 1-based indexing
        col = col_idx + 1

        # account bricks for recorded elements
        for ele in elements:
            if col % ele == 0:
                fragments -= 1
        
        # if we still have fragments, we need to add a new element with that column number
        if fragments > 0:
            elements.append(col)
    
    return elements

def part2(data: str):
    # Get all spell elements needed to build the wall
    elements = get_elements(data)
    # return product of all elements
    ans = 1
    for ele in elements:
        ans *= ele
    return ans

assert part2("1,2,2,2,2,3,1,2,3,3,1,3,1,2,3,2,1,4,1,3,2,2,1,3,2,2") == 270

# Part 3: Binary Search for maximum full columns
def part3(data: str):
    BRICKS = 202520252025000
    elements = get_elements(data)

    # Check if we can build 'cols' full columns within BRICKS bricks
    def can_build(cols: int) -> bool:
        bricks_used = 0
        for ele in elements:
            bricks_used += cols // ele
            if bricks_used > BRICKS:
                return False
        return True

    # binary search: break on first column size we cannot build
    lo = 1
    hi = BRICKS
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_build(mid):
            lo = mid + 1
        else:
            hi = mid
    
    # if lo is the first we cannot build, lo - 1 is the maximum we can build
    return lo - 1

assert part3("1,2,2,2,2,3,1,2,3,3,1,3,1,2,3,2,1,4,1,3,2,2,1,3,2,2") == 94439495762954
2
hades
programming.dev

Rust

fn build_wall(numbers: &[i64], length: usize) -> Vec<i64> {
    let mut divisors = vec![0; length];
    for n in numbers {
        for (i, d) in divisors.iter_mut().enumerate() {
            if (i + 1) as i64 % n == 0 {
                *d += 1;
            }
        }
    }
    divisors
}

pub fn solve_part_1(input: &str) -> String {
    let numbers = input
        .split(",")
        .map(|n| n.parse::<i64>().unwrap())
        .collect::<Vec<_>>();
    build_wall(&numbers, 90).iter().sum::<i64>().to_string()
}

fn solve(
    divisor_masks: &Vec<Vec<i32>>,
    selected_divisors: Vec<i64>,
    values: &Vec<i64>,
    next_divisor_to_try: i64,
) -> Option<Vec<i64>> {
    if values.iter().all(|v| *v == 0) {
        return Some(selected_divisors);
    }
    if values.iter().any(|v| *v < 0) {
        return None;
    }
    if next_divisor_to_try as usize > values.len() {
        return None;
    }
    let next_values = values
        .iter()
        .zip(divisor_masks[(next_divisor_to_try - 1) as usize].iter())
        .map(|(v, d)| *v - *d as i64)
        .collect();
    let mut next_selected_divisors = selected_divisors.clone();
    next_selected_divisors.push(next_divisor_to_try);
    if let Some(result) = solve(
        &divisor_masks,
        next_selected_divisors,
        &next_values,
        next_divisor_to_try + 1,
    ) {
        return Some(result);
    }
    return solve(
        &divisor_masks,
        selected_divisors,
        &values,
        next_divisor_to_try + 1,
    );
}

pub fn solve_part_2_raw(input: &str) -> Vec<i64> {
    let values = input
        .split(",")
        .map(|n| n.parse::<i64>().unwrap())
        .collect::<Vec<_>>();
    let mut divisor_masks = vec![vec![0; values.len()]; values.len()];
    for (i, mask) in divisor_masks.iter_mut().enumerate() {
        let divisor = i + 1;
        for (j, d) in mask.iter_mut().enumerate() {
            let number = j + 1;
            if number % divisor == 0 {
                *d += 1;
            }
        }
    }
    let result = solve(&divisor_masks, vec![], &values, 1).unwrap();
    result
}

pub fn solve_part_2(input: &str) -> String {
    solve_part_2_raw(input).iter().product::<i64>().to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let divisors = solve_part_2_raw(input);
    let blocks = 202520252025000i64;
    let mut l = 1i64;
    let mut r = 108420091881608i64;
    while r - l > 1 {
        let mid = (r + l) / 2;
        let b = divisors.iter().map(|d| mid / d).sum::<i64>();
        if b > blocks {
            r = mid;
        } else {
            l = mid;
        }
    }
    l.to_string()
}
1
hadesreply
programming.dev

Sadly, every client renders code blocks differently :/ Yours apparently doesn't keep line breaks for some reason. I assume this happens to other posts on programming.dev with code blocks, not just mine, right?

Either way, you can open it on the web to read the code.

1
Lise Andreasenreply
mastodon.world

@hades
My client is called mastodon. I assume it is official in some way.
I don't read a lot of code here.
I don't think there's a link to a site. Oh wait, found it.

1

You reached the end

🦆 Everybody.Codes 2025 Quest 16 Solutions 🦆 | Spyke