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