diff options
Diffstat (limited to '2022')
30 files changed, 4767 insertions, 0 deletions
diff --git a/2022/Cargo.lock b/2022/Cargo.lock new file mode 100644 index 0000000..b3377f8 --- /dev/null +++ b/2022/Cargo.lock @@ -0,0 +1,123 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "aoc2022" +version = "0.1.0" +dependencies = [ + "derive_more", + "nom", + "thiserror", +] + +[[package]] +name = "convert_case" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6245d59a3e82a7fc217c5828a6692dbc6dfb63a0c8c90495621f7b9d79704a0e" + +[[package]] +name = "derive_more" +version = "0.99.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4fb810d30a7c1953f91334de7244731fc3f3c10d7fe163338a35b9f640960321" +dependencies = [ + "convert_case", + "proc-macro2", + "quote", + "rustc_version", + "syn", +] + +[[package]] +name = "memchr" +version = "2.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "308cc39be01b73d0d18f82a0e7b2a3df85245f84af96fdddc5d202d27e47b86a" + +[[package]] +name = "minimal-lexical" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "68354c5c6bd36d73ff3feceb05efa59b6acb7626617f4962be322a825e61f79a" + +[[package]] +name = "nom" +version = "7.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a8903e5a29a317527874d0402f867152a3d21c908bb0b933e416c65e301d4c36" +dependencies = [ + "memchr", + "minimal-lexical", +] + +[[package]] +name = "proc-macro2" +version = "1.0.32" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ba508cc11742c0dc5c1659771673afbab7a0efab23aa17e854cbab0837ed0b43" +dependencies = [ + "unicode-xid", +] + +[[package]] +name = "quote" +version = "1.0.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38bc8cc6a5f2e3655e0899c1b848643b2562f853f114bfec7be120678e3ace05" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "rustc_version" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bfa0f585226d2e68097d4f95d113b15b83a82e819ab25717ec0590d9584ef366" +dependencies = [ + "semver", +] + +[[package]] +name = "semver" +version = "1.0.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e25dfac463d778e353db5be2449d1cce89bd6fd23c9f1ea21310ce6e5a1b29c4" + +[[package]] +name = "syn" +version = "1.0.82" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8daf5dd0bb60cbd4137b1b587d2fc0ae729bc07cf01cd70b36a1ed5ade3b9d59" +dependencies = [ + "proc-macro2", + "quote", + "unicode-xid", +] + +[[package]] +name = "thiserror" +version = "1.0.37" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "10deb33631e3c9018b9baf9dcbbc4f737320d2b576bac10f6aefa048fa407e3e" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "1.0.37" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "982d17546b47146b28f7c22e3d08465f6b8903d0ea13c1660d9d84a6e7adcdbb" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "unicode-xid" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "826e7639553986605ec5979c7dd957c7895e93eabed50ab2ffa7f6128a75097c" diff --git a/2022/Cargo.toml b/2022/Cargo.toml new file mode 100644 index 0000000..af8eee9 --- /dev/null +++ b/2022/Cargo.toml @@ -0,0 +1,13 @@ +[package] +name = "aoc2022" +version = "0.1.0" +authors = ["Justin Wernick <justin@worthe-it.co.za>"] +edition = "2021" + +[dependencies] +derive_more = "0.99.17" +nom = "7.1.1" +thiserror = "1.0.37" + +[profile.release] +# debug = true diff --git a/2022/inputs/.gitkeep b/2022/inputs/.gitkeep new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/2022/inputs/.gitkeep diff --git a/2022/readme.org b/2022/readme.org new file mode 100644 index 0000000..c073fed --- /dev/null +++ b/2022/readme.org @@ -0,0 +1,2 @@ +* Advent of Code 2022 + diff --git a/2022/src/bin/day_1.rs b/2022/src/bin/day_1.rs new file mode 100644 index 0000000..bc988b7 --- /dev/null +++ b/2022/src/bin/day_1.rs @@ -0,0 +1,61 @@ +use nom::{ + character::complete::{line_ending, u32 as nom_u32}, + combinator::map, + multi::separated_list1, + sequence::pair, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_1.txt")?; + let elves = Elves::parser(&input).unwrap().1; + dbg!(elves.max_calories_sum(1)); + dbg!(elves.max_calories_sum(3)); + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)] +struct Elves { + elves: Vec<Elf>, +} + +#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)] +struct Elf { + calories: Vec<u32>, +} + +impl Elves { + fn parser(input: &str) -> IResult<&str, Elves> { + map( + separated_list1(pair(line_ending, line_ending), Elf::parser), + Elves::new, + )(input) + } + + fn new(mut elves: Vec<Elf>) -> Elves { + elves.sort_unstable_by_key(|elf| elf.total_calories()); + Elves { elves } + } + + fn max_calories_sum(&self, count: usize) -> u32 { + self.elves + .iter() + .rev() + .take(count) + .map(|elf| elf.total_calories()) + .sum() + } +} + +impl Elf { + fn parser(input: &str) -> IResult<&str, Elf> { + map(separated_list1(line_ending, nom_u32), |calories| Elf { + calories, + })(input) + } + + fn total_calories(&self) -> u32 { + self.calories.iter().sum() + } +} diff --git a/2022/src/bin/day_10.rs b/2022/src/bin/day_10.rs new file mode 100644 index 0000000..6999c52 --- /dev/null +++ b/2022/src/bin/day_10.rs @@ -0,0 +1,103 @@ +use nom::{ + bytes::complete::tag, + character::complete::{i32, line_ending}, + combinator::map, + multi::{many0, separated_list1}, + sequence::{pair, tuple}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_10.txt")?; + let program = Program::parser(&input).unwrap().1; + let result = program.process(); + + dbg!(result.sum_of_signal_strengths(&[20, 60, 100, 140, 180, 220])); + + for y in 0..6 { + for x in 0..40 { + if result.pixel_should_activate(x, y) { + print!("#"); + } else { + print!("."); + } + } + println!(); + } + Ok(()) +} + +#[derive(Debug)] +struct Program(Vec<TimeSequence>); + +#[derive(Debug, Default)] +struct ProgramResult(Vec<TimeSequence>); + +#[derive(Debug, Clone)] +struct TimeSequence { + time: u32, + value: i32, +} + +impl Program { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, TimeSequence::parser), Program)(input) + } + + fn process(&self) -> ProgramResult { + let mut result = ProgramResult::default(); + + let mut current_state = TimeSequence { time: 1, value: 1 }; + result.0.push(current_state.clone()); + + for next_step in &self.0 { + current_state.time += next_step.time; + current_state.value += next_step.value; + result.0.push(current_state.clone()); + } + + result + } +} + +impl TimeSequence { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple((many0(pair(tag("noop"), line_ending)), tag("addx "), i32)), + |(noops, _, value)| TimeSequence { + time: noops.len() as u32 + 2, + value, + }, + )(input) + } +} + +impl ProgramResult { + fn value_at(&self, time: u32) -> i32 { + self.0 + .iter() + .filter(|t| t.time <= time) + .map(|t| t.value) + .last() + .unwrap_or(0) + } + + fn signal_strength_at(&self, time: u32) -> i32 { + let value = self.value_at(time); + value * time as i32 + } + + fn sum_of_signal_strengths(&self, times: &[u32]) -> i32 { + times + .iter() + .map(|time| self.signal_strength_at(*time)) + .sum() + } + + fn pixel_should_activate(&self, x: usize, y: usize) -> bool { + let time = (y * 40 + x + 1) as u32; + let sprite_middle = self.value_at(time); + ((x as i32) - sprite_middle).abs() <= 1 + } +} diff --git a/2022/src/bin/day_11.rs b/2022/src/bin/day_11.rs new file mode 100644 index 0000000..ffba6ab --- /dev/null +++ b/2022/src/bin/day_11.rs @@ -0,0 +1,154 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{line_ending, u64}, + combinator::{map, value}, + multi::separated_list1, + sequence::{pair, preceded, tuple}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_11.txt")?; + let troop = MonkeyTroop::parser(&input).unwrap().1; + + { + let mut troop_1 = troop.clone(); + for _ in 0..20 { + troop_1.monkey_game_round(true); + } + dbg!(&troop_1.monkey_business_score()); + } + + { + let mut troop_2 = troop.clone(); + for _ in 0..10000 { + troop_2.monkey_game_round(false); + } + dbg!(&troop_2.monkey_business_score()); + } + + Ok(()) +} + +#[derive(Debug, Clone)] +struct MonkeyTroop { + monkeys: Vec<Monkey>, + gcd: u64, +} + +#[derive(Debug, Clone)] +struct Monkey { + items: Vec<u64>, + operation: Operation, + test_denominator: u64, + true_target: usize, + false_target: usize, + inspection_count: usize, +} + +#[derive(Debug, Clone)] +enum Operation { + Add(u64), + Multiply(u64), + Square, +} + +impl MonkeyTroop { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(pair(line_ending, line_ending), Monkey::parser), + |monkeys| MonkeyTroop { + gcd: monkeys.iter().map(|m| m.test_denominator).product(), + monkeys, + }, + )(input) + } + + fn monkey_game_round(&mut self, worry_reduction: bool) { + for monkey_i in 0..self.monkeys.len() { + self.monkeys[monkey_i].inspect_items(worry_reduction, self.gcd); + + let items = std::mem::take(&mut self.monkeys[monkey_i].items); + let test_denominator = self.monkeys[monkey_i].test_denominator.clone(); + let true_target = self.monkeys[monkey_i].true_target.clone(); + let false_target = self.monkeys[monkey_i].false_target.clone(); + for item in items { + let target_monkey = if item % test_denominator == 0 { + true_target + } else { + false_target + }; + self.monkeys[target_monkey].items.push(item); + } + } + } + + fn monkey_business_score(&self) -> usize { + let mut counts: Vec<usize> = self + .monkeys + .iter() + .map(|m| m.inspection_count.clone()) + .collect(); + counts.sort(); + counts.reverse(); + counts[0] * counts[1] + } +} + +impl Monkey { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + preceded( + tuple(( + tag("Monkey "), + u64, + tag(":"), + line_ending, + tag(" Starting items: "), + )), + separated_list1(tag(", "), u64), + ), + preceded( + pair(line_ending, tag(" Operation: new = old ")), + alt(( + map(preceded(tag("+ "), u64), Operation::Add), + map(preceded(tag("* "), u64), Operation::Multiply), + value(Operation::Square, tag("* old")), + )), + ), + preceded(pair(line_ending, tag(" Test: divisible by ")), u64), + preceded(pair(line_ending, tag(" If true: throw to monkey ")), u64), + preceded( + pair(line_ending, tag(" If false: throw to monkey ")), + u64, + ), + )), + |(items, operation, test_denominator, true_target, false_target)| Monkey { + items, + operation, + test_denominator, + true_target: true_target as usize, + false_target: false_target as usize, + inspection_count: 0, + }, + )(input) + } + + fn inspect_items(&mut self, worry_reduction: bool, gcd: u64) { + for item in &mut self.items { + match self.operation { + Operation::Add(i) => *item += i, + Operation::Multiply(i) => *item *= i, + Operation::Square => *item = *item * *item, + }; + if worry_reduction { + *item /= 3; + } + *item = *item % gcd; + } + self.inspection_count += self.items.len() + } +} diff --git a/2022/src/bin/day_12.rs b/2022/src/bin/day_12.rs new file mode 100644 index 0000000..9190113 --- /dev/null +++ b/2022/src/bin/day_12.rs @@ -0,0 +1,174 @@ +use nom::{ + character::complete::{line_ending, satisfy}, + combinator::map, + multi::{many1, separated_list1}, + IResult, +}; +use std::{ + collections::{BTreeMap, BTreeSet}, + fs, +}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_12.txt")?; + let map = HeightMap::parser(&input).unwrap().1; + + let distance_map = MapExploration::explore(&map); + + dbg!(distance_map.distance_to.get(&map.start)); + + let min_distance_start = map + .heights + .iter() + .enumerate() + .flat_map(|(y, row)| { + row.iter() + .enumerate() + .filter(|(_x, height)| **height == 0) + .map(move |(x, _)| Point { x, y }) + }) + .filter_map(|p| distance_map.distance_to.get(&p)) + .min(); + dbg!(min_distance_start); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct HeightMap { + heights: Vec<Vec<u8>>, + start: Point, + end: Point, +} + +#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + x: usize, + y: usize, +} + +impl HeightMap { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, many1(satisfy(|c| c.is_ascii_alphabetic()))), + |height_chars| { + let mut start = Point::default(); + let mut end = Point::default(); + let mut heights = Vec::new(); + for y in 0..height_chars.len() { + let mut new_row = Vec::new(); + for x in 0..height_chars[y].len() { + let height = match height_chars[y][x] { + 'S' => { + start = Point { x, y }; + 0 + } + 'E' => { + end = Point { x, y }; + 25 + } + a if a.is_ascii_lowercase() => height_chars[y][x] as u8 - b'a', + a => panic!("Unexpected character {}", a), + }; + new_row.push(height); + } + heights.push(new_row); + } + + HeightMap { + heights, + start, + end, + } + }, + )(input) + } + + fn adjacent_to(&self, p: &Point) -> Vec<Point> { + let current_height = self + .heights + .get(p.y) + .and_then(|row| row.get(p.x)) + .cloned() + .unwrap_or(0); + + p.adjacent() + .into_iter() + .filter(|other_p| { + let other_height = self + .heights + .get(other_p.y) + .and_then(|row| row.get(other_p.x)); + + match other_height { + None => false, + Some(&other_height) => other_height + 1 >= current_height, + } + }) + .collect() + } +} + +impl Point { + fn adjacent(&self) -> Vec<Point> { + let mut result = Vec::new(); + if self.x > 0 { + result.push(Point { + x: self.x - 1, + y: self.y, + }); + } + if self.x < usize::MAX { + result.push(Point { + x: self.x + 1, + y: self.y, + }); + } + if self.y > 0 { + result.push(Point { + x: self.x, + y: self.y - 1, + }); + } + if self.y < usize::MAX { + result.push(Point { + x: self.x, + y: self.y + 1, + }); + } + result + } +} + +struct MapExploration { + distance_to: BTreeMap<Point, u32>, +} + +impl MapExploration { + fn explore(map: &HeightMap) -> MapExploration { + let mut frontier = BTreeSet::new(); + let mut distance_to = BTreeMap::new(); + let mut distance = 0; + + distance_to.insert(map.end.clone(), distance); + frontier.insert(map.end.clone()); + + while !frontier.is_empty() { + let mut next_frontier = BTreeSet::new(); + distance += 1; + + for frontier_point in frontier { + for adjacent_point in map.adjacent_to(&frontier_point) { + if !distance_to.contains_key(&adjacent_point) { + distance_to.insert(adjacent_point.clone(), distance); + next_frontier.insert(adjacent_point); + } + } + } + + frontier = next_frontier; + } + + MapExploration { distance_to } + } +} diff --git a/2022/src/bin/day_13.rs b/2022/src/bin/day_13.rs new file mode 100644 index 0000000..b00d790 --- /dev/null +++ b/2022/src/bin/day_13.rs @@ -0,0 +1,146 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{line_ending, u32}, + combinator::map, + multi::{separated_list0, separated_list1}, + sequence::{delimited, pair, preceded}, + IResult, +}; +use std::{cmp::Ordering, fs}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_13.txt")?; + let message = EncodedMessage::parser(&input).unwrap().1; + + dbg!(message.ordered_index_sum()); + dbg!(message.decoder_key()); + + Ok(()) +} + +#[derive(Debug)] +struct EncodedMessage { + message_pairs: Vec<(Message, Message)>, + ordered_indices: Vec<usize>, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +enum Message { + List(Vec<Message>), + Value(u32), +} + +impl EncodedMessage { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1( + pair(line_ending, line_ending), + pair(Message::parser, preceded(line_ending, Message::parser)), + ), + EncodedMessage::new, + )(input) + } + + fn new(message_pairs: Vec<(Message, Message)>) -> EncodedMessage { + let mut ordered_indices = Vec::new(); + + for (i, (left, right)) in message_pairs.iter().enumerate() { + if left <= right { + ordered_indices.push(i + 1); + } + } + EncodedMessage { + message_pairs, + ordered_indices, + } + } + + fn ordered_index_sum(&self) -> usize { + self.ordered_indices.iter().sum() + } + + fn decoder_key(&self) -> usize { + let mut all_packets: Vec<Message> = self + .message_pairs + .iter() + .flat_map(|(left, right)| [left.clone(), right.clone()]) + .collect(); + let divider_1 = Message::List(vec![Message::List(vec![Message::Value(2)])]); + let divider_2 = Message::List(vec![Message::List(vec![Message::Value(6)])]); + all_packets.push(divider_1.clone()); + all_packets.push(divider_2.clone()); + + all_packets.sort(); + + let index_1 = all_packets.iter().position(|m| *m == divider_1).unwrap() + 1; + let index_2 = all_packets.iter().position(|m| *m == divider_2).unwrap() + 1; + index_1 * index_2 + } +} + +impl Message { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + map(u32, Message::Value), + map( + delimited( + tag("["), + separated_list0(tag(","), Message::parser), + tag("]"), + ), + Message::List, + ), + ))(input) + } +} + +impl PartialOrd for Message { + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { + Some(self.cmp(other)) + } +} + +impl Ord for Message { + fn cmp(&self, other: &Self) -> Ordering { + match (self, other) { + (Message::Value(left), Message::Value(right)) => left.cmp(right), + (Message::List(left), Message::List(right)) => { + for i in 0..left.len() { + if i == right.len() { + return Ordering::Greater; + } + let inner_ord = left[i].cmp(&right[i]); + if inner_ord != Ordering::Equal { + return inner_ord; + } + } + left.len().cmp(&right.len()) + } + (Message::Value(left), Message::List(right)) => { + if right.len() == 0 { + Ordering::Greater + } else { + let inner_ord = Message::Value(*left).cmp(&right[0]); + if inner_ord != Ordering::Equal { + inner_ord + } else { + 1.cmp(&right.len()) + } + } + } + (Message::List(left), Message::Value(right)) => { + if left.len() == 0 { + Ordering::Less + } else { + let inner_ord = left[0].cmp(&Message::Value(*right)); + if inner_ord != Ordering::Equal { + inner_ord + } else { + left.len().cmp(&1) + } + } + } + } + } +} diff --git a/2022/src/bin/day_14.rs b/2022/src/bin/day_14.rs new file mode 100644 index 0000000..ec5b1cb --- /dev/null +++ b/2022/src/bin/day_14.rs @@ -0,0 +1,184 @@ +use nom::{ + bytes::complete::tag, + character::complete::{i32, line_ending}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_14.txt")?; + let room = Room::parser(&input).unwrap().1; + + { + let mut void_room = room.clone(); + let mut room_is_full = false; + while !room_is_full { + let drop_result = void_room.drop_sand(true); + room_is_full = drop_result != DropSandResult::Settled; + if drop_result == DropSandResult::RoomFull { + return Err("The room filled up to the top!".into()); + } + } + dbg!(void_room.sand.len()); + } + + { + let mut floor_room = room.clone(); + let mut room_is_full = false; + while !room_is_full { + let drop_result = floor_room.drop_sand(false); + room_is_full = drop_result != DropSandResult::Settled; + if drop_result == DropSandResult::FellIntoTheVoid { + return Err("This room shouldn't have a void!".into()); + } + } + dbg!(floor_room.sand.len()); + } + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Room { + walls: Vec<Wall>, + sand: BTreeSet<Point>, + sand_inlet: Point, + void_start_y: i32, +} + +#[derive(Debug, Clone)] +enum Wall { + Vertical(VerticalWall), + Horizontal(HorizontalWall), +} + +#[derive(Debug, Clone)] +struct VerticalWall { + x: i32, + y1: i32, + y2: i32, +} + +#[derive(Debug, Clone)] +struct HorizontalWall { + y: i32, + x1: i32, + x2: i32, +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + x: i32, + y: i32, +} + +#[derive(Debug, PartialEq, Eq)] +enum DropSandResult { + FellIntoTheVoid, + Settled, + RoomFull, +} + +impl Room { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, separated_list1(tag(" -> "), Point::parser)), + |wall_segments| { + let mut walls = Vec::new(); + let mut void_start_y = 0; + for wall_segment in wall_segments { + for point_pair in wall_segment.windows(2) { + walls.push(if point_pair[0].x == point_pair[1].x { + Wall::Vertical(VerticalWall { + x: point_pair[0].x, + y1: point_pair[0].y.min(point_pair[1].y), + y2: point_pair[0].y.max(point_pair[1].y), + }) + } else if point_pair[0].y == point_pair[1].y { + Wall::Horizontal(HorizontalWall { + y: point_pair[0].y, + x1: point_pair[0].x.min(point_pair[1].x), + x2: point_pair[0].x.max(point_pair[1].x), + }) + } else { + panic!("Invalid wall segment") + }); + + void_start_y = void_start_y.max(point_pair[0].y); + void_start_y = void_start_y.max(point_pair[1].y); + } + + void_start_y = + void_start_y.max(wall_segment.iter().map(|p| p.y).max().unwrap_or(0)) + } + Room { + walls, + sand: BTreeSet::new(), + sand_inlet: Point { x: 500, y: 0 }, + void_start_y, + } + }, + )(input) + } + + fn point_is_occupied(&self, p: &Point) -> bool { + p.y >= self.void_start_y + 2 + || self.sand.contains(p) + || self.walls.iter().any(|w| w.point_is_occupied(p)) + } + + fn point_is_in_the_void(&self, p: &Point) -> bool { + p.y >= self.void_start_y + } + + fn drop_sand(&mut self, allow_infinite_void: bool) -> DropSandResult { + if self.point_is_occupied(&self.sand_inlet) { + return DropSandResult::RoomFull; + } + + let mut falling_sand = self.sand_inlet.clone(); + loop { + if allow_infinite_void && self.point_is_in_the_void(&falling_sand) { + return DropSandResult::FellIntoTheVoid; + } else if !self.point_is_occupied(&Point { + x: falling_sand.x, + y: falling_sand.y + 1, + }) { + falling_sand.y += 1; + } else if !self.point_is_occupied(&Point { + x: falling_sand.x - 1, + y: falling_sand.y + 1, + }) { + falling_sand.x -= 1; + falling_sand.y += 1; + } else if !self.point_is_occupied(&Point { + x: falling_sand.x + 1, + y: falling_sand.y + 1, + }) { + falling_sand.x += 1; + falling_sand.y += 1; + } else { + self.sand.insert(falling_sand); + return DropSandResult::Settled; + } + } + } +} + +impl Wall { + fn point_is_occupied(&self, p: &Point) -> bool { + match self { + Wall::Vertical(VerticalWall { x, y1, y2 }) => p.x == *x && p.y >= *y1 && p.y <= *y2, + Wall::Horizontal(HorizontalWall { y, x1, x2 }) => p.y == *y && p.x >= *x1 && p.x <= *x2, + } + } +} + +impl Point { + fn parser(input: &str) -> IResult<&str, Self> { + map(tuple((i32, tag(","), i32)), |(x, _, y)| Point { x, y })(input) + } +} diff --git a/2022/src/bin/day_15.rs b/2022/src/bin/day_15.rs new file mode 100644 index 0000000..be7645d --- /dev/null +++ b/2022/src/bin/day_15.rs @@ -0,0 +1,167 @@ +use nom::{ + bytes::complete::tag, + character::complete::{i64, line_ending}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fs, ops::Range}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_15.txt")?; + let sensors = Sensors::parser(&input).unwrap().1; + + dbg!(sensors.count_covered_non_beacons_in_row(2000000)); + + dbg!(sensors + .find_hole_in_range( + Point { x: 0, y: 0 }..Point { + x: 4000001, + y: 4000001 + } + ) + .tuning_frequency()); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Sensors(Vec<Sensor>); + +#[derive(Debug, Clone)] +struct Sensor { + center: Point, + closest_beacon: Point, +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + x: i64, + y: i64, +} + +impl Sensors { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, Sensor::parser), Sensors)(input) + } + + fn ranges_in_row(&self, y: i64) -> Vec<Range<i64>> { + let mut ranges: Vec<Range<i64>> = self + .0 + .iter() + .filter_map(|s| s.get_range_in_row(y)) + .collect(); + + let mut any_changes = true; + while any_changes { + any_changes = false; + ranges.sort_unstable_by_key(|r| r.start); + if ranges.len() > 0 { + for i in 0..ranges.len() - 1 { + if ranges[i].end > ranges[i + 1].start { + ranges[i + 1].start = ranges[i].end; + any_changes = true; + } + } + ranges.retain(|r| !r.is_empty()); + } + } + ranges + } + + fn count_covered_non_beacons_in_row(&self, y: i64) -> u64 { + let ranges = self.ranges_in_row(y); + + // these beacons are all distinct, and are all definitely on + // the line because the beacons are how the line is found! + let beacons: BTreeSet<i64> = self + .0 + .iter() + .filter(|s| s.closest_beacon.y == y) + .map(|s| s.closest_beacon.x) + .collect(); + + ranges.into_iter().map(|r| r.count() as u64).sum::<u64>() - beacons.len() as u64 + } + + fn find_hole_in_range(&self, field_range: Range<Point>) -> Point { + let full_row_len = field_range.end.x - field_range.start.x; + for y in field_range.start.y..field_range.end.y { + let ranges = self.ranges_in_row(y); + let count = ranges + .into_iter() + .map(|mut r| { + if r.start < field_range.start.x { + r.start = field_range.start.x + }; + if r.end > field_range.end.x { + r.end = field_range.end.x + }; + r + }) + .map(|r| r.count() as i64) + .sum::<i64>(); + if full_row_len != count { + for x in field_range.start.x..field_range.end.x { + let p = Point { x, y }; + if !self.0.iter().any(|s| s.contains(&p)) { + return p; + } + } + } + } + panic!("Didn't find the hole as specified!") + } +} + +impl Sensor { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + tag("Sensor at "), + Point::parser, + tag(": closest beacon is at "), + Point::parser, + )), + |(_, center, _, closest_beacon)| Sensor { + center, + closest_beacon, + }, + )(input) + } + + fn get_range_in_row(&self, y: i64) -> Option<Range<i64>> { + let dy = (self.center.y - y).abs(); + let dx = self.radius() - dy; + if dx < 0 { + None + } else { + let min_x = self.center.x - dx; + let max_x = self.center.x + dx; + Some(min_x..(max_x + 1)) + } + } + + fn radius(&self) -> i64 { + (self.center.x - self.closest_beacon.x).abs() + + (self.center.y - self.closest_beacon.y).abs() + } + + fn contains(&self, other: &Point) -> bool { + let d = (self.center.x - other.x).abs() + (self.center.y - other.y).abs(); + d <= self.radius() + } +} + +impl Point { + fn parser(input: &str) -> IResult<&str, Self> { + map(tuple((tag("x="), i64, tag(", y="), i64)), |(_, x, _, y)| { + Point { x, y } + })(input) + } + + fn tuning_frequency(&self) -> i64 { + self.x * 4000000 + self.y + } +} diff --git a/2022/src/bin/day_16.rs b/2022/src/bin/day_16.rs new file mode 100644 index 0000000..e35f04e --- /dev/null +++ b/2022/src/bin/day_16.rs @@ -0,0 +1,236 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{alpha1, line_ending, u32}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{ + collections::{BTreeMap, BTreeSet}, + fs, +}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_16.txt")?; + let nodes = Nodes::parser(&input).unwrap().1; + let mut condensed = nodes.condense(); + + let mut initial_open_valves = BTreeSet::new(); + initial_open_valves.insert(0); + + let initial_state = State { + actors: vec![Actor { + position: 0, + time_remaining: 30, + }], + open_valves: initial_open_valves.clone(), + }; + + dbg!(condensed.find_optimal_pressure_relieved(&initial_state)); + + let initial_state_with_elephant = State { + actors: vec![ + Actor { + position: 0, + time_remaining: 26 + }; + 2 + ], + open_valves: initial_open_valves, + }; + dbg!(condensed.find_optimal_pressure_relieved(&initial_state_with_elephant)); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Nodes { + nodes: BTreeMap<String, Node>, +} + +#[derive(Debug, Clone)] +struct Node { + id: String, + flow_rate: u32, + exits: BTreeMap<String, u32>, +} + +#[derive(Debug)] +struct CondensedNodes { + nodes: Vec<CondensedNode>, + cache: BTreeMap<State, u32>, +} + +#[derive(Debug, Clone)] +struct CondensedNode { + flow_rate: u32, + exits: Vec<u32>, +} + +impl Nodes { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, Node::parser), |nodes| Nodes { + nodes: nodes + .into_iter() + .map(|node| (node.id.clone(), node)) + .collect(), + })(input) + } + + fn condense(&self) -> CondensedNodes { + let node_ids: Vec<String> = self + .nodes + .values() + .filter(|n| n.id == "AA" || n.flow_rate > 0) + .map(|n| n.id.clone()) + .collect(); + + let mut condensed = CondensedNodes { + nodes: self + .nodes + .values() + .filter(|n| n.id == "AA" || n.flow_rate > 0) + .map(|n| CondensedNode { + flow_rate: n.flow_rate, + exits: Vec::new(), + }) + .collect(), + cache: BTreeMap::new(), + }; + + for (id, mut node) in condensed.nodes.iter_mut().enumerate() { + node.exits = node_ids + .iter() + .map(|original_destination_id| { + // +1 because in condensed it includes opening the valve + self.find_shortest_path(&node_ids[id], &original_destination_id) + 1 + }) + .collect() + } + + condensed + } + + fn find_shortest_path(&self, from: &str, to: &str) -> u32 { + let mut frontier: BTreeSet<&str> = BTreeSet::new(); + let mut explored: BTreeSet<&str> = BTreeSet::new(); + let mut distance = 0; + + explored.insert(from); + frontier.insert(from); + + while !frontier.is_empty() { + let mut next_frontier: BTreeSet<&str> = BTreeSet::new(); + distance += 1; + + for frontier_point in frontier { + for adjacent_point in self.nodes.get(frontier_point).unwrap().exits.keys() { + if adjacent_point == to { + return distance; + } + if !explored.contains(&adjacent_point.as_ref()) { + explored.insert(adjacent_point); + next_frontier.insert(adjacent_point); + } + } + } + + frontier = next_frontier; + } + panic!("Didn't reach end"); + } +} + +impl Node { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + tag("Valve "), + alpha1, + tag(" has flow rate="), + u32, + alt(( + tag("; tunnels lead to valves "), + tag("; tunnel leads to valve "), + )), + separated_list1(tag(", "), alpha1), + )), + |(_, id, _, flow_rate, _, exits): (_, &str, _, u32, _, Vec<&str>)| Node { + id: id.to_owned(), + flow_rate, + exits: exits + .into_iter() + .map(|destination| (destination.to_owned(), 1)) + .collect(), + }, + )(input) + } +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct State { + actors: Vec<Actor>, + open_valves: BTreeSet<usize>, +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Actor { + position: usize, + time_remaining: u32, +} + +impl State { + fn sort_actors(&mut self) { + self.actors.sort() + } +} + +impl CondensedNodes { + fn find_optimal_pressure_relieved(&mut self, state: &State) -> u32 { + let cache_value = self.cache.get(state); + if let Some(cache_value) = cache_value { + return *cache_value; + } + + let mut computed_value = 0; + for (actor_i, actor) in state.actors.iter().enumerate() { + let exits_to_investigate: Vec<(usize, u32)> = self.nodes[actor.position] + .exits + .iter() + .enumerate() + .filter(|(destination, distance)| { + !state.open_valves.contains(destination) && **distance <= actor.time_remaining + }) + .map(|(destination, distance)| (destination.clone(), distance.clone())) + .collect(); + + for (destination, distance) in exits_to_investigate { + let mut open_valves = state.open_valves.clone(); + open_valves.insert(destination.clone()); + let new_actor = Actor { + time_remaining: actor.time_remaining - distance, + position: destination.clone(), + }; + let relief_from_this_valve = + self.nodes[destination].flow_rate * new_actor.time_remaining as u32; + let mut actors = state.actors.clone(); + actors[actor_i] = new_actor; + + let mut state_this_way = State { + actors, + open_valves, + }; + state_this_way.sort_actors(); + + let recursive_relief = self.find_optimal_pressure_relieved(&state_this_way); + let relief = relief_from_this_valve + recursive_relief; + computed_value = computed_value.max(relief); + } + } + + self.cache.insert(state.clone(), computed_value); + computed_value + } +} diff --git a/2022/src/bin/day_17.rs b/2022/src/bin/day_17.rs new file mode 100644 index 0000000..46fedc8 --- /dev/null +++ b/2022/src/bin/day_17.rs @@ -0,0 +1,238 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + combinator::{map, value}, + multi::many1, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_17.txt")?; + let nudges = Inputs::parser(&input).unwrap().1; + let pieces = Piece::all(); + let board = GameBoard::new(pieces, nudges.nudges); + + { + let mut part_1_board = board.clone(); + for _ in 0..2022 { + part_1_board.drop_next_piece(); + } + dbg!(part_1_board.full_height()); + } + + { + let mut part_2_board = board.clone(); + for i in 0..1_000_000_000_000u64 { + if i % 1_000_000_000 == 0 { + dbg!(i / 1_000_000_000, part_2_board.truncated); + } + part_2_board.drop_next_piece(); + } + dbg!(part_2_board.full_height()); + } + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Inputs { + nudges: Vec<Nudge>, +} + +#[derive(Debug, Clone)] +enum Nudge { + Left, + Right, +} + +#[derive(Debug, Clone)] +struct Piece { + data_at_x: Vec<Vec<u8>>, +} + +impl Inputs { + fn parser(input: &str) -> IResult<&str, Self> { + map( + many1(alt(( + value(Nudge::Left, tag("<")), + value(Nudge::Right, tag(">")), + ))), + |nudges| Inputs { nudges }, + )(input) + } +} + +impl Piece { + fn new(data_at_x_0: Vec<u8>) -> Piece { + let mut shifting_data = data_at_x_0.clone(); + + let mut data_at_x = vec![data_at_x_0]; + + while shifting_data.iter().all(|b| b & 0b00000010 == 0) { + for row in &mut shifting_data { + *row >>= 1; + } + data_at_x.push(shifting_data.clone()); + } + + Piece { data_at_x } + } + + fn all() -> Vec<Piece> { + vec![ + Piece::new(vec![0b11110000]), + Piece::new(vec![0b01000000, 0b11100000, 0b01000000]), + Piece::new(vec![0b11100000, 0b00100000, 0b00100000]), + Piece::new(vec![0b10000000, 0b10000000, 0b10000000, 0b10000000]), + Piece::new(vec![0b11000000, 0b11000000]), + ] + } +} + +#[derive(Debug, Clone)] +struct GameBoard { + pieces: Vec<Piece>, + piece_index: usize, + nudges: Vec<Nudge>, + compound_nudges: Vec<Vec<usize>>, + nudge_index: usize, + solidified: Vec<u8>, + truncated: u64, +} + +impl GameBoard { + fn new(pieces: Vec<Piece>, nudges: Vec<Nudge>) -> GameBoard { + GameBoard { + compound_nudges: pieces + .iter() + .map(|piece| { + (0..nudges.len()) + .map(|nudge_start| { + let mut piece_x = 2; + for i in 0..4 { + let nudge_i = (nudge_start + i) % nudges.len(); + match nudges[nudge_i] { + Nudge::Left => { + if piece_x > 0 { + piece_x -= 1; + } + } + Nudge::Right => { + if piece_x < piece.data_at_x.len() - 1 { + piece_x += 1; + } + } + } + } + piece_x + }) + .collect() + }) + .collect(), + pieces, + piece_index: 0, + nudges, + nudge_index: 0, + solidified: Vec::new(), + truncated: 0, + } + } + + fn drop_next_piece(&mut self) { + let piece = &self.pieces[self.piece_index]; + // precomputes the effect of the first 4 nudges + let mut piece_x = self.compound_nudges[self.piece_index][self.nudge_index]; + + self.piece_index += 1; + if self.piece_index >= self.pieces.len() { + self.piece_index -= self.pieces.len(); + } + + self.nudge_index += 4; + if self.nudge_index >= self.nudges.len() { + self.nudge_index -= self.nudges.len(); + } + + let mut piece_y = self.first_open_row(); + + loop { + if piece_y > 0 && self.piece_can_be_at(piece_y - 1, &piece.data_at_x[piece_x]) { + piece_y -= 1; + } else { + break; + } + + let nudge = &self.nudges[self.nudge_index]; + self.nudge_index += 1; + if self.nudge_index >= self.nudges.len() { + self.nudge_index -= self.nudges.len(); + } + + match nudge { + Nudge::Left => { + if piece_x > 0 && self.piece_can_be_at(piece_y, &piece.data_at_x[piece_x - 1]) { + piece_x -= 1; + } + } + Nudge::Right => { + if piece_x < piece.data_at_x.len() - 1 + && self.piece_can_be_at(piece_y, &piece.data_at_x[piece_x + 1]) + { + piece_x += 1; + } + } + } + } + + let mut to_truncate = None; + for (i, piece_row) in piece.data_at_x[piece_x].iter().enumerate() { + let full_index = piece_y + i; + if full_index >= self.solidified.len() { + self.solidified.push(piece_row.clone()); + } else { + self.solidified[full_index] |= piece_row; + if self.solidified[full_index] == 0b11111110 { + to_truncate = Some(full_index); + } + } + } + + if let Some(to_truncate) = to_truncate { + self.truncated += to_truncate as u64; + let truncated_len = self.solidified.len() - to_truncate; + for move_i in 0..truncated_len { + self.solidified[move_i] = self.solidified[move_i + to_truncate]; + } + self.solidified.truncate(truncated_len); + } + } + + fn piece_can_be_at(&self, piece_y: usize, piece: &[u8]) -> bool { + for (i, row) in piece.iter().enumerate() { + let full_i = piece_y + i; + if full_i >= self.solidified.len() { + return true; + } + if self.solidified[full_i] & row != 0 { + return false; + } + } + return true; + } + + fn first_open_row(&self) -> usize { + self.solidified.len() + } + + fn full_height(&self) -> u64 { + self.first_open_row() as u64 + self.truncated + } + + fn debug(&self) { + println!("Clearerd: {}", self.truncated); + for row in self.solidified.iter().rev() { + println!("{:08b}", row); + } + } +} diff --git a/2022/src/bin/day_18.rs b/2022/src/bin/day_18.rs new file mode 100644 index 0000000..1111441 --- /dev/null +++ b/2022/src/bin/day_18.rs @@ -0,0 +1,157 @@ +use nom::{ + bytes::complete::tag, + character::complete::{i32, line_ending}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_18.txt")?; + let voxels = Voxels::parser(&input).unwrap().1; + dbg!(voxels.naive_surface_area()); + dbg!(voxels.exterior_surface_area()); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Voxels(BTreeSet<Point3d>); + +#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point3d { + x: i32, + y: i32, + z: i32, +} + +impl Voxels { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, Point3d::parser), |vox| { + Voxels(vox.into_iter().collect()) + })(input) + } + + fn naive_surface_area(&self) -> usize { + let units = Point3d::units(); + self.0 + .iter() + .flat_map(|v| units.iter().map(move |u| v + u)) + .filter(|v| !self.0.contains(v)) + .count() + } + + fn exterior_surface_area(&self) -> usize { + let units = Point3d::units(); + let mut known_internal: BTreeSet<Point3d> = BTreeSet::new(); + let known_external = self.bounds(); + + self.0 + .iter() + .flat_map(|v| units.iter().map(move |u| v + u)) + .filter(|v| !self.0.contains(v)) + .filter(|v| { + if known_internal.contains(v) { + return false; + } + + let mut flooded: BTreeSet<Point3d> = BTreeSet::new(); + let mut frontier: BTreeSet<Point3d> = BTreeSet::new(); + flooded.insert(v.clone()); + frontier.insert(v.clone()); + let mut is_internal = true; + while is_internal && frontier.len() > 0 { + let mut next_frontier = BTreeSet::new(); + for front in &frontier { + for unit in &units { + let adjacent = front + unit; + if !self.0.contains(&adjacent) && !flooded.contains(&adjacent) { + if known_external.contains(&adjacent) { + is_internal = false; + } + flooded.insert(adjacent.clone()); + next_frontier.insert(adjacent); + } + } + } + frontier = next_frontier; + } + if is_internal { + known_internal.append(&mut flooded); + } + + !is_internal + }) + .count() + } + + fn bounds(&self) -> BTreeSet<Point3d> { + let min_x = self.0.iter().map(|v| v.x).min().unwrap_or(0) - 1; + let max_x = self.0.iter().map(|v| v.x).max().unwrap_or(0) + 1; + let min_y = self.0.iter().map(|v| v.y).min().unwrap_or(0) - 1; + let max_y = self.0.iter().map(|v| v.y).max().unwrap_or(0) + 1; + let min_z = self.0.iter().map(|v| v.z).min().unwrap_or(0) - 1; + let max_z = self.0.iter().map(|v| v.z).max().unwrap_or(0) + 1; + + let mut result = BTreeSet::new(); + for x in [min_x, max_x] { + for y in [min_y, max_y] { + for z in [min_z, max_z] { + result.insert(Point3d { x, y, z }); + } + } + } + result + } +} + +impl Point3d { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple((i32, tag(","), i32, tag(","), i32)), + |(x, _, y, _, z)| Point3d { x, y, z }, + )(input) + } + + fn units() -> Vec<Point3d> { + vec![ + Point3d { + x: -1, + ..Point3d::default() + }, + Point3d { + x: 1, + ..Point3d::default() + }, + Point3d { + y: -1, + ..Point3d::default() + }, + Point3d { + y: 1, + ..Point3d::default() + }, + Point3d { + z: -1, + ..Point3d::default() + }, + Point3d { + z: 1, + ..Point3d::default() + }, + ] + } +} + +impl ::core::ops::Add<&Point3d> for &Point3d { + type Output = Point3d; + fn add(self, rhs: &Point3d) -> Point3d { + Point3d { + x: self.x.add(rhs.x), + y: self.y.add(rhs.y), + z: self.z.add(rhs.z), + } + } +} diff --git a/2022/src/bin/day_19.rs b/2022/src/bin/day_19.rs new file mode 100644 index 0000000..a6c1737 --- /dev/null +++ b/2022/src/bin/day_19.rs @@ -0,0 +1,352 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{line_ending, u32}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{cell::RefCell, collections::BTreeMap, fs}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_19.txt")?; + let blueprints = Blueprints::parser(&input).unwrap().1; + + dbg!(blueprints.quality_sum()); + + let part_2_state = State { + time_remaining: 32, + resources: Resources::default(), + robots: Resources { + ore: 1, + ..Resources::default() + }, + }; + + dbg!(blueprints + .0 + .iter() + .take(3) + .map(|b| { + let result = b.max_geodes(part_2_state.clone()); + b.clear_cache(); + result + }) + .product::<u32>()); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Blueprints(Vec<Blueprint>); + +#[derive(Debug, Clone)] +struct Blueprint { + id: u32, + ore_robot: Resources, + clay_robot: Resources, + obsidian_robot: Resources, + geode_robot: Resources, + max_geode_cache: RefCell<BTreeMap<State, u32>>, +} + +#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Resources { + ore: u32, + clay: u32, + obsidian: u32, + geodes: u32, +} + +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct State { + time_remaining: u32, + resources: Resources, + robots: Resources, +} + +impl Blueprints { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, Blueprint::parser), Blueprints)(input) + } + + fn quality_sum(&self) -> u32 { + self.0.iter().map(|b| b.quality_level()).sum() + } +} + +impl Blueprint { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + tag("Blueprint "), + u32, + tag(": Each ore robot costs "), + Resources::parser, + tag(". Each clay robot costs "), + Resources::parser, + tag(". Each obsidian robot costs "), + Resources::parser, + tag(". Each geode robot costs "), + Resources::parser, + tag("."), + )), + |(_, id, _, ore_robot, _, clay_robot, _, obsidian_robot, _, geode_robot, _)| { + Blueprint { + id, + ore_robot, + clay_robot, + obsidian_robot, + geode_robot, + max_geode_cache: RefCell::new(BTreeMap::new()), + } + }, + )(input) + } + + fn quality_level(&self) -> u32 { + let result = self.id + * self.max_geodes(State { + time_remaining: 24, + resources: Resources::default(), + robots: Resources { + ore: 1, + ..Resources::default() + }, + }); + self.clear_cache(); + result + } + + fn max_geodes(&self, state: State) -> u32 { + if state.time_remaining == 0 { + state.resources.geodes + } else { + if let Some(cache) = self.max_geode_cache.borrow().get(&state) { + return cache.clone(); + } + + let calculated = state + .possible_next_states(&self) + .into_iter() + .map(|next_state| self.max_geodes(next_state)) + .max() + .unwrap(); + self.max_geode_cache + .borrow_mut() + .insert(state.clone(), calculated); + calculated + } + } + + fn clear_cache(&self) { + self.max_geode_cache.borrow_mut().clear(); + } +} + +impl Resources { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1( + tag(" and "), + tuple(( + u32, + tag(" "), + alt((tag("ore"), tag("clay"), tag("obsidian"))), + )), + ), + |resources| { + let mut ore = 0; + let mut clay = 0; + let mut obsidian = 0; + + for (amount, _, resource) in resources { + match resource { + "ore" => ore = amount, + "clay" => clay = amount, + "obsidian" => obsidian = amount, + unknown => panic!("{} isn't one of the specified tags", unknown), + } + } + + Resources { + ore, + clay, + obsidian, + geodes: 0, + } + }, + )(input) + } +} + +impl State { + fn possible_next_states(&self, blueprint: &Blueprint) -> Vec<State> { + let mut next_states = Vec::new(); + + // build an ore robot + if let Some(time) = self.time_to_afford(&blueprint.ore_robot) { + let mut next_state = self.simulate_time_passing(time + 1); + next_state.robots.ore += 1; + next_state.resources -= &blueprint.ore_robot; + next_states.push(next_state); + } + + // build a clay robot + if let Some(time) = self.time_to_afford(&blueprint.clay_robot) { + let mut next_state = self.simulate_time_passing(time + 1); + next_state.robots.clay += 1; + next_state.resources -= &blueprint.clay_robot; + next_states.push(next_state); + } + + // build an obsidian robot + if let Some(time) = self.time_to_afford(&blueprint.obsidian_robot) { + let mut next_state = self.simulate_time_passing(time + 1); + next_state.robots.obsidian += 1; + next_state.resources -= &blueprint.obsidian_robot; + next_states.push(next_state); + } + + // build a geode robot + if let Some(time) = self.time_to_afford(&blueprint.geode_robot) { + let mut next_state = self.simulate_time_passing(time + 1); + next_state.robots.geodes += 1; + next_state.resources -= &blueprint.geode_robot; + next_states.push(next_state); + } + + // or just do nothing + if next_states.len() == 0 { + next_states.push(self.simulate_time_passing(self.time_remaining)); + } + + next_states + } + + fn simulate_time_passing(&self, time: u32) -> State { + State { + time_remaining: self.time_remaining - time, + resources: &self.resources + &(&self.robots * time), + robots: self.robots.clone(), + } + } + + fn time_to_afford(&self, cost: &Resources) -> Option<u32> { + let mut time_required = 0; + + if self.resources.ore < cost.ore { + if self.robots.ore == 0 { + return None; + } + time_required = time_required + .max((cost.ore - self.resources.ore + self.robots.ore - 1) / self.robots.ore); + } + + if self.resources.clay < cost.clay { + if self.robots.clay == 0 { + return None; + } + time_required = time_required + .max((cost.clay - self.resources.clay + self.robots.clay - 1) / self.robots.clay); + } + + if self.resources.obsidian < cost.obsidian { + if self.robots.obsidian == 0 { + return None; + } + time_required = time_required.max( + (cost.obsidian - self.resources.obsidian + self.robots.obsidian - 1) + / self.robots.obsidian, + ); + } + + if self.resources.geodes < cost.geodes { + if self.robots.geodes == 0 { + return None; + } + time_required = time_required.max( + (cost.geodes - self.resources.geodes + self.robots.geodes - 1) / self.robots.geodes, + ); + } + + if time_required + 1 >= self.time_remaining { + None + } else { + Some(time_required) + } + } +} + +impl ::core::ops::Add<&Resources> for &Resources { + type Output = Resources; + fn add(self, rhs: &Resources) -> Resources { + Resources { + ore: self.ore.add(rhs.ore), + clay: self.clay.add(rhs.clay), + obsidian: self.obsidian.add(rhs.obsidian), + geodes: self.geodes.add(rhs.geodes), + } + } +} + +impl ::core::ops::Sub<&Resources> for &Resources { + type Output = Resources; + fn sub(self, rhs: &Resources) -> Resources { + Resources { + ore: self.ore.sub(rhs.ore), + clay: self.clay.sub(rhs.clay), + obsidian: self.obsidian.sub(rhs.obsidian), + geodes: self.geodes.sub(rhs.geodes), + } + } +} + +impl ::core::ops::SubAssign<&Resources> for Resources { + fn sub_assign(&mut self, rhs: &Resources) { + self.ore -= rhs.ore; + self.clay -= rhs.clay; + self.obsidian -= rhs.obsidian; + self.geodes -= rhs.geodes; + } +} + +impl ::core::ops::Mul<u32> for &Resources { + type Output = Resources; + fn mul(self, rhs: u32) -> Resources { + Resources { + ore: self.ore.mul(rhs), + clay: self.clay.mul(rhs), + obsidian: self.obsidian.mul(rhs), + geodes: self.geodes.mul(rhs), + } + } +} + +#[test] +fn time_to_afford() { + let current_state = State { + time_remaining: 17, + resources: Resources { + ore: 1, + clay: 6, + obsidian: 0, + geodes: 0, + }, + robots: Resources { + ore: 1, + clay: 3, + obsidian: 0, + geodes: 0, + }, + }; + + let time_to_afford = current_state.time_to_afford(&Resources { + ore: 3, + clay: 14, + obsidian: 0, + geodes: 0, + }); + assert_eq!(time_to_afford, Some(3)); +} diff --git a/2022/src/bin/day_2.rs b/2022/src/bin/day_2.rs new file mode 100644 index 0000000..deb5294 --- /dev/null +++ b/2022/src/bin/day_2.rs @@ -0,0 +1,167 @@ +use nom::{ + branch::alt, + character::complete::{char as nom_char, line_ending}, + combinator::{map, value}, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_2.txt")?; + let game_log_part_1 = GameLog::parser(&input).unwrap().1; + dbg!(game_log_part_1.total_score()); + + let game_log_part_2 = GameLog::parser_part_2(&input).unwrap().1; + dbg!(game_log_part_2.total_score()); + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct GameLog { + moves: Vec<GameRound>, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct GameRound { + opponent: Move, + me: Move, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +enum Move { + Rock, + Paper, + Scissors, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +enum GameResult { + Win, + Lose, + Draw, +} + +impl GameLog { + fn parser(input: &str) -> IResult<&str, GameLog> { + map(separated_list1(line_ending, GameRound::parser), |moves| { + GameLog { moves } + })(input) + } + + fn parser_part_2(input: &str) -> IResult<&str, GameLog> { + map( + separated_list1(line_ending, GameRound::parser_part_2), + |moves| GameLog { moves }, + )(input) + } + + fn total_score(&self) -> u32 { + self.moves.iter().map(|m| m.score()).sum() + } +} + +impl GameRound { + fn parser(input: &str) -> IResult<&str, GameRound> { + map( + tuple((Move::opponent_parser, nom_char(' '), Move::player_parser)), + |(opponent, _, me)| GameRound { opponent, me }, + )(input) + } + + fn parser_part_2(input: &str) -> IResult<&str, GameRound> { + map( + tuple((Move::opponent_parser, nom_char(' '), GameResult::parser)), + |(opponent, _, result)| { + use GameResult::*; + use Move::*; + + let me = match opponent { + Rock => match result { + Win => Paper, + Draw => Rock, + Lose => Scissors, + }, + Paper => match result { + Win => Scissors, + Draw => Paper, + Lose => Rock, + }, + Scissors => match result { + Win => Rock, + Draw => Scissors, + Lose => Paper, + }, + }; + GameRound { opponent, me } + }, + )(input) + } + + fn score(&self) -> u32 { + let victory_points = match self.me.beats(&self.opponent) { + GameResult::Lose => 0, + GameResult::Draw => 3, + GameResult::Win => 6, + }; + + let throw_points = match self.me { + Move::Rock => 1, + Move::Paper => 2, + Move::Scissors => 3, + }; + + victory_points + throw_points + } +} + +impl Move { + fn opponent_parser(input: &str) -> IResult<&str, Move> { + alt(( + value(Move::Rock, nom_char('A')), + value(Move::Paper, nom_char('B')), + value(Move::Scissors, nom_char('C')), + ))(input) + } + + fn player_parser(input: &str) -> IResult<&str, Move> { + alt(( + value(Move::Rock, nom_char('X')), + value(Move::Paper, nom_char('Y')), + value(Move::Scissors, nom_char('Z')), + ))(input) + } + + fn beats(&self, other: &Move) -> GameResult { + use GameResult::*; + use Move::*; + match self { + Rock => match other { + Rock => Draw, + Paper => Lose, + Scissors => Win, + }, + Paper => match other { + Rock => Win, + Paper => Draw, + Scissors => Lose, + }, + Scissors => match other { + Rock => Lose, + Paper => Win, + Scissors => Draw, + }, + } + } +} + +impl GameResult { + fn parser(input: &str) -> IResult<&str, GameResult> { + alt(( + value(GameResult::Lose, nom_char('X')), + value(GameResult::Draw, nom_char('Y')), + value(GameResult::Win, nom_char('Z')), + ))(input) + } +} diff --git a/2022/src/bin/day_20.rs b/2022/src/bin/day_20.rs new file mode 100644 index 0000000..dc4bf4f --- /dev/null +++ b/2022/src/bin/day_20.rs @@ -0,0 +1,91 @@ +use nom::{ + character::complete::{i64, line_ending}, + combinator::map, + multi::separated_list1, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_20.txt")?; + let coordinates = GroveCoordinates::parser(&input).unwrap().1; + + { + let mut coordinates_1 = coordinates.clone(); + coordinates_1.mix(); + dbg!(coordinates_1.coordinate_sum()); + } + + { + let mut coordinates_2 = coordinates.clone(); + coordinates_2.decrypt(811589153); + dbg!(coordinates_2.coordinate_sum()); + } + + Ok(()) +} + +#[derive(Debug, Clone)] +struct GroveCoordinates(Vec<CoordinatePoint>); + +#[derive(Debug, Clone, Copy)] +struct CoordinatePoint { + val: i64, + original_order: usize, +} + +impl GroveCoordinates { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, i64), |points| { + GroveCoordinates( + points + .into_iter() + .enumerate() + .map(|(original_order, val)| CoordinatePoint { + val, + original_order, + }) + .collect(), + ) + })(input) + } + + fn decrypt(&mut self, key: i64) { + for p in &mut self.0 { + p.val *= key; + } + + for _ in 0..10 { + self.mix(); + } + } + + fn mix(&mut self) { + for original_i in 0..self.0.len() { + let encrypted_i = self + .0 + .iter() + .position(|p| p.original_order == original_i) + .unwrap(); + let to_move = self.0.remove(encrypted_i); + + let mut destination_i = encrypted_i as i64 + to_move.val; + destination_i %= self.0.len() as i64; + if destination_i < 0 { + destination_i += self.0.len() as i64; + } + self.0.insert(destination_i as usize, to_move); + } + } + + fn get(&self, i: usize) -> i64 { + self.0[i % self.0.len()].val + } + + fn coordinate_sum(&self) -> i64 { + let zero_position = self.0.iter().position(|p| p.val == 0).unwrap(); + self.get(zero_position + 1000) + + self.get(zero_position + 2000) + + self.get(zero_position + 3000) + } +} diff --git a/2022/src/bin/day_21.rs b/2022/src/bin/day_21.rs new file mode 100644 index 0000000..d118826 --- /dev/null +++ b/2022/src/bin/day_21.rs @@ -0,0 +1,298 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{alpha1, i64, line_ending}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{ + collections::{BTreeMap, BTreeSet}, + fs, +}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_21.txt")?; + let mut monkeys = Monkeys::parser(&input).unwrap().1; + + dbg!(monkeys.eval("root")); + + let (original_root_left, original_root_right) = + monkeys.0.get("root").expect("No root monkey!").values(); + + monkeys.0.insert( + "root".into(), + Expression::Eql(original_root_left, original_root_right.expect("foo")), + ); + monkeys + .0 + .insert("humn".into(), Expression::Value(Value::Input)); + + while monkeys.0.len() > 1 { + monkeys.simplify(); + } + println!("{}", monkeys.print_expression("root")); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Monkeys(BTreeMap<String, Expression>); + +#[derive(Debug, Clone)] +enum Expression { + Value(Value), + Add(Value, Value), + Sub(Value, Value), + Mul(Value, Value), + Div(Value, Value), + Eql(Value, Value), +} + +#[derive(Debug, Clone)] +enum Value { + Ref(String), + Literal(i64), + Input, +} + +impl Monkeys { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, tuple((alpha1, tag(": "), Expression::parser))), + |lines| { + Monkeys( + lines + .into_iter() + .map(|(id, _, expression): (&str, _, Expression)| { + (id.to_owned(), expression) + }) + .collect(), + ) + }, + )(input) + } + + fn simplify(&mut self) { + let ids: Vec<String> = self.0.keys().cloned().collect(); + + // simplify to literals where possible + for id in &ids { + if let Some(val) = self.eval(id) { + self.0 + .insert(id.clone(), Expression::Value(Value::Literal(val))); + } + } + + // simplify single sides of expressions where possible (especially unwrap refs) + for id in &ids { + let monkey = self.0.get(id).expect("Unknown monkey!"); + let simplified = match monkey { + Expression::Value(v) => Expression::Value(self.simplify_value(v)), + Expression::Add(a, b) => { + Expression::Add(self.simplify_value(a), self.simplify_value(b)) + } + Expression::Sub(a, b) => { + Expression::Sub(self.simplify_value(a), self.simplify_value(b)) + } + Expression::Mul(a, b) => { + Expression::Mul(self.simplify_value(a), self.simplify_value(b)) + } + Expression::Div(a, b) => { + Expression::Div(self.simplify_value(a), self.simplify_value(b)) + } + Expression::Eql(a, b) => { + Expression::Eql(self.simplify_value(a), self.simplify_value(b)) + } + }; + self.0.insert(id.clone(), simplified); + + if let Some(val) = self.eval(id) { + self.0 + .insert(id.clone(), Expression::Value(Value::Literal(val))); + } + } + + // simplify across the equals + for id in &ids { + let monkey = self.0.get(id).expect("Unknown monkey!").clone(); + match monkey { + Expression::Eql(Value::Ref(r), Value::Literal(v)) + | Expression::Eql(Value::Literal(v), Value::Ref(r)) => { + let referenced_monkey = self.0.get(&r).expect("Unknown monkey!").clone(); + + let new_eql = match referenced_monkey { + Expression::Add(new_lhs, Value::Literal(added)) + | Expression::Add(Value::Literal(added), new_lhs) => { + Some((new_lhs.clone(), v - added)) + } + Expression::Sub(new_lhs, Value::Literal(subtracted)) => { + Some((new_lhs.clone(), v + subtracted)) + } + Expression::Sub(Value::Literal(subtracted_from), new_lhs) => { + Some((new_lhs.clone(), subtracted_from - v)) + } + Expression::Mul(new_lhs, Value::Literal(mult)) + | Expression::Mul(Value::Literal(mult), new_lhs) => { + Some((new_lhs.clone(), v / mult)) + } + Expression::Div(new_lhs, Value::Literal(denom)) => { + Some((new_lhs.clone(), v * denom)) + } + _ => None, + }; + + if let Some((new_lhs, new_v)) = new_eql { + self.0 + .insert(id.clone(), Expression::Eql(new_lhs, Value::Literal(new_v))); + } + } + _ => {} + } + } + + // clearing out unreferenced monkeys + let monkey_references: BTreeSet<String> = self + .0 + .values() + .flat_map(|expression| match expression.values() { + (Value::Ref(v1), Some(Value::Ref(v2))) => vec![v1, v2], + (Value::Ref(v), _) | (_, Some(Value::Ref(v))) => vec![v], + _ => vec![], + }) + .collect(); + for id in &ids { + if id != "root" && !monkey_references.contains(id) { + self.0.remove(id); + } + } + } + + fn simplify_value(&self, val: &Value) -> Value { + match val { + Value::Ref(r) => { + let referenced = self.0.get(r).expect("Unknown monkey!"); + match referenced { + Expression::Value(v) => v.clone(), + _ => val.clone(), + } + } + v => v.clone(), + } + } + + fn eval(&self, id: &str) -> Option<i64> { + let monkey = self.0.get(id).expect("Unknown monkey!"); + + match monkey { + Expression::Value(v) => self.resolve_value(v), + Expression::Add(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| a + b), + Expression::Sub(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| a - b), + Expression::Mul(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| a * b), + Expression::Div(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| a / b), + Expression::Eql(a, b) => self + .resolve_value(a) + .zip(self.resolve_value(b)) + .map(|(a, b)| if a == b { 1 } else { 0 }), + } + } + + fn resolve_value(&self, value: &Value) -> Option<i64> { + match value { + Value::Ref(id) => self.eval(id), + Value::Literal(num) => Some(*num), + Value::Input => None, + } + } + + fn print_expression(&self, id: &str) -> String { + let monkey = self.0.get(id).expect("Unknown monkey!"); + + // The crazy newlines here make it easier to see the + // brackets. Drop it in emacs and autoindent, and it's easy to + // see the next expression which isn't being collapsed. + match monkey { + Expression::Value(v) => format!("(\n{}\n)", self.print_value(v)), + Expression::Add(a, b) => { + format!("(\n{}\n+\n{}\n)", self.print_value(a), self.print_value(b)) + } + Expression::Sub(a, b) => { + format!("(\n{}\n-\n{}\n)", self.print_value(a), self.print_value(b)) + } + Expression::Mul(a, b) => { + format!("(\n{}\n*\n{}\n)", self.print_value(a), self.print_value(b)) + } + Expression::Div(a, b) => { + format!("(\n{}\n/\n{}\n)", self.print_value(a), self.print_value(b)) + } + Expression::Eql(a, b) => { + format!("(\n{}\n=\n{}\n)", self.print_value(a), self.print_value(b)) + } + } + } + + fn print_value(&self, value: &Value) -> String { + match value { + Value::Ref(id) => self.print_expression(id), + Value::Literal(num) => format!("{}", num), + Value::Input => "input".into(), + } + } +} + +impl Expression { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + map( + tuple((Value::parser, tag(" + "), Value::parser)), + |(a, _, b)| Expression::Add(a, b), + ), + map( + tuple((Value::parser, tag(" - "), Value::parser)), + |(a, _, b)| Expression::Sub(a, b), + ), + map( + tuple((Value::parser, tag(" * "), Value::parser)), + |(a, _, b)| Expression::Mul(a, b), + ), + map( + tuple((Value::parser, tag(" / "), Value::parser)), + |(a, _, b)| Expression::Div(a, b), + ), + map(Value::parser, Expression::Value), + ))(input) + } + + fn values(&self) -> (Value, Option<Value>) { + match self.clone() { + Expression::Value(v) => (v, None), + Expression::Add(a, b) => (a, Some(b)), + Expression::Sub(a, b) => (a, Some(b)), + Expression::Mul(a, b) => (a, Some(b)), + Expression::Div(a, b) => (a, Some(b)), + Expression::Eql(a, b) => (a, Some(b)), + } + } +} + +impl Value { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + map(i64, Value::Literal), + map(alpha1, |s: &str| Value::Ref(s.to_owned())), + ))(input) + } +} diff --git a/2022/src/bin/day_22.rs b/2022/src/bin/day_22.rs new file mode 100644 index 0000000..784a608 --- /dev/null +++ b/2022/src/bin/day_22.rs @@ -0,0 +1,501 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{line_ending, u32}, + combinator::{map, value}, + multi::{many1, separated_list1}, + sequence::tuple, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_22.txt")?; + let parsed = Input::parser(&input).unwrap().1; + + dbg!(State::walk_the_map(&parsed, false).score()); + dbg!(State::walk_the_map(&parsed, true).score()); + + Ok(()) +} + +#[derive(Debug, Clone)] +struct Input { + map: Map, + instructions: Vec<Instruction>, +} + +#[derive(Debug, Clone)] +struct Map { + grid: Vec<Vec<MapPoint>>, + portals: Vec<Portal>, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum MapPoint { + Wall, + Empty, + Void, +} + +#[derive(Debug, Clone)] +enum Instruction { + TurnLeft, + TurnRight, + Walk(u32), +} + +impl Input { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + Map::parser, + line_ending, + line_ending, + many1(Instruction::parser), + )), + |(map, _, _, instructions)| Input { map, instructions }, + )(input) + } +} + +impl Map { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, many1(MapPoint::parser)), + |grid| Map { + grid, + portals: Portal::add_reverse_portals(vec![ + Portal { + // A -> F + src_boundary: LineSegment { + start: Point { x: 50, y: 0 }, + end: Point { x: 99, y: 0 }, + }, + src_facing: Direction::Up, + dest_boundary: LineSegment { + start: Point { x: 0, y: 150 }, + end: Point { x: 0, y: 199 }, + }, + dest_facing: Direction::Right, + }, + Portal { + // A -> D + src_boundary: LineSegment { + start: Point { x: 50, y: 0 }, + end: Point { x: 50, y: 49 }, + }, + src_facing: Direction::Left, + dest_boundary: LineSegment { + start: Point { x: 0, y: 149 }, + end: Point { x: 0, y: 100 }, + }, + dest_facing: Direction::Right, + }, + Portal { + // B -> F + src_boundary: LineSegment { + start: Point { x: 100, y: 0 }, + end: Point { x: 149, y: 0 }, + }, + src_facing: Direction::Up, + dest_boundary: LineSegment { + start: Point { x: 0, y: 199 }, + end: Point { x: 49, y: 199 }, + }, + dest_facing: Direction::Up, + }, + Portal { + // B -> E + src_boundary: LineSegment { + start: Point { x: 149, y: 0 }, + end: Point { x: 149, y: 49 }, + }, + src_facing: Direction::Right, + dest_boundary: LineSegment { + start: Point { x: 99, y: 149 }, + end: Point { x: 99, y: 100 }, + }, + dest_facing: Direction::Left, + }, + Portal { + // B -> C + src_boundary: LineSegment { + start: Point { x: 100, y: 49 }, + end: Point { x: 149, y: 49 }, + }, + src_facing: Direction::Down, + dest_boundary: LineSegment { + start: Point { x: 99, y: 50 }, + end: Point { x: 99, y: 99 }, + }, + dest_facing: Direction::Left, + }, + Portal { + // C -> D + src_boundary: LineSegment { + start: Point { x: 50, y: 50 }, + end: Point { x: 50, y: 99 }, + }, + src_facing: Direction::Left, + dest_boundary: LineSegment { + start: Point { x: 0, y: 100 }, + end: Point { x: 49, y: 100 }, + }, + dest_facing: Direction::Down, + }, + Portal { + // E -> F + src_boundary: LineSegment { + start: Point { x: 50, y: 149 }, + end: Point { x: 99, y: 149 }, + }, + src_facing: Direction::Down, + dest_boundary: LineSegment { + start: Point { x: 49, y: 150 }, + end: Point { x: 49, y: 199 }, + }, + dest_facing: Direction::Left, + }, + // AB + // C + // DE + // F + ]), + }, + )(input) + } +} + +impl MapPoint { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(MapPoint::Wall, tag("#")), + value(MapPoint::Empty, tag(".")), + value(MapPoint::Void, tag(" ")), + ))(input) + } +} + +impl Instruction { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(Instruction::TurnLeft, tag("L")), + value(Instruction::TurnRight, tag("R")), + map(u32, Instruction::Walk), + ))(input) + } +} + +#[derive(Debug, Clone)] +struct State { + position: Point, + facing: Direction, +} + +#[derive(Debug, Clone)] +struct Point { + x: usize, + y: usize, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +enum Direction { + Right, + Down, + Left, + Up, +} + +impl State { + fn walk_the_map(input: &Input, cube_wrapping: bool) -> State { + let mut state = State::spawn(&input.map); + for instruction in &input.instructions { + state.process_instruction(&input.map, &instruction, cube_wrapping); + } + state + } + + fn spawn(map: &Map) -> State { + let y = 0; + let x = map.grid[y] + .iter() + .position(|p| p == &MapPoint::Empty) + .unwrap(); + State { + position: Point { x, y }, + facing: Direction::Right, + } + } + + fn step_with_wrapping(&self, map: &Map) -> Point { + let mut next_point = self.position.clone(); + let mut made_a_step = false; + let mut hit_a_wall = false; + while !made_a_step && !hit_a_wall { + let peek = match self.facing { + Direction::Right => Point { + x: if next_point.x < map.grid[next_point.y].len() - 1 { + next_point.x + 1 + } else { + 0 + }, + ..next_point + }, + Direction::Left => Point { + x: if next_point.x > 0 { + next_point.x - 1 + } else { + map.grid[next_point.y].len() - 1 + }, + ..next_point + }, + Direction::Down => Point { + y: if next_point.y < map.grid.len() - 1 { + next_point.y + 1 + } else { + 0 + }, + ..next_point + }, + Direction::Up => Point { + y: if next_point.y > 0 { + next_point.y - 1 + } else { + map.grid.len() - 1 + }, + ..next_point + }, + }; + + let peek_value = map.grid[peek.y].get(peek.x); + match peek_value { + Some(MapPoint::Empty) => { + next_point = peek; + made_a_step = true; + } + Some(MapPoint::Void) | None => { + next_point = peek; + } + Some(MapPoint::Wall) => { + hit_a_wall = true; + } + } + } + + if hit_a_wall { + self.position.clone() + } else { + next_point + } + } + + fn step_with_cube_wrapping(&self, map: &Map) -> (Point, Direction) { + let (peek_position, peek_facing) = map + .portals + .iter() + .filter(|portal| portal.src_facing == self.facing) + .filter_map(|portal| { + portal + .src_boundary + .distance_from_start_on_line(&self.position) + .map(|distance| { + ( + portal.dest_boundary.find_point_on_line(distance), + portal.dest_facing.clone(), + ) + }) + }) + .next() + .unwrap_or_else(|| { + ( + match self.facing { + Direction::Right => Point { + x: self.position.x + 1, + ..self.position + }, + Direction::Left => Point { + x: self.position.x - 1, + ..self.position + }, + Direction::Down => Point { + y: self.position.y + 1, + ..self.position + }, + Direction::Up => Point { + y: self.position.y - 1, + ..self.position + }, + }, + self.facing.clone(), + ) + }); + + let peek_value = map.grid[peek_position.y].get(peek_position.x); + match peek_value { + Some(MapPoint::Empty) => (peek_position, peek_facing), + Some(MapPoint::Wall) => (self.position.clone(), self.facing.clone()), + Some(MapPoint::Void) | None => { + panic!("Cube wrapping shouldn't land on voids"); + } + } + } + + fn process_instruction(&mut self, map: &Map, instruction: &Instruction, cube_wrapping: bool) { + match instruction { + Instruction::TurnLeft => { + self.facing = self.facing.spin_left(); + } + Instruction::TurnRight => { + self.facing = self.facing.spin_right(); + } + Instruction::Walk(amount) => { + for _ in 0..*amount { + if cube_wrapping { + let (next_position, next_facing) = self.step_with_cube_wrapping(&map); + self.position = next_position; + self.facing = next_facing; + } else { + self.position = self.step_with_wrapping(&map); + } + } + } + } + } + + fn score(&self) -> usize { + (self.position.y + 1) * 1000 + (self.position.x + 1) * 4 + self.facing.score() + } +} + +impl Direction { + fn spin_left(&self) -> Direction { + match self { + Direction::Right => Direction::Up, + Direction::Down => Direction::Right, + Direction::Left => Direction::Down, + Direction::Up => Direction::Left, + } + } + + fn spin_right(&self) -> Direction { + self.spin_left().spin_left().spin_left() + } + + fn score(&self) -> usize { + match self { + Direction::Right => 0, + Direction::Down => 1, + Direction::Left => 2, + Direction::Up => 3, + } + } +} + +#[derive(Debug, Clone)] +struct Portal { + src_boundary: LineSegment, + src_facing: Direction, + dest_boundary: LineSegment, + dest_facing: Direction, +} + +#[derive(Debug, Clone)] +struct LineSegment { + start: Point, + end: Point, +} + +impl Portal { + fn add_reverse_portals(mut portals: Vec<Portal>) -> Vec<Portal> { + let mut reverse = portals + .iter() + .map(|forward_portal| Portal { + src_boundary: forward_portal.dest_boundary.clone(), + src_facing: forward_portal.dest_facing.spin_left().spin_left(), + dest_boundary: forward_portal.src_boundary.clone(), + dest_facing: forward_portal.src_facing.spin_left().spin_left(), + }) + .collect(); + portals.append(&mut reverse); + portals + } +} + +impl LineSegment { + fn distance_from_start_on_line(&self, p: &Point) -> Option<usize> { + if self.start.x == self.end.x { + if self.start.x != p.x { + None + } else { + if self.start.y < self.end.y { + if self.start.y <= p.y && self.end.y >= p.y { + Some(p.y - self.start.y) + } else { + None + } + } else { + if self.start.y >= p.y && self.end.y <= p.y { + Some(self.start.y - p.y) + } else { + None + } + } + } + } else if self.start.y == self.end.y { + if self.start.y != p.y { + None + } else { + if self.start.x < self.end.x { + if self.start.x <= p.x && self.end.x >= p.x { + Some(p.x - self.start.x) + } else { + None + } + } else { + if self.start.x >= p.x && self.end.x <= p.x { + Some(self.start.x - p.x) + } else { + None + } + } + } + } else { + unimplemented!("Oh no, we only handle straight portals") + } + } + + fn find_point_on_line(&self, distance: usize) -> Point { + if self.start.x == self.end.x { + if self.start.y < self.end.y { + assert!(self.start.y + distance <= self.end.y); + Point { + x: self.start.x, + y: self.start.y + distance, + } + } else { + assert!(self.start.y - distance >= self.end.y); + Point { + x: self.start.x, + y: self.start.y - distance, + } + } + } else if self.start.y == self.end.y { + if self.start.x < self.end.x { + assert!(self.start.x + distance <= self.end.x); + Point { + y: self.start.y, + x: self.start.x + distance, + } + } else { + assert!(self.start.x - distance >= self.end.x); + Point { + y: self.start.y, + x: self.start.x - distance, + } + } + } else { + unimplemented!("Oh no, we only handle straight portals") + } + } +} diff --git a/2022/src/bin/day_23.rs b/2022/src/bin/day_23.rs new file mode 100644 index 0000000..44483a5 --- /dev/null +++ b/2022/src/bin/day_23.rs @@ -0,0 +1,346 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::line_ending, + combinator::{map, value}, + multi::{many1, separated_list1}, + IResult, +}; +use std::{ + collections::{BTreeMap, BTreeSet, VecDeque}, + fs, +}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_23.txt")?; + let elves = ElfMap::parser(&input).unwrap().1; + + { + let mut elves_1 = elves.clone(); + for _ in 0..10 { + elves_1.process_round(); + } + dbg!(elves_1.count_empty_ground()); + } + + { + let mut elves_2 = elves; + for round in 1.. { + if !elves_2.process_round() { + dbg!(round); + break; + } + } + } + + Ok(()) +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct ElfMap { + elves: BTreeSet<Point>, + check_order: VecDeque<Direction>, +} + +#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + y: i64, + x: i64, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +enum Direction { + North, + South, + West, + East, +} + +impl ElfMap { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1( + line_ending, + map( + many1(alt((value(true, tag("#")), value(false, tag("."))))), + |row| { + row.into_iter() + .enumerate() + .filter_map(|(x, occupied)| occupied.then_some(x as i64)) + .collect::<Vec<i64>>() + }, + ), + ), + |rows| { + let elves = rows + .into_iter() + .enumerate() + .flat_map(|(y, row)| row.into_iter().map(move |x| Point { x, y: y as i64 })) + .collect(); + ElfMap { + elves, + check_order: [ + Direction::North, + Direction::South, + Direction::West, + Direction::East, + ] + .into(), + } + }, + )(input) + } + + fn process_round(&mut self) -> bool { + // key is destination! + let mut elf_moves: BTreeMap<Point, Point> = BTreeMap::new(); + let mut conflict_moves: BTreeSet<Point> = BTreeSet::new(); + + // phase 1: figure out where each elf wants to move + for elf in &self.elves { + if let Some(destination) = self.find_elf_move(elf) { + use std::collections::btree_map::Entry; + match elf_moves.entry(destination) { + Entry::Occupied(elf_move_entry) => { + conflict_moves.insert(elf_move_entry.key().clone()); + elf_move_entry.remove_entry(); + } + Entry::Vacant(elf_move_entry) => { + if !conflict_moves.contains(elf_move_entry.key()) { + elf_move_entry.insert(elf.clone()); + } + } + } + } + } + + let any_elf_moved = !elf_moves.is_empty(); + + // phase 2: move the elves + for (dest, src) in elf_moves { + self.elves.remove(&src); + self.elves.insert(dest); + } + + let rotate = self + .check_order + .pop_front() + .expect("Where did the directions go?"); + self.check_order.push_back(rotate); + + any_elf_moved + } + + fn find_elf_move(&self, elf: &Point) -> Option<Point> { + let all_adjacent = elf.adjacent(None); + let any_adjacent_elves = all_adjacent.into_iter().any(|p| self.elves.contains(&p)); + if !any_adjacent_elves { + None + } else { + self.check_order + .iter() + .filter_map(|dir| { + let adjacent = elf.adjacent(Some(*dir)); + let any_adjacent_elves = adjacent.iter().any(|p| self.elves.contains(p)); + if !any_adjacent_elves { + Some(adjacent[1].clone()) + } else { + None + } + }) + .next() + } + } + + fn count_empty_ground(&self) -> i64 { + let elf_x = self.elves.iter().map(|elf| elf.x); + let min_x = elf_x.clone().min().unwrap_or(0); + let max_x = elf_x.max().unwrap_or(0); + + let elf_y = self.elves.iter().map(|elf| elf.y); + let min_y = elf_y.clone().min().unwrap_or(0); + let max_y = elf_y.max().unwrap_or(0); + + let all_ground = (max_x - min_x + 1) * (max_y - min_y + 1); + let covered_ground = self.elves.len() as i64; + all_ground - covered_ground + } +} + +impl Point { + fn adjacent(&self, direction: Option<Direction>) -> Vec<Point> { + let (y_range, x_range) = match direction { + None => ((-1..=1), (-1..=1)), + Some(Direction::North) => ((-1..=-1), (-1..=1)), + Some(Direction::South) => ((1..=1), (-1..=1)), + Some(Direction::West) => ((-1..=1), (-1..=-1)), + Some(Direction::East) => ((-1..=1), (1..=1)), + }; + + y_range + .flat_map(|dy| { + x_range.clone().map(move |dx| Point { + x: self.x + dx, + y: self.y + dy, + }) + }) + .filter(|p| p != self) + .collect() + } +} + +#[test] +fn follows_the_example() { + let mut elf_map = ElfMap::parser( + r".............. +.............. +.......#...... +.....###.#.... +...#...#.#.... +....#...##.... +...#.###...... +...##.#.##.... +....#..#...... +.............. +.............. +..............", + ) + .unwrap() + .1; + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".............. +.......#...... +.....#...#.... +...#..#.#..... +.......#..#... +....#.#.##.... +..#..#.#...... +..#.#.#.##.... +.............. +....#..#...... +.............. +.............. +" + ) + .unwrap() + .1 + .elves + ); + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".............. +.......#...... +....#.....#... +...#..#.#..... +.......#...#.. +...#..#.#..... +.#...#.#.#.... +.............. +..#.#.#.##.... +....#..#...... +.............. +.............. +" + ) + .unwrap() + .1 + .elves + ); + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".............. +.......#...... +.....#....#... +..#..#...#.... +.......#...#.. +...#..#.#..... +.#..#.....#... +.......##..... +..##.#....#... +...#.......... +.......#...... +.............." + ) + .unwrap() + .1 + .elves + ); + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".............. +.......#...... +......#....#.. +..#...##...... +...#.....#.#.. +.........#.... +.#...###..#... +..#......#.... +....##....#... +....#......... +.......#...... +.............." + ) + .unwrap() + .1 + .elves + ); + + elf_map.process_round(); + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".......#...... +.............. +..#..#.....#.. +.........#.... +......##...#.. +.#.#.####..... +...........#.. +....##..#..... +..#........... +..........#... +....#..#...... +.............." + ) + .unwrap() + .1 + .elves + ); + + for _ in 0..5 { + elf_map.process_round(); + } + assert_eq!( + elf_map.elves, + ElfMap::parser( + r".......#...... +...........#.. +..#.#..#...... +......#....... +...#.....#..#. +.#......##.... +.....##....... +..#........#.. +....#.#..#.... +.............. +....#..#..#... +.............." + ) + .unwrap() + .1 + .elves + ); +} diff --git a/2022/src/bin/day_24.rs b/2022/src/bin/day_24.rs new file mode 100644 index 0000000..71edc71 --- /dev/null +++ b/2022/src/bin/day_24.rs @@ -0,0 +1,195 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::line_ending, + combinator::{map, value}, + multi::{many1, separated_list1}, + sequence::{delimited, tuple}, + IResult, +}; +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_24.txt")?; + let blizzard_map = BlizzardMap::parser(&input).unwrap().1; + let start = Point { x: 0, y: 0 }; + let end = Point { + x: blizzard_map.width - 1, + y: blizzard_map.height - 1, + }; + let there_the_first_time = + dbg!(blizzard_map.find_shortest_path_through(start.clone(), end.clone(), 1)); + let back_again = dbg!(blizzard_map.find_shortest_path_through( + end.clone(), + start.clone(), + there_the_first_time + 1 + )); + dbg!(blizzard_map.find_shortest_path_through(start, end, back_again + 1)); + + Ok(()) +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct BlizzardMap { + width: usize, + height: usize, + blizzards: Vec<Blizzard>, +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct Blizzard { + start: Point, + direction: Direction, +} + +#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)] +struct Point { + y: usize, + x: usize, +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +enum Direction { + North, + South, + West, + East, +} + +impl BlizzardMap { + fn parser(input: &str) -> IResult<&str, Self> { + map( + delimited( + tuple((many1(tag("#")), tag("."), many1(tag("#")), line_ending)), + separated_list1( + line_ending, + delimited(tag("#"), many1(Direction::parser), tag("#")), + ), + tuple((line_ending, many1(tag("#")), tag("."), many1(tag("#")))), + ), + |blizzard_directions| BlizzardMap { + width: blizzard_directions[0].len(), + height: blizzard_directions.len(), + blizzards: blizzard_directions + .into_iter() + .enumerate() + .flat_map(|(y, row)| { + row.into_iter() + .enumerate() + .filter_map(move |(x, direction)| { + direction.map(|direction| Blizzard { + start: Point { x, y }, + direction, + }) + }) + }) + .collect(), + }, + )(input) + } + + fn find_shortest_path_through( + &self, + start: Point, + end: Point, + mut current_round: usize, + ) -> usize { + // Not sure if "visited" makes sense here because of the time + // delay. Same position at different times is different. Maybe + // makes sense if I keep time in too. + let mut frontier = BTreeSet::new(); + frontier.insert(start); + while !frontier.contains(&end) { + current_round += 1; + let last_frontier = std::mem::take(&mut frontier); + + let blizzards = self.blizzards_at_time(current_round); + + for frontier_state in last_frontier { + let mut possible_moves = vec![frontier_state.clone()]; + if frontier_state.x > 0 { + possible_moves.push(Point { + x: frontier_state.x - 1, + y: frontier_state.y, + }); + } + if frontier_state.x < self.width - 1 { + possible_moves.push(Point { + x: frontier_state.x + 1, + y: frontier_state.y, + }); + } + if frontier_state.y > 0 { + possible_moves.push(Point { + x: frontier_state.x, + y: frontier_state.y - 1, + }); + } + if frontier_state.y < self.height - 1 { + possible_moves.push(Point { + x: frontier_state.x, + y: frontier_state.y + 1, + }); + } + + for next in possible_moves { + if !blizzards.contains(&next) { + frontier.insert(next); + } + } + } + } + + current_round + 1 // extra minute to leave + } + + fn blizzards_at_time(&self, t: usize) -> BTreeSet<Point> { + self.blizzards + .iter() + .map(|blizzard| match blizzard.direction { + Direction::North => { + let t = t % self.height; + Point { + y: if blizzard.start.y > t { + blizzard.start.y - t + } else { + blizzard.start.y + self.height - t + }, + ..blizzard.start + } + } + Direction::South => Point { + y: (blizzard.start.y + t) % self.height, + ..blizzard.start + }, + Direction::West => { + let t = t % self.width; + Point { + x: if blizzard.start.x > t { + blizzard.start.x - t + } else { + blizzard.start.x + self.width - t + }, + ..blizzard.start + } + } + Direction::East => Point { + x: (blizzard.start.x + t) % self.width, + ..blizzard.start + }, + }) + .collect() + } +} + +impl Direction { + fn parser(input: &str) -> IResult<&str, Option<Self>> { + alt(( + value(None, tag(".")), + value(Some(Direction::South), tag("v")), + value(Some(Direction::West), tag("<")), + value(Some(Direction::East), tag(">")), + value(Some(Direction::North), tag("^")), + ))(input) + } +} diff --git a/2022/src/bin/day_25.rs b/2022/src/bin/day_25.rs new file mode 100644 index 0000000..d55f30a --- /dev/null +++ b/2022/src/bin/day_25.rs @@ -0,0 +1,111 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::line_ending, + combinator::{map, value}, + multi::{many1, separated_list1}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_25.txt")?; + let parsed = SnafuList::parser(&input).unwrap().1; + dbg!(to_snafu(parsed.sum())); + + Ok(()) +} + +#[derive(Debug, Clone, PartialEq, Eq)] +struct SnafuList(Vec<i64>); + +impl SnafuList { + fn parser(input: &str) -> IResult<&str, SnafuList> { + map( + separated_list1( + line_ending, + map( + many1(alt(( + value(2, tag("2")), + value(1, tag("1")), + value(0, tag("0")), + value(-1, tag("-")), + value(-2, tag("=")), + ))), + |digits| { + let mut result: i64 = 0; + for digit in digits { + result *= 5; + result += digit; + } + result + }, + ), + ), + SnafuList, + )(input) + } + + fn sum(&self) -> i64 { + self.0.iter().sum() + } +} + +fn to_snafu(mut remaining_value: i64) -> String { + let mut result = String::new(); + + let mut current_power = 5i64.pow(26); + + while current_power > 0 { + let next_digit_range = { + let mut next_digit_power = current_power / 5; + let mut max_next_digit = 0; + while next_digit_power > 0 { + max_next_digit += 2 * next_digit_power; + next_digit_power /= 5; + } + -max_next_digit..=max_next_digit + }; + + let (digit, digit_value) = [('=', -2), ('-', -1), ('0', 0), ('1', 1), ('2', 2)] + .into_iter() + .filter_map(|(digit, digit_value)| { + let digit_value = digit_value * current_power; + let remaining_if_digit_set = remaining_value - digit_value; + if next_digit_range.contains(&remaining_if_digit_set) { + Some((digit, digit_value)) + } else { + None + } + }) + .next() + .expect("No digit found"); + + remaining_value -= digit_value; + result.push(digit); + + current_power /= 5; + } + + result.trim_start_matches("0").to_owned() +} + +#[test] +fn round_trip_works() { + let str_list = vec![ + "1=-0-2", "12111", "2=0=", "21", "2=01", "111", "20012", "112", "1=-1=", "1-12", "12", + "1=", "122", + ]; + let list = SnafuList::parser(&str_list.join("\n")).unwrap().1; + + assert_eq!( + list, + SnafuList(vec![ + 1747, 906, 198, 11, 201, 31, 1257, 32, 353, 107, 7, 3, 37 + ]) + ); + + for (i, num) in list.0.iter().enumerate() { + assert_eq!(to_snafu(*num), str_list[i]); + } +} diff --git a/2022/src/bin/day_3.rs b/2022/src/bin/day_3.rs new file mode 100644 index 0000000..ec2d5e2 --- /dev/null +++ b/2022/src/bin/day_3.rs @@ -0,0 +1,100 @@ +use nom::{ + character::complete::{line_ending, satisfy}, + combinator::map, + multi::{many1, separated_list1}, + IResult, +}; +use std::{collections::BTreeSet, fs, iter::Iterator}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_3.txt")?; + let rucksacks = Rucksacks::parser(&input).unwrap().1; + dbg!(rucksacks.disorder_sum()); + dbg!(rucksacks.groups_sum()); + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct Rucksacks(Vec<Rucksack>); + +#[derive(Debug, PartialEq, Eq, Clone)] +struct Rucksack { + front: BTreeSet<ItemType>, + back: BTreeSet<ItemType>, +} + +#[derive(Debug, PartialEq, Eq, Clone, PartialOrd, Ord)] +struct ItemType(char); + +impl Rucksacks { + fn parser(input: &str) -> IResult<&str, Rucksacks> { + map(separated_list1(line_ending, Rucksack::parser), Rucksacks)(input) + } + + fn disorder_sum(&self) -> u32 { + self.0.iter().map(|r| r.intersection_priority()).sum() + } + + fn groups_sum(&self) -> u32 { + self.0 + .chunks(3) + .map(|group| { + let mut overlap = group[0].union(); + for m in group.iter().skip(1) { + overlap = overlap.intersection(&m.union()).cloned().collect(); + } + overlap.iter().map(|c| c.priority()).sum::<u32>() + }) + .sum() + } +} + +impl Rucksack { + fn parser(input: &str) -> IResult<&str, Rucksack> { + map(many1(ItemType::parser), Rucksack::new)(input) + } + + fn new(contents: Vec<ItemType>) -> Rucksack { + let mid = contents.len() / 2; + let front_str = &contents[0..mid]; + let back_str = &contents[mid..]; + + let mut front = BTreeSet::new(); + for c in front_str { + front.insert(c.clone()); + } + + let mut back = BTreeSet::new(); + for c in back_str { + back.insert(c.clone()); + } + + Rucksack { front, back } + } + + fn intersection(&self) -> BTreeSet<ItemType> { + self.front.intersection(&self.back).cloned().collect() + } + + fn union(&self) -> BTreeSet<ItemType> { + self.front.union(&self.back).cloned().collect() + } + + fn intersection_priority(&self) -> u32 { + self.intersection().iter().map(|c| c.priority()).sum() + } +} + +impl ItemType { + fn parser(input: &str) -> IResult<&str, ItemType> { + map(satisfy(|c| c.is_alphabetic()), ItemType)(input) + } + + fn priority(&self) -> u32 { + if self.0.is_uppercase() { + (self.0 as u32 - 'A' as u32) + 27 + } else { + (self.0 as u32 - 'a' as u32) + 1 + } + } +} diff --git a/2022/src/bin/day_4.rs b/2022/src/bin/day_4.rs new file mode 100644 index 0000000..5f08d70 --- /dev/null +++ b/2022/src/bin/day_4.rs @@ -0,0 +1,88 @@ +use nom::{ + bytes::complete::tag, + character::complete::{line_ending, u32 as nom_u32}, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{fs, iter::Iterator, ops::RangeInclusive}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_4.txt")?; + let assignments = Assignments::parser(&input).unwrap().1; + dbg!(assignments.count_containing_assignments()); + dbg!(assignments.count_overlapping_assignments()); + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct Assignments(Vec<AssignmentPair>); + +#[derive(Debug, PartialEq, Eq, Clone)] +struct AssignmentPair { + elf_1: Assignment, + elf_2: Assignment, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct Assignment(RangeInclusive<u32>); + +impl Assignments { + fn parser(input: &str) -> IResult<&str, Assignments> { + map( + separated_list1(line_ending, AssignmentPair::parser), + Assignments, + )(input) + } + + fn count_containing_assignments(&self) -> usize { + self.0 + .iter() + .filter(|pair| pair.one_completely_overlaps_other()) + .count() + } + + fn count_overlapping_assignments(&self) -> usize { + self.0 + .iter() + .filter(|pair| pair.one_overlaps_other()) + .count() + } +} + +impl AssignmentPair { + fn parser(input: &str) -> IResult<&str, AssignmentPair> { + map( + tuple((Assignment::parser, tag(","), Assignment::parser)), + |(elf_1, _, elf_2)| AssignmentPair { elf_1, elf_2 }, + )(input) + } + + fn one_completely_overlaps_other(&self) -> bool { + self.elf_1.contains(&self.elf_2) || self.elf_2.contains(&self.elf_1) + } + + fn one_overlaps_other(&self) -> bool { + self.elf_1.overlaps(&self.elf_2) + } +} + +impl Assignment { + fn parser(input: &str) -> IResult<&str, Assignment> { + map(tuple((nom_u32, tag("-"), nom_u32)), |(start, _, end)| { + Assignment(RangeInclusive::new(start, end)) + })(input) + } + + fn contains(&self, other: &Assignment) -> bool { + self.0.contains(other.0.start()) && self.0.contains(other.0.end()) + } + + fn overlaps(&self, other: &Assignment) -> bool { + self.0.contains(other.0.start()) + || self.0.contains(other.0.end()) + || other.0.contains(self.0.start()) + || other.0.contains(self.0.end()) + } +} diff --git a/2022/src/bin/day_5.rs b/2022/src/bin/day_5.rs new file mode 100644 index 0000000..f06012c --- /dev/null +++ b/2022/src/bin/day_5.rs @@ -0,0 +1,147 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{ + anychar, char as nom_char, line_ending, not_line_ending, u32 as nom_u32, + }, + combinator::map, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_5.txt")?; + let state = CraneState::parser(&input).unwrap().1; + + let mut state_part_1 = state.clone(); + while !state_part_1.done() { + state_part_1.process_next_instruction(false); + } + dbg!(state_part_1.read_top_row()); + + let mut state_part_2 = state.clone(); + while !state_part_2.done() { + state_part_2.process_next_instruction(true); + } + dbg!(state_part_2.read_top_row()); + + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct CraneState { + towers: Vec<Tower>, + instructions: Vec<Instruction>, +} + +#[derive(Debug, Default, PartialEq, Eq, Clone)] +struct Tower { + crates: Vec<char>, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct Instruction { + number: usize, + src: usize, + dest: usize, +} + +impl CraneState { + fn parser(input: &str) -> IResult<&str, CraneState> { + let single_crate = alt(( + map(tuple((tag("["), anychar, tag("]"))), |(_, c, _)| Some(c)), + map(tag(" "), |_| None), + )); + let crate_row = separated_list1(nom_char(' '), single_crate); + + map( + tuple(( + separated_list1(line_ending, crate_row), + line_ending, + not_line_ending, + line_ending, + line_ending, + separated_list1(line_ending, Instruction::parser), + )), + |(crate_rows, _, _, _, _, mut instructions)| { + let mut towers = Vec::new(); + for row in &crate_rows { + for (i, c) in row + .iter() + .enumerate() + .filter_map(|(i, c)| c.map(|some_c| (i, some_c))) + { + while i >= towers.len() { + towers.push(Tower::default()); + } + towers[i].crates.push(c); + } + } + for tower in &mut towers { + tower.crates.reverse(); + } + + instructions.reverse(); + CraneState { + towers, + instructions, + } + }, + )(input) + } + + fn process_next_instruction(&mut self, maintain_order: bool) { + let Some(instruction) = self.instructions.pop() else { + return + }; + let mut to_move = Vec::new(); + for _ in 0..instruction.number { + let Some(crate_to_move) = self.towers[instruction.src].crates.pop() else { + panic!("Invalid puzzle input: failed to get crate"); + }; + to_move.push(crate_to_move); + } + if maintain_order { + to_move.reverse(); + } + for crate_to_move in to_move { + self.towers[instruction.dest].crates.push(crate_to_move); + } + } + + fn done(&self) -> bool { + self.instructions.len() == 0 + } + + fn read_top_row(&self) -> String { + let mut res = String::new(); + for tower in &self.towers { + if let Some(top) = tower.crates.last() { + res.push(*top); + } + } + res + } +} + +impl Instruction { + fn parser(input: &str) -> IResult<&str, Instruction> { + map( + tuple(( + tag("move "), + nom_u32, + tag(" from "), + nom_u32, + tag(" to "), + nom_u32, + )), + |(_, number, _, src, _, dest)| Instruction { + number: number as usize, + src: (src - 1) as usize, + dest: (dest - 1) as usize, + }, + )(input) + } +} diff --git a/2022/src/bin/day_6.rs b/2022/src/bin/day_6.rs new file mode 100644 index 0000000..f02feca --- /dev/null +++ b/2022/src/bin/day_6.rs @@ -0,0 +1,20 @@ +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_6.txt")?; + let chars: Vec<char> = input.trim().chars().collect(); + dbg!(find_distinct_char_run(&chars, 4)); + dbg!(find_distinct_char_run(&chars, 14)); + + Ok(()) +} + +fn find_distinct_char_run(chars: &[char], window_size: usize) -> Option<usize> { + for (i, char_window) in chars.windows(window_size).enumerate() { + let set: BTreeSet<&char> = char_window.iter().collect(); + if set.len() == window_size { + return Some(i + window_size); + } + } + return None; +} diff --git a/2022/src/bin/day_7.rs b/2022/src/bin/day_7.rs new file mode 100644 index 0000000..8933816 --- /dev/null +++ b/2022/src/bin/day_7.rs @@ -0,0 +1,227 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{line_ending, not_line_ending, u32 as nom_u32}, + combinator::map, + multi::separated_list1, + sequence::{preceded, tuple}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_7.txt")?; + let terminal_log = TerminalLog::parser(&input).unwrap().1; + let dir_tree = terminal_log.process_to_dir_tree(); + + dbg!(dir_tree.sum_sizes_below_threshhold(100000)); + + let required_disk_usage = 70000000 - 30000000; + let required_deletion = dir_tree.size() - required_disk_usage; + dbg!(dir_tree.find_min_size_greater_than(required_deletion)); + + Ok(()) +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct TerminalLog(Vec<TerminalLogItem>); + +#[derive(Debug, PartialEq, Eq, Clone)] +enum TerminalLogItem { + Command(TerminalLogCommand), + Output(TerminalLogOutput), +} + +#[derive(Debug, PartialEq, Eq, Clone)] +enum TerminalLogCommand { + CdRoot, + CdUp, + CdDown(String), + List, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +enum TerminalLogOutput { + Dir(String), + File(u32, String), +} + +impl TerminalLog { + fn parser(input: &str) -> IResult<&str, TerminalLog> { + map( + separated_list1(line_ending, TerminalLogItem::parser), + TerminalLog, + )(input) + } + + fn process_to_dir_tree(&self) -> DirTree { + use TerminalLogCommand::*; + use TerminalLogItem::*; + use TerminalLogOutput::*; + + let mut dir_tree_root = DirTree::root(); + let mut dir_path = Vec::new(); + + for log in &self.0 { + match log { + Command(CdRoot) => dir_path.clear(), + Command(CdUp) => { + dir_path.pop(); + } + Command(CdDown(dir_name)) => { + dir_path.push(dir_name.clone()); + } + Command(List) => {} + Output(Dir(dir_name)) => { + let dir = DirTree::new(dir_name.clone()); + dir_tree_root.push_dir(&dir_path, dir); + } + Output(File(size, name)) => { + let file = DirTreeFile { + name: name.clone(), + size: size.clone(), + }; + dir_tree_root.push_file(&dir_path, file); + } + } + } + + dir_tree_root + } +} + +impl TerminalLogItem { + fn parser(input: &str) -> IResult<&str, TerminalLogItem> { + alt(( + map( + preceded(tag("$ "), TerminalLogCommand::parser), + TerminalLogItem::Command, + ), + map(TerminalLogOutput::parser, TerminalLogItem::Output), + ))(input) + } +} + +impl TerminalLogCommand { + fn parser(input: &str) -> IResult<&str, TerminalLogCommand> { + alt(( + map(tag("cd /"), |_| TerminalLogCommand::CdRoot), + map(tag("cd .."), |_| TerminalLogCommand::CdUp), + map(preceded(tag("cd "), name_parser), |name| { + TerminalLogCommand::CdDown(name) + }), + map(tag("ls"), |_| TerminalLogCommand::List), + ))(input) + } +} + +impl TerminalLogOutput { + fn parser(input: &str) -> IResult<&str, TerminalLogOutput> { + alt(( + map(preceded(tag("dir "), name_parser), |name| { + TerminalLogOutput::Dir(name) + }), + map( + tuple((nom_u32, tag(" "), name_parser)), + |(size, _, name)| TerminalLogOutput::File(size, name), + ), + ))(input) + } +} + +fn name_parser(input: &str) -> IResult<&str, String> { + map(not_line_ending, |s: &str| s.to_owned())(input) +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct DirTree { + name: String, + files: Vec<DirTreeFile>, + dirs: Vec<DirTree>, +} + +#[derive(Debug, PartialEq, Eq, Clone)] +struct DirTreeFile { + name: String, + size: u32, +} + +impl DirTree { + fn root() -> DirTree { + DirTree { + name: "/".into(), + files: Vec::new(), + dirs: Vec::new(), + } + } + + fn new(name: String) -> DirTree { + DirTree { + name, + files: Vec::new(), + dirs: Vec::new(), + } + } + + fn push_dir(&mut self, path: &[String], dir: DirTree) { + if path.is_empty() { + self.dirs.push(dir); + } else { + let subdir = self + .dirs + .iter_mut() + .find(|d| d.name == path[0]) + .expect("Subdir doesn't exist"); + subdir.push_dir(&path[1..], dir); + } + } + + fn push_file(&mut self, path: &[String], dir: DirTreeFile) { + if path.is_empty() { + self.files.push(dir); + } else { + let subdir = self + .dirs + .iter_mut() + .find(|d| d.name == path[0]) + .expect("Subdir doesn't exist"); + subdir.push_file(&path[1..], dir); + } + } + + fn size(&self) -> u32 { + self.files.iter().map(|f| f.size).sum::<u32>() + + self.dirs.iter().map(|f| f.size()).sum::<u32>() + } + + fn sum_sizes_below_threshhold(&self, threshhold: u32) -> u32 { + let self_size = self.size(); + let self_size_below_threshold = if self_size < threshhold { self_size } else { 0 }; + self_size_below_threshold + + self + .dirs + .iter() + .map(|f| f.sum_sizes_below_threshhold(threshhold)) + .sum::<u32>() + } + + fn find_min_size_greater_than(&self, threshhold: u32) -> Option<u32> { + let min_subdir = self + .dirs + .iter() + .filter_map(|d| d.find_min_size_greater_than(threshhold)) + .min(); + + match min_subdir { + Some(min) => Some(min), + None => { + let self_size = self.size(); + if self_size > threshhold { + Some(self_size) + } else { + None + } + } + } + } +} diff --git a/2022/src/bin/day_8.rs b/2022/src/bin/day_8.rs new file mode 100644 index 0000000..d044aa6 --- /dev/null +++ b/2022/src/bin/day_8.rs @@ -0,0 +1,231 @@ +use nom::{ + character::complete::{anychar, line_ending}, + combinator::map_res, + multi::{many1, separated_list1}, + IResult, +}; +use std::fs; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_8.txt")?; + let trees = TreeField::parser(&input).unwrap().1; + + dbg!(trees.count_visible_trees()); + dbg!(trees.find_best_scenic_score()); + + Ok(()) +} + +#[derive(Debug)] +struct TreeField { + width: usize, + height: usize, + tree_heights: Vec<Vec<i8>>, + row_height_fields: Vec<HeightField>, + column_height_fields: Vec<HeightField>, +} + +#[derive(Default, Debug)] +struct HeightField { + left_breaking_points: Vec<(usize, i8)>, + right_breaking_points: Vec<(usize, i8)>, +} + +enum TreeFieldError { + Empty, + NotRectangular, +} + +impl TreeField { + fn parser(input: &str) -> IResult<&str, TreeField> { + map_res( + separated_list1( + line_ending, + many1(map_res(anychar, |c: char| c.to_string().parse::<i8>())), + ), + TreeField::new, + )(input) + } + + fn new(tree_heights: Vec<Vec<i8>>) -> Result<TreeField, TreeFieldError> { + let height = tree_heights.len(); + if height == 0 { + return Result::Err(TreeFieldError::Empty); + } + + let width = tree_heights[0].len(); + let mut row_height_fields = Vec::new(); + for row in &tree_heights { + if row.len() != width { + return Result::Err(TreeFieldError::NotRectangular); + } + row_height_fields.push(HeightField::new(&row)); + } + + let mut column_height_fields = Vec::new(); + for column_i in 0..width { + let mut column = Vec::new(); + for row in &tree_heights { + column.push(row[column_i].clone()); + } + column_height_fields.push(HeightField::new(&column)); + } + + Ok(TreeField { + width, + height, + tree_heights, + row_height_fields, + column_height_fields, + }) + } + + fn tree_is_visible(&self, x: usize, y: usize) -> bool { + let tree_height = self.tree_heights[y][x]; + let (left_height, right_height) = self.row_height_fields[y].heights_at(x); + let (up_height, down_height) = self.column_height_fields[x].heights_at(y); + tree_height > left_height + || tree_height > right_height + || tree_height > up_height + || tree_height > down_height + } + + fn count_visible_trees(&self) -> usize { + let mut count = 0; + for y in 0..self.height { + for x in 0..self.width { + if self.tree_is_visible(x, y) { + count += 1; + } + } + } + count + } + + fn tree_scenic_score(&self, x: usize, y: usize) -> usize { + let tree_height = self.tree_heights[y][x]; + let (left_height, right_height) = self.row_height_fields[y].heights_at(x); + let left_score = if tree_height > left_height { + x + } else { + let mut count = 0; + let mut shift_x = x; + while shift_x > 0 { + count += 1; + shift_x -= 1; + let height = self.tree_heights[y][shift_x]; + if height >= tree_height { + break; + } + } + count + }; + let right_score = if tree_height > right_height { + self.width - 1 - x + } else { + let mut count = 0; + let mut shift_x = x; + while shift_x < self.width - 1 { + count += 1; + shift_x += 1; + let height = self.tree_heights[y][shift_x]; + if height >= tree_height { + break; + } + } + count + }; + + let (up_height, down_height) = self.column_height_fields[x].heights_at(y); + let up_score = if tree_height > up_height { + y + } else { + let mut count = 0; + let mut shift_y = y; + while shift_y > 0 { + count += 1; + shift_y -= 1; + let height = self.tree_heights[shift_y][x]; + if height >= tree_height { + break; + } + } + count + }; + let down_score = if tree_height > down_height { + self.height - 1 - y + } else { + let mut count = 0; + let mut shift_y = y; + while shift_y < self.height - 1 { + count += 1; + shift_y += 1; + let height = self.tree_heights[shift_y][x]; + if height >= tree_height { + break; + } + } + count + }; + + left_score * right_score * up_score * down_score + } + + fn find_best_scenic_score(&self) -> usize { + let mut max = 0; + for y in 0..self.height { + for x in 0..self.width { + let next = self.tree_scenic_score(x, y); + max = max.max(next); + } + } + max + } +} + +impl HeightField { + fn new(row: &[i8]) -> HeightField { + let mut left_breaking_points = Vec::new(); + let mut last_height = -1; + for (i, height) in row.iter().enumerate() { + if height > &last_height { + last_height = height.clone(); + left_breaking_points.push((i.clone(), height.clone())); + } + } + + let mut right_breaking_points = Vec::new(); + last_height = -1; + for (i, height) in row.iter().enumerate().rev() { + if height > &last_height { + last_height = height.clone(); + right_breaking_points.push((i.clone(), height.clone())); + } + } + + HeightField { + left_breaking_points, + right_breaking_points, + } + } + + fn heights_at(&self, i: usize) -> (i8, i8) { + let left = self + .left_breaking_points + .iter() + .filter(|(left_i, _)| left_i < &i) + .map(|(_, height)| height.clone()) + .last() + .unwrap_or(-1); + + let right = self + .right_breaking_points + .iter() + .filter(|(right_i, _)| right_i > &i) + .map(|(_, height)| height.clone()) + .last() + .unwrap_or(-1); + + (left, right) + } +} diff --git a/2022/src/bin/day_9.rs b/2022/src/bin/day_9.rs new file mode 100644 index 0000000..ccbb66a --- /dev/null +++ b/2022/src/bin/day_9.rs @@ -0,0 +1,134 @@ +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{i32, line_ending}, + combinator::{map, value}, + multi::separated_list1, + sequence::tuple, + IResult, +}; +use std::{collections::BTreeSet, fs}; + +fn main() -> Result<(), Box<dyn std::error::Error>> { + let input = fs::read_to_string("inputs/day_9.txt")?; + let movements = Movements::parser(&input).unwrap().1; + + let mut game_board_part_1 = GameBoard::new(2); + for instruction in &movements.0 { + game_board_part_1.step(instruction); + } + dbg!(game_board_part_1.tail_visited.len()); + + let mut game_board_part_2 = GameBoard::new(10); + for instruction in &movements.0 { + game_board_part_2.step(instruction); + } + dbg!(game_board_part_2.tail_visited.len()); + + Ok(()) +} + +#[derive(Debug)] +struct Movements(Vec<Instruction>); + +#[derive(Debug)] +struct Instruction { + direction: Direction, + distance: i32, +} + +#[derive(Debug, Clone, Copy)] +enum Direction { + Down, + Up, + Left, + Right, +} + +impl Movements { + fn parser(input: &str) -> IResult<&str, Self> { + map(separated_list1(line_ending, Instruction::parser), Movements)(input) + } +} + +impl Instruction { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple((Direction::parser, tag(" "), i32)), + |(direction, _, distance)| Instruction { + direction, + distance, + }, + )(input) + } +} + +impl Direction { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(Direction::Down, tag("D")), + value(Direction::Up, tag("U")), + value(Direction::Left, tag("L")), + value(Direction::Right, tag("R")), + ))(input) + } +} + +#[derive(Debug)] +struct GameBoard { + rope: Vec<Position>, + tail_visited: BTreeSet<Position>, +} + +#[derive(Default, Debug, PartialEq, Eq, PartialOrd, Ord, Clone)] +struct Position { + x: i32, + y: i32, +} + +impl GameBoard { + fn new(length: usize) -> GameBoard { + let mut tail_visited = BTreeSet::new(); + tail_visited.insert(Position::default()); + GameBoard { + rope: vec![Position::default(); length], + tail_visited, + } + } + + fn step(&mut self, instruction: &Instruction) { + for _ in 0..instruction.distance { + match instruction.direction { + Direction::Down => self.rope[0].y -= 1, + Direction::Up => self.rope[0].y += 1, + Direction::Left => self.rope[0].x -= 1, + Direction::Right => self.rope[0].x += 1, + }; + + for tail_i in 1..self.rope.len() { + let head_i = tail_i - 1; + let head = self.rope[head_i].clone(); + let tail = &mut self.rope[tail_i]; + + let tail_must_move = (head.x - tail.x).abs() > 1 || (head.y - tail.y).abs() > 1; + + if tail_must_move { + if head.x > tail.x { + tail.x += 1; + } else if head.x < tail.x { + tail.x -= 1; + } + + if head.y > tail.y { + tail.y += 1; + } else if head.y < tail.y { + tail.y -= 1; + } + } + } + + self.tail_visited + .insert(self.rope[self.rope.len() - 1].clone()); + } + } +} diff --git a/2022/src/lib.rs b/2022/src/lib.rs new file mode 100644 index 0000000..8b13789 --- /dev/null +++ b/2022/src/lib.rs @@ -0,0 +1 @@ + |