Spyke
advent_of_code·Advent Of Codebyhades

🦆 Everybody.Codes 2025 Quest 14 Solutions 🦆

Quest 14: The Game of Light

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

Python

I spent way too long optimizing this solution from ~20s to <1s

# Build grid as list of integers (bitmask for each row)
def build_grid(data: str) -> list[int]:
    grid = []
    for line in data.splitlines():
        row = 0
        for j, cell in enumerate(line):
            if cell == '#':
                row |= (1 << j)
        grid.append(row)
    return grid

# Compute next step of the grid while counting new active cells
# Highly optimized using bitwise operations
def compute_next_step(grid: list[int], m, n):
    next_grid = []
    new_active_cells = 0
    mask = (1 << n) - 1     # mask to keep only n bits

    for i in range(m):
        row_above = grid[i-1] if i > 0 else 0
        row_below = grid[i+1] if i < m - 1 else 0
        
        # Neighbors are diagonal: (i-1, j-1), (i-1, j+1), (i+1, j-1), (i+1, j+1)
        n_above = (row_above << 1) ^ (row_above >> 1)   # above neighbors are odd parity
        n_below = (row_below << 1) ^ (row_below >> 1)   # below neighbors are odd parity
        # total active neighbors are odd parity
        neighbors_xor = n_above ^ n_below
        
        # the rules say a cell becomes active if:
        # - it is currently active, and has an odd number of active neighbors
        # - it is currently inactive, and has an even number of active neighbors
        # this is equivalent to having an even number of (active neighbors + itself)
        # For single bit, equivalent to: ~(self ^ neighbors_xor) & 1
        #   self ^ neighbors_xor = 0 if both are even or both are odd (desired case)
        #   so we negate it to get 1 in desired case
        #   and we apply mask to keep only n bits
        # This is all done in parallel for the entire row using bitwise operations
        next_row = ~(grid[i] ^ neighbors_xor) & mask
        
        next_grid.append(next_row)
        new_active_cells += next_row.bit_count()

    return next_grid, new_active_cells

# Simulate for given rounds and return total active cells
def part1(data: str, rounds = 10):
    grid = build_grid(data)
    m, n = len(grid), data.index('\n')

    total_active = 0
    for _ in range(rounds):
        next_grid, new_active_cells = compute_next_step(grid, m, n)
        total_active += new_active_cells
        grid = next_grid
    return total_active

assert (t := part1(""".#.##.
##..#.
..##.#
.#.##.
.###..
###.##""")) == 200, f"Expected 200 but got {t}"

# part 2 is just part 1 with more rounds
from functools import partial
part2 = partial(part1, rounds=2025)

# Match 8x8 pattern with center of 34x34 grid
def match_pattern(next_grid, pattern_grid):
    for i in range(8):
        # skip first 13 rows and shift right by 13 to align with pattern
        if ((next_grid[i+13] >> 13) & 0xFF) != pattern_grid[i]:
            return False
    return True

def part3(pattern: str):
    pattern_grid = build_grid(pattern)
    grid_size = 34

    rounds = 1000000000
    grid = [0] * grid_size  # we start with an empty 34x34 grid

    seen = set()                    # grids we have seen
    cumu_matches_for_round = [0]    # cumulative matches for each round in the cycle
    cumu_matches = 0                # current cumulative matches

    # Simulate until we find a cycle or reach the rounds limit
    round = 1
    while round <= rounds:
        next_grid, next_actives = compute_next_step(grid, grid_size, grid_size)

        # get current state and check for cycles
        state = tuple(next_grid)
        if state in seen:
            break
        else:
            seen.add(state)
        
        # check for pattern match and update cumulative matches
        if match_pattern(next_grid, pattern_grid):
            cumu_matches += next_actives        
        # store cumulative matches from the start to this round
        cumu_matches_for_round.append(cumu_matches)

        # update variables for next round
        grid = next_grid
        round += 1
    
    # the length of the cycle is round - 1 since we break AFTER detecting a cycle (cycle + 1)
    cycle_len = round - 1
    # the number of full cycles we can fit in rounds
    full_cycles = rounds // cycle_len
    # the total matches from full cycles
    matches = full_cycles * cumu_matches
    # the remaining rounds after full cycles
    matches += cumu_matches_for_round[rounds % cycle_len]

    return matches

assert (t := part3("""#......#
..#..#..
.##..##.
...##...
...##...
.##..##.
..#..#..
#......#""")) == 278388552, f"Expected 278388552 but got {t}"
2
hadesreply
programming.dev

Are you assuming that the cycle will always include the initial state? It does, as it turns out, but that's not really obvious (at least to me) from the problem.

2
Pyroreply
programming.dev

Yes, I'm not sure how to prove it but I had a hunch that was the case. So I initially wrote some code to print the grid right after the cycle is detected and lo and behold, it was the initial state.

2
hades
programming.dev

Rust

Finally caught up with the puzzles.

use std::collections::{HashMap, HashSet};

use itertools::Itertools;

