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()
}

union find: nice! I was too lazy to use union find, so I brute forced merging of the families, it was fast enough :)

good job! yeah it doesn't matter what you do if you need to scan the entire state space :)

You even have comments, very nice!

Rust

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

use itertools::Itertools;

fn explode_from_barrel(
    map: &HashMap<(isize, isize), i8>,
    mut exploded: HashSet<(isize, isize)>,
    mut front: HashSet<(isize, isize)>,
) -> HashSet<(isize, isize)> {
    while !front.is_empty() {
        let mut next_front = HashSet::new();
        for (i, j) in front.drain() {
            exploded.insert((i, j));
            let my_size = map[&(i, j)];
            for (di, dj) in [(-1, 0), (0, -1), (0, 1), (1, 0)] {
                let (ni, nj) = (i + di, j + dj);
                if exploded.contains(&(ni, nj)) {
                    continue;
                }
                if let Some(neighour_size) = map.get(&(ni, nj))
                    && *neighour_size <= my_size
                {
                    next_front.insert((ni, nj));
                }
            }
        }
        front = next_front;
    }
    exploded
}

pub fn solve_part_1(input: &str) -> String {
    let map: HashMap<(isize, isize), i8> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .map(move |(j, ch)| ((i as isize, j as isize), ch as i8 - '0' as i8))
        })
        .collect();
    let exploded = HashSet::<(isize, isize)>::new();
    let front: HashSet<(isize, isize)> = [(0, 0)].into_iter().collect();
    explode_from_barrel(&map, exploded, front).len().to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let map: HashMap<(isize, isize), i8> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .map(move |(j, ch)| ((i as isize, j as isize), ch as i8 - '0' as i8))
        })
        .collect();
    let exploded = HashSet::<(isize, isize)>::new();
    let max_i = map.keys().map(|(i, _)| *i).max().unwrap();
    let max_j = map.keys().map(|(_, j)| *j).max().unwrap();
    let front: HashSet<(isize, isize)> = [(0, 0), (max_i, max_j)].into_iter().collect();
    explode_from_barrel(&map, exploded, front).len().to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let map: HashMap<(isize, isize), i8> = input
        .lines()
        .enumerate()
        .flat_map(|(i, line)| {
            line.chars()
                .enumerate()
                .map(move |(j, ch)| ((i as isize, j as isize), ch as i8 - '0' as i8))
        })
        .collect();
    let max_i = map.keys().map(|(i, _)| *i).max().unwrap();
    let max_j = map.keys().map(|(_, j)| *j).max().unwrap();
    let best_barrel = (0..=max_i)
        .cartesian_product(0..=max_j)
        .map(|(i, j)| {
            ((i, j), {
                let exploded = HashSet::<(isize, isize)>::new();
                let front: HashSet<(isize, isize)> = [(i, j)].into_iter().collect();
                explode_from_barrel(&map, exploded, front)
            })
        })
        .max_by_key(|(_, exploded)| exploded.len())
        .unwrap();
    let second_best_barrel = (0..=max_i)
        .cartesian_product(0..=max_j)
        .filter(|&(i, j)| !best_barrel.1.contains(&(i, j)))
        .map(|(i, j)| {
            ((i, j), {
                let exploded = best_barrel.1.clone();
                let front: HashSet<(isize, isize)> = [(i, j)].into_iter().collect();
                explode_from_barrel(&map, exploded, front)
            })
        })
        .max_by_key(|(_, exploded)| exploded.len())
        .unwrap();
    let third_best_barrel = (0..=max_i)
        .cartesian_product(0..=max_j)
        .filter(|&(i, j)| !second_best_barrel.1.contains(&(i, j)))
        .map(|(i, j)| {
            ((i, j), {
                let exploded = second_best_barrel.1.clone();
                let front: HashSet<(isize, isize)> = [(i, j)].into_iter().collect();
                explode_from_barrel(&map, exploded, front)
            })
        })
        .max_by_key(|(_, exploded)| exploded.len())
        .unwrap();
    let exploded = HashSet::<(isize, isize)>::new();
    let front: HashSet<(isize, isize)> = [best_barrel.0, second_best_barrel.0, third_best_barrel.0]
        .into_iter()
        .collect();
    explode_from_barrel(&map, exploded, front).len().to_string()
}

Rust

