From 11b2fd042a72eb93fb0741e2dec7d0ec035178f8 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Wed, 8 Dec 2021 10:05:20 +0100 Subject: Yes, I totally didn't forget to commit --- src/day_5.rs | 125 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/day_6.rs | 55 ++++++++++++++++++++++++++ src/day_7.rs | 58 +++++++++++++++++++++++++++ src/main.rs | 6 +++ 4 files changed, 244 insertions(+) create mode 100644 src/day_5.rs create mode 100644 src/day_6.rs create mode 100644 src/day_7.rs diff --git a/src/day_5.rs b/src/day_5.rs new file mode 100644 index 0000000..acd2ac1 --- /dev/null +++ b/src/day_5.rs @@ -0,0 +1,125 @@ +use std::cmp; +use std::convert::Infallible; +use std::str::FromStr; + +const SIZE: usize = 1000; + +#[derive(Debug)] +struct Line +{ + pub a: (u32, u32), + pub b: (u32, u32), +} + +fn part1(input: &[Line]) +{ + let mut map = [[0; SIZE]; SIZE]; + for line in input { + line.cast_vh(&mut map); + } + + let num_intersections = map.iter().flatten().filter(|&n| *n >= 2).count(); + println!("Solution part 1: {}", num_intersections); +} + +fn part2(input: &[Line]) +{ + let mut map = [[0; SIZE]; SIZE]; + for line in input { + line.cast_vh(&mut map); + line.cast_diag(&mut map); + } + + let num_intersections = map.iter().flatten().filter(|&n| *n >= 2).count(); + println!("Solution part 2: {}", num_intersections); +} + +pub fn run(input: Vec) +{ + let lines: Vec = input.iter().map(|s| Line::from_str(s).unwrap()).collect(); + + part1(&lines); + part2(&lines); +} + +impl Line +{ + pub fn is_horizontal(&self) -> bool { self.a.1 == self.b.1 } + + pub fn is_vertical(&self) -> bool { self.a.0 == self.b.0 } + + pub fn cast_vh(&self, onto: &mut [[u8; SIZE]]) + { + if self.is_horizontal() { + let start = cmp::min(self.a.0, self.b.0); + let end = cmp::max(self.a.0, self.b.0); + for x in start..=end { + onto[self.a.1 as usize][x as usize] += 1; + } + } + else if self.is_vertical() { + let start = cmp::min(self.a.1, self.b.1); + let end = cmp::max(self.a.1, self.b.1); + for y in start..=end { + onto[y as usize][self.a.0 as usize] += 1; + } + } + } + + pub fn cast_diag(&self, onto: &mut [[u8; SIZE]]) + { + if self.is_horizontal() || self.is_vertical() { + return; + } + + // We know all other lines are 45 deg + let mut dir = (0, 0); + let len: i32 = if self.a.0 < self.b.0 { + dir.0 = 1; + (self.b.0 - self.a.0) as i32 + } + else if self.a.0 > self.b.0 { + dir.0 = -1; + (self.a.0 - self.b.0) as i32 + } + else { + panic!("line is unexpectedly vertical!"); + }; + if self.a.1 < self.b.1 { + dir.1 = 1; + } + else if self.a.1 > self.b.1 { + dir.1 = -1; + } + else { + panic!("line is unexpectedly horizontal!"); + } + + for i in 0..=len { + onto[(self.a.1 as i32 + (i * dir.1)) as usize] + [(self.a.0 as i32 + (i * dir.0)) as usize] += 1; + } + } +} + +impl FromStr for Line +{ + type Err = Infallible; + + fn from_str(s: &str) -> Result + { + let parse_point = |s: &str| { + let nums: Vec = s.split(',').map(|s| s.parse().unwrap()).collect(); + assert_eq!(nums.len(), 2); + (nums[0], nums[1]) + }; + + let points: Vec<(u32, u32)> = s.split(" -> ").map(|s| parse_point(s)).collect(); + assert_eq!(points.len(), 2); + + Ok(Line { + a: points[0], + b: points[1], + }) + } +} diff --git a/src/day_6.rs b/src/day_6.rs new file mode 100644 index 0000000..c9d7d86 --- /dev/null +++ b/src/day_6.rs @@ -0,0 +1,55 @@ +#[derive(Copy, Clone, Debug)] +struct Fish(u8); + +fn simulate(swarm: &[Fish], days: usize) -> usize +{ + let mut new_count = [0; 2]; + let mut count = [0; 7]; + for fish in swarm { + count[fish.0 as usize] += 1; + } + + let mut day = 0; + let mut birth = 0; + for i in 0..days { + let today = count[day] + new_count[birth]; + new_count[birth] = count[day]; + count[day] = today; + day = (day + 1) % 7; + birth = (birth + 1) % 2; + } + + new_count.into_iter().sum::() + count.into_iter().sum::() +} + +fn part1(swarm: &[Fish]) +{ + println!("Solution to part 1: {}", simulate(swarm, 80)); +} + +fn part2(swarm: &[Fish]) +{ + println!("Solution to part 2: {}", simulate(swarm, 256)); +} + +pub fn run(input: Vec) +{ + let initial_swarm: Vec = input + .iter() + .map(|s| s.split(',').map(|s| Fish::new(s.parse().unwrap()))) + .flatten() + .collect(); + + part1(&initial_swarm); + part2(&initial_swarm); +} + +impl Fish +{ + pub fn new(timer: u8) -> Self { Self(timer) } +} + +impl Default for Fish +{ + fn default() -> Self { Self(8) } +} diff --git a/src/day_7.rs b/src/day_7.rs new file mode 100644 index 0000000..e14512a --- /dev/null +++ b/src/day_7.rs @@ -0,0 +1,58 @@ +use std::cmp; + +fn abs_diff(a: u32, b: u32) -> u32 { cmp::max(a, b) - cmp::min(a, b) } + +fn fuel_required_constant(positions: &[u32], destination: u32) -> u32 +{ + positions.iter().fold(0, |fuel_total, pos| { + fuel_total + abs_diff(*pos, destination) + }) +} + +fn fuel_required_linear(positions: &[u32], destination: u32) -> u32 +{ + let fuel_required = |pos, dest| { + let distance = abs_diff(pos, dest); + // Get total fuel cost by adding all integers until distance on top of each + // other + (distance * (distance + 1)) / 2 + }; + + positions.iter().fold(0, |fuel_total, pos| { + fuel_total + fuel_required(*pos, destination) + }) +} + +fn part1(positions: &[u32]) +{ + // Stupid approach: Try all positions out + let mut min_required = fuel_required_constant(positions, 0); + for pos in 1..positions.len() { + min_required = cmp::min(fuel_required_constant(positions, pos as u32), min_required); + } + + println!("Solution to part 1: {}", min_required); +} + +fn part2(positions: &[u32]) +{ + // Stupid approach: Try all positions out + let mut min_required = fuel_required_linear(positions, 0); + for pos in 1..positions.len() { + min_required = cmp::min(fuel_required_linear(positions, pos as u32), min_required); + } + + println!("Solution to part 2: {}", min_required); +} + +pub fn run(input: Vec) +{ + let positions: Vec = input + .iter() + .map(|s| s.split(',').map(|s| s.parse().unwrap())) + .flatten() + .collect(); + + part1(&positions); + part2(&positions); +} diff --git a/src/main.rs b/src/main.rs index dcb7762..57d56b6 100644 --- a/src/main.rs +++ b/src/main.rs @@ -2,6 +2,9 @@ mod day_1; mod day_2; mod day_3; mod day_4; +mod day_5; +mod day_6; +mod day_7; use std::fs::File; use std::io::{BufRead, BufReader}; @@ -32,6 +35,9 @@ fn run(day: u8, input: Vec) 2 => day_2::run(input), 3 => day_3::run(input), 4 => day_4::run(input), + 5 => day_5::run(input), + 6 => day_6::run(input), + 7 => day_7::run(input), o => panic!("Day {} is not implemented (yet)", o), } } -- cgit v1.2.3-70-g09d2