pub fn solve_part_1(input: &str) -> String {
    let mut barrels: HashSet<(isize, isize)> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .filter(|&(_, ch)| ch == '#')
                .map(move |(j, _)| (i as isize, j as isize))
        })
        .collect();
    let max_i = barrels.iter().map(|(i, _)| *i).max().unwrap();
    let max_j = barrels.iter().map(|(_, j)| *j).max().unwrap();
    let mut total_active = 0;
    for _ in 0..10 {
        let mut next_barrels = HashSet::new();
        for i in 0..=max_i {
            for j in 0..=max_j {
                let active_neighbours = [(-1, -1), (1, 1), (-1, 1), (1, -1)]
                    .iter()
                    .filter(|(di, dj)| barrels.contains(&(i + di, j + dj)))
                    .count();
                let will_be_active = if barrels.contains(&(i, j)) {
                    active_neighbours % 2 == 1
                } else {
                    active_neighbours % 2 == 0
                };
                if will_be_active {
                    next_barrels.insert((i, j));
                }
            }
        }
        barrels = next_barrels;
        total_active += barrels.len();
    }
    total_active.to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let mut barrels: HashSet<(isize, isize)> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .filter(|&(_, ch)| ch == '#')
                .map(move |(j, _)| (i as isize, j as isize))
        })
        .collect();
    let max_i = barrels.iter().map(|(i, _)| *i).max().unwrap();
    let max_j = barrels.iter().map(|(_, j)| *j).max().unwrap();
    let mut total_active = 0;
    for _ in 0..2025 {
        let mut next_barrels = HashSet::new();
        for i in 0..=max_i {
            for j in 0..=max_j {
                let active_neighbours = [(-1, -1), (1, 1), (-1, 1), (1, -1)]
                    .iter()
                    .filter(|(di, dj)| barrels.contains(&(i + di, j + dj)))
                    .count();
                let will_be_active = if barrels.contains(&(i, j)) {
                    active_neighbours % 2 == 1
                } else {
                    active_neighbours % 2 == 0
                };
                if will_be_active {
                    next_barrels.insert((i, j));
                }
            }
        }
        barrels = next_barrels;
        total_active += barrels.len();
    }
    total_active.to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let pattern: HashSet<(isize, isize)> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .filter(|&(_, ch)| ch == '#')
                .map(move |(j, _)| (i as isize, j as isize))
        })
        .collect();
    let pattern_max_i = pattern.iter().map(|(i, _)| *i).max().unwrap();
    let pattern_max_j = pattern.iter().map(|(_, j)| *j).max().unwrap();
    assert_eq!(7, pattern_max_i);
    assert_eq!(7, pattern_max_j);
    let mut barrels: HashSet<(isize, isize)> = HashSet::new();
    let max_i = 33;
    let max_j = 33;
    let mut state_map = HashMap::<Vec<(isize, isize)>, usize>::new();
    state_map.insert(vec![], 0);
    let mut current_round = 0;
    let rounds_to_simulate = 1000000000;
    let mut active_tiles_after_rounds = vec![0];
    while current_round < rounds_to_simulate {
        let mut next_barrels = HashSet::new();
        for i in 0..=max_i {
            for j in 0..=max_j {
                let active_neighbours = [(-1, -1), (1, 1), (-1, 1), (1, -1)]
                    .iter()
                    .filter(|(di, dj)| barrels.contains(&(i + di, j + dj)))
                    .count();
                let will_be_active = if barrels.contains(&(i, j)) {
                    active_neighbours % 2 == 1
                } else {
                    active_neighbours % 2 == 0
                };
                if will_be_active {
                    next_barrels.insert((i, j));
                }
            }
        }
        barrels = next_barrels;
        current_round += 1;
        let state_key: Vec<_> = barrels.iter().copied().collect();
        if let Some(&seen_before_after_round) = state_map.get(&state_key) {
            let loop_length = current_round - seen_before_after_round;
            let loops_remaining = (rounds_to_simulate - current_round) / loop_length;
            let iterations_remaining =
                rounds_to_simulate - current_round - (loops_remaining * loop_length);
            return (active_tiles_after_rounds[0..current_round]
                .iter()
                .sum::<usize>()
                + active_tiles_after_rounds[seen_before_after_round..current_round]
                    .iter()
                    .sum::<usize>()
                    * loops_remaining
                + active_tiles_after_rounds
                    [seen_before_after_round..(seen_before_after_round + iterations_remaining)]
                    .iter()
                    .sum::<usize>())
            .to_string();
        }
        state_map.insert(state_key, current_round);
        let does_pattern_match = (13..=20)
            .cartesian_product(13..=20)
            .all(|(i, j)| barrels.contains(&(i, j)) == pattern.contains(&(i - 13, j - 13)));
        active_tiles_after_rounds.push(if does_pattern_match { barrels.len() } else { 0 });
    }
    active_tiles_after_rounds.iter().sum::<usize>().to_string()
}
2

You reached the end

🦆 Everybody.Codes 2025 Quest 14 Solutions 🦆 | Spyke