From cfd9b4f2ad1a09bedf7f764f84448a61faab54a3 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:26:02 +0200 Subject: Refile for merging repos --- 2018/src/bin/day_1.rs | 32 ++++++ 2018/src/bin/day_10.rs | 82 +++++++++++++++ 2018/src/bin/day_11.rs | 66 ++++++++++++ 2018/src/bin/day_12.rs | 102 +++++++++++++++++++ 2018/src/bin/day_13.rs | 249 ++++++++++++++++++++++++++++++++++++++++++++ 2018/src/bin/day_14.rs | 111 ++++++++++++++++++++ 2018/src/bin/day_15.rs | 272 +++++++++++++++++++++++++++++++++++++++++++++++++ 2018/src/bin/day_16.rs | 205 +++++++++++++++++++++++++++++++++++++ 2018/src/bin/day_17.rs | 175 +++++++++++++++++++++++++++++++ 2018/src/bin/day_18.rs | 123 ++++++++++++++++++++++ 2018/src/bin/day_19.rs | 139 +++++++++++++++++++++++++ 2018/src/bin/day_2.rs | 53 ++++++++++ 2018/src/bin/day_20.rs | 137 +++++++++++++++++++++++++ 2018/src/bin/day_21.rs | 137 +++++++++++++++++++++++++ 2018/src/bin/day_22.rs | 165 ++++++++++++++++++++++++++++++ 2018/src/bin/day_23.rs | 114 +++++++++++++++++++++ 2018/src/bin/day_24.rs | 217 +++++++++++++++++++++++++++++++++++++++ 2018/src/bin/day_25.rs | 47 +++++++++ 2018/src/bin/day_3.rs | 76 ++++++++++++++ 2018/src/bin/day_4.rs | 116 +++++++++++++++++++++ 2018/src/bin/day_5.rs | 53 ++++++++++ 2018/src/bin/day_6.rs | 103 +++++++++++++++++++ 2018/src/bin/day_7.rs | 135 ++++++++++++++++++++++++ 2018/src/bin/day_8.rs | 66 ++++++++++++ 2018/src/bin/day_9.rs | 91 +++++++++++++++++ 25 files changed, 3066 insertions(+) create mode 100644 2018/src/bin/day_1.rs create mode 100644 2018/src/bin/day_10.rs create mode 100644 2018/src/bin/day_11.rs create mode 100644 2018/src/bin/day_12.rs create mode 100644 2018/src/bin/day_13.rs create mode 100644 2018/src/bin/day_14.rs create mode 100644 2018/src/bin/day_15.rs create mode 100644 2018/src/bin/day_16.rs create mode 100644 2018/src/bin/day_17.rs create mode 100644 2018/src/bin/day_18.rs create mode 100644 2018/src/bin/day_19.rs create mode 100644 2018/src/bin/day_2.rs create mode 100644 2018/src/bin/day_20.rs create mode 100644 2018/src/bin/day_21.rs create mode 100644 2018/src/bin/day_22.rs create mode 100644 2018/src/bin/day_23.rs create mode 100644 2018/src/bin/day_24.rs create mode 100644 2018/src/bin/day_25.rs create mode 100644 2018/src/bin/day_3.rs create mode 100644 2018/src/bin/day_4.rs create mode 100644 2018/src/bin/day_5.rs create mode 100644 2018/src/bin/day_6.rs create mode 100644 2018/src/bin/day_7.rs create mode 100644 2018/src/bin/day_8.rs create mode 100644 2018/src/bin/day_9.rs (limited to '2018/src/bin') diff --git a/2018/src/bin/day_1.rs b/2018/src/bin/day_1.rs new file mode 100644 index 0000000..4693579 --- /dev/null +++ b/2018/src/bin/day_1.rs @@ -0,0 +1,32 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +extern crate im_rc; + +use std::error::Error; +use std::path::PathBuf; + +use im_rc::HashSet; + +// cargo watch -cs "cargo run --release --bin day_1" + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/1.txt"))?; + let input_ints: Vec = input.iter().map(|str| str.parse::().unwrap()).collect(); + + println!("Input: {:?}", input_ints); + + let sum: i32 = input_ints.iter().sum(); + println!("Sum: {}", sum); + + let first_repeat = input_ints.iter().cycle().try_fold((0, HashSet::new()), |(acc, seen), &i| { + if seen.contains(&acc) { + Err(acc) + } else { + Ok((acc + i, seen.update(acc))) + } + }).err().unwrap(); + println!("First repeat: {}", first_repeat); + + Ok(()) +} diff --git a/2018/src/bin/day_10.rs b/2018/src/bin/day_10.rs new file mode 100644 index 0000000..082be7c --- /dev/null +++ b/2018/src/bin/day_10.rs @@ -0,0 +1,82 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::str::FromStr; + +use std::error::Error; +use std::path::PathBuf; + +use std::i32; + +// cargo watch -cs "cargo run --release --bin day_10" + + + +#[derive(Debug, Clone)] +struct Star { + x: i32, + y: i32, + dx: i32, + dy: i32 +} + +impl FromStr for Star { + type Err = Box; + + fn from_str(s: &str) -> Result { + let split = s + .split(|c: char| c != '-' && !c.is_numeric()) + .filter(|s| !s.is_empty()) + .map(|s| s.parse()) + .collect::, _>>()?; + + Ok(Star { + x: split[0], + y: split[1], + dx: split[2], + dy: split[3] + }) + } +} + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/10.txt"))?; + let mut stars = input.iter().map(|line| line.parse::().unwrap()).collect::>(); + + //debug!(input); + //debug!(stars); + + let screen_width = 80; + let screen_height = 80; + + for seconds in 0..1000000 { + let min_x = stars.iter().map(|s| s.x).min().unwrap(); + let max_x = stars.iter().map(|s| s.x).max().unwrap(); + let min_y = stars.iter().map(|s| s.y).min().unwrap(); + let max_y = stars.iter().map(|s| s.y).max().unwrap(); + + if max_x - min_x < screen_width && max_y - min_y < screen_height { + debug!(seconds); + for y in min_y..max_y+1 { + for x in min_x..max_x+1 { + let star_at_point = stars.iter().any(|s| s.x == x && s.y == y); + if star_at_point { + print!("#"); + } else { + print!(" "); + } + } + println!(); + } + println!(); + println!(); + } + + for star in &mut stars { + star.x += star.dx; + star.y += star.dy; + } + } + + Ok(()) +} diff --git a/2018/src/bin/day_11.rs b/2018/src/bin/day_11.rs new file mode 100644 index 0000000..0e458a3 --- /dev/null +++ b/2018/src/bin/day_11.rs @@ -0,0 +1,66 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::i32; + +// cargo watch -cs "cargo run --release --bin day_11" + +fn main() -> Result<(), Box> { + let input = 1723; + + println!("Input: {:?}", input); + + let powers = precompute_powers(input); + + let power_per_size = (1..300).map(|size| { + (1..302-size).map(|left| { + (1..302-size).map(|top| { + (power_for_block(left, top, size, &powers), (left, top, size)) + }).max_by_key(|(p, _)| *p).unwrap() + }).max_by_key(|(p, _)| *p).unwrap() + }).collect::>(); + + let (max_power_at_size_3, coordinate_at_size_3) = power_per_size[2]; // index from 0 vs 1 + debug!(max_power_at_size_3); + debug!(coordinate_at_size_3); + + let (max_power, coordinate) = power_per_size.iter().max_by_key(|(p, _)| p).unwrap(); + + debug!(max_power); + debug!(coordinate); + + Ok(()) +} + +fn power_for_block(left: i32, top: i32, size: i32, powers: &[[i32;300];300]) -> i32 { + (left..left+size).map(|x| { + (top..top+size).map(|y| { + powers[x as usize - 1][y as usize - 1] + }).sum::() + }).sum() +} + +fn precompute_powers(input: i32) -> [[i32;300];300] { + let mut powers: [[i32;300];300] = [[0;300];300]; + for x in 1..301 { + for y in 1..301 { + powers[x as usize - 1][y as usize - 1] = power_from_coordinates(x, y, input); + } + } + powers +} + +fn power_from_coordinates(x: i32, y: i32, input: i32) -> i32 { + let rack_id = x + 10; + ((((rack_id * y) + input) * rack_id / 100) % 10) - 5 +} + + +#[test] +fn power_from_coord_example() { + assert_eq!(power_from_coordinates(3, 5, 8), 4); + assert_eq!(power_from_coordinates(122, 79, 57), -5); + assert_eq!(power_from_coordinates(217,196, 39), 0); + assert_eq!(power_from_coordinates(101, 153, 71), 4); +} diff --git a/2018/src/bin/day_12.rs b/2018/src/bin/day_12.rs new file mode 100644 index 0000000..65a966d --- /dev/null +++ b/2018/src/bin/day_12.rs @@ -0,0 +1,102 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +use std::str::FromStr; + +// cargo watch -cs "cargo run --release --bin day_12" + +use std::collections::HashSet; + +#[derive(Debug)] +struct Rule { + input: [bool; 5], + output: bool +} + +impl FromStr for Rule { + type Err = Box; + + fn from_str(s: &str) -> Result { + //##..# => # + let mut input = [false; 5]; + let mut iter = s.chars().filter(|c| *c == '#' || *c == '.'); + for (i, c) in iter.by_ref().take(5).enumerate() { + if c == '#' { + input[i] = true; + } + } + Ok(Rule { + input, + output: iter.next() == Some('#') + }) + } +} + +impl Rule { + fn matches(&self, state: &HashSet, index: i64) -> bool { + self.input.iter().enumerate().all(|(i, expected)| { + let pot_index = index - 2 + i as i64; + *expected == state.contains(&pot_index) + }) + } +} + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/12.txt"))?; + + println!("Input: {:?}", input); + + let mut initial_state: HashSet = HashSet::new(); + for (i, c) in input[0].chars().filter(|c| *c == '#' || *c == '.').enumerate() { + if c == '#' { + initial_state.insert(i as i64); + } + } + let rules = input.iter().skip(1).map(|line| line.parse()).collect::, Box>>()?; + + debug!(initial_state); + debug!(rules); + + let part1_time = 20; + let part2_time = 50000000000; + + let part1_final_state = iterate_states(&initial_state, &rules, part1_time); + let sum_of_part1_pot_numbers: i64 = part1_final_state.iter().sum(); + debug!(sum_of_part1_pot_numbers); + + let part2_final_state = iterate_states(&initial_state, &rules, part2_time); + let sum_of_part2_pot_numbers: i64 = part2_final_state.iter().sum(); + debug!(sum_of_part2_pot_numbers); + + Ok(()) +} + +fn iterate_states(initial_state: &HashSet, rules: &[Rule], time: i64) -> HashSet { + let mut current_state = initial_state.clone(); + for current_time in 0..time { + let mut new_state = HashSet::new(); + let min = current_state.iter().min().cloned().unwrap_or(-1) - 2; + let max = current_state.iter().max().cloned().unwrap_or(-1) + 2; + + for i in min..max+1 { + if rules.iter().find(|r| r.matches(¤t_state, i)).expect("No matching rule").output { + new_state.insert(i as i64); + } + } + + if current_state.iter().map(|v| v + 1).collect::>() == new_state { + // Iterations are just shifting 1 to the right at this + // point. Found by inspecting a debugging log of the + // generations. + + let remaining_iterations = time-current_time; + return current_state.iter().map(|v| v + remaining_iterations).collect::>(); + } + + current_state = new_state; + } + current_state +} diff --git a/2018/src/bin/day_13.rs b/2018/src/bin/day_13.rs new file mode 100644 index 0000000..005f216 --- /dev/null +++ b/2018/src/bin/day_13.rs @@ -0,0 +1,249 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +// cargo watch -cs "cargo run --release --bin day_13" + +#[derive(Debug)] +enum Road { + LeftRight, + UpDown, + LeftUpRightDown, + RightUpLeftDown, + Intersection, + None +} + +#[derive(Debug)] +struct Cart { + next_turn: TurnDirection, + facing: FacingDirection, + x: usize, + y: usize, + crashed: bool + +} + +#[derive(Debug, Clone, Copy)] +enum FacingDirection { + Up, + Down, + Left, + Right +} + +#[derive(Debug, Clone, Copy)] +enum TurnDirection { + Left, + Straight, + Right +} + +impl TurnDirection { + fn next(&self) -> TurnDirection { + use TurnDirection::*; + + match *self { + Left => Straight, + Straight => Right, + Right => Left + } + } + + fn rotate(&self, facing: &FacingDirection) -> FacingDirection { + match *self { + TurnDirection::Left => match *facing { + FacingDirection::Up => FacingDirection::Left, + FacingDirection::Left => FacingDirection::Down, + FacingDirection::Down => FacingDirection::Right, + FacingDirection::Right => FacingDirection::Up + }, + TurnDirection::Right => match *facing { + FacingDirection::Up => FacingDirection::Right, + FacingDirection::Left => FacingDirection::Up, + FacingDirection::Down => FacingDirection::Left, + FacingDirection::Right => FacingDirection::Down + }, + TurnDirection::Straight => facing.clone() + } + } +} + + + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/13.txt"))?; + +// for i in &input { +// println!("{}", i); +// } + + let mut map: Vec> = Vec::new(); + let mut carts: Vec = Vec::new(); + + for (y, line) in input.iter().enumerate() { + let mut map_row = Vec::new(); + for (x, c) in line.chars().enumerate() { + let tile = match c { + ' ' => Road::None, + '-' => Road::LeftRight, + '|' => Road::UpDown, + '/' => Road::LeftUpRightDown, + '\\' => Road::RightUpLeftDown, + '+' => Road::Intersection, + '^' => { + carts.push(Cart { + next_turn: TurnDirection::Left, + facing: FacingDirection::Up, + x: x, + y: y, + crashed: false + }); + Road::UpDown + }, + '<' => { + carts.push(Cart { + next_turn: TurnDirection::Left, + facing: FacingDirection::Left, + x: x, + y: y, + crashed: false + }); + Road::LeftRight + }, + 'v' => { + carts.push(Cart { + next_turn: TurnDirection::Left, + facing: FacingDirection::Down, + x: x, + y: y, + crashed: false + }); + Road::UpDown + }, + '>' => { + carts.push(Cart { + next_turn: TurnDirection::Left, + facing: FacingDirection::Right, + x: x, + y: y, + crashed: false + }); + Road::LeftRight + }, + + _ => { + panic!("Unknown character {}", c); + } + }; + map_row.push(tile); + } + map.push(map_row); + } + + while carts.len() > 1 { + carts.sort_unstable_by(|a, b| a.y.cmp(&b.y).then(a.x.cmp(&b.x))); + + for i in 0..carts.len() { + { + let mut cart = &mut carts[i]; + let road = &map[cart.y][cart.x]; + + match (road, cart.facing, cart.next_turn) { + (Road::LeftRight, FacingDirection::Left, _) => { + cart.x -= 1; + }, + (Road::LeftRight, FacingDirection::Right, _) => { + cart.x += 1; + }, + (Road::LeftRight, _, _) => { + panic!("Sideways cart heading left-right"); + }, + + (Road::UpDown, FacingDirection::Up, _) => { + cart.y -= 1; + }, + (Road::UpDown, FacingDirection::Down, _) => { + cart.y += 1; + }, + (Road::UpDown, _, _) => { + panic!("Sideways cart heading up-down"); + }, + + // / + (Road::LeftUpRightDown, FacingDirection::Down, _) => { + cart.x -= 1; + cart.facing = FacingDirection::Left; + }, + (Road::LeftUpRightDown, FacingDirection::Right, _) => { + cart.y -= 1; + cart.facing = FacingDirection::Up; + }, + (Road::LeftUpRightDown, FacingDirection::Left, _) => { + cart.y += 1; + cart.facing = FacingDirection::Down; + }, + (Road::LeftUpRightDown, FacingDirection::Up, _) => { + cart.x += 1; + cart.facing = FacingDirection::Right; + }, + + // \ + (Road::RightUpLeftDown, FacingDirection::Up, _) => { + cart.x -= 1; + cart.facing = FacingDirection::Left; + }, + (Road::RightUpLeftDown, FacingDirection::Left, _) => { + cart.y -= 1; + cart.facing = FacingDirection::Up; + }, + (Road::RightUpLeftDown, FacingDirection::Right, _) => { + cart.y += 1; + cart.facing = FacingDirection::Down; + }, + (Road::RightUpLeftDown, FacingDirection::Down, _) => { + cart.x += 1; + cart.facing = FacingDirection::Right; + }, + + (Road::Intersection, f, d) => { + cart.facing = d.rotate(&f); + cart.next_turn = d.next(); + match cart.facing { + FacingDirection::Up => { cart.y -= 1 }, + FacingDirection::Down => { cart.y += 1 }, + FacingDirection::Left => { cart.x -= 1 }, + FacingDirection::Right => { cart.x += 1 }, + } + }, + + (Road::None, _, _) => { + panic!("Offroad cart!"); + } + + } + + } + + let collisions = carts.iter() + .enumerate() + .filter(|(other_i, other)| *other_i != i && other.x == carts[i].x && other.y == carts[i].y) + .map(|(other_i, _)| other_i) + .collect::>(); + for other_i in collisions { + let crash_location = (carts[i].x, carts[i].y); + debug!(crash_location); + carts[i].crashed = true; + carts[other_i].crashed = true; + } + } + + carts.retain(|cart| !cart.crashed); + } + + debug!(carts); + + Ok(()) +} diff --git a/2018/src/bin/day_14.rs b/2018/src/bin/day_14.rs new file mode 100644 index 0000000..cb16623 --- /dev/null +++ b/2018/src/bin/day_14.rs @@ -0,0 +1,111 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +// cargo watch -cs "cargo run --release --bin day_14" + +fn main() -> Result<(), Box> { + let input = 540561; + + let scoreboard = find_ten_scoreboard_after(input); + + println!("Result: "); + scoreboard.iter().for_each(|s| { + print!("{}", s); + }); + println!(); + + let first_occurence = find_first_occurence_of(input); + debug!(first_occurence); + + Ok(()) +} + +fn find_ten_scoreboard_after(input: usize) -> Vec { + let mut scoreboard = vec!(3,7); + let mut elf1_pos = 0; + let mut elf2_pos = 1; + + while scoreboard.len() < (input + 10) { + let next = scoreboard[elf1_pos] + scoreboard[elf2_pos]; + for digit in number_to_digits_vec(next) { + scoreboard.push(digit); + } + + elf1_pos = (elf1_pos + 1 + scoreboard[elf1_pos]) % scoreboard.len(); + elf2_pos = (elf2_pos + 1 + scoreboard[elf2_pos]) % scoreboard.len(); + } + + scoreboard.iter().skip(input).take(10).cloned().collect() +} + +fn find_first_occurence_of(input: usize) -> usize { + let target_sequence = number_to_digits_vec(input); + debug!(target_sequence); + + let mut scoreboard = vec!(3,7); + let mut elf1_pos = 0; + let mut elf2_pos = 1; + let mut target_index = None; + + while target_index.is_none() { + let next = scoreboard[elf1_pos] + scoreboard[elf2_pos]; + for digit in number_to_digits_vec(next) { + scoreboard.push(digit); + } + + elf1_pos = (elf1_pos + 1 + scoreboard[elf1_pos]) % scoreboard.len(); + elf2_pos = (elf2_pos + 1 + scoreboard[elf2_pos]) % scoreboard.len(); + + if scoreboard.len() >= target_sequence.len() + 2 { + for potential_target_index in scoreboard.len()-target_sequence.len()-2..scoreboard.len()-target_sequence.len()+1 { + let found = scoreboard.iter() + .skip(potential_target_index) + .take(target_sequence.len()) + .zip(target_sequence.iter()) + .all(|(a, b)| a == b); + if found { + target_index = Some(potential_target_index); + } + } + } + } + + target_index.unwrap() +} + +fn number_to_digits_vec(input: usize) -> Vec { + if input == 0 { + return vec!(0); + } + + let mut result = Vec::new(); + let mut acc = input; + while acc > 0 { + result.push(acc % 10); + acc /= 10; + } + result.reverse(); + result +} + +#[test] +fn vectorification() { + assert_eq!(number_to_digits_vec(10), vec!(1, 0)); + assert_eq!(number_to_digits_vec(1), vec!(1)); + assert_eq!(number_to_digits_vec(0), vec!(0)); +} + +#[test] +fn part1_examples() { + assert_eq!(find_ten_scoreboard_after(9), vec!(5,1,5,8,9,1,6,7,7,9)); + assert_eq!(find_ten_scoreboard_after(2018), vec!(5,9,4,1,4,2,9,8,8,2)); +} + +#[test] +fn part2_examples() { + assert_eq!(find_first_occurence_of(51589), 9); + assert_eq!(find_first_occurence_of(59414), 2018); +} diff --git a/2018/src/bin/day_15.rs b/2018/src/bin/day_15.rs new file mode 100644 index 0000000..c6f3cf2 --- /dev/null +++ b/2018/src/bin/day_15.rs @@ -0,0 +1,272 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +// cargo watch -cs "cargo run --release --bin day_15" + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/15.txt"))?; + + let (round_hp_product, _) = calculate_round_hp_product(&input, 3); + debug!(round_hp_product); + + for power in 3.. { + let (round_hp_product_without_losses, elf_losses) = calculate_round_hp_product(&input, power); + if (elf_losses == 0) { + debug!(round_hp_product_without_losses); + break; + } + } + + Ok(()) +} + +fn calculate_round_hp_product(input: &[String], elf_power: i32) -> (i32, usize) { + let goblin_power = 3; + let initial_hp = 200; + + let mut map = Vec::new(); + let mut units = Vec::new(); + + for (y, line) in input.iter().enumerate() { + let mut map_row = Vec::new(); + for (x, c) in line.chars().enumerate() { + map_row.push(c == '#'); + + let maybe_unit = match c { + 'G' => Some(Unit { + team: false, + x: x as i32, + y: y as i32, + hp: initial_hp + }), + 'E' => Some(Unit { + team: true, + x: x as i32, + y: y as i32, + hp: initial_hp + }), + _ => None + }; + if let Some(unit) = maybe_unit { + units.push(unit); + } + } + + map.push(map_row); + } + let start_elves = units.iter().filter(|u| u.team).count(); + + for round in 0.. { + // debug!(round); + // debug!(units); + // debug_print(&units, &map); + units.sort_unstable_by(|a, b| a.y.cmp(&b.y).then(a.x.cmp(&b.x))); + + for i in 0..units.len() { + if units[i].hp > 0 { + let battle_over = !units.iter().any(|other| other.hp > 0 && other.team != units[i].team); + if battle_over { + println!("Battle over"); + let hp_sum = units.iter().filter(|u| u.hp > 0).map(|u| u.hp).sum::(); + debug!(round); + debug!(hp_sum); + + let elf_losses = start_elves - units.iter().filter(|u| u.team).count(); + debug!(elf_losses); + return (round * hp_sum, elf_losses); + } + + let is_next_to_opponent = unit_at_point(!units[i].team, units[i].x-1, units[i].y, &units) + .or_else(|| unit_at_point(!units[i].team, units[i].x+1, units[i].y, &units)) + .or_else(|| unit_at_point(!units[i].team, units[i].x, units[i].y-1, &units)) + .or_else(|| unit_at_point(!units[i].team, units[i].x, units[i].y+1, &units)).is_some(); + if !is_next_to_opponent { + if let Some((next_x, next_y)) = find_next_step(i, &units, &map) { + units[i].x = next_x; + units[i].y = next_y; + } + } + + let mut attack_candidates = adjacent_units(!units[i].team, units[i].x, units[i].y, &units); + attack_candidates.sort_by(|&a, &b| units[a].hp.cmp(&units[b].hp)); + if let Some(&to_attack) = attack_candidates.first() { + let attack_power = if units[i].team { elf_power } else { goblin_power }; + units[to_attack].hp -= attack_power; + } + } + } + + units.retain(|u| u.hp > 0); + } + + panic!("Match ended unexpectedly"); +} + +fn find_next_step(i: usize, units: &[Unit], map: &Vec>) -> Option<(i32, i32)> { + let mut explored = vec!(Explored { + x: units[i].x, + y: units[i].y, + distance: 0, + parent: 0 + }); + + let mut explored_index = 0; + let mut distance_found = None; + while explored_index < explored.len() && distance_found.map_or(true, |distance| explored[explored_index].distance < distance) { + let distance = explored[explored_index].distance; + for (new_x, new_y) in adjacent_empty_spaces(explored[explored_index].x, explored[explored_index].y, &map, &units, &explored) { + explored.push(Explored { + x: new_x, + y: new_y, + distance: distance + 1, + parent: explored_index + }); + + if adjacent_units(!units[i].team, new_x, new_y, &units).len() > 0 { + distance_found = Some(distance + 1); + } + } + explored_index += 1; + } + + if let Some(distance) = distance_found { + let mut candidates = explored.iter().enumerate() + .filter(|(_,e)| e.distance == distance) + .filter(|(_,e)| adjacent_units(!units[i].team, e.x, e.y, &units).len() > 0) + .collect::>(); + candidates.sort_by(|(_,a), (_,b)| a.y.cmp(&b.y).then(a.x.cmp(&b.x))); + let (best_index, _) = candidates[0]; + + let mut result_index = best_index; + let mut next_index = best_index; + while next_index != 0 { + result_index = next_index; + next_index = explored[result_index].parent; + } + return Some((explored[result_index].x, explored[result_index].y)); + } + None +} + +fn adjacent_empty_spaces(x: i32, y: i32, map: &Vec>, units: &[Unit], explored: &[Explored]) -> Vec<(i32, i32)> { + [(x, y-1), (x-1, y), (x+1, y), (x, y+1)].iter() + .filter(|(x, y)| *x >= 0 && *y >= 0) + .filter(|(x, y)| !explored.iter().any(|e| e.x == *x && e.y == *y)) + .filter(|(x, y)| !units.iter().any(|e| e.hp > 0 && e.x == *x && e.y == *y)) + .filter(|(x, y)| !map[*y as usize][*x as usize]) + .cloned() + .collect() +} + +fn adjacent_units(team: bool, x: i32, y: i32, units: &[Unit]) -> Vec { + [(x, y-1), (x-1, y), (x+1, y), (x, y+1)].iter() + .filter_map(|(x, y)| unit_at_point(team, *x, *y, units)) + .collect() +} + +fn unit_at_point(team: bool, x: i32, y: i32, units: &[Unit]) -> Option { + units.iter().enumerate() + .find(|(_, u)| u.hp > 0 && u.team == team && u.x == x && u.y == y) + .map(|(i, _)| i) +} + +#[derive(Debug, Clone)] +struct Unit { + team: bool, + x: i32, + y: i32, + hp: i32 +} + +#[derive(Debug)] +struct Explored { + x: i32, + y: i32, + distance: u32, + parent: usize +} + + +fn debug_print(units: &[Unit], map: &Vec>) { + for (y, line) in map.iter().enumerate() { + for (x, wall) in line.iter().enumerate() { + let unit = units.iter().find(|u| u.hp > 0 && u.x == x as i32 && u.y == y as i32); + print!("{}", match (wall, unit) { + (true, _) => '#', + (false, Some(unit)) if unit.team => 'E', + (false, Some(_)) => 'G', + (false, None) => '.' + }); + } + println!(); + } + println!(); + println!(); +} + +fn part_1_test(input: &[&str]) -> i32 { + let owned_input = input.iter() + .map(|&line| line.to_owned()) + .collect::>(); + let (product, _) = calculate_round_hp_product(&owned_input, 3); + product +} + +#[test] +fn example_1() { + let input = vec!( + "#######", + "#.G...#", + "#...EG#", + "#.#.#G#", + "#..G#E#", + "#.....#", + "#######"); + assert_eq!(part_1_test(&input), 27730); +} + +#[test] +fn example_2() { + let input = vec!( + "#######", + "#G..#E#", + "#E#E.E#", + "#G.##.#", + "#...#E#", + "#...E.#", + "#######" + ); + assert_eq!(part_1_test(&input), 36334); +} + +#[test] +fn example_3() { + let input = vec!( + "#######", + "#E.G#.#", + "#.#G..#", + "#G.#.G#", + "#G..#.#", + "#...E.#", + "#######" + ); + assert_eq!(part_1_test(&input), 27755); +} + +#[test] +fn example_4() { + let input = vec!( + "#######", + "#.E...#", + "#.#..G#", + "#.###.#", + "#E#G#G#", + "#...#G#", + "#######" + ); + assert_eq!(part_1_test(&input), 28944); +} + diff --git a/2018/src/bin/day_16.rs b/2018/src/bin/day_16.rs new file mode 100644 index 0000000..275ec45 --- /dev/null +++ b/2018/src/bin/day_16.rs @@ -0,0 +1,205 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +use std::collections::{HashMap, HashSet}; + +// cargo watch -cs "cargo run --release --bin day_16" + +struct Instruction { + op: Op, + a: i32, + b: i32, + c: i32 +} + +impl Instruction { + fn execute(&self, registers: &[i32; 4]) -> [i32; 4] { + use Op::*; + + let mut result_registers = registers.clone(); + + result_registers[self.c as usize] = match self.op { + Addr => registers[self.a as usize] + registers[self.b as usize], + Addi => registers[self.a as usize] + self.b, + Mulr => registers[self.a as usize] * registers[self.b as usize], + Muli => registers[self.a as usize] * self.b, + Banr => registers[self.a as usize] & registers[self.b as usize], + Bani => registers[self.a as usize] & self.b, + Borr => registers[self.a as usize] | registers[self.b as usize], + Bori => registers[self.a as usize] | self.b, + Setr => registers[self.a as usize], + Seti => self.a, + Gtir => if self.a > registers[self.b as usize] { 1 } else { 0 }, + Gtri => if registers[self.a as usize] > self.b { 1 } else { 0 }, + Gtrr => if registers[self.a as usize] > registers[self.b as usize] { 1 } else { 0 }, + Eqir => if self.a == registers[self.b as usize] { 1 } else { 0 }, + Eqri => if registers[self.a as usize] == self.b { 1 } else { 0 }, + Eqrr => if registers[self.a as usize] == registers[self.b as usize] { 1 } else { 0 } + }; + + result_registers + } +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +enum Op { + Addr, + Addi, + Mulr, + Muli, + Banr, + Bani, + Borr, + Bori, + Setr, + Seti, + Gtir, + Gtri, + Gtrr, + Eqir, + Eqri, + Eqrr +} + +impl Op { + fn all() -> [Op; 16] { + use Op::*; + [ + Addr, + Addi, + Mulr, + Muli, + Banr, + Bani, + Borr, + Bori, + Setr, + Seti, + Gtir, + Gtri, + Gtrr, + Eqir, + Eqri, + Eqrr + ] + } +} + +struct UnknownInstruction { + before: [i32; 4], + after: [i32; 4], + opcode: i32, + a: i32, + b: i32, + c: i32 +} + +impl UnknownInstruction { + fn possible_matches(&self) -> HashSet { + Op::all() + .iter() + .filter(|&&op| { + let instruction = Instruction { + op: op, + a: self.a, + b: self.b, + c: self.c + }; + let result = instruction.execute(&self.before); + result == self.after + }) + .cloned() + .collect() + } +} + +fn main() -> Result<(), Box> { + let input_part_1 = read_file(&PathBuf::from("inputs/16_1.txt"))?; + + let unknown_instructions: Vec = input_part_1.chunks(3) + .map(|chunk| { + let mut before_iter = chunk[0].trim_matches(|c: char| !c.is_numeric()).split(", ").map(|c| c.parse::().unwrap()); + let before = [ + before_iter.next().unwrap(), + before_iter.next().unwrap(), + before_iter.next().unwrap(), + before_iter.next().unwrap(), + ]; + let mut after_iter = chunk[2].trim_matches(|c: char| !c.is_numeric()).split(", ").map(|c| c.parse::().unwrap()); + let after = [ + after_iter.next().unwrap(), + after_iter.next().unwrap(), + after_iter.next().unwrap(), + after_iter.next().unwrap(), + ]; + let mut instruction_iter = chunk[1].split_whitespace().map(|c| c.parse::().unwrap()); + UnknownInstruction { + before, after, + opcode: instruction_iter.next().unwrap(), + a: instruction_iter.next().unwrap(), + b: instruction_iter.next().unwrap(), + c: instruction_iter.next().unwrap(), + } + }) + .collect(); + + let matches_more_then_3 = unknown_instructions.iter() + .filter(|unknown| { + unknown.possible_matches().len() >= 3 + }) + .count(); + + debug!(matches_more_then_3); + + + let mut opcodes: HashMap> = HashMap::new(); + for unknown in unknown_instructions { + let matches = unknown.possible_matches(); + let to_insert = match opcodes.get(&unknown.opcode) { + None => matches, + Some(existing) => existing.intersection(&matches).cloned().collect() + }; + opcodes.insert(unknown.opcode, to_insert); + } + debug!(opcodes); + + let mut known_opcodes: HashMap = HashMap::new(); + + while known_opcodes.len() < 16 { + let (opcode, op) = { + let (opcode, opset) = opcodes.iter().find(|(_,set)| set.len() == 1).unwrap(); + let op = opset.iter().next().unwrap().clone(); + (opcode.clone(), op) + }; + known_opcodes.insert(opcode, op); + opcodes.iter_mut().for_each(|(_, set)| { + set.remove(&op); + }); + } + debug!(known_opcodes); + + + let input_part_2 = read_file(&PathBuf::from("inputs/16_2.txt"))?; + let instructions: Vec = input_part_2.iter() + .map(|line| { + let mut instruction_iter = line.split_whitespace().map(|c| c.parse::().unwrap()); + Instruction { + op: known_opcodes.get(&instruction_iter.next().unwrap()).unwrap().clone(), + a: instruction_iter.next().unwrap(), + b: instruction_iter.next().unwrap(), + c: instruction_iter.next().unwrap(), + } + }) + .collect(); + + let mut registers = [0; 4]; + for instruction in instructions { + registers = instruction.execute(®isters); + } + debug!(registers); + + Ok(()) +} diff --git a/2018/src/bin/day_17.rs b/2018/src/bin/day_17.rs new file mode 100644 index 0000000..f479c3a --- /dev/null +++ b/2018/src/bin/day_17.rs @@ -0,0 +1,175 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +// cargo watch -cs "cargo run --release --bin day_17" + +struct CoordBuilder { + xmin: Option, + xmax: Option, + ymin: Option, + ymax: Option +} + +#[derive(Debug)] +struct Coord { + xmin: usize, + xmax: usize, + ymin: usize, + ymax: usize +} + +impl CoordBuilder { + fn new() -> CoordBuilder { + CoordBuilder { + xmin: None, + xmax: None, + ymin: None, + ymax: None + } + } + + fn build(&self) -> Coord { + Coord { + xmin: self.xmin.unwrap(), + xmax: self.xmax.unwrap(), + ymin: self.ymin.unwrap(), + ymax: self.ymax.unwrap(), + } + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum Tile { + Clay, + RunningWater, + HalfSettledWater, + SettledWater, + Sand +} + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/17.txt"))?; + + let clay_coords = input.iter().map(|line| { + let mut builder = CoordBuilder::new(); + for split in line.split(", ") { + if split.starts_with("x=") { + let mut range_split = split + .trim_matches(|c: char| !c.is_numeric()) + .split("..") + .map(|s| s.parse().unwrap()); + if let Some(min) = range_split.next() { + builder.xmin = Some(min); + builder.xmax = Some(min+1); + } + if let Some(max) = range_split.next() { + builder.xmax = Some(max+1); + } + } else { + let mut range_split = split + .trim_matches(|c: char| !c.is_numeric()) + .split("..") + .map(|s| s.parse().unwrap()); + if let Some(min) = range_split.next() { + builder.ymin = Some(min); + builder.ymax = Some(min+1); + } + if let Some(max) = range_split.next() { + builder.ymax = Some(max+1); + } + } + } + builder.build() + }).collect::>(); + + let range = CoordinateSystem { + xmin: clay_coords.iter().min_by_key(|coord| coord.xmin).unwrap().xmin-2, + xmax: clay_coords.iter().max_by_key(|coord| coord.xmax).unwrap().xmax+2, + ymin: clay_coords.iter().min_by_key(|coord| coord.ymin).unwrap().ymin, + ymax: clay_coords.iter().max_by_key(|coord| coord.ymax).unwrap().ymax + }; + + debug!(range); + + + let mut map = vec!(Tile::Sand; range.vector_size()); + for coord in clay_coords { + for y in coord.ymin..coord.ymax { + for x in coord.xmin..coord.xmax { + map[range.to_vec(x, y)] = Tile::Clay; + } + } + } + + debug!(map[range.to_vec(500, range.ymin)]); + map[range.to_vec(500, range.ymin)] = Tile::RunningWater; + + let mut last_iter = Vec::new(); + while last_iter != map { + last_iter = map.clone(); + for y in range.ymin..range.ymax-1 { + for x in range.xmin..range.xmax { + match map[range.to_vec(x, y)] { + Tile::RunningWater => { + if map[range.to_vec(x, y+1)] == Tile::Sand { + map[range.to_vec(x, y+1)] = Tile::RunningWater; + } + if map[range.to_vec(x-1, y)] == Tile::Sand && (map[range.to_vec(x, y+1)] == Tile::Clay || map[range.to_vec(x, y+1)] == Tile::SettledWater) { + map[range.to_vec(x-1, y)] = Tile::RunningWater; + } + if map[range.to_vec(x+1, y)] == Tile::Sand && (map[range.to_vec(x, y+1)] == Tile::Clay || map[range.to_vec(x, y+1)] == Tile::SettledWater) { + map[range.to_vec(x+1, y)] = Tile::RunningWater; + } + if (map[range.to_vec(x-1, y)] == Tile::Clay || map[range.to_vec(x-1, y)] == Tile::HalfSettledWater) && (map[range.to_vec(x, y+1)] == Tile::Clay || map[range.to_vec(x, y+1)] == Tile::SettledWater) { + map[range.to_vec(x, y)] = Tile::HalfSettledWater; + } + }, + Tile::HalfSettledWater => { + if map[range.to_vec(x+1, y)] == Tile::Clay { + for xleft in 0.. { + if map[range.to_vec(x-xleft, y)] == Tile::HalfSettledWater { + map[range.to_vec(x-xleft, y)] = Tile::SettledWater; + } else { + break; + } + } + } + }, + _ => {} + } + } + } + } + + let water_tiles = map.iter() + .filter(|&&t| t == Tile::RunningWater || t == Tile::SettledWater || t == Tile::HalfSettledWater) + .count(); + debug!(water_tiles); + + let settled_water_tiles = map.iter() + .filter(|&&t| t == Tile::SettledWater) + .count(); + debug!(settled_water_tiles); + + Ok(()) +} + +#[derive(Debug)] +struct CoordinateSystem { + xmin: usize, + xmax: usize, + ymin: usize, + ymax: usize +} + +impl CoordinateSystem { + fn vector_size(&self) -> usize { + (self.xmax - self.xmin) * (self.ymax - self.ymin) + } + fn to_vec(&self, x: usize, y: usize) -> usize { + ((y - self.ymin) * (self.xmax - self.xmin)) + (x - self.xmin) + } +} diff --git a/2018/src/bin/day_18.rs b/2018/src/bin/day_18.rs new file mode 100644 index 0000000..3908ea7 --- /dev/null +++ b/2018/src/bin/day_18.rs @@ -0,0 +1,123 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +extern crate arrayvec; +use arrayvec::ArrayVec; + +use std::error::Error; +use std::path::PathBuf; + +use std::collections::HashMap; + +// cargo watch -cs "cargo run --release --bin day_18" + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +enum State { + Open, + Trees, + Lumber +} + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/18.txt"))?; + +// println!("Input: {:?}", input); + + let map = input.iter().map(|line| { + line.chars().map(|c| match c { + '.' => State::Open, + '|' => State::Trees, + '#' => State::Lumber, + _ => panic!("Unknown character {}", c) + }).collect::>() + }).collect::>(); +// debug!(map); + + let after_10 = simulate(&map, 10); + let trees_count_10: usize = after_10.iter().map(|row| row.iter().filter(|&&x| x == State::Trees).count()).sum(); + let lumber_count_10: usize = after_10.iter().map(|row| row.iter().filter(|&&x| x == State::Lumber).count()).sum(); + debug!(trees_count_10); + debug!(lumber_count_10); + debug!(trees_count_10 * lumber_count_10); + + let after_many = simulate(&map, 1000000000); + let trees_count_many: usize = after_many.iter().map(|row| row.iter().filter(|&&x| x == State::Trees).count()).sum(); + let lumber_count_many: usize = after_many.iter().map(|row| row.iter().filter(|&&x| x == State::Lumber).count()).sum(); + debug!(trees_count_many); + debug!(lumber_count_many); + debug!(trees_count_many * lumber_count_many); + + + Ok(()) +} + + +fn simulate(start_map: &Vec>, duration: u32) -> Vec> { + let mut previous_maps = HashMap::new(); + + let mut map = start_map.clone(); + + let mut t = 0; + while t < duration { + let map0 = map.clone(); + for y in 0..map.len() { + for x in 0..map[y].len() { + let adjacent = [ + (x.wrapping_sub(1), y.wrapping_sub(1)), + (x, y.wrapping_sub(1)), + (x+1, y.wrapping_sub(1)), + (x.wrapping_sub(1), y), + (x+1, y), + (x.wrapping_sub(1), y+1), + (x, y+1), + (x+1, y+1) + ].iter().map(|&(other_x,other_y)| { + if other_y >= map0.len() || other_x >= map0[other_y].len() { + State::Open + } else { + map0[other_y][other_x] + } + }).collect::>(); + + let adjacent_trees = adjacent.iter().filter(|&&x| x == State::Trees).count(); + let adjacent_lumber = adjacent.iter().filter(|&&x| x == State::Lumber).count(); + + map[y][x] = match (map0[y][x], adjacent_trees, adjacent_lumber) { + (State::Open, trees, _) if trees >= 3 => State::Trees, + (State::Open, _, _) => State::Open, + (State::Trees, _, lumber) if lumber >= 3 => State::Lumber, + (State::Trees, _, _) => State::Trees, + (State::Lumber, trees, lumber) if trees >= 1 && lumber >= 1 => State::Lumber, + (State::Lumber, _, _) => State::Open + } + } + } + + t += match previous_maps.get(&map) { + Some(previous_t) => { + let period = t + 1 - previous_t; + let whole_periods = (duration - t - 1) / period; + (period * whole_periods) + 1 + }, + None => 1 + }; + previous_maps.insert(map.clone(), t); + } + + map +} + +fn debug_print(map: &Vec>) { + for row in map { + for c in row { + print!("{}", match c { + State::Open => '.', + State::Trees => '|', + State::Lumber => '#' + }); + } + println!(); + } + println!(); + println!(); +} diff --git a/2018/src/bin/day_19.rs b/2018/src/bin/day_19.rs new file mode 100644 index 0000000..37ffef1 --- /dev/null +++ b/2018/src/bin/day_19.rs @@ -0,0 +1,139 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +// cargo watch -cs "cargo run --release --bin day_19" + +#[derive(Debug)] +struct Instruction { + op: Op, + a: i32, + b: i32, + c: i32 +} + +impl Instruction { + fn execute(&self, counter_register: usize, registers: &mut [i32; 6]) -> i32{ + use Op::*; + + registers[self.c as usize] = match self.op { + Addr => registers[self.a as usize] + registers[self.b as usize], + Addi => registers[self.a as usize] + self.b, + Mulr => registers[self.a as usize] * registers[self.b as usize], + Muli => registers[self.a as usize] * self.b, + Banr => registers[self.a as usize] & registers[self.b as usize], + Bani => registers[self.a as usize] & self.b, + Borr => registers[self.a as usize] | registers[self.b as usize], + Bori => registers[self.a as usize] | self.b, + Setr => registers[self.a as usize], + Seti => self.a, + Gtir => if self.a > registers[self.b as usize] { 1 } else { 0 }, + Gtri => if registers[self.a as usize] > self.b { 1 } else { 0 }, + Gtrr => if registers[self.a as usize] > registers[self.b as usize] { 1 } else { 0 }, + Eqir => if self.a == registers[self.b as usize] { 1 } else { 0 }, + Eqri => if registers[self.a as usize] == self.b { 1 } else { 0 }, + Eqrr => if registers[self.a as usize] == registers[self.b as usize] { 1 } else { 0 }, + }; + + registers[counter_register]+1 + } +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +enum Op { + Addr, + Addi, + Mulr, + Muli, + Banr, + Bani, + Borr, + Bori, + Setr, + Seti, + Gtir, + Gtri, + Gtrr, + Eqir, + Eqri, + Eqrr +} + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/19.txt"))?; + + println!("Input: {:?}", input); + + let mut input_iter = input.iter(); + let counter_register: usize = input_iter.next() + .map(|line| line.split_whitespace().nth(1).unwrap().parse().unwrap()) + .unwrap(); + + let instructions: Vec = input_iter + .map(|line| { + let mut instruction_iter = line.split_whitespace(); + Instruction { + op: match instruction_iter.next().unwrap() { + "addr" => Op::Addr, + "addi" => Op::Addi, + "mulr" => Op::Mulr, + "muli" => Op::Muli, + "banr" => Op::Banr, + "bani" => Op::Bani, + "borr" => Op::Borr, + "bori" => Op::Bori, + "setr" => Op::Setr, + "seti" => Op::Seti, + "gtir" => Op::Gtir, + "gtri" => Op::Gtri, + "gtrr" => Op::Gtrr, + "eqir" => Op::Eqir, + "eqri" => Op::Eqri, + "eqrr" => Op::Eqrr, + _ => panic!("unknown instruction") + }, + a: instruction_iter.next().unwrap().parse().unwrap(), + b: instruction_iter.next().unwrap().parse().unwrap(), + c: instruction_iter.next().unwrap().parse().unwrap(), + } + }) + .collect(); + + debug!(counter_register); + debug!(instructions); + + let part1_registers = execute_program(&instructions, counter_register, [0; 6]); + debug!(part1_registers); + + //let part2_registers = execute_program(&instructions, counter_register, [1, 0, 0, 0, 0, 0]); + //debug!(part2_registers); + part2(); + + Ok(()) +} + +fn execute_program(instructions: &Vec, counter_register: usize, registers: [i32; 6]) -> [i32; 6] { + let mut counter_val: i32 = 0; + let mut registers = registers.clone(); + while counter_val >= 0 && counter_val < instructions.len() as i32 { + registers[counter_register] = counter_val; + counter_val = instructions[counter_val as usize].execute(counter_register, &mut registers); + } + + registers +} + + + +fn part2() { + let r1 = ((27*28)+29)*30*14*32 + (11 * 19 * 2 * 2) + (3 * 22) + 9; + let mut r0 = 0; + for r5 in 1..r1+1 { + if r1 % r5 == 0 { + r0 += r1 / r5; + } + } + debug!(r0); +} diff --git a/2018/src/bin/day_2.rs b/2018/src/bin/day_2.rs new file mode 100644 index 0000000..7700871 --- /dev/null +++ b/2018/src/bin/day_2.rs @@ -0,0 +1,53 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +extern crate im_rc; +use im_rc::HashMap; + +// cargo watch -cs "cargo run --release --bin day_2" + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/2.txt"))?; + + println!("Input: {:?}", input); + + let (twice, thrice) = input.iter().fold((0,0), |(twice, thrice), next| { + let occurances = next.chars().fold(HashMap::new(), |occurances, c| { + let counter = occurances.get(&c).cloned().unwrap_or(0); + occurances.update(c, counter + 1) + }); + let has_twice = occurances.values().any(|count| *count == 2); + let has_thrice = occurances.values().any(|count| *count == 3); + + ( + twice + if has_twice { 1 } else { 0 }, + thrice + if has_thrice { 1 } else { 0 }, + ) + }); + + println!("Twice: {}", twice); + println!("Thrice: {}", thrice); + + let checksum = twice * thrice; + println!("Checksum: {}", checksum); + + for i in &input { + for j in &input { + let diff = i.chars().zip(j.chars()).fold(0, |diff, (x, y)| { + if x != y { + diff + 1 + } else { + diff + } + }); + if diff == 1 { + println!("Diff of 1: {} + {}", i, j); + } + } + } + + Ok(()) +} diff --git a/2018/src/bin/day_20.rs b/2018/src/bin/day_20.rs new file mode 100644 index 0000000..6486d72 --- /dev/null +++ b/2018/src/bin/day_20.rs @@ -0,0 +1,137 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +use std::collections::{HashSet, HashMap}; + +// cargo watch -cs "cargo run --release --bin day_20" + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +enum Dir { + N, S, E, W +} + +#[derive(Debug)] +struct Room { + doors: HashSet +} + +impl Room { + fn new() -> Room { + Room { + doors: HashSet::new() + } + } +} + +fn main() -> Result<(), Box> { + let input = &read_file(&PathBuf::from("inputs/20.txt"))?[0]; + + println!("Input: {:?}", input); + + let rooms = populate_rooms(input); + let distances = distance_map(&rooms); + + debug!(distance_to_furthest_room(&distances)); + debug!(distances_more_than_1000(&distances)); + + Ok(()) +} + +fn populate_rooms(input: &str) -> HashMap<(i32, i32), Room> { + let mut rooms: HashMap<(i32, i32), Room> = HashMap::new(); + rooms.insert((0,0), Room::new()); + + let mut coords = vec!((0, 0)); + + let mut coord_stack: Vec<(Vec<(i32, i32)>, Vec<(i32, i32)>)> = Vec::new(); + + for c in input.chars() { + match c { + '^' | '$' => {}, + 'E' => { + for coord in &mut coords { + rooms.get_mut(coord).unwrap().doors.insert(Dir::E); + coord.0 += 1; + rooms.entry(*coord).or_insert(Room::new()); + } + }, + 'W' => { + for coord in &mut coords { + rooms.get_mut(coord).unwrap().doors.insert(Dir::W); + coord.0 -= 1; + rooms.entry(*coord).or_insert(Room::new()); + } + }, + 'N' => { + for coord in &mut coords { + rooms.get_mut(coord).unwrap().doors.insert(Dir::N); + coord.1 -= 1; + rooms.entry(*coord).or_insert(Room::new()); + } + }, + 'S' => { + for coord in &mut coords { + rooms.get_mut(coord).unwrap().doors.insert(Dir::S); + coord.1 += 1; + rooms.entry(*coord).or_insert(Room::new()); + } + }, + '(' => { + coord_stack.push((coords.clone(), Vec::new())); + }, + '|' => { + coord_stack.last_mut().unwrap().1.append(&mut coords); + coords = coord_stack.last().unwrap().0.clone(); + }, + ')' => { + coord_stack.last_mut().unwrap().1.append(&mut coords); + coords = coord_stack.pop().unwrap().1; + coords.sort(); + coords.dedup(); + }, + c => { + panic!("Unknown character {}", c); + } + } + } + + debug!(rooms.len()); + + rooms +} + +fn distance_map(rooms: &HashMap<(i32, i32), Room>) -> HashMap<(i32, i32), u32> { + let mut distances: HashMap<(i32, i32), u32> = HashMap::new(); + distances.insert((0,0), 0); + + while distances.len() < rooms.len() { + let current_max = *distances.values().max().unwrap(); + let new_distances = distances.iter() + .filter(|(_, &d)| d == current_max) + .flat_map(|(&coord, _)| { + let room = rooms.get(&coord).unwrap(); + room.doors.iter().map(|dir| match dir { + Dir::N => (coord.0, coord.1-1), + Dir::S => (coord.0, coord.1+1), + Dir::W => (coord.0-1, coord.1), + Dir::E => (coord.0+1, coord.1) + }).collect::>() + }) + .collect::>(); + for coord in new_distances { + distances.entry(coord).or_insert(current_max + 1); + } + } + distances +} + +fn distance_to_furthest_room(distances: &HashMap<(i32, i32), u32>) -> u32 { + distances.values().max().unwrap().clone() +} + +fn distances_more_than_1000(distances: &HashMap<(i32, i32), u32>) -> u32 { + distances.values().filter(|&&x| x >= 1000).count() as u32 +} diff --git a/2018/src/bin/day_21.rs b/2018/src/bin/day_21.rs new file mode 100644 index 0000000..0d9a97c --- /dev/null +++ b/2018/src/bin/day_21.rs @@ -0,0 +1,137 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; +use std::u32; + +use std::collections::HashMap; +// cargo watch -cs "cargo run --release --bin day_21" + +use std::i32; + +#[derive(Debug)] +struct Instruction { + op: Op, + a: i32, + b: i32, + c: i32 +} + +impl Instruction { + fn execute(&self, counter_register: usize, registers: &mut [i32; 6]) -> i32{ + use Op::*; + + registers[self.c as usize] = match self.op { + Addr => registers[self.a as usize].wrapping_add(registers[self.b as usize]), + Addi => registers[self.a as usize].wrapping_add(self.b), + Mulr => registers[self.a as usize].wrapping_mul(registers[self.b as usize]), + Muli => registers[self.a as usize].wrapping_mul(self.b), + Banr => registers[self.a as usize] & registers[self.b as usize], + Bani => registers[self.a as usize] & self.b, + Borr => registers[self.a as usize] | registers[self.b as usize], + Bori => registers[self.a as usize] | self.b, + Setr => registers[self.a as usize], + Seti => self.a, + Gtir => if self.a > registers[self.b as usize] { 1 } else { 0 }, + Gtri => if registers[self.a as usize] > self.b { 1 } else { 0 }, + Gtrr => if registers[self.a as usize] > registers[self.b as usize] { 1 } else { 0 }, + Eqir => if self.a == registers[self.b as usize] { 1 } else { 0 }, + Eqri => if registers[self.a as usize] == self.b { 1 } else { 0 }, + Eqrr => if registers[self.a as usize] == registers[self.b as usize] { 1 } else { 0 }, + }; + + registers[counter_register]+1 + } +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +enum Op { + Addr, + Addi, + Mulr, + Muli, + Banr, + Bani, + Borr, + Bori, + Setr, + Seti, + Gtir, + Gtri, + Gtrr, + Eqir, + Eqri, + Eqrr +} + + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/21.txt"))?; + + let mut input_iter = input.iter(); + let counter_register: usize = input_iter.next() + .map(|line| line.split_whitespace().nth(1).unwrap().parse().unwrap()) + .unwrap(); + + let instructions: Vec = input_iter + .map(|line| { + let mut instruction_iter = line.split_whitespace(); + Instruction { + op: match instruction_iter.next().unwrap() { + "addr" => Op::Addr, + "addi" => Op::Addi, + "mulr" => Op::Mulr, + "muli" => Op::Muli, + "banr" => Op::Banr, + "bani" => Op::Bani, + "borr" => Op::Borr, + "bori" => Op::Bori, + "setr" => Op::Setr, + "seti" => Op::Seti, + "gtir" => Op::Gtir, + "gtri" => Op::Gtri, + "gtrr" => Op::Gtrr, + "eqir" => Op::Eqir, + "eqri" => Op::Eqri, + "eqrr" => Op::Eqrr, + _ => panic!("unknown instruction") + }, + a: instruction_iter.next().unwrap().parse().unwrap(), + b: instruction_iter.next().unwrap().parse().unwrap(), + c: instruction_iter.next().unwrap().parse().unwrap(), + } + }) + .collect(); + + execute_program(&instructions, counter_register, [0, 0, 0, 0, 0, 0]); + + Ok(()) +} + +fn execute_program(instructions: &Vec, counter_register: usize, registers: [i32; 6]) { + let mut instructions_executed: u64 = 0; + let mut counter_val: i32 = 0; + let mut registers = registers.clone(); + let mut halting_values = HashMap::new(); + + while counter_val >= 0 && counter_val < instructions.len() as i32 { + if counter_val == 28 { + if halting_values.contains_key(®isters[4]) { + break; + } + halting_values.entry(registers[4]).or_insert(instructions_executed+2); + } + registers[counter_register] = counter_val; + counter_val = instructions[counter_val as usize].execute(counter_register, &mut registers); + instructions_executed += 1; + } + + let (min_halting, min_halting_time) = halting_values.iter().min_by_key(|&(_, v)| v).unwrap(); + debug!(min_halting); + debug!(min_halting_time); + let (max_halting, max_halting_time) = halting_values.iter().max_by_key(|&(_, v)| v).unwrap(); + debug!(max_halting); + debug!(max_halting_time); + +} diff --git a/2018/src/bin/day_22.rs b/2018/src/bin/day_22.rs new file mode 100644 index 0000000..f9013cf --- /dev/null +++ b/2018/src/bin/day_22.rs @@ -0,0 +1,165 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +use std::u32; +use std::collections::{HashMap, HashSet}; + +// cargo watch -cs "cargo run --release --bin day_22" + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +struct Position { + x: u32, + y: u32, + equipment: u32 // 0 = nothing, 1 = torch, 2 = climbing +} + +impl Position { + fn adjacent(&self, map: &Vec>) -> Vec<(Position, u32)> { + let all_adjacent = [ + (Position { + x: self.x.saturating_sub(1), + ..*self + }, 1), + (Position { + y: self.y.saturating_sub(1), + ..*self + }, 1), + (Position { + x: self.x+1, + ..*self + }, 1), + (Position { + y: self.y+1, + ..*self + }, 1), + (Position { + equipment: (self.equipment+1)%3, + ..*self + }, 7), + (Position { + equipment: (self.equipment+2)%3, + ..*self + }, 7) + ]; + all_adjacent.iter() + .filter(|(p, _)| { + let region = map[p.y as usize][p.x as usize]; + let out_of_bounds = self == p; + let invalid_equipment = (region == 0 && p.equipment == 0) || + (region == 1 && p.equipment == 1) || + (region == 2 && p.equipment == 2); + !out_of_bounds && !invalid_equipment + }) + .cloned() + .collect() + } +} + +fn main() -> Result<(), Box> { + let input = &read_file(&PathBuf::from("inputs/22.txt"))?; + + let depth: u32 = input[0].trim_matches(|c: char| !c.is_numeric()).parse().unwrap(); + debug!(depth); + let mut input_target_iter = input[1] + .split(|c: char| !c.is_numeric()) + .filter(|s| !s.is_empty()) + .map(|s| s.parse::().unwrap()); + + let target_x = input_target_iter.next().unwrap(); + let target_y = input_target_iter.next().unwrap(); + + debug!((target_x, target_y)); + + let mut map_width = target_x; + let mut map_height = target_y; + let mut map = build_map(map_width, map_height, depth, target_x, target_y); + + let risk: u32 = map.iter().take((target_y+1) as usize).map(|row| row.iter().take((target_x+1) as usize).sum::()).sum(); + debug!(risk); + + + let mut distances = HashMap::new(); + let mut unexplored = HashSet::new(); + let initial = Position { + x: 0, + y: 0, + equipment: 1 + }; + let target = Position { + x: target_x, + y: target_y, + equipment: 1 + }; + distances.insert(initial, 0); + unexplored.insert(initial); + + while !distances.contains_key(&target) || unexplored.contains(&target) { + let (current, current_distance) = unexplored.iter() + .map(|unexp| (unexp.clone(), distances.get(unexp).cloned().unwrap())) + .min_by_key(|(_, d)| *d) + .unwrap(); + + if current.y+1 >= map_height { + map_height *= 2; + map = build_map(map_width, map_height, depth, target_x, target_y); + debug!(map_height); + } + if current.x+1 >= map_width { + map_width *= 2; + map = build_map(map_width, map_height, depth, target_x, target_y); + debug!(map_width); + } + + for (adjacent, further) in current.adjacent(&map) { + let distance = current_distance + further; + let best_previous_distance = distances.get(&adjacent).cloned().unwrap_or(u32::MAX); + if best_previous_distance > distance { + distances.insert(adjacent, distance); + unexplored.insert(adjacent); + } + + } + unexplored.remove(¤t); + } + + debug!(distances.get(&target)); + + Ok(()) +} + + +fn build_map(max_x: u32, max_y: u32, depth: u32, target_x: u32, target_y: u32) -> Vec> { + let mut geologic_index: Vec> = Vec::new(); + let mut erosion_level: Vec> = Vec::new(); + let mut region_type: Vec> = Vec::new(); + + for y in 0..max_y { + let mut geologic_row = Vec::new(); + let mut erosion_row = Vec::new(); + let mut type_row = Vec::new(); + + for x in 0..max_x { + let index = match (x, y) { + (0, 0) => 0, + (x, y) if x == target_x && y == target_y => 0, + (x, 0) => x*16807, + (0, y) => y*48271, + (x, y) => erosion_row[(x-1) as usize] * erosion_level[(y-1) as usize][x as usize] + }; + let erosion = (index + depth) % 20183; + let block_type = erosion % 3; + + geologic_row.push(index); + erosion_row.push(erosion); + type_row.push(block_type); + } + + geologic_index.push(geologic_row); + erosion_level.push(erosion_row); + region_type.push(type_row); + } + region_type +} diff --git a/2018/src/bin/day_23.rs b/2018/src/bin/day_23.rs new file mode 100644 index 0000000..463f3d3 --- /dev/null +++ b/2018/src/bin/day_23.rs @@ -0,0 +1,114 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; +use std::cmp; + +// cargo watch -cs "cargo run --release --bin day_23" + +#[derive(Debug, Clone)] +struct Bot { + radius: i64, + position: Position +} + +#[derive(Debug, Clone)] +struct Position { + x: i64, + y: i64, + z: i64 +} + +impl Position { + fn distance(&self, other: &Position) -> i64 { + (other.z - self.z).abs() + + (other.y - self.y).abs() + + (other.x - self.x).abs() + } +} + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/23.txt"))?; + + let mut bots: Vec = input.iter().map(|line| { + let mut line_iter = line.split(|c: char| c != '-' && !c.is_numeric()) + .filter(|s| !s.is_empty()) + .map(|s| s.parse::().unwrap()); + Bot { + position: Position { + x: line_iter.next().unwrap(), + y: line_iter.next().unwrap(), + z: line_iter.next().unwrap() + }, + radius: line_iter.next().unwrap() + } + }).collect(); + + let biggest_radius = bots.iter().max_by_key(|bot| bot.radius).unwrap(); + let biggest_radius_in_range_count = bots.iter() + .filter(|bot| biggest_radius.position.distance(&bot.position) <= biggest_radius.radius) + .count(); + debug!(biggest_radius); + debug!(biggest_radius_in_range_count); + + + let min_x = bots.iter().min_by_key(|bot| bot.position.x).unwrap().position.x; + let max_x = bots.iter().max_by_key(|bot| bot.position.x).unwrap().position.x; + debug!(min_x); + debug!(max_x); + let min_y = bots.iter().min_by_key(|bot| bot.position.y).unwrap().position.y; + let max_y = bots.iter().max_by_key(|bot| bot.position.y).unwrap().position.y; + debug!(min_y); + debug!(max_y); + let min_z = bots.iter().min_by_key(|bot| bot.position.z).unwrap().position.z; + let max_z = bots.iter().max_by_key(|bot| bot.position.z).unwrap().position.z; + debug!(min_z); + debug!(max_z); + + let origin = Position { x: 0, y: 0, z: 0 }; + + let mut radius = cmp::max(max_x - min_x, cmp::max(max_y-min_y, max_z-min_z)); + let mut center = origin.clone(); + + while radius > 0 { + let delta = 0.8; + let new_radius = if radius == 1 { 0 } else { (radius as f32 * delta) as i64 }; + let deltas = [-1.0, -0.8, -0.6, -0.4, -0.2, 0.0, 0.2, 0.4, 0.6, 0.8, 1.0]; + let subs: Vec = deltas.iter().flat_map(|&dx| { + deltas.iter().flat_map(|&dy| { + deltas.iter().map(|&dz| { + Position { + x: center.x + (radius as f32 * dx) as i64, + y: center.y + (radius as f32 * dy) as i64, + z: center.z + (radius as f32 * dz) as i64 + } + }).collect::>() + }).collect::>() + }).collect(); + + center = subs.iter() + .map(|new_center| { + (new_center, bots.iter() + .filter(|bot| bot.position.distance(&new_center) <= bot.radius + new_radius) + .count()) + }) + .max_by(|(a_center, a_bots), (b_center, b_bots)| { + a_bots.cmp(&b_bots).then(b_center.distance(&origin).cmp(&a_center.distance(&origin))) + }) + .map(|(center, _)| center) + .unwrap().clone(); + + radius = new_radius; + } + + let connected_in_radius = bots.iter() + .filter(|bot| bot.position.distance(¢er) <= bot.radius) + .count(); + debug!(connected_in_radius); + debug!(center); + let distance_to_origin = center.distance(&origin); + debug!(distance_to_origin); + + Ok(()) +} diff --git a/2018/src/bin/day_24.rs b/2018/src/bin/day_24.rs new file mode 100644 index 0000000..d52f7d0 --- /dev/null +++ b/2018/src/bin/day_24.rs @@ -0,0 +1,217 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; +use std::str::FromStr; + +use std::collections::HashMap; + +// cargo watch -cs "cargo run --release --bin day_24" + +#[derive(Debug, Clone)] +struct Army { + units: u32, + hp: u32, + weaknesses: Vec, + immunities: Vec, + damage_type: String, + damage: u32, + initiative: u32 +} + +impl Army { + fn effective_power(&self) -> u32 { + self.units * self.damage + } + + fn actual_damage(&self, other: &Army) -> u32 { + let modifier = if other.weaknesses.contains(&self.damage_type) { + 2 + } else if other.immunities.contains(&self.damage_type) { + 0 + } else { + 1 + }; + self.effective_power() * modifier + } +} + +impl FromStr for Army { + type Err = Box; + + fn from_str(s: &str) -> Result { + // 2991 units each with 8084 hit points (weak to fire) with an attack that does 19 radiation damage at initiative 11 + let mut words = s.split_whitespace(); + let units = words.next().unwrap().parse()?; + let hp = words.nth(3).unwrap().parse()?; + let _ = words.nth(1); + + let mut weaknesses = Vec::new(); + let mut immunities = Vec::new(); + + let mut bracket_handled = false; + while !bracket_handled { + let maybe_weak_or_immune = words.next().unwrap().trim_matches(|c: char| !c.is_alphabetic()); + if maybe_weak_or_immune == "weak" { + let mut weakness = words.nth(1).unwrap(); + weaknesses.push(weakness.trim_matches(|c: char| !c.is_alphabetic()).to_string()); + while weakness.ends_with(',') { + weakness = words.next().unwrap(); + weaknesses.push(weakness.trim_matches(|c: char| !c.is_alphabetic()).to_string()); + } + } + else if maybe_weak_or_immune == "immune" { + let mut immunity = words.nth(1).unwrap(); + immunities.push(immunity.trim_matches(|c: char| !c.is_alphabetic()).to_string()); + while immunity.ends_with(',') { + immunity = words.next().unwrap(); + immunities.push(immunity.trim_matches(|c: char| !c.is_alphabetic()).to_string()); + } + } + else { + bracket_handled = true; + } + } + let damage = words.nth(4).unwrap().parse()?; + let damage_type = words.next().unwrap().to_string(); + let initiative = words.nth(3).unwrap().parse()?; + + Ok(Army { + units, hp, weaknesses, immunities, damage_type, damage, initiative + }) + } +} + + + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/24.txt"))?; + + let mut input_iter = input.iter(); + let _ = input_iter.next(); + let immune_army: Vec = input_iter.by_ref() + .take_while(|&line| line != "Infection:") + .map(|line| line.parse().unwrap()) + .collect(); + let infection_army: Vec = input_iter + .map(|line| line.parse().unwrap()) + .collect(); + + let (unboosted_immune_army_size, unboosted_infection_army_size) = simulate(&immune_army, &infection_army, 0); + debug!(unboosted_immune_army_size); + debug!(unboosted_infection_army_size); + + for boost in 0.. { + debug!(boost); + let (immune_army_size, infection_army_size) = simulate(&immune_army, &infection_army, boost); + debug!(immune_army_size); + debug!(infection_army_size); + if immune_army_size > 0 { + break; + } + } + + Ok(()) +} + + +fn target_selection(targeting_army: &Vec, targeted_army: &Vec) -> HashMap { + let mut targets = HashMap::new(); + for (i, army) in targeting_army.iter().enumerate() { + let best_target = (0..targeted_army.len()) + .filter(|potential_target| !targets.values().any(|targeted| targeted == potential_target)) + .fold(None, |best_target, next| { + let next_actual_damage = army.actual_damage(&targeted_army[next]); + let last_best_actual_damage = best_target.map(|best_target| army.actual_damage(&targeted_army[best_target])).unwrap_or(0); + let next_effective_power = targeted_army[next].effective_power(); + let last_best_effective_power = best_target.map(|best_target: usize| targeted_army[best_target].effective_power()).unwrap_or(0); + let next_initiative = targeted_army[next].initiative; + let last_best_initiative = best_target.map(|best_target| targeted_army[best_target].initiative).unwrap_or(0); + if next_actual_damage == 0 && last_best_actual_damage == 0 { + None + } else if next_actual_damage > last_best_actual_damage { + Some(next) + } else if next_actual_damage == last_best_actual_damage && next_effective_power > last_best_effective_power { + Some(next) + } else if next_actual_damage == last_best_actual_damage && next_effective_power == last_best_effective_power && next_initiative > last_best_initiative { + Some(next) + } else { + best_target + } + }); + + if let Some(best_target) = best_target { + targets.insert(i, best_target); + } + } + + targets +} + +fn attack(aggressor: &Army, target: &mut Army) { + let damage = aggressor.actual_damage(target); + let units_destroyed = damage / target.hp; + target.units = target.units.saturating_sub(units_destroyed); +} + + +fn simulate(immune_army: &[Army], infection_army: &[Army], boost: u32) -> (u32, u32) { + let mut infection_army = Vec::from(infection_army); + + let mut immune_army: Vec = immune_army.iter().map(|army| Army { + damage: army.damage + boost, + ..army.clone() + }).collect(); + + let mut watchdog_sum = immune_army.iter().map(|a| a.units).sum::() + infection_army.iter().map(|a| a.units).sum::(); + while immune_army.len() > 0 && infection_army.len() > 0 { + immune_army.sort_by(|a, b| b.effective_power().cmp(&a.effective_power()).then(b.initiative.cmp(&a.initiative))); + infection_army.sort_by(|a, b| b.effective_power().cmp(&a.effective_power()).then(b.initiative.cmp(&a.initiative))); + + let mut immune_targets = target_selection(&immune_army, &infection_army); + let mut infection_targets = target_selection(&infection_army, &immune_army); + + while immune_targets.len() > 0 || infection_targets.len() > 0 { + let next_immune = immune_targets.keys() + .map(|&k| (k, immune_army[k].initiative.clone())) + .max_by_key(|(_, initiative)| *initiative); + let next_infection = infection_targets.keys() + .map(|&k| (k, infection_army[k].initiative.clone())) + .max_by_key(|(_, initiative)| *initiative); + match (next_immune, next_infection) { + (None, None) => { + panic!("No targets left") + }, + (Some((immune_key, immune_init)), Some((_infect_key, infect_init))) if immune_init > infect_init => { + attack(&immune_army[immune_key], &mut infection_army[*immune_targets.get(&immune_key).unwrap()]); + immune_targets.remove(&immune_key); + }, + (Some((_immune_key, _immune_init)), Some((infect_key, _infect_init))) => { + attack(&infection_army[infect_key], &mut immune_army[*infection_targets.get(&infect_key).unwrap()]); + infection_targets.remove(&infect_key); + }, + (Some((immune_key, _immune_init)), None) => { + attack(&immune_army[immune_key], &mut infection_army[*immune_targets.get(&immune_key).unwrap()]); + immune_targets.remove(&immune_key); + }, + (None, Some((infect_key, _infect_init))) => { + attack(&infection_army[infect_key], &mut immune_army[*infection_targets.get(&infect_key).unwrap()]); + infection_targets.remove(&infect_key); + } + }; + } + + immune_army.retain(|a| a.units > 0); + infection_army.retain(|a| a.units > 0); + + let new_watchdog_sum = immune_army.iter().map(|a| a.units).sum::() + infection_army.iter().map(|a| a.units).sum::(); + if watchdog_sum == new_watchdog_sum { + // Stalemate! Everyone loses. + return (0, 0); + } + watchdog_sum = new_watchdog_sum; + } + + (immune_army.iter().map(|a| a.units).sum(), infection_army.iter().map(|a| a.units).sum()) +} diff --git a/2018/src/bin/day_25.rs b/2018/src/bin/day_25.rs new file mode 100644 index 0000000..9e74f49 --- /dev/null +++ b/2018/src/bin/day_25.rs @@ -0,0 +1,47 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +// cargo watch -cs "cargo run --release --bin day_25" + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/25.txt"))?; + + let mut constellations: Vec>> = input.iter() + .map(|line| line.split(',').map(|x| x.parse().unwrap()).collect::>()) + .map(|points| vec!(points)) + .collect(); + + // debug!(constellations); + + while join_constellations(&mut constellations) { + } + + debug!(constellations.len()); + + Ok(()) +} + +fn distance(xs: &[i32], ys: &[i32]) -> i32 { + xs.iter().zip(ys.iter()).map(|(x,y)| (x - y).abs()).sum() +} + +fn join_constellations(constellations: &mut Vec>>) -> bool { + for i in 0..constellations.len()-1 { + for j in i+1..constellations.len() { + let connected = constellations[i].iter().any(|ci| { + constellations[j].iter().any(|cj| { + distance(&ci, &cj) <= 3 + }) + }); + if connected { + let mut to_join = constellations.remove(j); + constellations[i].append(&mut to_join); + return true; + } + } + } + false +} diff --git a/2018/src/bin/day_3.rs b/2018/src/bin/day_3.rs new file mode 100644 index 0000000..685e288 --- /dev/null +++ b/2018/src/bin/day_3.rs @@ -0,0 +1,76 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::str::FromStr; + +use std::error::Error; +use std::path::PathBuf; + +use std::collections::HashMap; + +// cargo watch -cs "cargo run --release --bin day_3" + +#[derive(Debug)] +struct Claim { + id: u32, + x: u32, + y: u32, + w: u32, + h: u32 +} + +impl FromStr for Claim { + type Err = Box; + + fn from_str(s: &str) -> Result { + //#123 @ 3,2: 5x4 + let split = s + .split(|c: char| !c.is_numeric()) + .filter(|s| !s.is_empty()) + .map(|s| s.parse()) + .collect::, _>>()?; + + Ok(Claim { + id: split[0], + x: split[1], + y: split[2], + w: split[3], + h: split[4] + }) + } +} + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/3.txt"))?; + let claims = input.iter().map(|line| line.parse::()).collect::, _>>()?; + + let mut claimed = HashMap::new(); + for claim in &claims { + for x in claim.x..claim.x+claim.w { + for y in claim.y..claim.y+claim.h { + *claimed.entry((x,y)).or_insert(0) += 1; + } + } + } + + let conflicts = claimed.values().filter(|&x| *x > 1).count(); + println!("Conflicts: {}", conflicts); + + let conflict_free = claims.iter().filter(|c| check_for_conflicts(c, &claimed)).collect::>(); + + println!("Conflict free: {:?}", conflict_free); + + Ok(()) +} + + +fn check_for_conflicts(claim: &Claim, claimed: &HashMap<(u32, u32), u32>) -> bool { + for x in claim.x..claim.x+claim.w { + for y in claim.y..claim.y+claim.h { + if claimed.get(&(x,y)).map_or(false, |c| *c > 1) { + return false; + } + } + } + true +} diff --git a/2018/src/bin/day_4.rs b/2018/src/bin/day_4.rs new file mode 100644 index 0000000..2010cf8 --- /dev/null +++ b/2018/src/bin/day_4.rs @@ -0,0 +1,116 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::str::FromStr; + +use std::error::Error; +use std::path::PathBuf; +use std::collections::HashMap; + +// cargo watch -cs "cargo run --release --bin day_4" + +#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)] +struct Event { + date: String, + hour: u32, + minute: u32, + what: EventType +} + +#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)] +enum EventType { + BeginShift(u32), + Asleep, + Awake +} + +impl FromStr for Event { + type Err = Box; + + fn from_str(s: &str) -> Result { + let date = s.split_whitespace().nth(0).unwrap().trim_matches('[').to_string(); + let time = s.split_whitespace().nth(1).unwrap().trim_matches(']'); + let hour = time.split(':').nth(0).unwrap().parse().unwrap(); + let minute = time.split(':').nth(1).unwrap().parse().unwrap(); + let guard = s.split_whitespace().nth(3).and_then(|x| x.trim_matches('#').parse().ok()); + + let what = match s.split_whitespace().nth(2).unwrap() { + "Guard" => EventType::BeginShift(guard.unwrap()), + "falls" => EventType::Asleep, + "wakes" => EventType::Awake, + _ => panic!("Unknown event") + }; + + Ok(Event { + date, + hour, + minute, + what + }) + } +} + +#[derive(Debug)] +struct GuardSleepStats { + per_minute: HashMap +} + +impl GuardSleepStats { + fn new() -> GuardSleepStats { + GuardSleepStats { + per_minute: HashMap::new() + } + } + fn total(&self) -> u32 { + self.per_minute.values().sum() + } +} + + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/4.txt"))?; + + //println!("Input: {:?}", input); + + let mut events: Vec = input.iter().map(|line| line.parse().unwrap()).collect(); + events.sort(); + //println!("Events: {:?}", events); + + + let mut sleep = HashMap::new(); + let mut current_guard = 0; + let mut last_asleep = 0; + for event in events { + match event.what { + EventType::BeginShift(guard) => current_guard = guard, + EventType::Asleep => last_asleep = event.minute, + EventType::Awake => { + for i in last_asleep..event.minute { + *sleep + .entry(current_guard) + .or_insert(GuardSleepStats::new()) + .per_minute + .entry(i) + .or_insert(0) += 1 + } + } + } + } + + println!("Stats: {:?}", sleep); + + let (sleepiest_guard, sleepiest_stats) = sleep.iter().max_by_key(|(_,v)| v.total()).unwrap().clone(); + println!("Sleepiest guard: {:?}", sleepiest_guard); + let (sleepiest_minute, sleepiest_occurances) = sleepiest_stats.per_minute.iter().max_by_key(|(_,v)| *v).unwrap().clone(); + println!("Sleepiest minute: {:?}", sleepiest_minute); + println!("Part 1 answer: {}", sleepiest_guard * sleepiest_minute); + + + let (specific_minute_offender, specific_minute_stats) = sleep.iter().max_by_key(|(_,v)| v.per_minute.values().max().unwrap()).unwrap().clone(); + println!("Specific minute: {:?}", specific_minute_offender); + let (specific_minute_minute, specific_minute_occurances) = specific_minute_stats.per_minute.iter().max_by_key(|(_,v)| *v).unwrap().clone(); + println!("Specific Minute minute: {:?}", specific_minute_minute); + println!("Part 2 answer: {}", specific_minute_offender * specific_minute_minute); + + Ok(()) +} diff --git a/2018/src/bin/day_5.rs b/2018/src/bin/day_5.rs new file mode 100644 index 0000000..2b24d4c --- /dev/null +++ b/2018/src/bin/day_5.rs @@ -0,0 +1,53 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; +use std::cmp; + +// cargo watch -cs "cargo run --release --bin day_5" + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/5.txt"))?; + + //println!("Input: {:?}", input); + let polymer = { + let mut polymer: Vec = input[0].chars().collect(); + reduce(&mut polymer); + polymer + }; + + debug!(polymer.len()); + + + let mut min_length = polymer.len(); + for c in "abcdefghijklmnopqrstuvwxyz".chars() { + let mut polymer_without_char = polymer.clone(); + polymer_without_char.retain(|x| x.to_ascii_lowercase() != c); + reduce(&mut polymer_without_char); + min_length = cmp::min(min_length, polymer_without_char.len()); + } + + debug!(min_length); + + Ok(()) +} + + +fn reduce(polymer: &mut Vec) { + let mut had_reductions = true; + while had_reductions { + had_reductions = false; + + for i in 0..polymer.len()-1 { + if polymer[i].to_ascii_lowercase() == polymer[i+1].to_ascii_lowercase() && polymer[i] != polymer[i+1] { + had_reductions = true; + polymer.remove(i+1); + polymer.remove(i); + + // break isn't efficient, but does prevent indexing issues after removing + break; + } + } + } +} diff --git a/2018/src/bin/day_6.rs b/2018/src/bin/day_6.rs new file mode 100644 index 0000000..16c8782 --- /dev/null +++ b/2018/src/bin/day_6.rs @@ -0,0 +1,103 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +use std::collections::{HashSet, HashMap}; + +// cargo watch -cs "cargo run --release --bin day_6" + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/6.txt"))?; + let coordinates = input.iter().map(|line| { + let mut split = line.split(|c: char| !c.is_numeric()); + let x: i32 = split.next().unwrap().parse().unwrap(); + let _ = split.next(); + let y: i32 = split.next().unwrap().parse().unwrap(); + (x, y) + }).collect::>(); + debug!(coordinates); + + let min_x = coordinates.iter().map(|(x, _)| x).min().unwrap().clone(); + let max_x = coordinates.iter().map(|(x, _)| x).max().unwrap().clone(); + let min_y = coordinates.iter().map(|(_, y)| y).min().unwrap().clone(); + let max_y = coordinates.iter().map(|(_, y)| y).max().unwrap().clone(); + + debug!(min_x); + debug!(max_x); + debug!(min_y); + debug!(max_y); + + let mut infinite = HashSet::new(); + for x in min_x..max_x+1 { + for y in &[0, max_y] { + if let Some(coord) = find_closest(&coordinates, x, *y) { + infinite.insert(coord); + } + } + } + for y in min_y..max_y+1 { + for x in &[0, max_x] { + if let Some(coord) = find_closest(&coordinates, *x, y) { + infinite.insert(coord); + } + } + } + + debug!(infinite); + + + let mut areas = HashMap::new(); + for x in min_x..max_x+1 { + for y in min_y..max_y+1 { + if let Some(coord) = find_closest(&coordinates, x, y) { + *areas.entry(coord).or_insert(0) += 1; + } + } + } + + debug!(areas); + + let biggest_non_infinite = areas.iter() + .filter(|(k,_)| !infinite.contains(&k)) + .max_by_key(|(_,v)| *v); + debug!(biggest_non_infinite); + + + + let safe_distance = 10000; + let mut safe_size = 0; + for x in min_x..max_x+1 { + for y in min_y..max_y+1 { + let distance_sum: i32 = coordinates.iter() + .map(|(x1, y1)| manhattan_distance(*x1, *y1, x, y)) + .sum(); + if distance_sum < safe_distance { + safe_size += 1; + } + } + } + debug!(safe_size); + + Ok(()) +} + +fn find_closest(coordinates: &Vec<(i32, i32)>, x: i32, y: i32) -> Option { + let mut distances = coordinates.iter() + .map(|(x1, y1)| manhattan_distance(*x1, *y1, x, y)) + .enumerate() + .collect::>(); + distances.sort_by_key(|(_, d)| *d); + + if distances[0] == distances[1] { + None + } + else { + distances.first().map(|(i, _)| *i) + } +} + +fn manhattan_distance(x1: i32, y1: i32, x2: i32, y2: i32) -> i32 { + (x2-x1).abs() + (y2-y1).abs() +} diff --git a/2018/src/bin/day_7.rs b/2018/src/bin/day_7.rs new file mode 100644 index 0000000..ec9d0be --- /dev/null +++ b/2018/src/bin/day_7.rs @@ -0,0 +1,135 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +use std::collections::{HashMap, HashSet}; + +// cargo watch -cs "cargo run --release --bin day_7" + +fn main() -> Result<(), Box> { + let input = read_file(&PathBuf::from("inputs/7.txt"))?; + + //println!("Input: {:?}", input); + + let (all_steps, blockers) = parse(&input); + + + let mut serial_ordered = Vec::new(); + let mut remaining_steps = all_steps.clone(); + let mut remaining_blockers = blockers.clone(); + + while !remaining_steps.is_empty() { + let mut unblocked: Vec = remaining_steps.iter() + .filter(|c| remaining_blockers.get(c).map(|blockers| blockers.is_empty()).unwrap_or(true)) + .cloned() + .collect(); + unblocked.sort(); + + let next_step = unblocked.first().unwrap().clone(); + + serial_ordered.push(next_step); + remaining_steps.remove(&next_step); + for (_k, mut v) in &mut remaining_blockers { + v.retain(|c| *c != next_step); + } + } + + debug!(serial_ordered); + for c in serial_ordered { + print!("{}", c); + } + println!(); + + + let workers = 5; + let mut worker_tasks: Vec = Vec::new(); + let mut parallel_ordered = Vec::new(); + let mut remaining_steps = all_steps.clone(); + let mut remaining_blockers = blockers.clone(); + let mut current_time = 0; + + while !remaining_steps.is_empty() { + let mut unblocked: Vec = remaining_steps.iter() + .filter(|c| + remaining_blockers.get(c).map(|blockers| blockers.is_empty()).unwrap_or(true) + && !worker_tasks.iter().any(|w| w.t == **c) + ) + .cloned() + .collect(); + unblocked.sort(); + + let next_unblocked = if worker_tasks.len() < workers { + unblocked.first().cloned() + } else { + None + }; + + if let Some(next_task) = next_unblocked { + worker_tasks.push(Task { + t: next_task, + completion: current_time + time(next_task) + }); + } + else { + //Advance time + worker_tasks.sort_by_key(|w| w.completion); + let complete = worker_tasks.swap_remove(0); + current_time = complete.completion; + let next_step = complete.t; + + parallel_ordered.push(next_step); + remaining_steps.remove(&next_step); + for (_k, mut v) in &mut remaining_blockers { + v.retain(|c| *c != next_step); + } + } + + + } + + debug!(parallel_ordered); + for c in parallel_ordered { + print!("{}", c); + } + println!(); + debug!(current_time); + + + Ok(()) +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +struct Task { + t: char, + completion: u32 +} + + +fn parse(input: &Vec) -> (HashSet, HashMap>) { + let mut blockers = HashMap::new(); + let mut all_steps = HashSet::new(); + + for line in input { + //Step I must be finished before step C can begin. + let mut split = line.split_whitespace(); + let blocker: char = split.nth(1).and_then(|x| x.chars().nth(0)).unwrap(); + let blocked: char = split.nth(5).and_then(|x| x.chars().nth(0)).unwrap(); + + blockers.entry(blocked).or_insert(Vec::new()).push(blocker); + all_steps.insert(blocker); + all_steps.insert(blocked); + } + + debug!(all_steps); + debug!(blockers); + + (all_steps, blockers) +} + +fn time(c: char) -> u32 { + let base_time = 60; + let char_time = c as u32 - 'A' as u32 + 1; + base_time + char_time +} diff --git a/2018/src/bin/day_8.rs b/2018/src/bin/day_8.rs new file mode 100644 index 0000000..59813b0 --- /dev/null +++ b/2018/src/bin/day_8.rs @@ -0,0 +1,66 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; +use std::path::PathBuf; + +use std::slice::Iter; + +// cargo watch -cs "cargo run --release --bin day_8" + +fn main() -> Result<(), Box> { + let input: Vec = read_file(&PathBuf::from("inputs/8.txt")) + .map(|lines| lines[0] + .split_whitespace() + .map(|s| s.parse().unwrap()) + .collect() + )?; + + //println!("Input: {:?}", input); + + let metadata_sum = sum_metadata(&mut input.iter()); + debug!(metadata_sum); + + let value = node_value(&mut input.iter()); + debug!(value); + + Ok(()) +} + +fn sum_metadata(iter: &mut Iter<'_, u32>) -> u32 { + let num_children = iter.next().unwrap().clone(); + let num_metadata = iter.next().unwrap().clone(); + + let children_sum: u32 = (0..num_children) + .map(|_| sum_metadata(iter)) + .sum(); + + let metadata_sum: u32 = (0..num_metadata) + .map(|_| iter.next().unwrap()) + .sum(); + + children_sum + metadata_sum +} + + +fn node_value(iter: &mut Iter<'_, u32>) -> u32 { + let num_children = iter.next().unwrap().clone(); + let num_metadata = iter.next().unwrap().clone(); + + let node_values: Vec = (0..num_children) + .map(|_| node_value(iter)) + .collect(); + + let metadata: Vec = (0..num_metadata) + .map(|_| iter.next().unwrap().clone()) + .collect(); + + if num_children == 0 { + metadata.iter().sum() + } else { + metadata.iter() + .filter(|m| **m > 0 && **m-1 < num_children) + .map(|m| node_values[*m as usize - 1]) + .sum() + } +} diff --git a/2018/src/bin/day_9.rs b/2018/src/bin/day_9.rs new file mode 100644 index 0000000..3f85620 --- /dev/null +++ b/2018/src/bin/day_9.rs @@ -0,0 +1,91 @@ +extern crate advent_of_code_2018; +use advent_of_code_2018::*; + +use std::error::Error; + +use std::collections::LinkedList; + +// cargo watch -cs "cargo run --release --bin day_9" + +fn main() -> Result<(), Box> { + debug!(get_winning_player_score(438, 71626)); + debug!(get_winning_player_score(438, 71626*100)); + + Ok(()) +} + + +fn get_winning_player_score(players: usize, last_marble_score: u32) -> u32 { + let mut marbles_head = LinkedList::new(); + let mut marbles_tail = LinkedList::new(); + marbles_head.push_back(0); + + let mut current_player = 0; + let mut next_marble = 1; + let mut scores = vec!(0; players); + + while next_marble <= last_marble_score { + if next_marble % 23 == 0 { + move_backwards(&mut marbles_head, &mut marbles_tail, 7); + let removed = marbles_head.pop_back().expect("Going backwards should have ended with pushing to head"); + move_forward(&mut marbles_head, &mut marbles_tail, 1); + + let score = next_marble + removed; + scores[current_player] += score; + } else { + move_forward(&mut marbles_head, &mut marbles_tail, 1); + marbles_head.push_back(next_marble); + } + + next_marble += 1; + current_player = (current_player + 1) % players; + } + + scores.iter().max().unwrap().clone() +} + +// WARNING: These don't play well with empty lists +fn move_forward(marbles_head: &mut LinkedList, marbles_tail: &mut LinkedList, i: usize) { + if i != 0 { + match marbles_tail.pop_front() { + Some(marble) => { + marbles_head.push_back(marble); + move_forward(marbles_head, marbles_tail, i-1); + }, + None => { + marbles_tail.append(marbles_head); + move_forward(marbles_head, marbles_tail, i); + }, + } + } +} + +fn move_backwards(marbles_head: &mut LinkedList, marbles_tail: &mut LinkedList, i: usize) { + if i != 0 { + match marbles_head.pop_back() { + Some(marble) => { + marbles_tail.push_front(marble); + move_backwards(marbles_head, marbles_tail, i-1); + }, + None => { + marbles_head.append(marbles_tail); + move_backwards(marbles_head, marbles_tail, i); + }, + } + } +} + + +#[test] +fn trivial() { + assert_eq!(get_winning_player_score(9, 32), 32); +} + +#[test] +fn examples() { + assert_eq!(get_winning_player_score(10, 1618), 8317); + assert_eq!(get_winning_player_score(13, 7999), 146373); + assert_eq!(get_winning_player_score(17, 1104), 2764); + assert_eq!(get_winning_player_score(21, 6111), 54718); + assert_eq!(get_winning_player_score(30, 5807), 37305); +} -- cgit v1.2.3