pub fn solve_part_1(input: &str) -> String {
    let numbers = input
        .lines()
        .map(|l| l.parse().unwrap())
        .collect::<Vec<i64>>();
    let offset = 2025 % (numbers.len() + 1);
    if offset == 0 {
        1
    } else if offset > numbers.len().div_ceil(2) {
        numbers[(numbers.len() - offset) * 2 + 1]
    } else {
        numbers[(offset - 1) * 2]
    }
    .to_string()
}

fn find_number(ranges: &[(i64, i64)], mut offset: i64, counterclockwise: bool) -> i64 {
    for (from, to) in ranges {
        let segment_size = (to - from) + 1;
        if offset >= segment_size {
            offset -= segment_size;
            continue;
        }
        return if counterclockwise {
            to - offset
        } else {
            from + offset
        };
    }
    panic!("find_number gave up and died");
}

fn solve_part_2_with_turns(input: &str, turns: i64) -> String {
    let ranges = input
        .lines()
        .map(|l| {
            let (l, r) = l.split_once("-").unwrap();
            (l.parse().unwrap(), r.parse().unwrap())
        })
        .collect::<Vec<(i64, i64)>>();
    let mut clockwise_length = 0;
    let mut clockwise_ranges = vec![];
    let mut counterclockwise_length = 0;
    let mut counterclockwise_ranges = vec![];
    for (i, (from, to)) in ranges.into_iter().enumerate() {
        if i % 2 == 0 {
            clockwise_length += to - from + 1;
            clockwise_ranges.push((from, to));
        } else {
            counterclockwise_length += to - from + 1;
            counterclockwise_ranges.push((from, to));
        }
    }
    counterclockwise_ranges.reverse();
    let offset = turns % (clockwise_length + counterclockwise_length + 1);
    if offset == 0 {
        1
    } else if offset > clockwise_length {
        find_number(
            &counterclockwise_ranges,
            offset - clockwise_length - 1,
            true,
        )
    } else {
        find_number(&clockwise_ranges, offset - 1, false)
    }
    .to_string()
}

pub fn solve_part_2(input: &str) -> String {
    solve_part_2_with_turns(input, 20252025)
}

pub fn solve_part_3(input: &str) -> String {
    solve_part_2_with_turns(input, 202520252025)
}

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()
}

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()
}

That chars() call hides a lot of complexity, but also even that might not be correct depending on what exactly you mean by “reversing a string”.

Thank you for watching the video and answering the question that I had from just reading the title.

Reversing a UTF-8 string is super hard in any language, rust doesn’t really make it that much harder.

Rust

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

use itertools::Itertools;

pub fn solve_part_1(input: &str) -> String {
    let board: Vec<Vec<_>> = input.lines().map(|l| l.chars().collect()).collect();
    let mut front: HashSet<_> = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == 'D')
        .collect();
    let mut visited = HashSet::new();
    let knight_moves: [(isize, isize); 8] = [
        (2, 1),
        (2, -1),
        (-2, -1),
        (-2, 1),
        (1, 2),
        (1, -2),
        (-1, -2),
        (-1, 2),
    ];
    for _ in 0..=4 {
        let mut next_front = HashSet::new();
        for (i, j) in front.drain() {
            for (di, dj) in knight_moves {
                let (ni, nj) = (i.wrapping_add_signed(di), j.wrapping_add_signed(dj));
                if ni >= board.len() || nj >= board[0].len() {
                    continue;
                }
                if visited.contains(&(ni, nj)) {
                    continue;
                }
                next_front.insert((ni, nj));
            }
            visited.insert((i, j));
        }
        front = next_front;
    }
    visited
        .drain()
        .filter(|&(i, j)| board[i][j] == 'S')
        .count()
        .to_string()
}

fn solve_part_2_with_turns(input: &str, turns: usize) -> String {
    let board: Vec<Vec<_>> = input.lines().map(|l| l.chars().collect()).collect();
    let mut front: HashSet<_> = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == 'D')
        .collect();
    let knight_moves: [(isize, isize); 8] = [
        (2, 1),
        (2, -1),
        (-2, -1),
        (-2, 1),
        (1, 2),
        (1, -2),
        (-1, -2),
        (-1, 2),
    ];
    let mut eaten_sheep = HashSet::new();
    for turn in 0..=turns {
        let mut next_front = HashSet::new();
        for (i, j) in front.drain() {
            for (di, dj) in knight_moves {
                let (ni, nj) = (i.wrapping_add_signed(di), j.wrapping_add_signed(dj));
                if ni >= board.len() || nj >= board[0].len() {
                    continue;
                }
                next_front.insert((ni, nj));
            }
            if board[i][j] != '#' {
                if let Some(sheep_i) = (i + 1).checked_sub(turn)
                    && board[sheep_i][j] == 'S'
                {
                    eaten_sheep.insert((sheep_i, j));
                }
                if let Some(sheep_i) = i.checked_sub(turn)
                    && turn != 0
                    && board[sheep_i][j] == 'S'
                {
                    eaten_sheep.insert((sheep_i, j));
                }
            }
        }
        front = next_front;
    }
    eaten_sheep.len().to_string()
}

