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