summaryrefslogtreecommitdiff
path: root/2018/src/bin
diff options
context:
space:
mode:
Diffstat (limited to '2018/src/bin')
-rw-r--r--2018/src/bin/day_1.rs32
-rw-r--r--2018/src/bin/day_10.rs82
-rw-r--r--2018/src/bin/day_11.rs66
-rw-r--r--2018/src/bin/day_12.rs102
-rw-r--r--2018/src/bin/day_13.rs249
-rw-r--r--2018/src/bin/day_14.rs111
-rw-r--r--2018/src/bin/day_15.rs272
-rw-r--r--2018/src/bin/day_16.rs205
-rw-r--r--2018/src/bin/day_17.rs175
-rw-r--r--2018/src/bin/day_18.rs123
-rw-r--r--2018/src/bin/day_19.rs139
-rw-r--r--2018/src/bin/day_2.rs53
-rw-r--r--2018/src/bin/day_20.rs137
-rw-r--r--2018/src/bin/day_21.rs137
-rw-r--r--2018/src/bin/day_22.rs165
-rw-r--r--2018/src/bin/day_23.rs114
-rw-r--r--2018/src/bin/day_24.rs217
-rw-r--r--2018/src/bin/day_25.rs47
-rw-r--r--2018/src/bin/day_3.rs76
-rw-r--r--2018/src/bin/day_4.rs116
-rw-r--r--2018/src/bin/day_5.rs53
-rw-r--r--2018/src/bin/day_6.rs103
-rw-r--r--2018/src/bin/day_7.rs135
-rw-r--r--2018/src/bin/day_8.rs66
-rw-r--r--2018/src/bin/day_9.rs91
25 files changed, 3066 insertions, 0 deletions
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<Error>> {
+ let input = read_file(&PathBuf::from("inputs/1.txt"))?;
+ let input_ints: Vec<i32> = input.iter().map(|str| str.parse::<i32>().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<Error>;
+
+ fn from_str(s: &str) -> Result<Self, Self::Err> {
+ let split = s
+ .split(|c: char| c != '-' && !c.is_numeric())
+ .filter(|s| !s.is_empty())
+ .map(|s| s.parse())
+ .collect::<Result<Vec<i32>, _>>()?;
+
+ Ok(Star {
+ x: split[0],
+ y: split[1],
+ dx: split[2],
+ dy: split[3]
+ })
+ }
+}
+
+fn main() -> Result<(), Box<Error>> {
+ let input = read_file(&PathBuf::from("inputs/10.txt"))?;
+ let mut stars = input.iter().map(|line| line.parse::<Star>().unwrap()).collect::<Vec<_>>();
+
+ //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<Error>> {
+ 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::<Vec<_>>();
+
+ 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::<i32>()
+ }).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<Error>;
+
+ fn from_str(s: &str) -> Result<Self, Self::Err> {
+ //##..# => #
+ 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<i64>, 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<Error>> {
+ let input = read_file(&PathBuf::from("inputs/12.txt"))?;
+
+ println!("Input: {:?}", input);
+
+ let mut initial_state: HashSet<i64> = 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::<Result<Vec<Rule>, Box<Error>>>()?;
+
+ 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<i64>, rules: &[Rule], time: i64) -> HashSet<i64> {
+ 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(&current_state, i)).expect("No matching rule").output {
+ new_state.insert(i as i64);
+ }
+ }
+
+ if current_state.iter().map(|v| v + 1).collect::<HashSet<i64>>() == 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::<HashSet<i64>>();
+ }
+
+ 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<Error>> {
+ let input = read_file(&PathBuf::from("inputs/13.txt"))?;
+
+// for i in &input {
+// println!("{}", i);
+// }
+
+ let mut map: Vec<Vec<Road>> = Vec::new();
+ let mut carts: Vec<Cart> = 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::<Vec<_>>();
+ 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<Error>> {
+ 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<usize> {
+ 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<usize> {
+ 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<Error>> {
+ 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::<i32>();
+ 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<Vec<bool>>) -> 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::<Vec<_>>();
+ 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<Vec<bool>>, 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<usize> {
+ [(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<usize> {
+ 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<Vec<bool>>) {
+ 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::<Vec<String>>();
+ 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> {
+ 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<Error>> {
+ let input_part_1 = read_file(&PathBuf::from("inputs/16_1.txt"))?;
+
+ let unknown_instructions: Vec<UnknownInstruction> = 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::<i32>().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::<i32>().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::<i32>().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<i32, HashSet<Op>> = 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<i32, Op> = 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<Instruction> = input_part_2.iter()
+ .map(|line| {
+ let mut instruction_iter = line.split_whitespace().map(|c| c.parse::<i32>().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(&registers);
+ }
+ 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<usize>,
+ xmax: Option<usize>,
+ ymin: Option<usize>,
+ ymax: Option<usize>
+}
+
+#[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<Error>> {
+ 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::<Vec<_>>();
+
+ 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<Error>> {
+ 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::<Vec<_>>()
+ }).collect::<Vec<_>>();
+// 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<Vec<State>>, duration: u32) -> Vec<Vec<State>> {
+ 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::<ArrayVec<[State; 8]>>();
+
+ 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<Vec<State>>) {
+ 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<Error>> {
+ 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<Instruction> = 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<Instruction>, 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<Error>> {
+ 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<Dir>
+}
+
+impl Room {
+ fn new() -> Room {
+ Room {
+ doors: HashSet::new()
+ }
+ }
+}
+
+fn main() -> Result<(), Box<Error>> {
+ 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::<Vec<_>>()
+ })
+ .collect::<Vec<_>>();
+ 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<Error>> {
+ 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<Instruction> = 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<Instruction>, 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(&registers[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<u32>>) -> 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<Error>> {
+ 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::<u32>().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::<u32>()).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(&current);
+ }
+
+ debug!(distances.get(&target));
+
+ Ok(())
+}
+
+
+fn build_map(max_x: u32, max_y: u32, depth: u32, target_x: u32, target_y: u32) -> Vec<Vec<u32>> {
+ let mut geologic_index: Vec<Vec<u32>> = Vec::new();
+ let mut erosion_level: Vec<Vec<u32>> = Vec::new();
+ let mut region_type: Vec<Vec<u32>> = 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<Error>> {
+ let input = read_file(&PathBuf::from("inputs/23.txt"))?;
+
+ let mut bots: Vec<Bot> = 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::<i64>().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<Position> = 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::<Vec<_>>()
+ }).collect::<Vec<_>>()
+ }).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(&center) <= 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<String>,
+ immunities: Vec<String>,
+ 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<Error>;
+
+ fn from_str(s: &str) -> Result<Self, Self::Err> {
+ // 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<Error>> {
+ let input = read_file(&PathBuf::from("inputs/24.txt"))?;
+
+ let mut input_iter = input.iter();
+ let _ = input_iter.next();
+ let immune_army: Vec<Army> = input_iter.by_ref()
+ .take_while(|&line| line != "Infection:")
+ .map(|line| line.parse().unwrap())
+ .collect();
+ let infection_army: Vec<Army> = 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<Army>, targeted_army: &Vec<Army>) -> HashMap<usize, usize> {
+ 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<Army> = 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::<u32>() + infection_army.iter().map(|a| a.units).sum::<u32>();
+ 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::<u32>() + infection_army.iter().map(|a| a.units).sum::<u32>();
+ 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<Error>> {
+ let input = read_file(&PathBuf::from("inputs/25.txt"))?;
+
+ let mut constellations: Vec<Vec<Vec<i32>>> = input.iter()
+ .map(|line| line.split(',').map(|x| x.parse().unwrap()).collect::<Vec<_>>())
+ .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<Vec<Vec<i32>>>) -> 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<Error>;
+
+ fn from_str(s: &str) -> Result<Self, Self::Err> {
+ //#123 @ 3,2: 5x4
+ let split = s
+ .split(|c: char| !c.is_numeric())
+ .filter(|s| !s.is_empty())
+ .map(|s| s.parse())
+ .collect::<Result<Vec<u32>, _>>()?;
+
+ Ok(Claim {
+ id: split[0],
+ x: split[1],
+ y: split[2],
+ w: split[3],
+ h: split[4]
+ })
+ }
+}
+
+fn main() -> Result<(), Box<Error>> {
+ let input = read_file(&PathBuf::from("inputs/3.txt"))?;
+ let claims = input.iter().map(|line| line.parse::<Claim>()).collect::<Result<Vec<_>, _>>()?;
+
+ 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::<Vec<_>>();
+
+ 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<Error>;
+
+ fn from_str(s: &str) -> Result<Self, Self::Err> {
+ 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<u32, u32>
+}
+
+impl GuardSleepStats {
+ fn new() -> GuardSleepStats {
+ GuardSleepStats {
+ per_minute: HashMap::new()
+ }
+ }
+ fn total(&self) -> u32 {
+ self.per_minute.values().sum()
+ }
+}
+
+
+fn main() -> Result<(), Box<Error>> {
+ let input = read_file(&PathBuf::from("inputs/4.txt"))?;
+
+ //println!("Input: {:?}", input);
+
+ let mut events: Vec<Event> = 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<Error>> {
+ let input = read_file(&PathBuf::from("inputs/5.txt"))?;
+
+ //println!("Input: {:?}", input);
+ let polymer = {
+ let mut polymer: Vec<char> = 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<char>) {
+ 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<Error>> {
+ 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::<Vec<_>>();
+ 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<usize> {
+ let mut distances = coordinates.iter()
+ .map(|(x1, y1)| manhattan_distance(*x1, *y1, x, y))
+ .enumerate()
+ .collect::<Vec<_>>();
+ 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<Error>> {
+ 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<char> = 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<Task> = 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<char> = 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<String>) -> (HashSet<char>, HashMap<char, Vec<char>>) {
+ 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<Error>> {
+ let input: Vec<u32> = 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<u32> = (0..num_children)
+ .map(|_| node_value(iter))
+ .collect();
+
+ let metadata: Vec<u32> = (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<Error>> {
+ 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<u32>, marbles_tail: &mut LinkedList<u32>, 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<u32>, marbles_tail: &mut LinkedList<u32>, 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);
+}