pub fn solve_part_2(input: &str) -> String {
    solve_part_2_with_turns(input, 20)
}
type VeryComplexType = HashMap<(usize, usize, usize, Vec<(usize, usize)>), usize>;
fn count_winning_sequences(
    turn: usize,
    dragon: (usize, usize),
    hiding_places: &HashSet<(usize, usize)>,
    sheep: BTreeSet<(usize, usize)>,
    height: usize,
    width: usize,
    cache: &mut VeryComplexType,
) -> usize {
    if sheep.is_empty() {
        return 1;
    }
    let cache_key = (
        turn % 2,
        dragon.0,
        dragon.1,
        sheep.iter().cloned().collect(),
    );
    if let Some(result) = cache.get(&cache_key) {
        return *result;
    }
    if turn % 2 == 1 {
        let knight_moves: [(isize, isize); 8] = [
            (2, 1),
            (2, -1),
            (-2, -1),
            (-2, 1),
            (1, 2),
            (1, -2),
            (-1, -2),
            (-1, 2),
        ];
        let (i, j) = dragon;
        let mut total = 0;
        for (di, dj) in knight_moves {
            let (ni, nj) = (i.wrapping_add_signed(di), j.wrapping_add_signed(dj));
            if ni >= height || nj >= width {
                continue;
            }
            if !hiding_places.contains(&(ni, nj)) && sheep.contains(&(ni, nj)) {
                let mut new_sheep = sheep.clone();
                new_sheep.remove(&(ni, nj));
                total += count_winning_sequences(
                    turn + 1,
                    (ni, nj),
                    hiding_places,
                    new_sheep,
                    height,
                    width,
                    cache,
                );
            } else {
                total += count_winning_sequences(
                    turn + 1,
                    (ni, nj),
                    hiding_places,
                    sheep.clone(),
                    height,
                    width,
                    cache,
                );
            }
        }
        cache.insert(cache_key, total);
        total
    } else {
        let mut sheep_moves_available = false;
        let mut total = 0;
        for &(i, j) in sheep.iter() {
            if dragon == (i + 1, j) && !hiding_places.contains(&(i + 1, j)) {
                continue;
            }
            sheep_moves_available = true;
            if i == (height - 1) {
                continue;
            }
            let mut new_sheep = sheep.clone();
            new_sheep.remove(&(i, j));
            new_sheep.insert((i + 1, j));
            total += count_winning_sequences(
                turn + 1,
                dragon,
                hiding_places,
                new_sheep,
                height,
                width,
                cache,
            );
        }
        if !sheep_moves_available {
            return count_winning_sequences(
                turn + 1,
                dragon,
                hiding_places,
                sheep,
                height,
                width,
                cache,
            );
        }
        cache.insert(cache_key, total);
        total
    }
}

pub fn solve_part_3(input: &str) -> String {
    let board: Vec<Vec<_>> = input.lines().map(|l| l.chars().collect()).collect();
    let dragon = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == 'D')
        .exactly_one()
        .unwrap();
    let sheep = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == 'S')
        .collect::<BTreeSet<_>>();
    let hiding_places = (0usize..board.len())
        .cartesian_product(0usize..board[0].len())
        .filter(|&(i, j)| board[i][j] == '#')
        .collect::<HashSet<_>>();
    let mut cache = HashMap::new();
    count_winning_sequences(
        0,
        dragon,
        &hiding_places,
        sheep,
        board.len(),
        board[0].len(),
        &mut cache,
    )
    .to_string()
}

Rust

use std::collections::HashMap;

use bit_set::BitSet;
use itertools::{Itertools, izip};

type BitSetBase = u32;

fn is_child(child: &str, parent1: &str, parent2: &str) -> bool {
    izip!(child.chars(), parent1.chars(), parent2.chars()).all(|(c, a, b)| c == a || c == b)
}

