From 6d72191e2ce5d423ca03c894d2dad1d3061bd4f3 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:27:29 +0200 Subject: Refile for merging repos --- 2021/src/bin/day_1.rs | 75 ++++++ 2021/src/bin/day_10.rs | 124 +++++++++ 2021/src/bin/day_11.rs | 130 ++++++++++ 2021/src/bin/day_12.rs | 146 +++++++++++ 2021/src/bin/day_13.rs | 136 ++++++++++ 2021/src/bin/day_14.rs | 125 +++++++++ 2021/src/bin/day_15.rs | 162 ++++++++++++ 2021/src/bin/day_16.rs | 217 ++++++++++++++++ 2021/src/bin/day_17.rs | 82 ++++++ 2021/src/bin/day_18.rs | 193 ++++++++++++++ 2021/src/bin/day_19.rs | 223 ++++++++++++++++ 2021/src/bin/day_2.rs | 100 ++++++++ 2021/src/bin/day_20.rs | 201 +++++++++++++++ 2021/src/bin/day_21.rs | 76 ++++++ 2021/src/bin/day_22.rs | 379 ++++++++++++++++++++++++++++ 2021/src/bin/day_23.rs | 224 +++++++++++++++++ 2021/src/bin/day_24.rs | 588 +++++++++++++++++++++++++++++++++++++++++++ 2021/src/bin/day_25.rs | 98 ++++++++ 2021/src/bin/day_2_part_2.rs | 124 +++++++++ 2021/src/bin/day_3.rs | 128 ++++++++++ 2021/src/bin/day_4.rs | 259 +++++++++++++++++++ 2021/src/bin/day_5.rs | 137 ++++++++++ 2021/src/bin/day_6.rs | 79 ++++++ 2021/src/bin/day_7.rs | 88 +++++++ 2021/src/bin/day_8.rs | 262 +++++++++++++++++++ 2021/src/bin/day_9.rs | 186 ++++++++++++++ 2021/src/lib.rs | 1 + 2021/src/parsers.rs | 1 + 28 files changed, 4544 insertions(+) create mode 100644 2021/src/bin/day_1.rs create mode 100644 2021/src/bin/day_10.rs create mode 100644 2021/src/bin/day_11.rs create mode 100644 2021/src/bin/day_12.rs create mode 100644 2021/src/bin/day_13.rs create mode 100644 2021/src/bin/day_14.rs create mode 100644 2021/src/bin/day_15.rs create mode 100644 2021/src/bin/day_16.rs create mode 100644 2021/src/bin/day_17.rs create mode 100644 2021/src/bin/day_18.rs create mode 100644 2021/src/bin/day_19.rs create mode 100644 2021/src/bin/day_2.rs create mode 100644 2021/src/bin/day_20.rs create mode 100644 2021/src/bin/day_21.rs create mode 100644 2021/src/bin/day_22.rs create mode 100644 2021/src/bin/day_23.rs create mode 100644 2021/src/bin/day_24.rs create mode 100644 2021/src/bin/day_25.rs create mode 100644 2021/src/bin/day_2_part_2.rs create mode 100644 2021/src/bin/day_3.rs create mode 100644 2021/src/bin/day_4.rs create mode 100644 2021/src/bin/day_5.rs create mode 100644 2021/src/bin/day_6.rs create mode 100644 2021/src/bin/day_7.rs create mode 100644 2021/src/bin/day_8.rs create mode 100644 2021/src/bin/day_9.rs create mode 100644 2021/src/lib.rs create mode 100644 2021/src/parsers.rs (limited to '2021/src') diff --git a/2021/src/bin/day_1.rs b/2021/src/bin/day_1.rs new file mode 100644 index 0000000..62ab045 --- /dev/null +++ b/2021/src/bin/day_1.rs @@ -0,0 +1,75 @@ +use nom::{ + character::complete::{line_ending, u64 as nom_u64}, + combinator::map, + multi::separated_list1, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_1.txt")?; + let sonar_scan = parse_sonar_scan(&input).unwrap().1; + + let simple_increase_counter = count_increases(sonar_scan.iter()); + dbg!(simple_increase_counter); + + let windowed_sonar_scan = sonar_scan + .iter() + .zip(sonar_scan.iter().skip(1)) + .zip(sonar_scan.iter().skip(2)) + .map(|((depth1, depth2), depth3)| ThreeDepthWindowSum::new([*depth1, *depth2, *depth3])) + .collect::>(); + + let windowed_increase_counter = count_increases(windowed_sonar_scan.iter()); + dbg!(windowed_increase_counter); + + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)] +struct Depth(u64); + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)] +struct ThreeDepthWindowSum(u64); + +impl ThreeDepthWindowSum { + fn new(depths: [Depth; 3]) -> ThreeDepthWindowSum { + ThreeDepthWindowSum(depths.into_iter().map(|d| d.0).sum()) + } +} + +fn parse_sonar_scan(input: &str) -> IResult<&str, Vec> { + separated_list1(line_ending, parse_depth)(input) +} + +fn parse_depth(input: &str) -> IResult<&str, Depth> { + map(nom_u64, Depth)(input) +} + +#[derive(Default, Debug)] +struct DepthIncreaseCounter(u64); + +impl DepthIncreaseCounter { + fn increment(&mut self) { + self.0 += 1; + } +} + +fn count_increases(i: impl IntoIterator + Clone) -> DepthIncreaseCounter { + let mut increases = DepthIncreaseCounter::default(); + for (depth, next_depth) in i.clone().into_iter().zip(i.into_iter().skip(1)) { + if next_depth > depth { + increases.increment(); + } + } + increases +} + +#[cfg(test)] +mod tests { + use super::*; + #[test] + fn parses_a_depth() { + assert_eq!(parse_depth("96\n"), Ok(("\n", Depth(96)))); + } +} diff --git a/2021/src/bin/day_10.rs b/2021/src/bin/day_10.rs new file mode 100644 index 0000000..a9a9f75 --- /dev/null +++ b/2021/src/bin/day_10.rs @@ -0,0 +1,124 @@ +use nom::{ + branch::alt, character::complete::char as nom_char, combinator::map, multi::many0, IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_10.txt")?; + + let mut syntax_error_score = 0; + let mut autocomplete_scores = Vec::new(); + for line in input.split("\n") { + match parse_lisp(line) { + Ok(_) => { + // boring + } + Err(nom::Err::Failure(ParseError::MismatchedExpectation(_, actual))) => { + syntax_error_score += match actual { + ')' => 3, + ']' => 57, + '}' => 1197, + '>' => 25137, + _ => 0, + } + } + Err(nom::Err::Failure(ParseError::EndOfInput(_))) => { + let mut line = line.to_owned(); + let mut autocomplete_score = 0u64; + while let Err(nom::Err::Failure(ParseError::EndOfInput(expected))) = + parse_lisp(&line) + { + autocomplete_score *= 5; + autocomplete_score += match expected { + ')' => 1, + ']' => 2, + '}' => 3, + '>' => 4, + _ => 0, + }; + line.push(expected); + } + autocomplete_scores.push(autocomplete_score); + } + Err(_) => panic!("Unexpected nom error type"), + } + } + dbg!(syntax_error_score); + autocomplete_scores.sort(); + dbg!(autocomplete_scores[autocomplete_scores.len() / 2]); + + Ok(()) +} + +#[derive(Debug)] +enum ParseError<'a> { + MismatchedExpectation(char, char), + EndOfInput(char), + Other(nom::error::Error<&'a str>), +} + +impl<'a> From> for ParseError<'a> { + fn from(e: nom::error::Error<&'a str>) -> Self { + ParseError::Other(e) + } +} + +impl<'a> nom::error::ParseError<&'a str> for ParseError<'a> { + fn from_error_kind(input: &'a str, kind: nom::error::ErrorKind) -> Self { + nom::error::Error::from_error_kind(input, kind).into() + } + + fn append(_input: &'a str, _kind: nom::error::ErrorKind, other: Self) -> Self { + other + } + + fn from_char(input: &'a str, c: char) -> Self { + nom::error::Error::from_char(input, c).into() + } +} + +#[derive(Debug)] +struct Lisp { + blocks: Vec, +} + +#[derive(Debug)] +struct Block { + opening: char, + blocks: Vec, +} + +fn parse_lisp(input: &str) -> IResult<&str, Lisp, ParseError> { + map(parse_blocks, |blocks| Lisp { blocks })(input) +} + +fn parse_blocks(input: &str) -> IResult<&str, Vec, ParseError> { + many0(parse_block)(input) +} + +fn parse_block(input: &str) -> IResult<&str, Block, ParseError> { + alt(( + block('{', '}'), + block('[', ']'), + block('(', ')'), + block('<', '>'), + ))(input) +} + +fn block(opening: char, closing: char) -> impl Fn(&str) -> IResult<&str, Block, ParseError> { + move |input: &str| { + let (input, _) = nom_char(opening)(input)?; + let (input, blocks) = parse_blocks(input)?; + let (input, _) = match nom_char(closing)(input) { + Ok((input, closing)) => (input, closing), + Err(nom::Err::Error(_)) => { + return Err(nom::Err::Failure(match input.chars().next() { + Some(actual) => ParseError::MismatchedExpectation(closing, actual), + None => ParseError::EndOfInput(closing), + })) + } + Err(e) => return Err(e), + }; + Ok((input, Block { opening, blocks })) + } +} diff --git a/2021/src/bin/day_11.rs b/2021/src/bin/day_11.rs new file mode 100644 index 0000000..2a4cd89 --- /dev/null +++ b/2021/src/bin/day_11.rs @@ -0,0 +1,130 @@ +use nom::{ + character::complete::{line_ending, one_of}, + combinator::map_res, + multi::{many1, separated_list1}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_11.txt")?; + let squid_grid = parse_squid_grid(&input).unwrap().1; + + { + let mut squid_grid = squid_grid.clone(); + let mut flashes_on_100 = 0; + for _ in 0..100 { + flashes_on_100 += squid_grid.flash(); + } + dbg!(flashes_on_100); + } + + { + let mut squid_grid = squid_grid.clone(); + let sync_time = std::iter::repeat_with(|| squid_grid.flash()) + .position(|flashes| flashes == 100) + .map(|x| x + 1); + dbg!(sync_time); + } + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Squid { + energy: u8, + has_flashed: bool, +} + +impl Squid { + fn should_flash(&self) -> bool { + self.energy > 9 && !self.has_flashed + } + + fn reset(&mut self) { + self.energy = 0; + self.has_flashed = false; + } +} + +#[derive(Debug, Clone)] +struct SquidGrid { + squids: [[Squid; 10]; 10], +} + +impl SquidGrid { + fn flash(&mut self) -> usize { + for y in 0..10 { + for x in 0..10 { + self.squids[y][x].energy += 1; + } + } + + let mut any_new_flashes = true; + while any_new_flashes { + any_new_flashes = false; + for y in 0..10 { + for x in 0..10 { + if self.squids[y][x].should_flash() { + any_new_flashes = true; + self.squids[y][x].has_flashed = true; + if y > 0 && x > 0 { + self.squids[y - 1][x - 1].energy += 1; + } + if y > 0 { + self.squids[y - 1][x].energy += 1; + } + if y > 0 && x < 9 { + self.squids[y - 1][x + 1].energy += 1; + } + if x > 0 { + self.squids[y][x - 1].energy += 1; + } + if x < 9 { + self.squids[y][x + 1].energy += 1; + } + if y < 9 && x > 0 { + self.squids[y + 1][x - 1].energy += 1; + } + if y < 9 { + self.squids[y + 1][x].energy += 1; + } + if y < 9 && x < 9 { + self.squids[y + 1][x + 1].energy += 1; + } + } + } + } + } + + let mut flashes = 0; + for y in 0..10 { + for x in 0..10 { + if self.squids[y][x].has_flashed { + self.squids[y][x].reset(); + flashes += 1; + } + } + } + flashes + } +} + +fn parse_squid_grid(input: &str) -> IResult<&str, SquidGrid> { + map_res(separated_list1(line_ending, parse_squid_row), |squids| { + squids.try_into().map(|squids| SquidGrid { squids }) + })(input) +} + +fn parse_squid_row(input: &str) -> IResult<&str, [Squid; 10]> { + map_res(many1(parse_squid), |squids| squids.try_into())(input) +} + +fn parse_squid(input: &str) -> IResult<&str, Squid> { + map_res(one_of("0123456789"), |digit| { + digit.to_string().parse().map(|energy| Squid { + energy, + has_flashed: false, + }) + })(input) +} diff --git a/2021/src/bin/day_12.rs b/2021/src/bin/day_12.rs new file mode 100644 index 0000000..708037d --- /dev/null +++ b/2021/src/bin/day_12.rs @@ -0,0 +1,146 @@ +use nom::{ + character::complete::{alpha1, char as nom_char, line_ending}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeMap, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_12.txt")?; + let cave_system = parse_cave_system(&input).unwrap().1; + dbg!(cave_system.find_all_paths(0).len()); + dbg!(cave_system.find_all_paths(1).len()); + + Ok(()) +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct CaveId(String); + +impl CaveId { + fn big(&self) -> bool { + self.0.chars().next().map_or(false, char::is_uppercase) + } + fn terminal(&self) -> bool { + self.0 == "start" || self.0 == "end" + } +} + +#[derive(Debug)] +struct Cave { + id: CaveId, + exits: Vec, +} + +impl Cave { + fn new(id: CaveId) -> Cave { + Cave { + id, + exits: Vec::new(), + } + } +} + +#[derive(Debug, Clone)] +struct CavePath { + path: Vec, + remaining_small_cave_visits: usize, +} + +impl CavePath { + fn new(max_small_cave_visits: usize) -> CavePath { + CavePath { + path: vec![CaveId("start".into())], + remaining_small_cave_visits: max_small_cave_visits, + } + } + + fn push(&mut self, next: CaveId) { + if !next.big() && self.path.iter().any(|visited| visited == &next) { + self.remaining_small_cave_visits -= 1; + } + self.path.push(next); + } + + fn can_go_to(&self, dest: &CaveId) -> bool { + dest.big() + || !self.path.iter().any(|visited| visited == dest) + || (!dest.terminal() && self.remaining_small_cave_visits > 0) + } + + fn is_complete(&self) -> bool { + self.tail() == &CaveId("end".into()) + } + + fn tail(&self) -> &CaveId { + self.path + .get(self.path.len() - 1) + .expect("There should not be empty paths") + } +} + +#[derive(Debug)] +struct CaveSystem { + caves: BTreeMap, +} + +impl CaveSystem { + fn new(tunnels: Vec<(CaveId, CaveId)>) -> CaveSystem { + let mut caves = BTreeMap::new(); + for (tunnel_start, tunnel_end) in tunnels { + let start = caves + .entry(tunnel_start.clone()) + .or_insert(Cave::new(tunnel_start.clone())); + start.exits.push(tunnel_end.clone()); + + let end = caves + .entry(tunnel_end.clone()) + .or_insert(Cave::new(tunnel_end.clone())); + end.exits.push(tunnel_start); + } + CaveSystem { caves } + } + + fn find_all_paths(&self, max_small_cave_visits: usize) -> Vec { + self.find_paths(CavePath::new(max_small_cave_visits)) + } + + fn find_paths(&self, active_path: CavePath) -> Vec { + if active_path.is_complete() { + vec![active_path] + } else { + let current = self.caves.get(active_path.tail()).expect("Unknown path"); + current + .exits + .iter() + .filter(|next| active_path.can_go_to(next)) + .flat_map(|next| { + let mut active_path = active_path.clone(); + active_path.push(next.clone()); + self.find_paths(active_path) + }) + .collect() + } + } +} + +fn parse_cave_system(input: &str) -> IResult<&str, CaveSystem> { + map(parse_tunnels, CaveSystem::new)(input) +} + +fn parse_tunnels(input: &str) -> IResult<&str, Vec<(CaveId, CaveId)>> { + separated_list1(line_ending, parse_tunnel)(input) +} + +fn parse_tunnel(input: &str) -> IResult<&str, (CaveId, CaveId)> { + map( + tuple((parse_cave_id, nom_char('-'), parse_cave_id)), + |(a, _, b)| (a, b), + )(input) +} + +fn parse_cave_id(input: &str) -> IResult<&str, CaveId> { + map(alpha1, |s: &str| CaveId(s.to_owned()))(input) +} diff --git a/2021/src/bin/day_13.rs b/2021/src/bin/day_13.rs new file mode 100644 index 0000000..547c7a2 --- /dev/null +++ b/2021/src/bin/day_13.rs @@ -0,0 +1,136 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{char as nom_char, line_ending, u32 as nom_u32}, + combinator::map, + multi::{many0, separated_list1}, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fmt, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_13.txt")?; + let mut page = parse_page(&input).unwrap().1; + page.do_next_fold(); + dbg!(page.count_points()); + while page.do_next_fold() {} + println!("{}", page); + + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)] +struct Point { + x: u32, + y: u32, +} + +#[derive(Debug)] +enum Fold { + X(u32), + Y(u32), +} + +#[derive(Debug)] +struct Page { + points: BTreeSet, + folds: Vec, +} + +impl Page { + fn do_next_fold(&mut self) -> bool { + let fold = self.folds.pop(); + match fold { + Some(Fold::X(x)) => { + self.points = std::mem::take(&mut self.points) + .into_iter() + .filter(|point| point.x != x) + .map(|point| { + if point.x > x { + Point { + x: x - (point.x - x), + y: point.y, + } + } else { + point + } + }) + .collect(); + true + } + Some(Fold::Y(y)) => { + self.points = std::mem::take(&mut self.points) + .into_iter() + .filter(|point| point.y != y) + .map(|point| { + if point.y > y { + Point { + x: point.x, + y: y - (point.y - y), + } + } else { + point + } + }) + .collect(); + true + } + None => false, + } + } + + fn count_points(&self) -> usize { + self.points.len() + } +} + +impl fmt::Display for Page { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> { + let width = self.points.iter().map(|p| p.x).max().unwrap_or(0); + let height = self.points.iter().map(|p| p.y).max().unwrap_or(0); + for y in 0..=height { + for x in 0..=width { + let p = Point { x, y }; + if self.points.contains(&p) { + write!(f, "#")?; + } else { + write!(f, ".")?; + } + } + writeln!(f)?; + } + Ok(()) + } +} + +fn parse_page(input: &str) -> IResult<&str, Page> { + let (input, points) = separated_list1(line_ending, parse_point)(input)?; + let (input, _) = many0(line_ending)(input)?; + let (input, mut folds) = separated_list1(line_ending, parse_fold)(input)?; + folds.reverse(); + Ok(( + input, + Page { + points: points.into_iter().collect(), + folds, + }, + )) +} + +fn parse_fold(input: &str) -> IResult<&str, Fold> { + alt(( + map(tuple((tag("fold along x="), nom_u32)), |(_, val)| { + Fold::X(val) + }), + map(tuple((tag("fold along y="), nom_u32)), |(_, val)| { + Fold::Y(val) + }), + ))(input) +} + +fn parse_point(input: &str) -> IResult<&str, Point> { + map(tuple((nom_u32, nom_char(','), nom_u32)), |(x, _, y)| { + Point { x, y } + })(input) +} diff --git a/2021/src/bin/day_14.rs b/2021/src/bin/day_14.rs new file mode 100644 index 0000000..e757faf --- /dev/null +++ b/2021/src/bin/day_14.rs @@ -0,0 +1,125 @@ +use nom::{ + bytes::complete::tag, + character::complete::{alpha1, anychar, line_ending}, + combinator::map, + multi::{many0, separated_list1}, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeMap, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_14.txt")?; + let mut polymer = parse_polymer_expansion(&input).unwrap().1; + + let small_expansion_counts = polymer.count_after_expansions(10); + dbg!(small_expansion_counts.most_common() - small_expansion_counts.least_common()); + + let big_expansion_counts = polymer.count_after_expansions(40); + dbg!(big_expansion_counts.most_common() - big_expansion_counts.least_common()); + + Ok(()) +} + +#[derive(Debug)] +struct PolymerExpansion { + polymer: Vec, + rules: Rules, + cache: BTreeMap<(char, char, usize), ElementCount>, +} + +impl PolymerExpansion { + fn new(polymer: Vec, rules: Rules) -> PolymerExpansion { + PolymerExpansion { + polymer, + rules, + cache: BTreeMap::new(), + } + } + + fn count_after_expansions(&mut self, expansions: usize) -> ElementCount { + let mut counts = ElementCount::default(); + for i in 0..self.polymer.len() - 1 { + counts.add(self.polymer[i]); + counts.append(self.count_between(self.polymer[i], self.polymer[i + 1], expansions)); + } + counts.add(self.polymer[self.polymer.len() - 1]); + counts + } + + fn count_between( + &mut self, + left: char, + right: char, + remaining_expansions: usize, + ) -> ElementCount { + if remaining_expansions == 0 { + ElementCount::default() + } else if let Some(cached) = self.cache.get(&(left, right, remaining_expansions)) { + cached.clone() + } else { + let mut counts = ElementCount::default(); + let middle = self.rules.get(&[left, right]).expect("No rule!"); + counts.add(middle); + counts.append(self.count_between(left, middle, remaining_expansions - 1)); + counts.append(self.count_between(middle, right, remaining_expansions - 1)); + self.cache + .insert((left, right, remaining_expansions), counts.clone()); + counts + } + } +} + +#[derive(Debug, Default, Clone)] +struct ElementCount(BTreeMap); + +impl ElementCount { + fn add(&mut self, c: char) { + *self.0.entry(c).or_insert(0) += 1; + } + + fn append(&mut self, other: ElementCount) { + for (key, val) in other.0 { + *self.0.entry(key).or_insert(0) += val; + } + } + + fn most_common(&self) -> u64 { + self.0.values().max().cloned().unwrap_or(0) + } + + fn least_common(&self) -> u64 { + self.0.values().min().cloned().unwrap_or(0) + } +} + +#[derive(Debug)] +struct Rules { + rules: BTreeMap<[char; 2], char>, +} + +impl Rules { + fn get(&self, key: &[char; 2]) -> Option { + self.rules.get(key).cloned() + } +} + +fn parse_polymer_expansion(input: &str) -> IResult<&str, PolymerExpansion> { + let (input, polymer) = map(alpha1, |s: &str| s.chars().collect())(input)?; + let (input, _) = many0(line_ending)(input)?; + let (input, rules) = parse_rules(input)?; + Ok((input, PolymerExpansion::new(polymer, rules))) +} + +fn parse_rules(input: &str) -> IResult<&str, Rules> { + map(separated_list1(line_ending, parse_rule), |rules| Rules { + rules: rules.into_iter().collect(), + })(input) +} + +fn parse_rule(input: &str) -> IResult<&str, ([char; 2], char)> { + map( + tuple((anychar, anychar, tag(" -> "), anychar)), + |(p1, p2, _, r)| ([p1, p2], r), + )(input) +} diff --git a/2021/src/bin/day_15.rs b/2021/src/bin/day_15.rs new file mode 100644 index 0000000..6103384 --- /dev/null +++ b/2021/src/bin/day_15.rs @@ -0,0 +1,162 @@ +use nom::{ + character::complete::{line_ending, one_of}, + combinator::{map, map_res}, + multi::{many1, separated_list1}, + IResult, +}; +use std::{collections::BTreeMap, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_15.txt")?; + let risk_grid = parse_risk_grid(&input).unwrap().1; + let big_risk_grid = risk_grid.expand(); + { + let mut searcher = Searcher::new(risk_grid); + while searcher.end_risk().is_none() { + searcher.explore_next(); + } + dbg!(searcher.end_risk()); + } + { + let mut big_searcher = Searcher::new(big_risk_grid); + while big_searcher.end_risk().is_none() { + big_searcher.explore_next(); + } + dbg!(big_searcher.end_risk()); + } + + Ok(()) +} + +#[derive(Debug)] +struct Searcher { + grid: RiskGrid, + frontier: Vec<(Risk, Point)>, + explored: BTreeMap, +} + +impl Searcher { + fn new(grid: RiskGrid) -> Searcher { + let start = grid.start(); + let mut explored = BTreeMap::new(); + explored.insert(start.clone(), Risk(0)); + Searcher { + grid, + explored, + frontier: vec![(Risk(0), start)], + } + } + + fn explore_next(&mut self) { + if let Some((next_risk, next_point)) = self.frontier.pop() { + for (neighbour_risk, neighbour_point) in self.grid.neighbours(&next_point) { + if !self.explored.contains_key(&neighbour_point) { + let total_risk = next_risk + neighbour_risk; + self.explored.insert(neighbour_point.clone(), total_risk); + self.frontier.push((total_risk, neighbour_point)); + } + } + self.frontier.sort_unstable_by(|a, b| b.0.cmp(&a.0)); + } + } + + fn end_risk(&self) -> Option { + self.explored.get(&self.grid.end()).cloned() + } +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + x: usize, + y: usize, +} + +#[derive(Debug)] +struct RiskGrid { + map: Vec>, +} + +impl RiskGrid { + fn start(&self) -> Point { + Point { x: 0, y: 0 } + } + + fn end(&self) -> Point { + let y = self.map.len() - 1; + let x = self.map[y].len() - 1; + Point { x, y } + } + + fn risk_at_point(&self, p: &Point) -> Option { + self.map.get(p.y).and_then(|row| row.get(p.x)).cloned() + } + + fn neighbours(&self, p: &Point) -> Vec<(Risk, Point)> { + let mut neighbours = Vec::new(); + if p.x > 0 { + let left = Point { x: p.x - 1, y: p.y }; + if let Some(risk) = self.risk_at_point(&left) { + neighbours.push((risk, left)); + } + } + if p.y > 0 { + let up = Point { x: p.x, y: p.y - 1 }; + if let Some(risk) = self.risk_at_point(&up) { + neighbours.push((risk, up)); + } + } + let right = Point { x: p.x + 1, y: p.y }; + if let Some(risk) = self.risk_at_point(&right) { + neighbours.push((risk, right)); + } + let down = Point { x: p.x, y: p.y + 1 }; + if let Some(risk) = self.risk_at_point(&down) { + neighbours.push((risk, down)); + } + neighbours + } + + fn expand(&self) -> RiskGrid { + let mut new_map = Vec::new(); + for y_repeat in 0..5 { + for original_row in &self.map { + let mut new_row = Vec::new(); + for x_repeat in 0..5 { + let risk_modifier = y_repeat + x_repeat; + for original_risk in original_row { + let modified_risk = original_risk.grid_wrap_increment(risk_modifier); + new_row.push(modified_risk); + } + } + new_map.push(new_row); + } + } + RiskGrid { map: new_map } + } +} + +#[derive(Debug, Clone, Copy, derive_more::Add, PartialEq, Eq, PartialOrd, Ord)] +struct Risk(u64); + +impl Risk { + fn grid_wrap_increment(&self, increment_count: u64) -> Risk { + let new = (self.0 + increment_count) % 9; + if new == 0 { + Risk(9) + } else { + Risk(new) + } + } +} + +fn parse_risk_grid(input: &str) -> IResult<&str, RiskGrid> { + map(separated_list1(line_ending, many1(parse_risk)), |risks| { + RiskGrid { map: risks } + })(input) +} + +fn parse_risk(input: &str) -> IResult<&str, Risk> { + map_res(one_of("0123456789"), |digit| { + digit.to_string().parse().map(Risk) + })(input) +} diff --git a/2021/src/bin/day_16.rs b/2021/src/bin/day_16.rs new file mode 100644 index 0000000..368ecc8 --- /dev/null +++ b/2021/src/bin/day_16.rs @@ -0,0 +1,217 @@ +use nom::{ + branch::alt, + bytes::complete::take, + character::complete::{char as nom_char, one_of}, + combinator::{consumed, map, map_res}, + error::FromExternalError, + multi::many0, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_16.txt")?; + let binary = convert_to_binary(&input).unwrap().1; + let packet = parse_packet(&binary).unwrap().1; + dbg!(packet.version_sum()); + dbg!(packet.eval()); + + Ok(()) +} + +#[derive(Debug)] +struct Packet { + version: u8, + data: PacketData, +} + +impl Packet { + fn version_sum(&self) -> u32 { + self.version as u32 + + match &self.data { + PacketData::Literal(_) => 0, + PacketData::Operator(data) => { + data.sub_packets.iter().map(|p| p.version_sum()).sum() + } + } + } + + fn eval(&self) -> u64 { + match &self.data { + PacketData::Literal(val) => *val, + PacketData::Operator(data) => data.eval(), + } + } +} + +#[derive(Debug)] +enum PacketData { + Literal(u64), + Operator(OperatorData), +} + +#[derive(Debug)] +struct OperatorData { + type_id: OperatorType, + sub_packets: Vec, +} + +impl OperatorData { + fn eval(&self) -> u64 { + match &self.type_id { + OperatorType::Sum => self.sub_packets.iter().map(|p| p.eval()).sum(), + OperatorType::Product => self.sub_packets.iter().map(|p| p.eval()).product(), + OperatorType::Minimum => self.sub_packets.iter().map(|p| p.eval()).min().unwrap_or(0), + OperatorType::Maximum => self.sub_packets.iter().map(|p| p.eval()).max().unwrap_or(0), + OperatorType::GreaterThan => { + if self.sub_packets[0].eval() > self.sub_packets[1].eval() { + 1 + } else { + 0 + } + } + OperatorType::LessThan => { + if self.sub_packets[0].eval() < self.sub_packets[1].eval() { + 1 + } else { + 0 + } + } + OperatorType::EqualTo => { + if self.sub_packets[0].eval() == self.sub_packets[1].eval() { + 1 + } else { + 0 + } + } + } + } +} + +#[derive(Debug)] +enum OperatorType { + Sum, + Product, + Minimum, + Maximum, + GreaterThan, + LessThan, + EqualTo, +} + +#[derive(Debug, thiserror::Error)] +enum OperatorError { + #[error("type was not a valid operator")] + InvalidType, +} + +impl TryFrom for OperatorType { + type Error = OperatorError; + fn try_from(num: u8) -> Result { + match num { + 0 => Ok(Self::Sum), + 1 => Ok(Self::Product), + 2 => Ok(Self::Minimum), + 3 => Ok(Self::Maximum), + 5 => Ok(Self::GreaterThan), + 6 => Ok(Self::LessThan), + 7 => Ok(Self::EqualTo), + _ => Err(OperatorError::InvalidType), + } + } +} + +fn convert_to_binary(input: &str) -> IResult<&str, String> { + map( + many0(map(one_of("0123456789ABCDEF"), |hex_char| { + let digit = hex_char.to_digit(16).unwrap(); + format!("{:04b}", digit) + })), + |bin_strings| bin_strings.join(""), + )(input) +} + +fn parse_packet(input: &str) -> IResult<&str, Packet> { + let (input, version) = parse_bits3(input)?; + let (input, type_id) = parse_bits3(input)?; + if type_id == 4 { + let (input, literal) = parse_literal(input)?; + Ok(( + input, + Packet { + version, + data: PacketData::Literal(literal), + }, + )) + } else { + let (input, sub_packets) = + alt((parse_sub_packets_bits_mode, parse_sub_packets_count_mode))(input)?; + Ok(( + input, + Packet { + version, + data: PacketData::Operator(OperatorData { + type_id: type_id.try_into().expect("Invalid operator"), + sub_packets, + }), + }, + )) + } +} + +fn parse_bits3(input: &str) -> IResult<&str, u8> { + map_res(take(3usize), |bin_str| u8::from_str_radix(bin_str, 2))(input) +} + +fn parse_literal(input: &str) -> IResult<&str, u64> { + let (input, mut chunks) = many0(parse_literal_continuing_chunk)(input)?; + let (input, last_chunk) = parse_literal_last_chunk(input)?; + chunks.push(last_chunk); + let binary_num = chunks.join(""); + let num = u64::from_str_radix(&binary_num, 2).map_err(|e| { + nom::Err::Error(nom::error::Error::from_external_error( + input, + nom::error::ErrorKind::MapRes, + e, + )) + })?; + Ok((input, num)) +} + +fn parse_literal_continuing_chunk(input: &str) -> IResult<&str, &str> { + let (input, _) = nom_char('1')(input)?; + take(4usize)(input) +} + +fn parse_literal_last_chunk(input: &str) -> IResult<&str, &str> { + let (input, _) = nom_char('0')(input)?; + take(4usize)(input) +} + +fn parse_sub_packets_bits_mode(input: &str) -> IResult<&str, Vec> { + let (input, _) = nom_char('0')(input)?; + let (mut input, length_in_bits) = + map_res(take(15usize), |bin_str| usize::from_str_radix(bin_str, 2))(input)?; + let mut consumed_by_subpackets = String::new(); + let mut sub_packets = Vec::new(); + while consumed_by_subpackets.len() < length_in_bits { + let (next_input, (next_consumed, next_packet)) = consumed(parse_packet)(input)?; + input = next_input; + consumed_by_subpackets += next_consumed; + sub_packets.push(next_packet); + } + Ok((input, sub_packets)) +} + +fn parse_sub_packets_count_mode(input: &str) -> IResult<&str, Vec> { + let (input, _) = nom_char('1')(input)?; + let (mut input, number_of_packets) = + map_res(take(11usize), |bin_str| u16::from_str_radix(bin_str, 2))(input)?; + let mut sub_packets = Vec::new(); + for _ in 0..number_of_packets { + let (next_input, next_packet) = parse_packet(input)?; + input = next_input; + sub_packets.push(next_packet); + } + Ok((input, sub_packets)) +} diff --git a/2021/src/bin/day_17.rs b/2021/src/bin/day_17.rs new file mode 100644 index 0000000..0d60240 --- /dev/null +++ b/2021/src/bin/day_17.rs @@ -0,0 +1,82 @@ +use nom::{ + bytes::complete::tag, character::complete::i32 as nom_i32, combinator::map, sequence::tuple, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_17.txt")?; + let target = parse_target(&input).unwrap().1; + + let max_y_throw = 0 - target.min_y - 1; + let max_height = max_y_throw * (max_y_throw + 1) / 2; + dbg!(max_height); + + let min_y_throw = target.min_y; + let max_x_throw = target.max_x; + let min_x_throw = (2.0 * target.min_x as f32).sqrt() as i32; + + let mut count = 0; + for x in min_x_throw..=max_x_throw { + for y in min_y_throw..=max_y_throw { + if simulate_throw(x, y, &target) { + count += 1; + } + } + } + dbg!(count); + + Ok(()) +} + +fn simulate_throw(mut x_vel: i32, mut y_vel: i32, target: &TargetArea) -> bool { + let mut x_pos = 0; + let mut y_pos = 0; + loop { + x_pos += x_vel; + y_pos += y_vel; + if x_vel > 0 { + x_vel -= 1; + } + y_vel -= 1; + if x_pos >= target.min_x + && x_pos <= target.max_x + && y_pos >= target.min_y + && y_pos <= target.max_y + { + return true; + } + if x_pos > target.max_x || y_pos < target.min_y { + return false; + } + } +} + +#[derive(Debug)] +struct TargetArea { + min_x: i32, + max_x: i32, + min_y: i32, + max_y: i32, +} + +fn parse_target(input: &str) -> IResult<&str, TargetArea> { + map( + tuple(( + tag("target area: x="), + nom_i32, + tag(".."), + nom_i32, + tag(", y="), + nom_i32, + tag(".."), + nom_i32, + )), + |(_, min_x, _, max_x, _, min_y, _, max_y)| TargetArea { + min_x, + max_x, + min_y, + max_y, + }, + )(input) +} diff --git a/2021/src/bin/day_18.rs b/2021/src/bin/day_18.rs new file mode 100644 index 0000000..b77f1f1 --- /dev/null +++ b/2021/src/bin/day_18.rs @@ -0,0 +1,193 @@ +use nom::{ + branch::alt, + character::complete::{char as nom_char, line_ending, u8 as nom_u8}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_18.txt")?; + let snail_nums = parse_snail_nums(&input).unwrap().1; + { + let mut snail_nums_iter = snail_nums.clone().into_iter(); + let sum = snail_nums_iter + .next() + .map(|first_num| snail_nums_iter.fold(first_num, |acc, next| acc + next)) + .expect("Expected at least one snail number"); + + dbg!(&sum); + dbg!(sum.magnitude()); + } + + let mut max_magnitude = 0; + for i in 0..snail_nums.len() { + for j in 0..snail_nums.len() { + if i != j { + let new_magnitude = (snail_nums[i].clone() + snail_nums[j].clone()).magnitude(); + if new_magnitude > max_magnitude { + max_magnitude = new_magnitude; + } + } + } + } + dbg!(max_magnitude); + + Ok(()) +} + +#[derive(Debug, Clone, PartialEq, Eq)] +enum SnailNum { + Regular(u8), + Pair(Box, Box), +} + +impl Default for SnailNum { + fn default() -> SnailNum { + SnailNum::Regular(0) + } +} + +#[derive(PartialEq, Eq)] +enum NormalizeResult { + AlreadyNormalized, + NormalizeActionHandledInternally, + Explode(u8, u8), +} + +impl SnailNum { + fn unwrap_val(&self) -> u8 { + match self { + SnailNum::Regular(val) => *val, + SnailNum::Pair(_, _) => panic!("unwrapped the val on a pair"), + } + } + fn add_to_left(&mut self, add: u8) { + match self { + Self::Regular(val) => *val += add, + Self::Pair(left, _) => left.add_to_left(add), + } + } + fn add_to_right(&mut self, add: u8) { + match self { + Self::Regular(val) => *val += add, + Self::Pair(_, right) => right.add_to_right(add), + } + } + fn normalize_split_pass(&mut self) -> NormalizeResult { + match self { + Self::Regular(val) => { + if *val > 9 { + let half = *val / 2; + *self = SnailNum::Pair( + Box::new(SnailNum::Regular(half)), + Box::new(SnailNum::Regular(if *val % 2 == 0 { + half + } else { + half + 1 + })), + ); + return NormalizeResult::NormalizeActionHandledInternally; + } + } + Self::Pair(left, right) => { + match left.normalize_split_pass() { + NormalizeResult::AlreadyNormalized => {} + _ => { + return NormalizeResult::NormalizeActionHandledInternally; + } + } + match right.normalize_split_pass() { + NormalizeResult::AlreadyNormalized => {} + _ => { + return NormalizeResult::NormalizeActionHandledInternally; + } + } + } + } + NormalizeResult::AlreadyNormalized + } + fn normalize_explode_pass(&mut self, current_depth: u8) -> NormalizeResult { + match self { + Self::Regular(_val) => {} + Self::Pair(left, right) => { + if current_depth >= 4 { + let result = NormalizeResult::Explode(left.unwrap_val(), right.unwrap_val()); + *self = SnailNum::Regular(0); + return result; + } + match left.normalize_explode_pass(current_depth + 1) { + NormalizeResult::AlreadyNormalized => {} + NormalizeResult::NormalizeActionHandledInternally => { + return NormalizeResult::NormalizeActionHandledInternally; + } + NormalizeResult::Explode(leftadd, rightadd) => { + right.add_to_left(rightadd); + return NormalizeResult::Explode(leftadd, 0); + } + } + match right.normalize_explode_pass(current_depth + 1) { + NormalizeResult::AlreadyNormalized => {} + NormalizeResult::NormalizeActionHandledInternally => { + return NormalizeResult::NormalizeActionHandledInternally; + } + NormalizeResult::Explode(leftadd, rightadd) => { + left.add_to_right(leftadd); + return NormalizeResult::Explode(0, rightadd); + } + } + } + } + NormalizeResult::AlreadyNormalized + } + + fn normalize(&mut self) { + let mut normalized = false; + while !normalized { + let explode_result = self.normalize_explode_pass(0); + if explode_result == NormalizeResult::AlreadyNormalized { + let split_result = self.normalize_split_pass(); + if split_result == NormalizeResult::AlreadyNormalized { + normalized = true; + } + } + } + } + fn magnitude(&self) -> u64 { + match self { + Self::Regular(val) => *val as u64, + Self::Pair(left, right) => 3 * left.magnitude() + 2 * right.magnitude(), + } + } +} + +impl std::ops::Add for SnailNum { + type Output = SnailNum; + fn add(self, other: SnailNum) -> SnailNum { + let mut result = SnailNum::Pair(Box::new(self), Box::new(other)); + result.normalize(); + result + } +} + +fn parse_snail_nums(input: &str) -> IResult<&str, Vec> { + separated_list1(line_ending, parse_snail_num)(input) +} + +fn parse_snail_num(input: &str) -> IResult<&str, SnailNum> { + alt(( + map(nom_u8, SnailNum::Regular), + map( + tuple(( + nom_char('['), + parse_snail_num, + nom_char(','), + parse_snail_num, + nom_char(']'), + )), + |(_, left, _, right, _)| SnailNum::Pair(Box::new(left), Box::new(right)), + ), + ))(input) +} diff --git a/2021/src/bin/day_19.rs b/2021/src/bin/day_19.rs new file mode 100644 index 0000000..3fd8291 --- /dev/null +++ b/2021/src/bin/day_19.rs @@ -0,0 +1,223 @@ +use nom::{ + bytes::complete::tag, + character::complete::{char as nom_char, i32 as nom_i32, line_ending, not_line_ending}, + combinator::map, + multi::{many1, separated_list1}, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_19.txt")?; + let mut scanner_data = parse_scanner_cloud(&input).unwrap().1; + scanner_data.align_scanners(); + let beacons = scanner_data.combine_beacons(); + dbg!(&beacons.len()); + dbg!(scanner_data.max_aligned_sensor_distance()); + Ok(()) +} + +#[derive(Default, Debug)] +struct ScannerCloud { + aligned_scanners: Vec, + aligned_checking_for_neighbours_scanners: Vec, + unaligned_scanners: Vec, +} + +impl ScannerCloud { + fn new(mut scanners: Vec) -> ScannerCloud { + if let Some(first_aligned_scanner) = scanners.pop() { + ScannerCloud { + aligned_scanners: Vec::new(), + aligned_checking_for_neighbours_scanners: vec![first_aligned_scanner], + unaligned_scanners: scanners, + } + } else { + ScannerCloud::default() + } + } + + fn align_scanners(&mut self) { + while let Some(current_aligned_scanner) = + self.aligned_checking_for_neighbours_scanners.pop() + { + let mut to_remove_indices = Vec::new(); + for i in 0..self.unaligned_scanners.len() { + if let Some(aligned) = + self.unaligned_scanners[i].try_align_with(¤t_aligned_scanner) + { + to_remove_indices.push(i); + self.aligned_checking_for_neighbours_scanners.push(aligned); + } + } + for i in to_remove_indices.into_iter().rev() { + self.unaligned_scanners.remove(i); + } + + self.aligned_scanners.push(current_aligned_scanner); + } + + assert_eq!( + self.unaligned_scanners.len(), + 0, + "Not all scanners were aligned" + ); + assert_eq!( + self.aligned_checking_for_neighbours_scanners.len(), + 0, + "Not all aligned scanners were processed" + ); + } + + fn combine_beacons(&self) -> BTreeSet { + let mut combined_beacons = BTreeSet::new(); + for scanner in &self.aligned_scanners { + combined_beacons.append(&mut scanner.beacons.clone()) + } + combined_beacons + } + + fn max_aligned_sensor_distance(&self) -> i32 { + let mut max_distance = 0; + for a in &self.aligned_scanners { + for b in &self.aligned_scanners { + let distance = a.position.manhattan_distance(&b.position); + if distance > max_distance { + max_distance = distance; + } + } + } + max_distance + } +} + +#[derive(Debug, Clone)] +struct Scanner { + position: Point, + beacons: BTreeSet, +} + +impl Scanner { + fn try_align_with(&self, other: &Scanner) -> Option { + for (roll, pitch) in [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (0, 3)] { + for yaw in [0, 1, 2, 3] { + let candidate = self.spin(roll, pitch, yaw); + for candidate_position in candidate.beacons.iter() { + for other_position in other.beacons.iter() { + let aligned_candidate = + candidate.position(*other_position - *candidate_position); + if aligned_candidate.count_overlap(other) >= 12 { + return Some(aligned_candidate); + } + } + } + } + } + None + } + + fn spin(&self, roll: u8, pitch: u8, yaw: u8) -> Scanner { + let beacons = self + .beacons + .clone() + .into_iter() + .map(|mut beacon| { + for _ in 0..roll { + beacon = beacon.roll(); + } + beacon + }) + .map(|mut beacon| { + for _ in 0..pitch { + beacon = beacon.pitch(); + } + beacon + }) + .map(|mut beacon| { + for _ in 0..yaw { + beacon = beacon.yaw(); + } + beacon + }) + .collect(); + Scanner { + position: self.position, // this is wrong, but doesn't matter because we spin then position + beacons, + } + } + + fn position(&self, offset: Point) -> Scanner { + Scanner { + position: self.position + offset, + beacons: self.beacons.iter().map(|b| *b + offset).collect(), + } + } + + fn count_overlap(&self, other: &Scanner) -> usize { + self.beacons.intersection(&other.beacons).count() + } +} + +#[derive( + Debug, Default, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, derive_more::Sub, derive_more::Add, +)] +struct Point { + x: i32, + y: i32, + z: i32, +} + +impl Point { + fn roll(self) -> Self { + Point { + x: self.x, + y: self.z, + z: -self.y, + } + } + + fn pitch(self) -> Self { + Point { + x: -self.z, + y: self.y, + z: self.x, + } + } + + fn yaw(self) -> Self { + Point { + x: -self.y, + y: self.x, + z: self.z, + } + } + + fn manhattan_distance(&self, other: &Point) -> i32 { + (self.x - other.x).abs() + (self.y - other.y).abs() + (self.z - other.z).abs() + } +} + +fn parse_scanner_cloud(input: &str) -> IResult<&str, ScannerCloud> { + map( + separated_list1(many1(line_ending), parse_scanner), + ScannerCloud::new, + )(input) +} + +fn parse_scanner(input: &str) -> IResult<&str, Scanner> { + let (input, _) = tuple((tag("--- scanner"), not_line_ending, line_ending))(input)?; + map(separated_list1(line_ending, parse_point), |beacons| { + Scanner { + position: Point::default(), + beacons: beacons.into_iter().collect(), + } + })(input) +} + +fn parse_point(input: &str) -> IResult<&str, Point> { + map( + tuple((nom_i32, nom_char(','), nom_i32, nom_char(','), nom_i32)), + |(x, _, y, _, z)| Point { x, y, z }, + )(input) +} diff --git a/2021/src/bin/day_2.rs b/2021/src/bin/day_2.rs new file mode 100644 index 0000000..08d01c3 --- /dev/null +++ b/2021/src/bin/day_2.rs @@ -0,0 +1,100 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{i64 as nom_i64, line_ending, space1}, + combinator::{map, value}, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_2.txt")?; + let route = parse_route(&input).unwrap().1; + + let mut position = Position::default(); + for instruction in &route { + position.advance(&instruction); + } + dbg!(position.horizontal.0 * position.depth.0); + + Ok(()) +} + +#[derive(Debug)] +struct Route(Vec); + +impl<'a> IntoIterator for &'a Route { + type Item = &'a Instruction; + type IntoIter = std::slice::Iter<'a, Instruction>; + fn into_iter(self) -> ::IntoIter { + self.0.iter() + } +} + +#[derive(Debug)] +struct Instruction { + direction: Direction, + distance: Distance, +} + +#[derive(Debug, Clone)] +enum Direction { + Forward, + Up, + Down, +} +#[derive( + Default, + Debug, + Clone, + Copy, + derive_more::Add, + derive_more::AddAssign, + derive_more::Sub, + derive_more::SubAssign, +)] +struct Distance(i64); + +#[derive(Default, Debug)] +struct Position { + horizontal: Distance, + depth: Distance, +} + +impl Position { + fn advance(&mut self, instruction: &Instruction) { + match instruction.direction { + Direction::Forward => self.horizontal += instruction.distance, + Direction::Down => self.depth += instruction.distance, + Direction::Up => self.depth -= instruction.distance, + } + } +} + +fn parse_route(input: &str) -> IResult<&str, Route> { + map(separated_list1(line_ending, parse_instruction), Route)(input) +} + +fn parse_instruction(input: &str) -> IResult<&str, Instruction> { + map( + tuple((parse_direction, space1, parse_distance)), + |(direction, _, distance)| Instruction { + direction, + distance, + }, + )(input) +} + +fn parse_direction(input: &str) -> IResult<&str, Direction> { + alt(( + value(Direction::Forward, tag("forward")), + value(Direction::Up, tag("up")), + value(Direction::Down, tag("down")), + ))(input) +} + +fn parse_distance(input: &str) -> IResult<&str, Distance> { + map(nom_i64, Distance)(input) +} diff --git a/2021/src/bin/day_20.rs b/2021/src/bin/day_20.rs new file mode 100644 index 0000000..4b42658 --- /dev/null +++ b/2021/src/bin/day_20.rs @@ -0,0 +1,201 @@ +use nom::{ + branch::alt, + character::complete::{char as nom_char, line_ending}, + combinator::{map, map_res, value}, + multi::{many1, separated_list1}, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_20.txt")?; + let mut enhanceable_image = parse_enhanceable_image(&input).unwrap().1; + for _ in 0..2 { + enhanceable_image = enhanceable_image.enhance(); + } + dbg!(enhanceable_image.image.count_light_spots().unwrap()); + for _ in 2..50 { + enhanceable_image = enhanceable_image.enhance(); + } + dbg!(enhanceable_image.image.count_light_spots().unwrap()); + + Ok(()) +} + +#[derive(Debug)] +struct EnhanceableImage { + enhancement_lights: [bool; 512], + image: Image, +} + +impl EnhanceableImage { + fn enhance(&self) -> EnhanceableImage { + let current_background_dark = matches!(self.image, Image::LightSpots(_)); + let next_background_dark = + !self.enhancement_lights[if current_background_dark { 0 } else { 511 }]; + let mut spots = BTreeSet::new(); + + let top_left = self.image.top_left(1); + let bottom_right = self.image.bottom_right(1); + for y in top_left.y..=bottom_right.y { + for x in top_left.x..=bottom_right.x { + let center = Point { x, y }; + let surrounds = center.surrounds(); + let number = self.image.to_number(surrounds); + let center_is_light = self.enhancement_lights[number]; + if center_is_light == next_background_dark { + spots.insert(center); + } + } + } + + EnhanceableImage { + enhancement_lights: self.enhancement_lights.clone(), + image: if next_background_dark { + Image::LightSpots(spots) + } else { + Image::DarkSpots(spots) + }, + } + } +} + +#[derive(Debug)] +enum Image { + LightSpots(BTreeSet), + DarkSpots(BTreeSet), +} + +#[derive(Debug)] +enum ImageError { + InfiniteLight, +} + +impl Image { + fn count_light_spots(&self) -> Result { + match self { + Self::LightSpots(spots) => Ok(spots.len()), + Self::DarkSpots(_) => Err(ImageError::InfiniteLight), + } + } + + fn top_left(&self, margin: i32) -> Point { + let (Self::LightSpots(spots) | Self::DarkSpots(spots)) = self; + let min_x = spots.iter().map(|p| p.x).min().unwrap_or(0); + let min_y = spots.iter().map(|p| p.y).min().unwrap_or(0); + Point { + x: min_x - margin, + y: min_y - margin, + } + } + + fn bottom_right(&self, margin: i32) -> Point { + let (Self::LightSpots(spots) | Self::DarkSpots(spots)) = self; + let max_x = spots.iter().map(|p| p.x).max().unwrap_or(0); + let max_y = spots.iter().map(|p| p.y).max().unwrap_or(0); + Point { + x: max_x + margin, + y: max_y + margin, + } + } + + fn to_number(&self, bit_locations: [Point; 9]) -> usize { + let mut result = 0; + for bit_location in bit_locations { + result <<= 1; + let next_is_1 = match self { + Self::LightSpots(spots) => spots.contains(&bit_location), + Self::DarkSpots(spots) => !spots.contains(&bit_location), + }; + if next_is_1 { + result += 1; + } + } + result + } +} + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + x: i32, + y: i32, +} + +impl Point { + fn surrounds(&self) -> [Point; 9] { + [ + Point { + x: self.x - 1, + y: self.y - 1, + }, + Point { + x: self.x, + y: self.y - 1, + }, + Point { + x: self.x + 1, + y: self.y - 1, + }, + Point { + x: self.x - 1, + y: self.y, + }, + Point { + x: self.x, + y: self.y, + }, + Point { + x: self.x + 1, + y: self.y, + }, + Point { + x: self.x - 1, + y: self.y + 1, + }, + Point { + x: self.x, + y: self.y + 1, + }, + Point { + x: self.x + 1, + y: self.y + 1, + }, + ] + } +} + +fn parse_enhanceable_image(input: &str) -> IResult<&str, EnhanceableImage> { + map( + tuple((parse_enhancement_lights, many1(line_ending), parse_image)), + |(enhancement_lights, _, image)| EnhanceableImage { + enhancement_lights, + image, + }, + )(input) +} + +fn parse_enhancement_lights(input: &str) -> IResult<&str, [bool; 512]> { + map_res(many1(parse_pixel), |pixels| pixels.try_into())(input) +} + +fn parse_image(input: &str) -> IResult<&str, Image> { + map(separated_list1(line_ending, many1(parse_pixel)), |pixels| { + let mut result = BTreeSet::new(); + for (y, row) in pixels.into_iter().enumerate() { + for (x, light) in row.into_iter().enumerate() { + if light { + result.insert(Point { + x: x as i32, + y: y as i32, + }); + } + } + } + Image::LightSpots(result) + })(input) +} + +fn parse_pixel(input: &str) -> IResult<&str, bool> { + alt((value(true, nom_char('#')), value(false, nom_char('.'))))(input) +} diff --git a/2021/src/bin/day_21.rs b/2021/src/bin/day_21.rs new file mode 100644 index 0000000..245a0e6 --- /dev/null +++ b/2021/src/bin/day_21.rs @@ -0,0 +1,76 @@ +use cached::proc_macro::cached; +use nom::{ + bytes::complete::tag, + character::complete::u32 as nom_u32, + combinator::map, + sequence::{preceded, tuple}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_21.txt")?; + let player_positions = parse_starting_positions(&input).unwrap().1; + { + let mut player_positions = player_positions.clone(); + let mut player_scores = [0, 0]; + let mut dice = (1..=100).cycle().enumerate().peekable(); + let mut player_turn = 0; + while player_scores[0] < 1000 && player_scores[1] < 1000 { + let dice_roll: u32 = dice.by_ref().take(3).map(|(_, roll)| roll).sum(); + player_positions[player_turn] = (player_positions[player_turn] + dice_roll) % 10; + if player_positions[player_turn] == 0 { + player_positions[player_turn] = 10; + } + player_scores[player_turn] += player_positions[player_turn]; + player_turn = (player_turn + 1) % 2; + } + let losing_score = player_scores.iter().min().cloned().unwrap_or(0); + let dice_roll_count = dice.peek().unwrap().0; + dbg!((losing_score, dice_roll_count)); + dbg!(losing_score * dice_roll_count as u32); + } + + let win_counts = player_win_counts(player_positions, [0, 0]); + dbg!(win_counts); + dbg!(win_counts.into_iter().max().unwrap_or(0)); + Ok(()) +} + +#[cached] +fn player_win_counts(player_positions: [u32; 2], player_scores: [u32; 2]) -> [u64; 2] { + let mut win_counts = [0; 2]; + for dice_roll_1 in 1..=3 { + for dice_roll_2 in 1..=3 { + for dice_roll_3 in 1..=3 { + let dice_roll = dice_roll_1 + dice_roll_2 + dice_roll_3; + let mut new_position = (player_positions[0] + dice_roll) % 10; + if new_position == 0 { + new_position = 10; + } + let new_score = player_scores[0] + new_position; + if new_score >= 21 { + win_counts[0] += 1; + } else { + let recursive_wins = player_win_counts( + [player_positions[1], new_position], + [player_scores[1], new_score], + ); + win_counts[0] += recursive_wins[1]; + win_counts[1] += recursive_wins[0]; + } + } + } + } + win_counts +} + +fn parse_starting_positions(input: &str) -> IResult<&str, [u32; 2]> { + map( + tuple(( + preceded(tag("Player 1 starting position: "), nom_u32), + preceded(tag("\nPlayer 2 starting position: "), nom_u32), + )), + |(a, b)| [a, b], + )(input) +} diff --git a/2021/src/bin/day_22.rs b/2021/src/bin/day_22.rs new file mode 100644 index 0000000..85d9ec9 --- /dev/null +++ b/2021/src/bin/day_22.rs @@ -0,0 +1,379 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{i32 as nom_i32, line_ending}, + combinator::{map, value}, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{cmp, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_22.txt")?; + let instructions = parse_instructions(&input).unwrap().1; + { + let bounds_50 = Block { + min_x: -50, + max_x: 51, + min_y: -50, + max_y: 51, + min_z: -50, + max_z: 51, + }; + let mut octtree_50 = OctTree::default(); + for instruction in &instructions { + octtree_50.set_block(&bounds_50, &instruction.bounds, instruction.new_state); + } + dbg!(octtree_50.count_on_blocks(&bounds_50)); + } + + { + let problem_boundary = Block { + min_x: instructions + .iter() + .map(|i| i.bounds.min_x) + .min() + .unwrap_or(0), + max_x: instructions + .iter() + .map(|i| i.bounds.max_x) + .max() + .unwrap_or(0), + min_y: instructions + .iter() + .map(|i| i.bounds.min_y) + .min() + .unwrap_or(0), + max_y: instructions + .iter() + .map(|i| i.bounds.max_y) + .max() + .unwrap_or(0), + min_z: instructions + .iter() + .map(|i| i.bounds.min_z) + .min() + .unwrap_or(0), + max_z: instructions + .iter() + .map(|i| i.bounds.max_z) + .max() + .unwrap_or(0), + } + .expand_to_power_cube(); + + // This chunking and adding partial solutions is necessary + // because I can't fit the whole thing in memory at once :( + // It runs really slowly. + let mut count = 0; + for chunk_index in 0..8 { + let problem_boundary = problem_boundary.oct_chunk(chunk_index); + for chunk_index in 0..8 { + let problem_boundary = problem_boundary.oct_chunk(chunk_index); + for chunk_index in 0..8 { + let problem_boundary = problem_boundary.oct_chunk(chunk_index); + let mut octtree = OctTree::default(); + for instruction in &instructions { + octtree.set_block( + &problem_boundary, + &instruction.bounds, + instruction.new_state, + ); + } + count += dbg!(octtree.count_on_blocks(&problem_boundary)); + } + } + } + dbg!(count); + } + + Ok(()) +} + +#[derive(Default, Clone)] +struct OctTree { + data: OctTreeData, +} + +impl OctTree { + fn set_block(&mut self, self_bounds: &Block, bounds: &Block, new_val: bool) { + if bounds.completely_covers(self_bounds) { + self.data = new_val.into(); + } else if bounds.intersects(self_bounds) { + match &mut self.data { + OctTreeData::AllOff => { + if new_val { + self.split(self_bounds); + self.set_block(self_bounds, bounds, new_val); + } + } + OctTreeData::AllOn => { + if !new_val { + self.split(self_bounds); + self.set_block(self_bounds, bounds, new_val); + } + } + OctTreeData::BitSet(ref mut bits) => { + let min_x = cmp::max(self_bounds.min_x, bounds.min_x); + let max_x = cmp::min(self_bounds.max_x, bounds.max_x); + let min_x_index = (min_x - self_bounds.min_x) as usize; + let max_x_index = min_x_index + (max_x - min_x) as usize; + + let min_y = cmp::max(self_bounds.min_y, bounds.min_y); + let max_y = cmp::min(self_bounds.max_y, bounds.max_y); + let min_y_index = (min_y - self_bounds.min_y) as usize; + let max_y_index = min_y_index + (max_y - min_y) as usize; + + let min_z = cmp::max(self_bounds.min_z, bounds.min_z); + let max_z = cmp::min(self_bounds.max_z, bounds.max_z); + let min_z_index = (min_z - self_bounds.min_z) as usize; + let max_z_index = min_z_index + (max_z - min_z) as usize; + + for z_index in min_z_index..max_z_index { + let z_bit_index = z_index << 4; + for y_index in min_y_index..max_y_index { + let y_bit_index = y_index << 2; + for x_index in min_x_index..max_x_index { + let x_bit_index = x_index; + let bit_mask = 1u64 << (z_bit_index + y_bit_index + x_bit_index); + if new_val { + *bits |= bit_mask; + } else { + *bits &= !bit_mask; + } + } + } + } + + if *bits == 0 { + self.data = OctTreeData::AllOff; + } else if *bits == !0u64 { + self.data = OctTreeData::AllOn; + } + } + OctTreeData::Diverse(ref mut subtrees) => { + for (sub_index, sub) in subtrees.iter_mut().enumerate() { + sub.set_block(&self_bounds.oct_chunk(sub_index as u8), bounds, new_val); + } + if subtrees + .iter() + .all(|sub| matches!(sub.data, OctTreeData::AllOn)) + { + self.data = OctTreeData::AllOn; + } else if subtrees + .iter() + .all(|sub| matches!(sub.data, OctTreeData::AllOff)) + { + self.data = OctTreeData::AllOff; + } + } + }; + } + } + + fn split(&mut self, self_bounds: &Block) { + assert!(!matches!(self.data, OctTreeData::Diverse(_))); + if self_bounds.volume() == 64 { + let new_bitset = match self.data { + OctTreeData::AllOn => !0u64, + OctTreeData::AllOff => 0, + _ => panic!("weird split"), + }; + self.data = OctTreeData::BitSet(new_bitset); + } else { + let template = OctTree { + data: self.data.clone(), + }; + self.data = OctTreeData::Diverse(Box::new([ + template.clone(), + template.clone(), + template.clone(), + template.clone(), + template.clone(), + template.clone(), + template.clone(), + template.clone(), + ])); + } + } + + fn count_on_blocks(&self, self_bounds: &Block) -> usize { + match &self.data { + OctTreeData::AllOff => 0, + OctTreeData::AllOn => self_bounds.volume(), + OctTreeData::BitSet(bitset) => bitset.count_ones() as usize, + OctTreeData::Diverse(subtrees) => subtrees + .iter() + .enumerate() + .map(|(index, sub)| sub.count_on_blocks(&self_bounds.oct_chunk(index as u8))) + .sum(), + } + } +} + +#[derive(Clone)] +enum OctTreeData { + AllOff, + AllOn, + BitSet(u64), + Diverse(Box<[OctTree; 8]>), +} + +impl Default for OctTreeData { + fn default() -> OctTreeData { + Self::AllOff + } +} + +impl From for OctTreeData { + fn from(b: bool) -> Self { + if b { + Self::AllOn + } else { + Self::AllOff + } + } +} + +#[derive(Debug)] +struct Instruction { + new_state: bool, + bounds: Block, +} + +#[derive(Debug, Clone)] +struct Block { + min_x: i32, + max_x: i32, + min_y: i32, + max_y: i32, + min_z: i32, + max_z: i32, +} + +impl Block { + fn volume(&self) -> usize { + let x = (self.max_x - self.min_x) as usize; + let y = (self.max_y - self.min_y) as usize; + let z = (self.max_z - self.min_z) as usize; + x * y * z + } + + fn completely_covers(&self, other: &Self) -> bool { + self.min_x <= other.min_x + && self.max_x >= other.max_x + && self.min_y <= other.min_y + && self.max_y >= other.max_y + && self.min_z <= other.min_z + && self.max_z >= other.max_z + } + + fn intersects(&self, other: &Self) -> bool { + if self.max_x <= other.min_x + || self.min_x >= other.max_x + || self.max_y <= other.min_y + || self.min_y >= other.max_y + || self.max_z <= other.min_z + || self.min_z >= other.max_z + { + false + } else { + true + } + } + + fn oct_chunk(&self, chunk: u8) -> Block { + let lower_x = (chunk & 1) == 0; + let lower_y = (chunk & 2) == 0; + let lower_z = (chunk & 4) == 0; + + let mid_x = (self.min_x + self.max_x) / 2; + let mid_y = (self.min_y + self.max_y) / 2; + let mid_z = (self.min_z + self.max_z) / 2; + + Block { + min_x: if lower_x { self.min_x } else { mid_x }, + max_x: if lower_x { mid_x } else { self.max_x }, + min_y: if lower_y { self.min_y } else { mid_y }, + max_y: if lower_y { mid_y } else { self.max_y }, + min_z: if lower_z { self.min_z } else { mid_z }, + max_z: if lower_z { mid_z } else { self.max_z }, + } + } + + fn expand_to_power_cube(&self) -> Block { + let mag_x = self.max_x - self.min_x; + let mag_y = self.max_y - self.min_y; + let mag_z = self.max_z - self.min_z; + let mag_max = cmp::max(mag_x, cmp::max(mag_y, mag_z)); + let first_power_of_2 = (0..) + .map(|pow| 2_i32.pow(pow)) + .filter(|pow_size| *pow_size >= mag_max) + .next() + .unwrap(); + + Block { + min_x: self.min_x, + max_x: self.max_x + first_power_of_2 - mag_x, + min_y: self.min_y, + max_y: self.max_y + first_power_of_2 - mag_y, + min_z: self.min_z, + max_z: self.max_z + first_power_of_2 - mag_z, + } + } +} + +fn parse_instructions(input: &str) -> IResult<&str, Vec> { + separated_list1(line_ending, parse_instruction)(input) +} + +fn parse_instruction(input: &str) -> IResult<&str, Instruction> { + map( + tuple(( + alt((value(true, tag("on ")), value(false, tag("off ")))), + parse_block, + )), + |(new_state, bounds)| Instruction { new_state, bounds }, + )(input) +} + +fn parse_block(input: &str) -> IResult<&str, Block> { + map( + tuple(( + tag("x="), + nom_i32, + tag(".."), + nom_i32, + tag(",y="), + nom_i32, + tag(".."), + nom_i32, + tag(",z="), + nom_i32, + tag(".."), + nom_i32, + )), + |( + _, + min_x, + _, + max_x_inclusive, + _, + min_y, + _, + max_y_inclusive, + _, + min_z, + _, + max_z_inclusive, + )| Block { + min_x, + max_x: max_x_inclusive + 1, + min_y, + max_y: max_y_inclusive + 1, + min_z, + max_z: max_z_inclusive + 1, + }, + )(input) +} diff --git a/2021/src/bin/day_23.rs b/2021/src/bin/day_23.rs new file mode 100644 index 0000000..ed2fb01 --- /dev/null +++ b/2021/src/bin/day_23.rs @@ -0,0 +1,224 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{char as nom_char, line_ending, not_line_ending}, + combinator::value, + multi::{many1, separated_list1}, + sequence::{delimited, pair}, + IResult, +}; +use std::{cmp, collections::HashSet, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_23.txt")?; + let maze = parse_maze(&input).unwrap().1; + dbg!(find_shortest_path(&maze).cost); + Ok(()) +} + +fn find_shortest_path(maze: &Maze) -> Move { + let mut visited = HashSet::new(); + visited.insert(maze.clone()); + let mut frontier = vec![Move { + next_state: maze.clone(), + cost: 0, + }]; + + let mut best_so_far: Option = None; + + while let Some(current) = frontier.pop() { + if let Some(best_so_far) = &best_so_far { + if current.cost >= best_so_far.cost { + return best_so_far.clone(); + } + } + + let next_moves: Vec = current + .next_state + .valid_moves() + .into_iter() + .map(|next| Move { + cost: next.cost + current.cost, + ..next + }) + .collect(); + for next in next_moves { + if next.next_state.is_complete() { + best_so_far = if let Some(best_so_far) = best_so_far { + if best_so_far.cost < next.cost { + Some(best_so_far) + } else { + Some(next.clone()) + } + } else { + Some(next.clone()) + }; + } else if !visited.contains(&next.next_state) { + visited.insert(next.next_state.clone()); + frontier.push(next); + } + } + frontier.sort_unstable_by(|a, b| b.cost.cmp(&a.cost)); + } + best_so_far.expect("There is no path through!") +} + +#[derive(Debug, Clone)] +struct Move { + next_state: Maze, + cost: usize, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +struct Maze { + corridor: Vec>, + rooms: Vec, +} + +impl Maze { + fn is_complete(&self) -> bool { + self.rooms.iter().all(|room| room.is_complete()) + } + + fn valid_moves(&self) -> Vec { + let mut valid_moves = Vec::new(); + + for i in 0..self.corridor.len() { + if let Some(shrimp) = self.corridor[i] { + let target_room = &self.rooms[shrimp / 2 - 1]; + if target_room.can_enter() { + let route_free = (cmp::min(shrimp, i)..=cmp::max(shrimp, i)) + .all(|route_i| route_i == i || self.corridor[route_i].is_none()); + if route_free { + let mut next_state = self.clone(); + next_state.corridor[i] = None; + let next_room = &mut next_state.rooms[shrimp / 2 - 1]; + let room_depth = next_room + .max_free() + .expect("no space in room, but we checked!"); + next_room.contents[room_depth] = Some(shrimp); + let distance = room_depth + 1 + cmp::max(shrimp, i) - cmp::min(shrimp, i); + let cost = calculate_cost(shrimp, distance); + valid_moves.push(Move { next_state, cost }); + } + } + } + } + + for (room_i, room) in self + .rooms + .iter() + .enumerate() + .filter(|(_, room)| !room.can_enter()) + { + if let Some((room_depth, shrimp)) = room + .contents + .iter() + .enumerate() + .filter_map(|(room_depth, maybe_shrimp)| { + maybe_shrimp.map(|shrimp| (room_depth, shrimp)) + }) + .next() + { + for corridor_i in 0..self.corridor.len() { + let in_entrance = self.rooms.iter().any(|room| room.entrance == corridor_i); + let route_free = (cmp::min(room.entrance, corridor_i) + ..=cmp::max(room.entrance, corridor_i)) + .all(|route_i| self.corridor[route_i].is_none()); + if !in_entrance && route_free { + let mut next_state = self.clone(); + next_state.corridor[corridor_i] = Some(shrimp); + next_state.rooms[room_i].contents[room_depth] = None; + + let distance = room_depth + 1 + cmp::max(room.entrance, corridor_i) + - cmp::min(room.entrance, corridor_i); + let cost = calculate_cost(shrimp, distance); + valid_moves.push(Move { next_state, cost }); + } + } + } + } + + valid_moves + } +} + +fn calculate_cost(shrimp: usize, distance: usize) -> usize { + let shrimp_cost = match shrimp { + 2 => 1, + 4 => 10, + 6 => 100, + 8 => 1000, + _ => panic!("Unknown shrimp"), + }; + shrimp_cost * distance +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +struct Room { + entrance: usize, + contents: Vec>, +} + +impl Room { + fn is_complete(&self) -> bool { + self.contents + .iter() + .all(|slot| slot == &Some(self.entrance)) + } + fn can_enter(&self) -> bool { + self.contents + .iter() + .all(|slot| slot.is_none() || slot == &Some(self.entrance)) + } + fn max_free(&self) -> Option { + self.contents.iter().rposition(|slot| slot.is_none()) + } +} + +fn parse_maze(input: &str) -> IResult<&str, Maze> { + let (input, _) = pair(not_line_ending, line_ending)(input)?; // skip first line + let (input, corridor) = delimited(nom_char('#'), many1(corridor_contents), tag("#\n"))(input)?; + + let (input, rooms_line_1) = delimited( + tag("###"), + separated_list1(nom_char('#'), corridor_contents), + tag("###\n"), + )(input)?; + let (input, rooms_line_2) = delimited( + tag(" #"), + separated_list1(nom_char('#'), corridor_contents), + tag("#\n"), + )(input)?; + + let rooms = vec![ + Room { + entrance: 2, + contents: vec![rooms_line_1[0], Some(8), Some(8), rooms_line_2[0]], + }, + Room { + entrance: 4, + contents: vec![rooms_line_1[1], Some(6), Some(4), rooms_line_2[1]], + }, + Room { + entrance: 6, + contents: vec![rooms_line_1[2], Some(4), Some(2), rooms_line_2[2]], + }, + Room { + entrance: 8, + contents: vec![rooms_line_1[3], Some(2), Some(6), rooms_line_2[3]], + }, + ]; + + Ok((input, Maze { corridor, rooms })) +} + +fn corridor_contents(input: &str) -> IResult<&str, Option> { + alt(( + value(None, nom_char('.')), + value(Some(2), nom_char('A')), + value(Some(4), nom_char('B')), + value(Some(6), nom_char('C')), + value(Some(8), nom_char('D')), + ))(input) +} diff --git a/2021/src/bin/day_24.rs b/2021/src/bin/day_24.rs new file mode 100644 index 0000000..2916f57 --- /dev/null +++ b/2021/src/bin/day_24.rs @@ -0,0 +1,588 @@ +use nom::{ + branch::alt, + bytes::complete::{is_not, tag}, + character::complete::{line_ending, space1}, + combinator::map, + multi::separated_list1, + sequence::{pair, preceded, separated_pair}, + IResult, +}; +use proptest::prelude::*; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_24.txt")?; + let program = parse_program(&input).unwrap().1; + program.print_oracle(); + + // input[2] - 8 == input[3] + // input[4] + 8 == input[5] + // input[7] + 6 == input[8] + // input[9] + 5 == input[10] + // input[6] - 3 == input[11] + // input[1] - 1 == input[12] + // input[0] - 5 == input[13] + + dbg!(refactored([9, 9, 9, 1, 1, 9, 9, 3, 9, 4, 9, 6, 8, 4]).unwrap()); + dbg!(refactored([6, 2, 9, 1, 1, 9, 4, 1, 7, 1, 6, 1, 1, 1]).unwrap()); + Ok(()) +} + +fn subroutine_1( + next_input: i64, + running_total: i64, + mod_conditional: i64, + result_additive: i64, +) -> i64 { + if next_input != (running_total % 26) + mod_conditional { + running_total * 26 + next_input + result_additive + } else { + running_total + } +} + +fn subroutine_2( + next_input: i64, + running_total: i64, + mod_conditional: i64, + result_additive: i64, +) -> i64 { + if next_input != running_total % 26 + mod_conditional { + running_total / 26 * 26 + next_input + result_additive + } else { + running_total / 26 + } +} + +fn refactored_one_to_nine_assumption(input: [i64; 14]) -> Result { + let mut z = input[0] + 6; + // z-stack 1 + z = z * 26 + input[1] + 6; + // z-stack 2 + z = z * 26 + input[2] + 3; + // z-stack 3 + z = if input[2] - 8 == input[3] { + z / 26 + } else { + z / 26 * 26 + input[3] + 11 + }; + // z-stack 2 + z = z * 26 + input[4] + 9; + // z-stack 3 + z = if input[4] + 8 == input[5] { + z / 26 + } else { + z / 26 * 26 + input[5] + 3 + }; + // z-stack 2 + z = z * 26 + input[6] + 13; + // z-stack 3 + z = z * 26 + input[7] + 6; + // z-stack 4 + z = if input[7] + 6 == input[8] { + z / 26 + } else { + z / 26 * 26 + input[8] + 14 + }; + // z-stack 3 + z = z * 26 + input[9] + 10; + // z-stack 4 + z = if input[9] + 5 == input[10] { + z / 26 + } else { + z / 26 * 26 + input[10] + 12 + }; + // z-stack 3 + z = if input[9] + 5 == input[10] { + if input[7] + 6 == input[8] { + if input[6] + 13 - 16 == input[11] { + z / 26 + } else { + z / 26 * 26 + input[11] + 10 + } + } else { + if input[8] + 14 - 16 == input[11] { + z / 26 + } else { + z / 26 * 26 + input[11] + 10 + } + } + } else { + if input[10] + 12 - 16 == input[11] { + z / 26 + } else { + z / 26 * 26 + input[11] + 10 + } + }; + // z-stack 2 + z = subroutine_2(input[12], z, -7, 11); + // z-stack 1 + z = subroutine_2(input[13], z, -11, 15); + // z-stack 0 + + Ok(z) +} + +fn refactored(input: [i64; 14]) -> Result { + let mut z: i64 = 0; + + z = subroutine_1(input[0], z, 12, 6); + z = subroutine_1(input[1], z, 10, 6); + z = subroutine_1(input[2], z, 13, 3); + z = subroutine_2(input[3], z, -11, 11); + z = subroutine_1(input[4], z, 13, 9); + z = subroutine_2(input[5], z, -1, 3); + z = subroutine_1(input[6], z, 10, 13); + z = subroutine_1(input[7], z, 11, 6); + z = subroutine_2(input[8], z, 0, 14); + z = subroutine_1(input[9], z, 10, 10); + z = subroutine_2(input[10], z, -5, 12); + z = subroutine_2(input[11], z, -16, 10); + z = subroutine_2(input[12], z, -7, 11); + z = subroutine_2(input[13], z, -11, 15); + + Ok(z) +} + +#[derive(Debug)] +struct Program(Vec); +impl Program { + fn print_oracle(&self) { + println!("fn oracle(input: [i64; 14]) -> Result {{"); + println!("let mut w: i64 = 0;"); + println!("let mut x: i64 = 0;"); + println!("let mut y: i64 = 0;"); + println!("let mut z: i64 = 0;"); + + let mut input_index = 0; + for instruction in &self.0 { + match instruction { + Instruction::Inp(a) => { + println!("{} = input[{}];", a, input_index); + input_index += 1; + } + Instruction::Add(a, b) => { + println!("{0} = {0} + {1};", a, b); + } + Instruction::Mul(a, b) => { + println!("{0} = {0} * {1};", a, b); + } + Instruction::Div(a, b) => { + println!("if {0} == 0 {{ return Err(\"Div by 0\".into()); }}", b); + println!("{0} = {0} / {1};", a, b); + } + Instruction::Mod(a, b) => { + println!("if {0} == 0 {{ return Err(\"Mod by 0\".into()); }}", b); + println!("{0} = {0} % {1};", a, b); + } + Instruction::Eql(a, b) => { + println!("{0} = if {0} == {1} {{ 1 }} else {{ 0 }};", a, b); + } + } + } + println!("Ok(z)"); + println!("}}"); + } +} + +#[derive(Debug)] +enum Instruction { + Inp(String), + Add(String, String), + Mul(String, String), + Div(String, String), + Mod(String, String), + Eql(String, String), +} + +fn parse_program(input: &str) -> IResult<&str, Program> { + map(separated_list1(line_ending, parse_instruction), Program)(input) +} + +fn parse_instruction(input: &str) -> IResult<&str, Instruction> { + alt(( + map(preceded(pair(tag("inp"), space1), word), |a| { + Instruction::Inp(a) + }), + map( + preceded(pair(tag("add"), space1), separated_pair(word, space1, word)), + |(a, b)| Instruction::Add(a, b), + ), + map( + preceded(pair(tag("mul"), space1), separated_pair(word, space1, word)), + |(a, b)| Instruction::Mul(a, b), + ), + map( + preceded(pair(tag("div"), space1), separated_pair(word, space1, word)), + |(a, b)| Instruction::Div(a, b), + ), + map( + preceded(pair(tag("mod"), space1), separated_pair(word, space1, word)), + |(a, b)| Instruction::Mod(a, b), + ), + map( + preceded(pair(tag("eql"), space1), separated_pair(word, space1, word)), + |(a, b)| Instruction::Eql(a, b), + ), + ))(input) +} + +fn word(input: &str) -> IResult<&str, String> { + map(is_not(" \t\r\n"), |s: &str| s.to_string())(input) +} + +#[allow(unused_assignments)] +fn oracle(input: [i64; 14]) -> Result { + let mut w: i64 = 0; + let mut x: i64 = 0; + let mut y: i64 = 0; + let mut z: i64 = 0; + w = input[0]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 1 == 0 { + return Err("Div by 0".into()); + } + z = z / 1; + x = x + 12; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 6; + y = y * x; + z = z + y; + w = input[1]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 1 == 0 { + return Err("Div by 0".into()); + } + z = z / 1; + x = x + 10; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 6; + y = y * x; + z = z + y; + w = input[2]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 1 == 0 { + return Err("Div by 0".into()); + } + z = z / 1; + x = x + 13; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 3; + y = y * x; + z = z + y; + w = input[3]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 26 == 0 { + return Err("Div by 0".into()); + } + z = z / 26; + x = x + -11; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 11; + y = y * x; + z = z + y; + w = input[4]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 1 == 0 { + return Err("Div by 0".into()); + } + z = z / 1; + x = x + 13; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 9; + y = y * x; + z = z + y; + w = input[5]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 26 == 0 { + return Err("Div by 0".into()); + } + z = z / 26; + x = x + -1; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 3; + y = y * x; + z = z + y; + w = input[6]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 1 == 0 { + return Err("Div by 0".into()); + } + z = z / 1; + x = x + 10; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 13; + y = y * x; + z = z + y; + w = input[7]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 1 == 0 { + return Err("Div by 0".into()); + } + z = z / 1; + x = x + 11; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 6; + y = y * x; + z = z + y; + w = input[8]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 26 == 0 { + return Err("Div by 0".into()); + } + z = z / 26; + x = x + 0; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 14; + y = y * x; + z = z + y; + w = input[9]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 1 == 0 { + return Err("Div by 0".into()); + } + z = z / 1; + x = x + 10; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 10; + y = y * x; + z = z + y; + w = input[10]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 26 == 0 { + return Err("Div by 0".into()); + } + z = z / 26; + x = x + -5; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 12; + y = y * x; + z = z + y; + w = input[11]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 26 == 0 { + return Err("Div by 0".into()); + } + z = z / 26; + x = x + -16; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 10; + y = y * x; + z = z + y; + w = input[12]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 26 == 0 { + return Err("Div by 0".into()); + } + z = z / 26; + x = x + -7; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 11; + y = y * x; + z = z + y; + w = input[13]; + x = x * 0; + x = x + z; + if 26 == 0 { + return Err("Mod by 0".into()); + } + x = x % 26; + if 26 == 0 { + return Err("Div by 0".into()); + } + z = z / 26; + x = x + -11; + x = if x == w { 1 } else { 0 }; + x = if x == 0 { 1 } else { 0 }; + y = y * 0; + y = y + 25; + y = y * x; + y = y + 1; + z = z * y; + y = y * 0; + y = y + w; + y = y + 15; + y = y * x; + z = z + y; + Ok(z) +} + +proptest! { + #[test] + fn oracle_matches_refactored(input in proptest::array::uniform14(1i64..10)) { + let oracle_result = oracle(input.clone()); + let refactored_result = refactored(input.clone()); + let refactored_one_to_nine_assumption_result = refactored_one_to_nine_assumption(input); + assert_eq!(oracle_result, refactored_result); + assert_eq!(oracle_result, refactored_one_to_nine_assumption_result); + } +} diff --git a/2021/src/bin/day_25.rs b/2021/src/bin/day_25.rs new file mode 100644 index 0000000..742c911 --- /dev/null +++ b/2021/src/bin/day_25.rs @@ -0,0 +1,98 @@ +use nom::{ + branch::alt, + character::complete::{char as nom_char, line_ending}, + combinator::{map, value}, + multi::{many1, separated_list1}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_25.txt")?; + let mut seafloor = parse_seafloor(&input).unwrap().1; + for i in 1.. { + let next = seafloor.next(); + if next == seafloor { + dbg!(i); + break; + } + seafloor = next; + } + Ok(()) +} + +#[derive(Debug, PartialEq, Eq)] +struct Seafloor(Vec>>); + +impl Seafloor { + fn next(&self) -> Seafloor { + self.next_east().next_south() + } + + fn next_east(&self) -> Seafloor { + let mut results = Vec::new(); + for y in 0..self.0.len() { + let mut current_row = Vec::new(); + for x in 0..self.0[y].len() { + let old = &self.0[y][x]; + let old_left = &self.0[y][if x == 0 { self.0[y].len() - 1 } else { x - 1 }]; + let old_right = &self.0[y][(x + 1) % self.0[y].len()]; + + let new = if *old == None && *old_left == Some(Cucumber::East) { + old_left.clone() + } else if *old == Some(Cucumber::East) && *old_right == None { + None + } else { + old.clone() + }; + current_row.push(new); + } + results.push(current_row); + } + Seafloor(results) + } + + fn next_south(&self) -> Seafloor { + let mut results = Vec::new(); + for y in 0..self.0.len() { + let mut current_row = Vec::new(); + for x in 0..self.0[y].len() { + let old = &self.0[y][x]; + let old_up = &self.0[if y == 0 { self.0.len() - 1 } else { y - 1 }][x]; + let old_down = &self.0[(y + 1) % self.0.len()][x]; + + let new = if *old == None && *old_up == Some(Cucumber::South) { + old_up.clone() + } else if *old == Some(Cucumber::South) && *old_down == None { + None + } else { + old.clone() + }; + current_row.push(new); + } + results.push(current_row); + } + Seafloor(results) + } +} + +#[derive(Debug, Clone, PartialEq, Eq)] +enum Cucumber { + East, + South, +} + +fn parse_seafloor(input: &str) -> IResult<&str, Seafloor> { + map( + separated_list1(line_ending, many1(parse_cucumber)), + Seafloor, + )(input) +} + +fn parse_cucumber(input: &str) -> IResult<&str, Option> { + alt(( + value(None, nom_char('.')), + value(Some(Cucumber::East), nom_char('>')), + value(Some(Cucumber::South), nom_char('v')), + ))(input) +} diff --git a/2021/src/bin/day_2_part_2.rs b/2021/src/bin/day_2_part_2.rs new file mode 100644 index 0000000..de5b334 --- /dev/null +++ b/2021/src/bin/day_2_part_2.rs @@ -0,0 +1,124 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{i64 as nom_i64, line_ending, space1}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_2.txt")?; + let route = parse_route(&input).unwrap().1; + + let mut position = Position::default(); + for instruction in &route { + position.advance(&instruction); + } + dbg!(position.horizontal.0 * position.depth.0); + + Ok(()) +} + +#[derive(Debug)] +struct Route(Vec); + +impl<'a> IntoIterator for &'a Route { + type Item = &'a Instruction; + type IntoIter = std::slice::Iter<'a, Instruction>; + fn into_iter(self) -> ::IntoIter { + self.0.iter() + } +} + +#[derive(Debug)] +enum Instruction { + Forward(Distance), + Up(Aim), + Down(Aim), +} + +#[derive( + Default, + Debug, + Clone, + Copy, + derive_more::Add, + derive_more::AddAssign, + derive_more::Sub, + derive_more::SubAssign, +)] +struct Distance(i64); +#[derive( + Default, + Debug, + Clone, + Copy, + derive_more::Add, + derive_more::AddAssign, + derive_more::Sub, + derive_more::SubAssign, +)] +struct Aim(i64); + +impl std::ops::Mul for Aim { + type Output = Distance; + fn mul(self, other: Distance) -> Distance { + Distance(self.0 * other.0) + } +} + +#[derive(Default, Debug)] +struct Position { + horizontal: Distance, + depth: Distance, + aim: Aim, +} + +impl Position { + fn advance(&mut self, instruction: &Instruction) { + match instruction { + Instruction::Forward(distance) => { + self.horizontal += *distance; + self.depth += self.aim * *distance; + } + Instruction::Down(aim) => self.aim += *aim, + Instruction::Up(aim) => self.aim -= *aim, + } + } +} + +fn parse_route(input: &str) -> IResult<&str, Route> { + map(separated_list1(line_ending, parse_instruction), Route)(input) +} + +fn parse_instruction(input: &str) -> IResult<&str, Instruction> { + alt((parse_forward, parse_up, parse_down))(input) +} + +fn parse_forward(input: &str) -> IResult<&str, Instruction> { + map( + tuple((tag("forward"), space1, parse_distance)), + |(_, _, distance)| Instruction::Forward(distance), + )(input) +} +fn parse_up(input: &str) -> IResult<&str, Instruction> { + map(tuple((tag("up"), space1, parse_aim)), |(_, _, aim)| { + Instruction::Up(aim) + })(input) +} +fn parse_down(input: &str) -> IResult<&str, Instruction> { + map(tuple((tag("down"), space1, parse_aim)), |(_, _, aim)| { + Instruction::Down(aim) + })(input) +} + +fn parse_distance(input: &str) -> IResult<&str, Distance> { + map(nom_i64, Distance)(input) +} + +fn parse_aim(input: &str) -> IResult<&str, Aim> { + map(nom_i64, Aim)(input) +} diff --git a/2021/src/bin/day_3.rs b/2021/src/bin/day_3.rs new file mode 100644 index 0000000..2238dfb --- /dev/null +++ b/2021/src/bin/day_3.rs @@ -0,0 +1,128 @@ +use nom::{ + character::complete::{digit1, line_ending}, + combinator::{map, map_res}, + multi::separated_list1, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_3.txt")?; + let diagnostics = parse_diagnostics(&input).unwrap().1; + + dbg!(diagnostics.gamma()); + dbg!(diagnostics.epsilon()); + dbg!(diagnostics.oxygen()); + dbg!(diagnostics.co2()); + dbg!(diagnostics.gamma() * diagnostics.epsilon()); + dbg!(diagnostics.oxygen() * diagnostics.co2()); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Diagnostics { + bitsets: Vec, + bitset_len: usize, +} + +impl Diagnostics { + fn new(bitsets: Vec) -> Diagnostics { + Diagnostics { + bitset_len: bitsets.iter().map(|b| b.len).max().unwrap_or(0), + bitsets, + } + } + + fn gamma(&self) -> Bitset { + let mut gamma = Bitset { + bits: 0, + len: self.bitset_len, + }; + for bit in 0..gamma.len { + let ones_count = self + .bitsets + .iter() + .filter(|bitset| bitset.check_bit(bit)) + .count(); + if ones_count >= self.bitsets.len() / 2 { + gamma.set_bit(bit); + } + } + gamma + } + + fn epsilon(&self) -> Bitset { + !self.gamma() + } + + fn oxygen(&self) -> Bitset { + self.bit_criteria_match(|d| d.gamma()) + } + + fn co2(&self) -> Bitset { + self.bit_criteria_match(|d| d.epsilon()) + } + + fn bit_criteria_match(&self, criteria: impl Fn(&Diagnostics) -> Bitset) -> Bitset { + let mut candidates = self.clone(); + for bit in (0..self.bitset_len).rev() { + let bit_criteria = criteria(&candidates).check_bit(bit); + candidates + .bitsets + .retain(|candidate| candidate.check_bit(bit) == bit_criteria); + if candidates.bitsets.len() == 1 { + return candidates.bitsets[0]; + } + } + Bitset::default() + } +} + +#[derive(Default, Debug, Clone, Copy)] +struct Bitset { + bits: u32, + len: usize, +} + +impl Bitset { + fn check_bit(&self, bit: usize) -> bool { + self.bits & (1 << bit) != 0 + } + + fn set_bit(&mut self, bit: usize) { + self.bits |= 1 << bit; + } +} + +impl std::ops::Mul for Bitset { + type Output = Self; + fn mul(self, rhs: Bitset) -> Self::Output { + Bitset { + bits: self.bits * rhs.bits, + len: self.len.max(rhs.len), // dodgy. This might need to grow. + } + } +} +impl std::ops::Not for Bitset { + type Output = Bitset; + fn not(self) -> ::Output { + Bitset { + bits: !self.bits & ((1 << self.len) - 1), + len: self.len, + } + } +} + +fn parse_diagnostics(input: &str) -> IResult<&str, Diagnostics> { + map(separated_list1(line_ending, parse_bitset), Diagnostics::new)(input) +} + +fn parse_bitset(input: &str) -> IResult<&str, Bitset> { + map_res(digit1, |num| { + u32::from_str_radix(num, 2).map(|bits| Bitset { + bits, + len: num.len(), + }) + })(input) +} diff --git a/2021/src/bin/day_4.rs b/2021/src/bin/day_4.rs new file mode 100644 index 0000000..3938e14 --- /dev/null +++ b/2021/src/bin/day_4.rs @@ -0,0 +1,259 @@ +use nom::{ + bytes::complete::tag, + character::complete::{line_ending, space0, space1, u32 as nom_u32}, + combinator::{map, map_res}, + multi::{many1, separated_list1}, + sequence::{preceded, tuple}, + IResult, +}; +use std::fs; +use thiserror::Error; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_4.txt")?; + let mut bingo_game = parse_bingo_game(&input).unwrap().1; + let total_boards = bingo_game.boards.len(); + + let mut winning_game_iter = std::iter::repeat_with(|| bingo_game.do_draw()).flatten(); + + let (winning_block, winning_board, winning_mask) = winning_game_iter.next().unwrap(); + dbg!(winning_board.score(&winning_mask) * winning_block); + + let (losing_block, losing_board, losing_mask) = + winning_game_iter.nth(total_boards - 2).unwrap(); + dbg!(losing_board.score(&losing_mask) * losing_block); + + Ok(()) +} + +const BINGO_BOARD_WIDTH: usize = 5; + +#[derive(Debug)] +struct BingoGame { + draws: Vec, + boards: Vec, + masks: Vec, +} + +impl BingoGame { + fn do_draw(&mut self) -> Vec<(BingoBlock, BingoBoard, BingoBoardMask)> { + let mut wins = Vec::new(); + let mut results = Vec::new(); + + if let Some(block) = self.draws.pop() { + for (index, (mask, board)) in self + .masks + .iter_mut() + .zip(self.boards.iter()) + .enumerate() + .rev() + { + if let Some((row, col)) = board.find_block(&block) { + mask.mark(row, col); + if mask.has_bingo() { + wins.push(index); + } + } + } + for win in wins { + results.push(( + block.clone(), + self.boards.remove(win), + self.masks.remove(win), + )) + } + } + + results + } +} + +#[derive(Debug, Error)] +enum BingoBoardParseError { + #[error("input board was the wrong width")] + WrongWidth, + #[error("input board was the wrong height")] + WrongHeight, +} + +#[derive(Debug, Default, Clone, PartialEq, Eq)] +struct BingoBoardMask { + data: [[bool; BINGO_BOARD_WIDTH]; BINGO_BOARD_WIDTH], +} + +impl BingoBoardMask { + fn has_bingo(&self) -> bool { + for i in 0..BINGO_BOARD_WIDTH { + let row_bingo = self.data[i].iter().all(|marked| *marked); + let col_bingo = self.data.iter().all(|row| row[i]); + if row_bingo || col_bingo { + return true; + } + } + false + } + + fn mark(&mut self, row: usize, col: usize) { + self.data[row][col] = true; + } +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct BingoBoard { + data: [[BingoBlock; BINGO_BOARD_WIDTH]; BINGO_BOARD_WIDTH], +} + +impl BingoBoard { + fn find_block(&self, block: &BingoBlock) -> Option<(usize, usize)> { + for (row, row_data) in self.data.iter().enumerate() { + for (col, col_data) in row_data.iter().enumerate() { + if col_data == block { + return Some((row, col)); + } + } + } + None + } + + fn score(&self, mask: &BingoBoardMask) -> BingoGameScore { + let mut score = BingoGameScore::default(); + for row in 0..BINGO_BOARD_WIDTH { + for col in 0..BINGO_BOARD_WIDTH { + if !mask.data[row][col] { + score = score + self.data[row][col]; + } + } + } + score + } +} + +impl BingoBoard { + fn new(data: Vec>) -> Result { + let vec_array_data: Vec<[BingoBlock; BINGO_BOARD_WIDTH]> = data + .into_iter() + .map(|row| row.try_into()) + .collect::, _>>() + .map_err(|_| BingoBoardParseError::WrongWidth)?; + + let array_array_data: [[BingoBlock; BINGO_BOARD_WIDTH]; BINGO_BOARD_WIDTH] = vec_array_data + .try_into() + .map_err(|_| BingoBoardParseError::WrongHeight)?; + Ok(BingoBoard { + data: array_array_data, + }) + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +struct BingoBlock(u32); + +#[derive(Default, Debug, Clone, Copy, PartialEq, Eq)] +struct BingoGameScore(u32); + +impl std::ops::Add for BingoGameScore { + type Output = BingoGameScore; + fn add(self, rhs: BingoBlock) -> BingoGameScore { + BingoGameScore(self.0 + rhs.0) + } +} + +impl std::ops::Mul for BingoGameScore { + type Output = BingoGameScore; + fn mul(self, rhs: BingoBlock) -> BingoGameScore { + BingoGameScore(self.0 * rhs.0) + } +} + +fn parse_bingo_game(input: &str) -> IResult<&str, BingoGame> { + map( + tuple(( + parse_draws, + many1(line_ending), + separated_list1(many1(line_ending), parse_board), + )), + |(draws, _, boards)| BingoGame { + draws: draws.into_iter().rev().collect(), + masks: vec![BingoBoardMask::default(); boards.len()], + boards, + }, + )(input) +} + +fn parse_draws(input: &str) -> IResult<&str, Vec> { + separated_list1(tag(","), parse_block)(input) +} + +fn parse_block(input: &str) -> IResult<&str, BingoBlock> { + map(nom_u32, BingoBlock)(input) +} + +fn parse_board(input: &str) -> IResult<&str, BingoBoard> { + map_res( + separated_list1( + line_ending, + preceded(space0, separated_list1(space1, parse_block)), + ), + BingoBoard::new, + )(input) +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn parses_a_board() { + assert_eq!( + parse_board( + r##"86 31 71 11 56 +99 12 17 10 46 + 5 33 85 61 2 +30 1 28 88 66 +15 38 21 54 64"## + ), + Ok(( + "", + BingoBoard { + data: [ + [ + BingoBlock(86), + BingoBlock(31), + BingoBlock(71), + BingoBlock(11), + BingoBlock(56) + ], + [ + BingoBlock(99), + BingoBlock(12), + BingoBlock(17), + BingoBlock(10), + BingoBlock(46) + ], + [ + BingoBlock(5), + BingoBlock(33), + BingoBlock(85), + BingoBlock(61), + BingoBlock(2) + ], + [ + BingoBlock(30), + BingoBlock(1), + BingoBlock(28), + BingoBlock(88), + BingoBlock(66) + ], + [ + BingoBlock(15), + BingoBlock(38), + BingoBlock(21), + BingoBlock(54), + BingoBlock(64) + ] + ] + } + )) + ); + } +} diff --git a/2021/src/bin/day_5.rs b/2021/src/bin/day_5.rs new file mode 100644 index 0000000..08eaecd --- /dev/null +++ b/2021/src/bin/day_5.rs @@ -0,0 +1,137 @@ +use nom::{ + bytes::complete::tag, + character::complete::{char as nom_char, line_ending, u32 as nom_u32}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeMap, fs}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_5.txt")?; + let lines = parse_lines(&input).unwrap().1; + { + let mut map_simple = Bitmap::default(); + for line in &lines { + map_simple.mark_line_only_simple(line); + } + dbg!(map_simple.count_overlapped_points()); + } + { + let mut map = Bitmap::default(); + for line in &lines { + map.mark_line(line); + } + dbg!(map.count_overlapped_points()); + } + + Ok(()) +} + +#[derive(Default)] +struct Bitmap(BTreeMap); +impl Bitmap { + fn mark_line_only_simple(&mut self, l: &Line) { + if l.is_horizontal() { + for x in l.a.x..=l.b.x { + self.mark_point(&Point { x, y: l.a.y }); + } + } else if l.is_vertical() { + for y in l.a.y..=l.b.y { + self.mark_point(&Point { x: l.a.x, y }); + } + } else { + } + } + + fn mark_line(&mut self, l: &Line) { + if l.is_horizontal() { + for x in l.a.x..=l.b.x { + self.mark_point(&Point { x, y: l.a.y }); + } + } else if l.is_vertical() { + for y in l.a.y..=l.b.y { + self.mark_point(&Point { x: l.a.x, y }); + } + } else if l.is_diagonal_up() { + for delta in 0..=(l.b.x - l.a.x) { + self.mark_point(&Point { + x: l.a.x + delta, + y: l.a.y + delta, + }); + } + } else if l.is_diagonal_down() { + for delta in 0..=(l.b.x - l.a.x) { + let reverse_delta = l.b.x - l.a.x - delta; + self.mark_point(&Point { + x: l.a.x + delta, + y: l.b.y + reverse_delta, + }); + } + } else { + panic!("There shouldn't be other cases...") + } + } + + fn mark_point(&mut self, p: &Point) { + *self.0.entry(p.clone()).or_insert(0) += 1; + } + + fn count_overlapped_points(&self) -> usize { + self.0.values().filter(|v| **v > 1).count() + } +} + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)] +struct Point { + x: u32, + y: u32, +} + +#[derive(Debug)] +struct Line { + a: Point, + b: Point, +} + +impl Line { + fn is_horizontal(&self) -> bool { + self.a.y == self.b.y + } + + fn is_vertical(&self) -> bool { + self.a.x == self.b.x + } + + fn is_diagonal_up(&self) -> bool { + self.a.x < self.b.x && self.a.y < self.b.y + } + + fn is_diagonal_down(&self) -> bool { + self.a.x < self.b.x && self.a.y > self.b.y + } +} + +fn parse_lines(input: &str) -> IResult<&str, Vec> { + separated_list1(line_ending, parse_line)(input) +} + +fn parse_line(input: &str) -> IResult<&str, Line> { + map( + tuple((parse_point, tag(" -> "), parse_point)), + |(a, _, b)| { + if a < b { + Line { a, b } + } else { + Line { a: b, b: a } + } + }, + )(input) +} + +fn parse_point(input: &str) -> IResult<&str, Point> { + map(tuple((nom_u32, nom_char(','), nom_u32)), |(x, _, y)| { + Point { x, y } + })(input) +} diff --git a/2021/src/bin/day_6.rs b/2021/src/bin/day_6.rs new file mode 100644 index 0000000..9a40f9e --- /dev/null +++ b/2021/src/bin/day_6.rs @@ -0,0 +1,79 @@ +use nom::{ + bytes::complete::tag, + character::complete::u32 as nom_u32, + combinator::{map, map_res}, + multi::separated_list1, + IResult, ToUsize, +}; +use std::{collections::VecDeque, fs}; +use thiserror::Error; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_6.txt")?; + let mut swarm = parse_swarm(&input).unwrap().1; + for _ in 0..80 { + swarm.grow(); + } + dbg!(swarm.fish_sum()); + + for _ in 80..256 { + swarm.grow(); + } + dbg!(swarm.fish_sum()); + + Ok(()) +} + +#[derive( + Default, Debug, Clone, Copy, derive_more::Add, derive_more::AddAssign, derive_more::Sum, +)] +struct FishCount(u64); + +const FISH_INITIAL_SPAWN_COUNTDOWN: usize = 9; +const FISH_REPEAT_SPAWN_COUNTDOWN: usize = 7; +#[derive(Debug)] +struct Swarm { + fish: VecDeque, +} + +#[derive(Debug, Error)] +enum SwarmParseError { + #[error("input was out of range")] + OutOfRange, +} + +impl Swarm { + fn new(fish_counters: Vec) -> Result { + let mut fish = VecDeque::with_capacity(FISH_INITIAL_SPAWN_COUNTDOWN); + for _ in 0..FISH_INITIAL_SPAWN_COUNTDOWN { + fish.push_back(FishCount::default()); + } + for fish_counter in fish_counters { + if fish_counter > fish.len() { + return Err(SwarmParseError::OutOfRange); + } + fish[fish_counter] += FishCount(1); + } + Ok(Swarm { fish }) + } + + fn grow(&mut self) { + let spawning = self + .fish + .pop_front() + .expect("Fish buffer should maintain exactly 9 entries"); + self.fish[FISH_REPEAT_SPAWN_COUNTDOWN - 1] += spawning; + self.fish.push_back(spawning); + } + + fn fish_sum(&self) -> FishCount { + self.fish.iter().copied().sum() + } +} + +fn parse_swarm(input: &str) -> IResult<&str, Swarm> { + map_res( + separated_list1(tag(","), map(nom_u32, |n| n.to_usize())), + Swarm::new, + )(input) +} diff --git a/2021/src/bin/day_7.rs b/2021/src/bin/day_7.rs new file mode 100644 index 0000000..b568e07 --- /dev/null +++ b/2021/src/bin/day_7.rs @@ -0,0 +1,88 @@ +use nom::{ + bytes::complete::tag, character::complete::u64 as nom_u64, combinator::map, + multi::separated_list1, IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_7.txt")?; + let crabs = parse_swarm(&input).unwrap().1; + dbg!(crabs.linear_min_fuel_sum()); + dbg!(crabs.exponential_min_fuel_sum()); + Ok(()) +} + +#[derive( + Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, derive_more::Add, derive_more::Sum, +)] +struct Fuel(u64); + +#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +struct CrabPosition(u64); + +impl CrabPosition { + fn linear_fuel(&self, rhs: &Self) -> Fuel { + if self > rhs { + Fuel(self.0 - rhs.0) + } else { + Fuel(rhs.0 - self.0) + } + } + + fn exponential_fuel(&self, rhs: &Self) -> Fuel { + let linear_difference = if self > rhs { + self.0 - rhs.0 + } else { + rhs.0 - self.0 + }; + Fuel(linear_difference * (linear_difference + 1) / 2) + } +} + +#[derive(Default, Debug)] +struct CrabSwarm { + crabs: Vec, +} + +impl CrabSwarm { + fn new(mut crabs: Vec) -> CrabSwarm { + crabs.sort(); + CrabSwarm { crabs } + } + + fn linear_min_fuel_sum(&self) -> (CrabPosition, Fuel) { + (self.crabs[0].0..self.crabs[self.crabs.len() - 1].0) + .map(CrabPosition) + .map(|pos| { + ( + pos, + self.crabs.iter().map(|crab| crab.linear_fuel(&pos)).sum(), + ) + }) + .min_by_key(|(_pos, fuel)| *fuel) + .expect("Expected at least one crab") + } + + fn exponential_min_fuel_sum(&self) -> (CrabPosition, Fuel) { + (self.crabs[0].0..self.crabs[self.crabs.len() - 1].0) + .map(CrabPosition) + .map(|pos| { + ( + pos, + self.crabs + .iter() + .map(|crab| crab.exponential_fuel(&pos)) + .sum(), + ) + }) + .min_by_key(|(_pos, fuel)| *fuel) + .expect("Expected at least one crab") + } +} + +fn parse_swarm(input: &str) -> IResult<&str, CrabSwarm> { + map( + separated_list1(tag(","), map(nom_u64, CrabPosition)), + CrabSwarm::new, + )(input) +} diff --git a/2021/src/bin/day_8.rs b/2021/src/bin/day_8.rs new file mode 100644 index 0000000..6dc2bed --- /dev/null +++ b/2021/src/bin/day_8.rs @@ -0,0 +1,262 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{line_ending, space1}, + combinator::{map, map_res, value}, + multi::{many1, separated_list1}, + sequence::tuple, + IResult, +}; +use std::{ + collections::{BTreeMap, BTreeSet}, + fs, +}; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_8.txt")?; + let encrypted = parse_encrypted_inputs(&input).unwrap().1; + let permutations = WiringPermutation::all(); + + let unencrypted: Vec = encrypted + .into_iter() + .map(|encrypted_line| { + for permutation in &permutations { + if let Ok(input) = encrypted_line.decrypt(&permutation) { + return input; + } + } + panic!("Didn't find a solution!") + }) + .collect(); + + let part1_sum: usize = unencrypted + .iter() + .map(|input| { + input + .plaintext + .iter() + .filter(|digit| { + digit.value == 1 || digit.value == 4 || digit.value == 7 || digit.value == 8 + }) + .count() + }) + .sum(); + dbg!(part1_sum); + + let part2_sum: u32 = unencrypted + .iter() + .map(|input| { + input.plaintext[0].value * 1000 + + input.plaintext[1].value * 100 + + input.plaintext[2].value * 10 + + input.plaintext[3].value + }) + .sum(); + dbg!(part2_sum); + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)] +enum Wire { + A, + B, + C, + D, + E, + F, + G, +} + +impl Wire { + fn all() -> Vec { + vec![ + Wire::A, + Wire::B, + Wire::C, + Wire::D, + Wire::E, + Wire::F, + Wire::G, + ] + } +} + +#[derive(Debug)] +struct WiringPermutation { + mapping: BTreeMap, +} + +impl WiringPermutation { + fn all() -> Vec { + let all_wires = Wire::all(); + let all_wires_set: BTreeSet = all_wires.iter().cloned().collect(); + WiringPermutation::permutations(&all_wires, &all_wires_set) + } + + fn permutations( + remaining_starts: &[Wire], + remaining_ends: &BTreeSet, + ) -> Vec { + let mut permutations = Vec::new(); + if remaining_starts.is_empty() { + } else if remaining_starts.len() == 1 { + for end in remaining_ends { + let mut permutation = BTreeMap::new(); + permutation.insert(remaining_starts[0], *end); + permutations.push(WiringPermutation { + mapping: permutation, + }); + } + } else { + let start = remaining_starts[0]; + for first_end in remaining_ends { + let mut inner_remaining_ends = remaining_ends.clone(); + inner_remaining_ends.remove(first_end); + let inner_permutations = + WiringPermutation::permutations(&remaining_starts[1..], &inner_remaining_ends); + for mut permutation in inner_permutations { + permutation.mapping.insert(start, *first_end); + permutations.push(permutation); + } + } + } + permutations + } +} + +#[derive(Debug)] +struct Digit { + value: u32, + wires: BTreeSet, +} + +#[derive(Debug)] +struct Input { + plaintext: [Digit; 4], +} + +#[derive(Debug, thiserror::Error)] +enum WiringError { + #[error("digit was not a known digit")] + InvalidDigit, + #[error("wrong number of numbers")] + WrongNumberOfNumbers, +} + +impl Digit { + fn new(wires: BTreeSet) -> Result { + let valid_digits: [BTreeSet; 10] = [ + [Wire::A, Wire::B, Wire::C, Wire::E, Wire::F, Wire::G].into(), + [Wire::C, Wire::F].into(), + [Wire::A, Wire::C, Wire::D, Wire::E, Wire::G].into(), + [Wire::A, Wire::C, Wire::D, Wire::F, Wire::G].into(), + [Wire::B, Wire::C, Wire::D, Wire::F].into(), + [Wire::A, Wire::B, Wire::D, Wire::F, Wire::G].into(), + [Wire::A, Wire::B, Wire::D, Wire::E, Wire::F, Wire::G].into(), + [Wire::A, Wire::C, Wire::F].into(), + [ + Wire::A, + Wire::B, + Wire::C, + Wire::D, + Wire::E, + Wire::F, + Wire::G, + ] + .into(), + [Wire::A, Wire::B, Wire::C, Wire::D, Wire::F, Wire::G].into(), + ]; + + valid_digits + .into_iter() + .position(|digit| digit == wires) + .map(|pos| Digit { + value: pos as u32, + wires, + }) + .ok_or(WiringError::InvalidDigit) + } +} + +#[derive(Debug)] +struct EncryptedDigit { + wires: BTreeSet, +} + +impl EncryptedDigit { + fn decrypt(&self, permutation: &WiringPermutation) -> Result { + let mut fixed_wires = BTreeSet::new(); + for wire in &self.wires { + fixed_wires.insert(permutation.mapping[wire]); + } + Digit::new(fixed_wires) + } +} + +#[derive(Debug)] +struct EncryptedInput { + digits: [EncryptedDigit; 10], + ciphertext: [EncryptedDigit; 4], +} + +impl EncryptedInput { + fn decrypt(&self, permutation: &WiringPermutation) -> Result { + for test_digit in &self.digits { + let _ = test_digit.decrypt(&permutation)?; + } + + let plaintext = self + .ciphertext + .iter() + .map(|digit| digit.decrypt(&permutation)) + .collect::, WiringError>>()?; + Ok(Input { + plaintext: plaintext + .try_into() + .map_err(|_| WiringError::WrongNumberOfNumbers)?, + }) + } +} + +fn parse_encrypted_inputs(input: &str) -> IResult<&str, Vec> { + separated_list1(line_ending, parse_encrypted_input)(input) +} + +fn parse_encrypted_input(input: &str) -> IResult<&str, EncryptedInput> { + map_res( + tuple(( + separated_list1(space1, parse_encrypted_digit), + tag(" | "), + separated_list1(space1, parse_encrypted_digit), + )), + |(digits, _, ciphertext)| { + let digits = digits + .try_into() + .map_err(|_| WiringError::WrongNumberOfNumbers)?; + let ciphertext = ciphertext + .try_into() + .map_err(|_| WiringError::WrongNumberOfNumbers)?; + let result: Result = + Ok(EncryptedInput { digits, ciphertext }); + result + }, + )(input) +} + +fn parse_encrypted_digit(input: &str) -> IResult<&str, EncryptedDigit> { + map(many1(parse_wire), |wires| EncryptedDigit { + wires: wires.into_iter().collect(), + })(input) +} + +fn parse_wire(input: &str) -> IResult<&str, Wire> { + alt(( + value(Wire::A, tag("a")), + value(Wire::B, tag("b")), + value(Wire::C, tag("c")), + value(Wire::D, tag("d")), + value(Wire::E, tag("e")), + value(Wire::F, tag("f")), + value(Wire::G, tag("g")), + ))(input) +} diff --git a/2021/src/bin/day_9.rs b/2021/src/bin/day_9.rs new file mode 100644 index 0000000..5ef0dae --- /dev/null +++ b/2021/src/bin/day_9.rs @@ -0,0 +1,186 @@ +use nom::{ + character::complete::{line_ending, one_of}, + combinator::{map, map_res}, + multi::{many1, separated_list1}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box> { + let input = fs::read_to_string("inputs/day_9.txt")?; + let height_map = parse_height_map(&input).unwrap().1; + let risk_level_sum: RiskLevel = height_map.risk_levels().into_iter().sum(); + dbg!(risk_level_sum); + + let mut basin_sizes: Vec = height_map.basins.iter().map(|basin| basin.size).collect(); + basin_sizes.sort_unstable_by(|a, b| b.cmp(a)); + dbg!(basin_sizes.iter().take(3).product::()); + + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)] +struct Height(u8); +#[derive( + Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy, derive_more::Add, derive_more::Sum, +)] +struct RiskLevel(u32); + +impl From for RiskLevel { + fn from(h: Height) -> Self { + RiskLevel(h.0 as u32 + 1) + } +} + +#[derive(Debug, Default)] +struct Basin { + size: u32, +} + +#[derive(Debug)] +struct HeightMap { + heights: Vec>, + low_points: Vec<(usize, usize)>, + basins: Vec, + basin_map: Vec>>, +} + +impl HeightMap { + fn new(heights: Vec>) -> HeightMap { + let mut height_map = HeightMap { + heights, + low_points: Vec::new(), + basins: Vec::new(), + basin_map: Vec::new(), + }; + height_map.init_low_points(); + height_map.init_basins(); + height_map + } +} + +impl HeightMap { + fn init_low_points(&mut self) { + self.low_points = Vec::new(); + for y in 0..self.heights.len() { + for x in 0..self.heights[y].len() { + let current = self.heights[y][x]; + let mut is_low_point = true; + let edges = [ + (x as isize - 1, y as isize), + (x as isize + 1, y as isize), + (x as isize, y as isize - 1), + (x as isize, y as isize + 1), + ]; + for edge in edges { + if self + .get_height(edge.0, edge.1) + .map_or(false, |other| other <= current) + { + is_low_point = false; + } + } + + if is_low_point { + self.low_points.push((x, y)); + } + } + } + } + + fn init_basins(&mut self) { + for low_point in self.low_points.clone() { + if self + .get_basin(low_point.0 as isize, low_point.1 as isize) + .is_some() + { + continue; + } + + let mut basin = Basin::default(); + let basin_index = self.basins.len(); + self.set_basin(basin_index, low_point.0, low_point.1); + basin.size += 1; + let mut boundary = vec![low_point]; + while boundary.len() > 0 { + let (x, y) = boundary.pop().unwrap(); + let edges = [ + (x as isize - 1, y as isize), + (x as isize + 1, y as isize), + (x as isize, y as isize - 1), + (x as isize, y as isize + 1), + ]; + for edge in edges { + if self + .get_height(edge.0, edge.1) + .map_or(false, |other| other != Height(9)) + && self.get_basin(edge.0, edge.1).is_none() + { + let x = edge.0 as usize; + let y = edge.1 as usize; + self.set_basin(basin_index, x, y); + basin.size += 1; + boundary.push((x, y)); + } + } + } + self.basins.push(basin); + } + } + + fn get_height(&self, x: isize, y: isize) -> Option { + if x < 0 || y < 0 { + None + } else { + let x = x as usize; + let y = y as usize; + self.heights.get(y).and_then(|row| row.get(x)).cloned() + } + } + + fn get_basin(&self, x: isize, y: isize) -> Option { + if x < 0 || y < 0 { + None + } else { + let x = x as usize; + let y = y as usize; + self.basin_map + .get(y) + .and_then(|row| row.get(x)) + .cloned() + .flatten() + } + } + + fn set_basin(&mut self, basin: usize, x: usize, y: usize) { + while self.basin_map.len() <= y { + self.basin_map.push(Vec::new()); + } + while self.basin_map[y].len() <= x { + self.basin_map[y].push(None); + } + self.basin_map[y][x] = Some(basin); + } + + fn risk_levels(&self) -> Vec { + self.low_points + .iter() + .copied() + .map(|(x, y)| self.heights[y][x].clone().into()) + .collect() + } +} + +fn parse_height_map(input: &str) -> IResult<&str, HeightMap> { + map(separated_list1(line_ending, parse_row), HeightMap::new)(input) +} + +fn parse_row(input: &str) -> IResult<&str, Vec> { + many1(parse_height)(input) +} + +fn parse_height(input: &str) -> IResult<&str, Height> { + map_res(one_of("0123456789"), |digit| { + digit.to_string().parse().map(Height) + })(input) +} diff --git a/2021/src/lib.rs b/2021/src/lib.rs new file mode 100644 index 0000000..be756a0 --- /dev/null +++ b/2021/src/lib.rs @@ -0,0 +1 @@ +pub mod parsers; diff --git a/2021/src/parsers.rs b/2021/src/parsers.rs new file mode 100644 index 0000000..8b13789 --- /dev/null +++ b/2021/src/parsers.rs @@ -0,0 +1 @@ + -- cgit v1.2.3