From ff064b6f13019b15346ff320a486d70b95d80b2a Mon Sep 17 00:00:00 2001 From: Guillermo Ramos Date: Fri, 6 Dec 2024 15:59:32 +0100 Subject: Each day is now a binary --- 2024_rust/src/bin/day1.rs | 49 ++++++++++ 2024_rust/src/bin/day2.rs | 69 ++++++++++++++ 2024_rust/src/bin/day3.rs | 37 ++++++++ 2024_rust/src/bin/day4.rs | 141 +++++++++++++++++++++++++++++ 2024_rust/src/bin/day5.rs | 224 ++++++++++++++++++++++++++++++++++++++++++++++ 2024_rust/src/bin/dayN.rs | 15 ++++ 2024_rust/src/day1.rs | 45 ---------- 2024_rust/src/day2.rs | 65 -------------- 2024_rust/src/day3.rs | 33 ------- 2024_rust/src/day4.rs | 137 ---------------------------- 2024_rust/src/day5.rs | 220 --------------------------------------------- 2024_rust/src/dayN.rs | 11 --- 2024_rust/src/lib.rs | 12 +++ 2024_rust/src/main.rs | 10 --- 14 files changed, 547 insertions(+), 521 deletions(-) create mode 100644 2024_rust/src/bin/day1.rs create mode 100644 2024_rust/src/bin/day2.rs create mode 100644 2024_rust/src/bin/day3.rs create mode 100644 2024_rust/src/bin/day4.rs create mode 100644 2024_rust/src/bin/day5.rs create mode 100644 2024_rust/src/bin/dayN.rs delete mode 100644 2024_rust/src/day1.rs delete mode 100644 2024_rust/src/day2.rs delete mode 100644 2024_rust/src/day3.rs delete mode 100644 2024_rust/src/day4.rs delete mode 100644 2024_rust/src/day5.rs delete mode 100644 2024_rust/src/dayN.rs create mode 100644 2024_rust/src/lib.rs delete mode 100644 2024_rust/src/main.rs (limited to '2024_rust/src') diff --git a/2024_rust/src/bin/day1.rs b/2024_rust/src/bin/day1.rs new file mode 100644 index 0000000..2e0f01d --- /dev/null +++ b/2024_rust/src/bin/day1.rs @@ -0,0 +1,49 @@ +fn p1(input: &str) -> String { + let mut left: Vec = vec![]; + let mut right: Vec = vec![]; + for line in input.lines() { + let mut fields = line.split_whitespace(); + let e = "Wrong file format"; + left.push(fields.next().expect(e).parse().expect(e)); + right.push(fields.next().expect(e).parse().expect(e)); + } + left.sort_unstable(); + right.sort_unstable(); + + let mut distance: u32 = 0; + for i in 0..left.len() { + let l = left[i]; + let r = right[i]; + distance += if l >= r { l - r } else { r - l }; + } + + distance.to_string() +} + +use std::collections::HashMap; + +fn p2(input: &str) -> String { + let mut left: Vec = vec![]; + let mut right: HashMap = HashMap::new(); + for line in input.lines() { + let mut fields = line.split_whitespace(); + let e = "Wrong file format"; + left.push(fields.next().expect(e).parse().expect(e)); + let r: u32 = fields.next().expect(e).parse().expect(e); + match right.get(&r) { + None => right.insert(r, 1), + Some(v) => right.insert(r, v + 1), + }; + } + + let mut distance: u32 = 0; + for l in left { + distance += l * right.get(&l).unwrap_or(&0); + } + + distance.to_string() +} + +fn main() { + aoc2024::run_day("1", p1, p2); +} diff --git a/2024_rust/src/bin/day2.rs b/2024_rust/src/bin/day2.rs new file mode 100644 index 0000000..92d288f --- /dev/null +++ b/2024_rust/src/bin/day2.rs @@ -0,0 +1,69 @@ +#[derive(PartialEq, Clone, Copy)] +enum Direction { + Up, + Down, + Unknown, +} +use Direction::*; + +fn is_safe(levels: &[u32]) -> bool { + let mut direction = Unknown; + for i in 0..levels.len() - 1 { + let [x, y] = levels[i..=i + 1] else { + unreachable!() + }; + let (diff, d) = if x > y { (x - y, Down) } else { (y - x, Up) }; + if direction == Unknown { + direction = d; + } + if diff == 0 || diff > 3 || direction != d { + return false; + } + } + return true; +} + +fn p1(input: &str) -> String { + let mut total = 0; + for report in input.lines() { + let levels: Vec = report + .split_whitespace() + .map(|l| l.parse().unwrap()) + .collect(); + if is_safe(&levels) { + total += 1; + } + } + + total.to_string() +} + +fn is_safe_with_dampener(levels: &[u32]) -> bool { + for i in 0..levels.len() { + let mut levels_without_i: Vec = levels.to_vec(); + levels_without_i.remove(i); + if is_safe(&levels_without_i) { + return true; + } + } + return false; +} + +fn p2(input: &str) -> String { + let mut total = 0; + for report in input.lines() { + let levels: Vec = report + .split_whitespace() + .map(|l| l.parse().unwrap()) + .collect(); + if is_safe(&levels) || is_safe_with_dampener(&levels) { + total += 1; + } + } + + total.to_string() +} + +fn main() { + aoc2024::run_day("2", p1, p2); +} diff --git a/2024_rust/src/bin/day3.rs b/2024_rust/src/bin/day3.rs new file mode 100644 index 0000000..1eedefe --- /dev/null +++ b/2024_rust/src/bin/day3.rs @@ -0,0 +1,37 @@ +use regex::Regex; + +fn p1(input: &str) -> String { + let re = Regex::new(r"mul\(([0-9]{1,3}),([0-9]{1,3})\)").unwrap(); + + let mut result: u32 = 0; + for (_, [x, y]) in re.captures_iter(input).map(|cs| cs.extract()) { + result += x.parse::().unwrap() * y.parse::().unwrap(); + } + + result.to_string() +} + +fn p2(input: &str) -> String { + let re = Regex::new(r"do\(\)|don't\(\)|mul\(([0-9]{1,3}),([0-9]{1,3})\)").unwrap(); + + let mut doing = true; + let mut result: u32 = 0; + for cs in re.captures_iter(input) { + let mut it = cs.iter().flatten().map(|m| m.as_str()); + match it.next().unwrap() { + "do()" => doing = true, + "don't()" => doing = false, + mul if doing && mul.starts_with("mul") => { + let mut next = || it.next().unwrap().parse::().unwrap(); + result += next() * next(); + } + _ => (), + } + } + + result.to_string() +} + +fn main() { + aoc2024::run_day("3", p1, p2); +} diff --git a/2024_rust/src/bin/day4.rs b/2024_rust/src/bin/day4.rs new file mode 100644 index 0000000..7eb7b7a --- /dev/null +++ b/2024_rust/src/bin/day4.rs @@ -0,0 +1,141 @@ +const XMAS: &str = "XMAS"; +const MAS: &str = "MAS"; + +type Position = (usize, usize); +type Row = Vec; +type Rows = Vec; +type Move = (Position, (usize, isize)); + +struct Matrix { + chars: Vec>, + limit: Position, +} + +impl Matrix { + fn new(text: &str) -> Self { + let chars: Vec> = text.lines().map(|row| row.chars().collect()).collect(); + let limit = (chars.len(), chars[0].len()); + Self { chars, limit } + } + + fn check_iter<'a, I>(&self, it: I, needle: &str) -> bool + where + I: Iterator, + { + for (c, (i, j)) in needle.chars().zip(it) { + if self.chars[*i][*j] != c { + return false; + } + } + + true + } + + fn check_row(&self, row: &Row, needle: &str) -> bool { + self.check_iter(row.iter(), needle) || self.check_iter(row.iter().rev(), needle) + } +} + +struct Square<'a> { + pos: Position, + size: usize, + matrix: &'a Matrix, +} + +impl Square<'_> { + fn rows(&self, moves: M) -> Rows + where + M: Fn(&Square) -> Vec, + { + let mut rs: Rows = vec![]; + + // Horizontal / vertical / diagonal + for (p0, (di, dj)) in moves(self) { + // Bounds check + if p0.0 + di * self.size > self.matrix.limit.0 + || (dj > 0 && offplus(p0.1, dj * self.size as isize) > self.matrix.limit.1) + || p0.1 >= self.matrix.limit.1 + { + continue; + } + + let mut p_acc = p0; + let mut row: Row = vec![]; + for _idx in 0..self.size { + row.push(p_acc); + p_acc = (p_acc.0 + di, offplus(p_acc.1, dj)); + } + rs.push(row); + } + + rs + } +} + +fn offplus(x: usize, y: isize) -> usize { + (x as isize + y) as usize +} + +fn moves_xmas(Square { pos, size, .. }: &Square) -> Vec { + let v = vec![ + (*pos, (0, 1)), // diag from pos, top-down and left-to-right + (*pos, (1, 0)), // diag from pos, top-down and left-to-right + (*pos, (1, 1)), // diag from pos, top-down and left-to-right + ((pos.0, pos.1 + size - 1), (1, -1)), // the other diag, top-down and right-to-left + ]; + v +} + +fn p1(input: &str) -> String { + let matrix: Matrix = Matrix::new(input); + let mut result = 0; + + for i in 0..matrix.limit.0 { + for j in 0..matrix.limit.1 { + let sq = Square { + pos: (i, j), + size: XMAS.len(), + matrix: &matrix, + }; + for row in sq.rows(moves_xmas) { + if matrix.check_row(&row, XMAS) { + result += 1; + } + } + } + } + + result.to_string() +} + +fn moves_mas(Square { pos, size, .. }: &Square) -> Vec { + let v = vec![ + (*pos, (1, 1)), // diag from pos, top-down and left-to-right + ((pos.0, pos.1 + size - 1), (1, -1)), // the other diag, top-down and right-to-left + ]; + v +} + +fn p2(input: &str) -> String { + let matrix: Matrix = Matrix::new(input); + let mut result = 0; + + for i in 0..=matrix.limit.0 - MAS.len() { + for j in 0..=matrix.limit.1 - MAS.len() { + let sq = Square { + pos: (i, j), + size: MAS.len(), + matrix: &matrix, + }; + if sq.rows(moves_mas).iter().all(|r| matrix.check_row(r, MAS)) { + result += 1; + } + } + } + + result.to_string() +} + +fn main() { + aoc2024::run_day("4", p1, p2); +} diff --git a/2024_rust/src/bin/day5.rs b/2024_rust/src/bin/day5.rs new file mode 100644 index 0000000..fe22295 --- /dev/null +++ b/2024_rust/src/bin/day5.rs @@ -0,0 +1,224 @@ +use regex::Regex; +use std::collections::{HashMap, HashSet}; +use std::str::FromStr; + +type Page = u32; + +#[derive(Debug, Clone)] +struct Rule { + before: Page, + after: Page, +} + +#[derive(Debug)] +enum ParseError { + ParseError, +} + +impl FromStr for Rule { + type Err = ParseError; + fn from_str(s: &str) -> Result { + let Some(cs) = Regex::new("^([0-9]+)\\|([0-9]+)$").unwrap().captures(s) else { + return Err(ParseError::ParseError); + }; + let (_full, [bf, af]) = cs.extract(); + Ok(Rule { + before: bf.parse().unwrap(), + after: af.parse().unwrap(), + }) + } +} + +#[derive(Debug)] +struct RuleStatus { + previous: HashMap>, + invalid: HashSet, +} + +impl RuleStatus { + fn new(rules: &Vec) -> Self { + let mut previous = HashMap::new(); + for &Rule { before, after } in rules.iter() { + match previous.get_mut(&after) { + None => { + let mut set = HashSet::new(); + set.insert(before); + previous.insert(after, set); + } + Some(set) => { + set.insert(before); + } + } + } + RuleStatus { + previous, + invalid: HashSet::new(), + } + } + + fn step(&mut self, page: &Page) -> bool { + let RuleStatus { previous, invalid } = self; + if invalid.contains(page) { + return false; + } + if let Some(prev) = previous.get(page) { + for p in prev.iter() { + invalid.insert(*p); + } + } + true + } +} + +type Update = Vec; + +fn update_from_str(s: &str) -> Update { + Regex::new("([0-9]+)") + .unwrap() + .find_iter(s) + .map(|s| s.as_str().parse().unwrap()) + .collect() +} + +fn is_update_valid(update: &Update, rules: &Vec) -> bool { + let mut status = RuleStatus::new(&rules); + for page in update.iter() { + if !status.step(page) { + return false; + } + } + true +} + +fn middle_page(update: &Update) -> Page { + update[update.len() / 2] +} + +#[derive(Debug)] +struct Input { + rules: Vec, + updates: Vec, +} + +impl FromStr for Input { + type Err = ParseError; + fn from_str(s: &str) -> Result { + let mut lines = s.lines(); + + let mut input = Input { + rules: vec![], + updates: vec![], + }; + + // Read rules + while let Some(l) = lines.next() { + if l == "" { + break; + } + input.rules.push(Rule::from_str(l).unwrap()); + } + + // Read updates + while let Some(l) = lines.next() { + input.updates.push(update_from_str(l)); + } + + Ok(input) + } +} + +fn sum_valid_updates(Input { rules, updates }: &Input) -> u32 { + updates + .iter() + .filter(|u| is_update_valid(u, &rules)) + .map(|u| middle_page(u)) + .sum() +} + +fn p1(input: &str) -> String { + let input = Input::from_str(input).unwrap(); + sum_valid_updates(&input).to_string() +} + +// Remove useless rules for this particular update +fn filter_rules(rules: &Vec, update: &Update) -> Vec { + let updated: HashSet<&Page> = update.iter().collect(); + rules + .iter() + .cloned() + .filter(|r| updated.contains(&r.before)) + .collect() +} + +fn sort_rules(rules: &Vec) -> Vec { + let mut sorted: Vec = vec![]; + let mut afters: HashMap = HashMap::new(); + for a in rules.iter().map(|r| r.after) { + *afters.entry(a).or_default() += 1; + } + + // Allocate new "droppable" rules by wrapping the originals into Options + let mut rules: Vec> = rules.iter().map(|r| Some(r)).collect(); + while rules.iter().any(|x| x.is_some()) { + for rule in rules.iter_mut() { + let Some(r) = *rule else { continue }; + if let None = afters.get(&r.before) { + sorted.push(r.clone()); + match afters.get_mut(&r.after) { + None => { + panic!("This should not happen"); + } + Some(1) => { + afters.remove(&r.after); + } + Some(x) => { + *x -= 1; + } + }; + *rule = None; + } + } + } + + sorted +} + +fn update_reorder(update: &Update, rules: &Vec) -> Option { + let filtered_rules = filter_rules(rules, update); + let sorted_rules = sort_rules(&filtered_rules); + let mut result: Update = vec![]; + let mut pages: HashSet = update.iter().cloned().collect(); + for Rule { before, .. } in sorted_rules.iter() { + if pages.contains(before) { + result.push(*before); + pages.remove(before); + } + } + // Add unrestricted pages at the end + for &p in pages.iter() { + result.push(p); + } + if is_update_valid(&result, &sorted_rules) { + Some(result) + } else { + None + } +} + +fn sum_reordered_updates(Input { rules, updates }: &Input) -> u32 { + updates + .iter() + .filter(|u| !is_update_valid(u, &rules)) // drop valid updates + .filter_map(|u| update_reorder(u, &rules)) // reorder updates + .map(|u| middle_page(&u)) + .sum() +} + +fn p2(input: &str) -> String { + let input = Input::from_str(input).unwrap(); + sum_reordered_updates(&input).to_string() +} + +fn main() { + aoc2024::run_day("5", p1, p2); +} diff --git a/2024_rust/src/bin/dayN.rs b/2024_rust/src/bin/dayN.rs new file mode 100644 index 0000000..cdaa061 --- /dev/null +++ b/2024_rust/src/bin/dayN.rs @@ -0,0 +1,15 @@ +fn p1(_input: &str) -> String { + let result = "TODO"; + + result.to_string() +} + +fn p2(_input: &str) -> String { + let result = "TODO"; + + result.to_string() +} + +fn main() { + aoc2024::run_day("N", p1, p2); +} diff --git a/2024_rust/src/day1.rs b/2024_rust/src/day1.rs deleted file mode 100644 index 0b6c13d..0000000 --- a/2024_rust/src/day1.rs +++ /dev/null @@ -1,45 +0,0 @@ -pub fn p1(input: &str) -> String { - let mut left: Vec = vec![]; - let mut right: Vec = vec![]; - for line in input.lines() { - let mut fields = line.split_whitespace(); - let e = "Wrong file format"; - left.push(fields.next().expect(e).parse().expect(e)); - right.push(fields.next().expect(e).parse().expect(e)); - } - left.sort_unstable(); - right.sort_unstable(); - - let mut distance: u32 = 0; - for i in 0..left.len() { - let l = left[i]; - let r = right[i]; - distance += if l >= r { l - r } else { r - l }; - } - - distance.to_string() -} - -use std::collections::HashMap; - -pub fn p2(input: &str) -> String { - let mut left: Vec = vec![]; - let mut right: HashMap = HashMap::new(); - for line in input.lines() { - let mut fields = line.split_whitespace(); - let e = "Wrong file format"; - left.push(fields.next().expect(e).parse().expect(e)); - let r: u32 = fields.next().expect(e).parse().expect(e); - match right.get(&r) { - None => right.insert(r, 1), - Some(v) => right.insert(r, v + 1), - }; - } - - let mut distance: u32 = 0; - for l in left { - distance += l * right.get(&l).unwrap_or(&0); - } - - distance.to_string() -} diff --git a/2024_rust/src/day2.rs b/2024_rust/src/day2.rs deleted file mode 100644 index f809141..0000000 --- a/2024_rust/src/day2.rs +++ /dev/null @@ -1,65 +0,0 @@ -#[derive(PartialEq, Clone, Copy)] -enum Direction { - Up, - Down, - Unknown, -} -use Direction::*; - -fn is_safe(levels: &[u32]) -> bool { - let mut direction = Unknown; - for i in 0..levels.len() - 1 { - let [x, y] = levels[i..=i + 1] else { - unreachable!() - }; - let (diff, d) = if x > y { (x - y, Down) } else { (y - x, Up) }; - if direction == Unknown { - direction = d; - } - if diff == 0 || diff > 3 || direction != d { - return false; - } - } - return true; -} - -pub fn p1(input: &str) -> String { - let mut total = 0; - for report in input.lines() { - let levels: Vec = report - .split_whitespace() - .map(|l| l.parse().unwrap()) - .collect(); - if is_safe(&levels) { - total += 1; - } - } - - total.to_string() -} - -fn is_safe_with_dampener(levels: &[u32]) -> bool { - for i in 0..levels.len() { - let mut levels_without_i: Vec = levels.to_vec(); - levels_without_i.remove(i); - if is_safe(&levels_without_i) { - return true; - } - } - return false; -} - -pub fn p2(input: &str) -> String { - let mut total = 0; - for report in input.lines() { - let levels: Vec = report - .split_whitespace() - .map(|l| l.parse().unwrap()) - .collect(); - if is_safe(&levels) || is_safe_with_dampener(&levels) { - total += 1; - } - } - - total.to_string() -} diff --git a/2024_rust/src/day3.rs b/2024_rust/src/day3.rs deleted file mode 100644 index cdcd62a..0000000 --- a/2024_rust/src/day3.rs +++ /dev/null @@ -1,33 +0,0 @@ -use regex::Regex; - -pub fn p1(input: &str) -> String { - let re = Regex::new(r"mul\(([0-9]{1,3}),([0-9]{1,3})\)").unwrap(); - - let mut result: u32 = 0; - for (_, [x, y]) in re.captures_iter(input).map(|cs| cs.extract()) { - result += x.parse::().unwrap() * y.parse::().unwrap(); - } - - result.to_string() -} - -pub fn p2(input: &str) -> String { - let re = Regex::new(r"do\(\)|don't\(\)|mul\(([0-9]{1,3}),([0-9]{1,3})\)").unwrap(); - - let mut doing = true; - let mut result: u32 = 0; - for cs in re.captures_iter(input) { - let mut it = cs.iter().flatten().map(|m| m.as_str()); - match it.next().unwrap() { - "do()" => doing = true, - "don't()" => doing = false, - mul if doing && mul.starts_with("mul") => { - let mut next = || it.next().unwrap().parse::().unwrap(); - result += next() * next(); - } - _ => (), - } - } - - result.to_string() -} diff --git a/2024_rust/src/day4.rs b/2024_rust/src/day4.rs deleted file mode 100644 index 448fe19..0000000 --- a/2024_rust/src/day4.rs +++ /dev/null @@ -1,137 +0,0 @@ -const XMAS: &str = "XMAS"; -const MAS: &str = "MAS"; - -type Position = (usize, usize); -type Row = Vec; -type Rows = Vec; -type Move = (Position, (usize, isize)); - -struct Matrix { - chars: Vec>, - limit: Position, -} - -impl Matrix { - fn new(text: &str) -> Self { - let chars: Vec> = text.lines().map(|row| row.chars().collect()).collect(); - let limit = (chars.len(), chars[0].len()); - Self { chars, limit } - } - - fn check_iter<'a, I>(&self, it: I, needle: &str) -> bool - where - I: Iterator, - { - for (c, (i, j)) in needle.chars().zip(it) { - if self.chars[*i][*j] != c { - return false; - } - } - - true - } - - fn check_row(&self, row: &Row, needle: &str) -> bool { - self.check_iter(row.iter(), needle) || self.check_iter(row.iter().rev(), needle) - } -} - -struct Square<'a> { - pos: Position, - size: usize, - matrix: &'a Matrix, -} - -impl Square<'_> { - fn rows(&self, moves: M) -> Rows - where - M: Fn(&Square) -> Vec, - { - let mut rs: Rows = vec![]; - - // Horizontal / vertical / diagonal - for (p0, (di, dj)) in moves(self) { - // Bounds check - if p0.0 + di * self.size > self.matrix.limit.0 - || (dj > 0 && offplus(p0.1, dj * self.size as isize) > self.matrix.limit.1) - || p0.1 >= self.matrix.limit.1 - { - continue; - } - - let mut p_acc = p0; - let mut row: Row = vec![]; - for _idx in 0..self.size { - row.push(p_acc); - p_acc = (p_acc.0 + di, offplus(p_acc.1, dj)); - } - rs.push(row); - } - - rs - } -} - -fn offplus(x: usize, y: isize) -> usize { - (x as isize + y) as usize -} - -fn moves_xmas(Square { pos, size, .. }: &Square) -> Vec { - let v = vec![ - (*pos, (0, 1)), // diag from pos, top-down and left-to-right - (*pos, (1, 0)), // diag from pos, top-down and left-to-right - (*pos, (1, 1)), // diag from pos, top-down and left-to-right - ((pos.0, pos.1 + size - 1), (1, -1)), // the other diag, top-down and right-to-left - ]; - v -} - -pub fn p1(input: &str) -> String { - let matrix: Matrix = Matrix::new(input); - let mut result = 0; - - for i in 0..matrix.limit.0 { - for j in 0..matrix.limit.1 { - let sq = Square { - pos: (i, j), - size: XMAS.len(), - matrix: &matrix, - }; - for row in sq.rows(moves_xmas) { - if matrix.check_row(&row, XMAS) { - result += 1; - } - } - } - } - - result.to_string() -} - -fn moves_mas(Square { pos, size, .. }: &Square) -> Vec { - let v = vec![ - (*pos, (1, 1)), // diag from pos, top-down and left-to-right - ((pos.0, pos.1 + size - 1), (1, -1)), // the other diag, top-down and right-to-left - ]; - v -} - -pub fn p2(input: &str) -> String { - let matrix: Matrix = Matrix::new(input); - let mut result = 0; - - for i in 0..=matrix.limit.0 - MAS.len() { - for j in 0..=matrix.limit.1 - MAS.len() { - let sq = Square { - pos: (i, j), - size: MAS.len(), - matrix: &matrix, - }; - if sq.rows(moves_mas).iter().all(|r| matrix.check_row(r, MAS)) { - result += 1; - } - } - } - - result.to_string() -} diff --git a/2024_rust/src/day5.rs b/2024_rust/src/day5.rs deleted file mode 100644 index e13f8e5..0000000 --- a/2024_rust/src/day5.rs +++ /dev/null @@ -1,220 +0,0 @@ -use regex::Regex; -use std::collections::{HashMap, HashSet}; -use std::str::FromStr; - -type Page = u32; - -#[derive(Debug, Clone)] -struct Rule { - before: Page, - after: Page, -} - -#[derive(Debug)] -enum ParseError { - ParseError, -} - -impl FromStr for Rule { - type Err = ParseError; - fn from_str(s: &str) -> Result { - let Some(cs) = Regex::new("^([0-9]+)\\|([0-9]+)$").unwrap().captures(s) else { - return Err(ParseError::ParseError); - }; - let (_full, [bf, af]) = cs.extract(); - Ok(Rule { - before: bf.parse().unwrap(), - after: af.parse().unwrap(), - }) - } -} - -#[derive(Debug)] -struct RuleStatus { - previous: HashMap>, - invalid: HashSet, -} - -impl RuleStatus { - fn new(rules: &Vec) -> Self { - let mut previous = HashMap::new(); - for &Rule { before, after } in rules.iter() { - match previous.get_mut(&after) { - None => { - let mut set = HashSet::new(); - set.insert(before); - previous.insert(after, set); - } - Some(set) => { - set.insert(before); - } - } - } - RuleStatus { - previous, - invalid: HashSet::new(), - } - } - - fn step(&mut self, page: &Page) -> bool { - let RuleStatus { previous, invalid } = self; - if invalid.contains(page) { - return false; - } - if let Some(prev) = previous.get(page) { - for p in prev.iter() { - invalid.insert(*p); - } - } - true - } -} - -type Update = Vec; - -fn update_from_str(s: &str) -> Update { - Regex::new("([0-9]+)") - .unwrap() - .find_iter(s) - .map(|s| s.as_str().parse().unwrap()) - .collect() -} - -fn is_update_valid(update: &Update, rules: &Vec) -> bool { - let mut status = RuleStatus::new(&rules); - for page in update.iter() { - if !status.step(page) { - return false; - } - } - true -} - -fn middle_page(update: &Update) -> Page { - update[update.len() / 2] -} - -#[derive(Debug)] -struct Input { - rules: Vec, - updates: Vec, -} - -impl FromStr for Input { - type Err = ParseError; - fn from_str(s: &str) -> Result { - let mut lines = s.lines(); - - let mut input = Input { - rules: vec![], - updates: vec![], - }; - - // Read rules - while let Some(l) = lines.next() { - if l == "" { - break; - } - input.rules.push(Rule::from_str(l).unwrap()); - } - - // Read updates - while let Some(l) = lines.next() { - input.updates.push(update_from_str(l)); - } - - Ok(input) - } -} - -fn sum_valid_updates(Input { rules, updates }: &Input) -> u32 { - updates - .iter() - .filter(|u| is_update_valid(u, &rules)) - .map(|u| middle_page(u)) - .sum() -} - -pub fn p1(input: &str) -> String { - let input = Input::from_str(input).unwrap(); - sum_valid_updates(&input).to_string() -} - -// Remove useless rules for this particular update -fn filter_rules(rules: &Vec, update: &Update) -> Vec { - let updated: HashSet<&Page> = update.iter().collect(); - rules - .iter() - .cloned() - .filter(|r| updated.contains(&r.before)) - .collect() -} - -fn sort_rules(rules: &Vec) -> Vec { - let mut sorted: Vec = vec![]; - let mut afters: HashMap = HashMap::new(); - for a in rules.iter().map(|r| r.after) { - *afters.entry(a).or_default() += 1; - } - - // Allocate new "droppable" rules by wrapping the originals into Options - let mut rules: Vec> = rules.iter().map(|r| Some(r)).collect(); - while rules.iter().any(|x| x.is_some()) { - for rule in rules.iter_mut() { - let Some(r) = *rule else { continue }; - if let None = afters.get(&r.before) { - sorted.push(r.clone()); - match afters.get_mut(&r.after) { - None => { - panic!("This should not happen"); - } - Some(1) => { - afters.remove(&r.after); - } - Some(x) => { - *x -= 1; - } - }; - *rule = None; - } - } - } - - sorted -} - -fn update_reorder(update: &Update, rules: &Vec) -> Option { - let filtered_rules = filter_rules(rules, update); - let sorted_rules = sort_rules(&filtered_rules); - let mut result: Update = vec![]; - let mut pages: HashSet = update.iter().cloned().collect(); - for Rule { before, .. } in sorted_rules.iter() { - if pages.contains(before) { - result.push(*before); - pages.remove(before); - } - } - // Add unrestricted pages at the end - for &p in pages.iter() { - result.push(p); - } - if is_update_valid(&result, &sorted_rules) { - Some(result) - } else { - None - } -} - -fn sum_reordered_updates(Input { rules, updates }: &Input) -> u32 { - updates - .iter() - .filter(|u| !is_update_valid(u, &rules)) // drop valid updates - .filter_map(|u| update_reorder(u, &rules)) // reorder updates - .map(|u| middle_page(&u)) - .sum() -} - -pub fn p2(input: &str) -> String { - let input = Input::from_str(input).unwrap(); - sum_reordered_updates(&input).to_string() -} diff --git a/2024_rust/src/dayN.rs b/2024_rust/src/dayN.rs deleted file mode 100644 index d325291..0000000 --- a/2024_rust/src/dayN.rs +++ /dev/null @@ -1,11 +0,0 @@ -pub fn p1(input: &str) -> String { - let result = "TODO"; - - result.to_string() -} - -pub fn p2(input: &str) -> String { - let result = "TODO"; - - result.to_string() -} diff --git a/2024_rust/src/lib.rs b/2024_rust/src/lib.rs new file mode 100644 index 0000000..f8a84d6 --- /dev/null +++ b/2024_rust/src/lib.rs @@ -0,0 +1,12 @@ +pub fn run_day(day: &str, p1: S1, p2: S2) +where + S1: FnOnce(&str) -> String, + S2: FnOnce(&str) -> String, +{ + let input_file = format!("inputs/{day}"); + let input = std::fs::read_to_string(input_file).unwrap(); + + println!("==== DAY {day}"); + println!("Result (P1): {}", p1(&input)); + println!("Result (P2): {}", p2(&input)); +} diff --git a/2024_rust/src/main.rs b/2024_rust/src/main.rs deleted file mode 100644 index 4c5e7fd..0000000 --- a/2024_rust/src/main.rs +++ /dev/null @@ -1,10 +0,0 @@ -mod day5; -use day5 as current_day; -const INPUT_FILE: &str = "inputs/5"; - -fn main() { - let input = std::fs::read_to_string(INPUT_FILE).unwrap(); - - println!("Result (P1): {}", current_day::p1(&input)); - println!("Result (P2): {}", current_day::p2(&input)); -} -- cgit v1.2.3