fn similarity(a: &str, b: &str) -> usize {
    izip!(a.chars(), b.chars()).filter(|(a, b)| a == b).count()
}

fn unequality_bitset(a: &str, b: &str) -> BitSet<BitSetBase> {
    izip!(a.chars(), b.chars())
        .enumerate()
        .filter_map(|(i, (a_ch, b_ch))| if a_ch == b_ch { None } else { Some(i) })
        .collect()
}

pub fn solve_part_1(input: &str) -> String {
    let dnas = input
        .lines()
        .map(|l| {
            let (_, dna) = l.split_once(":").unwrap();
            dna
        })
        .collect::<Vec<_>>();
    let (child, parenta, parentb) = if is_child(dnas[0], dnas[1], dnas[2]) {
        (dnas[0], dnas[1], dnas[2])
    } else if is_child(dnas[1], dnas[0], dnas[2]) {
        (dnas[1], dnas[0], dnas[2])
    } else {
        (dnas[2], dnas[0], dnas[1])
    };
    (similarity(child, parenta) * similarity(child, parentb)).to_string()
}

pub fn solve_part_2(input: &str) -> String {
    let dnas = input
        .lines()
        .map(|l| {
            let (_, dna) = l.split_once(":").unwrap();
            dna
        })
        .collect::<Vec<_>>();
    let unequalities = dnas
        .iter()
        .enumerate()
        .cartesian_product(dnas.iter().enumerate())
        .map(|((a_id, a), (b_id, b))| ((a_id, b_id), unequality_bitset(a, b)))
        .collect::<HashMap<_, _>>();
    let mut total_similarities = 0;
    'outer: for (child_id, &child_string) in dnas.iter().enumerate() {
        for (parent_a_id, &parent_a_string) in dnas.iter().enumerate() {
            if parent_a_id == child_id {
                continue;
            }
            for (parent_b_id, &parent_b_string) in dnas.iter().enumerate() {
                if parent_b_id == child_id || parent_b_id == parent_a_id {
                    continue;
                }
                if unequalities[&(child_id, parent_a_id)]
                    .intersection(&unequalities[&(child_id, parent_b_id)])
                    .count()
                    == 0
                {
                    total_similarities += similarity(child_string, parent_a_string)
                        * similarity(child_string, parent_b_string);
                    continue 'outer;
                }
            }
        }
    }
    total_similarities.to_string()
}

pub fn solve_part_3(input: &str) -> String {
    let dnas = input
        .lines()
        .map(|l| {
            let (_, dna) = l.split_once(":").unwrap();
            dna
        })
        .collect::<Vec<_>>();
    let unequalities = dnas
        .iter()
        .enumerate()
        .cartesian_product(dnas.iter().enumerate())
        .map(|((a_id, a), (b_id, b))| ((a_id, b_id), unequality_bitset(a, b)))
        .collect::<HashMap<_, _>>();
    let mut parents: HashMap<usize, (usize, usize)> = HashMap::new();
    'outer: for (child_id, _) in dnas.iter().enumerate() {
        for (parent_a_id, _) in dnas.iter().enumerate() {
            if parent_a_id == child_id {
                continue;
            }
            for (parent_b_id, _) in dnas.iter().enumerate() {
                if parent_b_id == child_id || parent_b_id == parent_a_id {
                    continue;
                }
                if unequalities[&(child_id, parent_a_id)]
                    .intersection(&unequalities[&(child_id, parent_b_id)])
                    .count()
                    == 0
                {
                    parents.insert(child_id, (parent_a_id, parent_b_id));
                    continue 'outer;
                }
            }
        }
    }
    let mut family_id = (0usize..dnas.len()).collect::<Vec<_>>();
    for (child, (parent_a, parent_b)) in parents.drain() {
        let destination_family_id = family_id[child];
        let merge_families = (family_id[parent_a], family_id[parent_b]);
        for candidate_family in family_id.iter_mut() {
            if *candidate_family == merge_families.0 || *candidate_family == merge_families.1 {
                *candidate_family = destination_family_id;
            }
        }
    }
    let families = family_id
        .iter()
        .enumerate()
        .map(|(member_idx, &family_idx)| (family_idx, member_idx))
        .into_group_map();
    families
        .values()
        .max_by_key(|f| f.len())
        .unwrap()
        .iter()
        .map(|member_id| member_id + 1)
        .sum::<usize>()
        .to_string()
}