The "is between" operator in Python is perhaps the thing I miss the most from Python :)
I just noticed that you're probably the first person I've seen to include tests.
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.
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.
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