Skip to content

Instantly share code, notes, and snippets.

@samueltardieu
Last active December 14, 2022 13:45
Show Gist options
  • Save samueltardieu/e75eb3be0904873762f97ab07aa4a6d6 to your computer and use it in GitHub Desktop.
Save samueltardieu/e75eb3be0904873762f97ab07aa4a6d6 to your computer and use it in GitHub Desktop.
use super::FxHashSet; // type FxHashSet<T> = HashSet<T, BuildHasherDefault<FxHasher>>;
use nom::{
bytes::complete::tag, character::complete as ch, multi::separated_list1,
sequence::separated_pair, Finish, IResult,
};
fn parse_line(input: &str) -> IResult<&str, Vec<(u32, u32)>> {
separated_list1(tag(" -> "), separated_pair(ch::u32, ch::char(','), ch::u32))(input)
}
fn parse(input: &str) -> (FxHashSet<(u32, u32)>, u32) {
let mut obstacles = FxHashSet::default();
for l in input.lines().map(|l| parse_line(l).finish().unwrap().1) {
for s in l.windows(2) {
match s {
[(x1, y1), (x2, y2)] if x1 == x2 => {
for y in *(y1.min(y2))..=(*y2.max(y1)) {
obstacles.insert((*x1, y));
}
}
[(x1, y1), (x2, y2)] if y1 == y2 => {
for x in *(x1.min(x2))..=*(x2.max(x1)) {
obstacles.insert((x, *y1));
}
}
_ => unreachable!(),
}
}
}
let floor = *obstacles.iter().map(|(_, y)| y).max().unwrap();
(obstacles, floor)
}
fn fall(obstacles: &mut FxHashSet<(u32, u32)>, floor: u32) -> usize {
let mut latest = vec![(500, 0)];
let mut count = 0;
while let Some(mut pos) = latest.pop() {
count += 1;
'fall: while pos.1 < floor {
for x in [pos.0, pos.0 - 1, pos.0 + 1] {
if !obstacles.contains(&(x, pos.1 + 1)) {
latest.push(pos);
pos = (x, pos.1 + 1);
continue 'fall;
}
}
if obstacles.insert(pos) {
break;
}
return count;
}
if pos.1 >= floor {
return count;
}
}
count
}
#[aoc(day14, part1)]
fn part1(input: &str) -> usize {
let (mut obstacles, floor) = parse(input);
fall(&mut obstacles, floor) - 1
}
#[aoc(day14, part2)]
fn part2(input: &str) -> usize {
let (mut obstacles, mut floor) = parse(input);
floor += 2;
for x in 0..1000 {
obstacles.insert((x, floor));
}
fall(&mut obstacles, floor)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment