From c99848b907d2d63577ffdc81fc11a77e4d328a92 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Tue, 19 Apr 2022 20:24:37 +0200 Subject: Refile for merging repos --- 2017/src/bin/day_1.rs | 24 ++++++ 2017/src/bin/day_10.rs | 63 ++++++++++++++ 2017/src/bin/day_11.rs | 57 +++++++++++++ 2017/src/bin/day_12.rs | 52 ++++++++++++ 2017/src/bin/day_13.rs | 46 ++++++++++ 2017/src/bin/day_14.rs | 52 ++++++++++++ 2017/src/bin/day_15.rs | 40 +++++++++ 2017/src/bin/day_16.rs | 87 +++++++++++++++++++ 2017/src/bin/day_17.rs | 47 +++++++++++ 2017/src/bin/day_18.rs | 207 +++++++++++++++++++++++++++++++++++++++++++++ 2017/src/bin/day_19.rs | 78 +++++++++++++++++ 2017/src/bin/day_2.rs | 26 ++++++ 2017/src/bin/day_20.rs | 89 +++++++++++++++++++ 2017/src/bin/day_21.rs | 200 +++++++++++++++++++++++++++++++++++++++++++ 2017/src/bin/day_22.rs | 73 ++++++++++++++++ 2017/src/bin/day_23.rs | 168 ++++++++++++++++++++++++++++++++++++ 2017/src/bin/day_24.rs | 60 +++++++++++++ 2017/src/bin/day_25.rs | 125 +++++++++++++++++++++++++++ 2017/src/bin/day_3.rs | 62 ++++++++++++++ 2017/src/bin/day_4.rs | 37 ++++++++ 2017/src/bin/day_5.rs | 25 ++++++ 2017/src/bin/day_6.rs | 61 ++++++++++++++ 2017/src/bin/day_7.rs | 62 ++++++++++++++ 2017/src/bin/day_8.rs | 99 ++++++++++++++++++++++ 2017/src/bin/day_9.rs | 42 +++++++++ 2017/src/lib.rs | 225 +++++++++++++++++++++++++++++++++++++++++++++++++ 26 files changed, 2107 insertions(+) create mode 100644 2017/src/bin/day_1.rs create mode 100644 2017/src/bin/day_10.rs create mode 100644 2017/src/bin/day_11.rs create mode 100644 2017/src/bin/day_12.rs create mode 100644 2017/src/bin/day_13.rs create mode 100644 2017/src/bin/day_14.rs create mode 100644 2017/src/bin/day_15.rs create mode 100644 2017/src/bin/day_16.rs create mode 100644 2017/src/bin/day_17.rs create mode 100644 2017/src/bin/day_18.rs create mode 100644 2017/src/bin/day_19.rs create mode 100644 2017/src/bin/day_2.rs create mode 100644 2017/src/bin/day_20.rs create mode 100644 2017/src/bin/day_21.rs create mode 100644 2017/src/bin/day_22.rs create mode 100644 2017/src/bin/day_23.rs create mode 100644 2017/src/bin/day_24.rs create mode 100644 2017/src/bin/day_25.rs create mode 100644 2017/src/bin/day_3.rs create mode 100644 2017/src/bin/day_4.rs create mode 100644 2017/src/bin/day_5.rs create mode 100644 2017/src/bin/day_6.rs create mode 100644 2017/src/bin/day_7.rs create mode 100644 2017/src/bin/day_8.rs create mode 100644 2017/src/bin/day_9.rs create mode 100644 2017/src/lib.rs (limited to '2017/src') diff --git a/2017/src/bin/day_1.rs b/2017/src/bin/day_1.rs new file mode 100644 index 0000000..5d0e431 --- /dev/null +++ b/2017/src/bin/day_1.rs @@ -0,0 +1,24 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + + let number_chars = args.input[0].chars().collect::>(); + + let mut sum = 0; + + for i in 0..number_chars.len() { + let next = if args.part == 1 { + (i + 1) + } else { + (i + number_chars.len() / 2) + } % number_chars.len(); + if (number_chars[i] == number_chars[next]) { + let parsed: i32 = number_chars[i].to_string().parse().unwrap(); + sum += parsed; + } + } + + println!("Sum is {}", sum); +} diff --git a/2017/src/bin/day_10.rs b/2017/src/bin/day_10.rs new file mode 100644 index 0000000..faec18a --- /dev/null +++ b/2017/src/bin/day_10.rs @@ -0,0 +1,63 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + + let lengths: Vec = if args.part == 1 { + args.input[0].split(",").map(|x| x.parse().unwrap()).collect() + } else { + let suffix: [usize; 5] = [17, 31, 73, 47, 23]; + args.input[0].as_bytes() + .iter().map(|&x| x as usize) + .chain(suffix.iter().cloned()) + .collect() + }; + + let mut position = 0; + let mut list: Vec = (0..256).collect(); + + if args.part == 1 { + hash_round(&mut list, &lengths, &mut position, 0); + } else { + for i in 0..64 { + let skip = lengths.len() * i; + hash_round(&mut list, &lengths, &mut position, skip); + } + } + + + if args.part == 1 { + let answer = list[0]*list[1]; + println!("{}", answer); + } else { + let mut current_char = 0; + for (i, l) in list.iter().enumerate() { + current_char = current_char ^ l; + if i % 16 == 15 { + print!("{:02x}", current_char); + current_char = 0; + } + } + println!(""); + } +} + +fn hash_round(list: &mut Vec, lengths: &Vec, position: &mut usize, skip: usize) { + for (inner_skip, &length) in lengths.iter().enumerate() { + reverse(list, *position, length); + *position = (*position + length + skip + inner_skip) % list.len(); + } +} + +fn reverse(list: &mut Vec, position: usize, length: usize) { + let mut a = position; + let mut b = position + length - 1; + let len = list.len(); + while a < b { + list.swap(a%len, b%len); + + a += 1; + b -= 1; + } +} diff --git a/2017/src/bin/day_11.rs b/2017/src/bin/day_11.rs new file mode 100644 index 0000000..ffb0833 --- /dev/null +++ b/2017/src/bin/day_11.rs @@ -0,0 +1,57 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + + let directions: Vec<&str> = args.input[0].split(",").collect(); + + let mut x = 0.0; + let mut y = 0.0; + + let mut max_away = 0.0; + + for dir in directions { + y += match dir { + "ne" => 0.5, + "n" => 1.0, + "nw" => 0.5, + "se" => -0.5, + "s" => -1.0, + "sw" => -0.5, + _ => panic!("Unexpected direction {}", dir) + }; + + x += match dir { + "ne" => -0.5, + "n" => 0.0, + "nw" => 0.5, + "se" => -0.5, + "s" => 0.0, + "sw" => 0.5, + _ => panic!("Unexpected direction {}", dir) + }; + + let current_distance = tile_distance(x, y); + if current_distance > max_away { + max_away = current_distance; + } + } + + if args.part == 1 { + println!("Child process is {} away", tile_distance(x, y)); + } else { + println!("At most, child process was {} away", max_away); + } + +} + +fn tile_distance(x: f32, y: f32) -> f32 { + let tiles_x = x.abs()*2.0; + let tiles_y = if y.abs() < tiles_x { + 0.0 + } else { + y.abs() - tiles_x + }; + tiles_x + tiles_y +} diff --git a/2017/src/bin/day_12.rs b/2017/src/bin/day_12.rs new file mode 100644 index 0000000..39f05e9 --- /dev/null +++ b/2017/src/bin/day_12.rs @@ -0,0 +1,52 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +use std::cmp; + +fn main() { + let args = AdventArgs::init(); + + let mut groups: Vec> = vec!(vec!(0)); //0 in the first group + + for line in args.input { + let mut words_iter = line.split_whitespace(); + let current: i32 = words_iter.next().unwrap().parse().unwrap(); + if find_group(&groups, current).is_none() { + groups.push(vec!(current)); + } + words_iter.next().unwrap(); //<-> + for other_str in words_iter { + let other: i32 = other_str.trim_right_matches(",").parse().unwrap(); + + match (find_group(&groups, current), find_group(&groups, other)) { + (Some(current_group), Some(other_group)) if current_group != other_group => { + merge_groups(&mut groups, current_group, other_group); + }, + (Some(_), Some(_)) => { + }, + (Some(current_group), None) => { + groups[current_group].push(other); + }, + (None, _) => panic!("Current group not found!") + }; + } + } + + if args.part == 1 { + println!("First group has {} members", groups[0].len()); + } else { + println!("Total of {} groups", groups.len()); + } +} + +fn find_group(groups: &Vec>, x: i32) -> Option { + groups.iter().position(|group| group.contains(&x)) +} + +fn merge_groups(groups: &mut Vec>, a: usize, b: usize) { + let src = cmp::max(a, b); + let dest = cmp::min(a, b); + + let mut from = groups.swap_remove(src); + groups[dest].append(&mut from) +} diff --git a/2017/src/bin/day_13.rs b/2017/src/bin/day_13.rs new file mode 100644 index 0000000..e85b541 --- /dev/null +++ b/2017/src/bin/day_13.rs @@ -0,0 +1,46 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +use std::collections::HashMap; + +fn main() { + let args = AdventArgs::init(); + + let input: HashMap = args.input.iter().map(|line| { + let mut split_line = line.split(": "); + (split_line.next().unwrap().parse().unwrap(), split_line.next().unwrap().parse().unwrap()) + }).collect(); + + if args.part == 1 { + let severity = calculate_severity(&input, 0, &args); + println!("Severity: {}", severity); + } else { + let optimal_delay = (0u32..).find(|&delay| calculate_severity(&input, delay, &args) == 0).unwrap(); + println!("Wait {} picoseconds", optimal_delay); + } +} + +fn calculate_severity(input: &HashMap, delay: u32, args: &AdventArgs) -> u32 { + let mut severity = 0; + let max_depth = input.keys().max().cloned().unwrap(); + + for depth in 0..max_depth+1 { + severity += match input.get(&depth) { + Some(range) => { + let position = (depth + delay) % (2*range-2); + + if position == 0 { + if args.part == 1 { + range * depth + } else { + range * depth + 1 + } + } else { + 0 + } + }, + None => 0 + }; + } + severity +} diff --git a/2017/src/bin/day_14.rs b/2017/src/bin/day_14.rs new file mode 100644 index 0000000..778a57f --- /dev/null +++ b/2017/src/bin/day_14.rs @@ -0,0 +1,52 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + let input = args.input[0].clone(); + + let mut used = 0; + let mut grid: Vec> = vec!(vec!(false; 128); 128); + for i in 0..128 { + let to_hash = format!("{}-{}", input, i); + let hash = knot_hash(&to_hash); + for (x1,c) in hash.chars().enumerate() { + let parsed = u32::from_str_radix(&c.to_string(), 16).unwrap(); + used += parsed.count_ones(); + for (x2,b) in format!("{:04b}",parsed).chars().enumerate() { + grid[i][4*x1+x2] = b == '1'; + } + } + } + + if args.part == 1 { + println!("{} is used", used); + } else { + let mut group_count = 0; + for start_y in 0..128 { + for start_x in 0..128 { + if grid[start_y][start_x] { + group_count += 1; + clear_group(&mut grid, Point{ + x: start_x as i32, + y: start_y as i32 + }); + } + } + } + println!("{} groups", group_count); + + } +} + +fn clear_group(grid: &mut Vec>, point: Point) { + if point.x >= 0 && point.x < 128 && point.y >= 0 && point.y < 128 { + if grid[point.y as usize][point.x as usize] { + grid[point.y as usize][point.x as usize] = false; + clear_group(grid, point.up()); + clear_group(grid, point.down()); + clear_group(grid, point.left()); + clear_group(grid, point.right()); + } + } +} diff --git a/2017/src/bin/day_15.rs b/2017/src/bin/day_15.rs new file mode 100644 index 0000000..29b63ad --- /dev/null +++ b/2017/src/bin/day_15.rs @@ -0,0 +1,40 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + + let mut a: u64 = 591; + let mut b: u64 = 393; + + let mut matches: u64 = 0; + + let comparisons = if args.part == 1 { + 40_000_000 + } else { + 5_000_000 + }; + + for _ in 0..comparisons { + a = (a * 16807) % 2147483647; + b = (b * 48271) % 2147483647; + + while args.part != 1 && a % 4 != 0 { + a = (a * 16807) % 2147483647; + } + while args.part != 1 && b % 8 != 0 { + b = (b * 48271) % 2147483647; + } + + if lower_16_match(a, b) { + matches += 1; + } + } + + println!("There were {} matches", matches); +} + +fn lower_16_match(a: u64, b: u64) -> bool { + let mask = 65535; //2^16-1, ie 16 ones + (a & mask) == (b & mask) +} diff --git a/2017/src/bin/day_16.rs b/2017/src/bin/day_16.rs new file mode 100644 index 0000000..9676714 --- /dev/null +++ b/2017/src/bin/day_16.rs @@ -0,0 +1,87 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +extern crate regex; +use regex::Regex; + +fn main() { + let args = AdventArgs::init(); + + let spin_re = Regex::new(r"s(\d+)").unwrap(); + let exchange_re = Regex::new(r"x(\d+)/(\d+)").unwrap(); + let partner_re = Regex::new(r"p(\w)/(\w)").unwrap(); + let input: Vec = args.input[0] + .split(',') + .map(|instruction| { + if let Some(caps) = spin_re.captures(instruction) { + let spin_amount: usize = caps[1].parse().unwrap(); + Instruction::Spin(spin_amount) + } else if let Some(caps) = exchange_re.captures(instruction) { + let position_a: usize = caps[1].parse().unwrap(); + let position_b: usize = caps[2].parse().unwrap(); + Instruction::Exchange(position_a, position_b) + } else if let Some(caps) = partner_re.captures(instruction) { + let program_a = caps[1].chars().next().unwrap(); + let program_b = caps[2].chars().next().unwrap(); + Instruction::Partner(program_a, program_b) + } else { + panic!("Unhandled instruction: {}", instruction) + } + }) + .collect(); + + let mut states = vec!("abcdefghijklmnop".chars().collect()); + if args.part == 1 { + let answer = run(&input, &states.last().unwrap()); + println!("{}", answer.iter().collect::()); + } else { + let repetitions = 1_000_000_000; + let mut cycle_found = false; + let mut cycle_start = 0; + while !cycle_found { + let next = run(&input, &states.last().unwrap()); + if let Some(i) = states.iter().position(|&ref x| *x == next) { + cycle_found = true; + cycle_start = i; + } else { + states.push(next); + } + } + println!("Cycle found after pushing {} states", states.len()); + println!("Cycle starts at {} states", cycle_start); + + let solution_index = (repetitions - cycle_start) % (states.len() - cycle_start); + println!("{}", states[solution_index].iter().collect::()); + + } +} + +enum Instruction { + Spin(usize), + Exchange(usize, usize), + Partner(char, char) +} + +fn run(instructions: &[Instruction], start: &Vec) -> Vec { + let mut programs = start.clone(); + for instruction in instructions { + match instruction { + &Instruction::Exchange(a, b) => { + programs.swap(a, b); + }, + &Instruction::Spin(spin_amount) => { + for _ in 0..spin_amount { + //this may be slow, but will suffice for right now + let end = programs.pop().unwrap(); + programs.insert(0, end); + } + }, + &Instruction::Partner(program_a, program_b) => { + let position_a: usize = programs.iter().position(|&x| x == program_a).unwrap(); + let position_b: usize = programs.iter().position(|&x| x == program_b).unwrap(); + programs.swap(position_a, position_b); + } + } + } + programs +} diff --git a/2017/src/bin/day_17.rs b/2017/src/bin/day_17.rs new file mode 100644 index 0000000..09d6fdc --- /dev/null +++ b/2017/src/bin/day_17.rs @@ -0,0 +1,47 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + let step_size: usize = args.input[0].parse().unwrap(); + + let inserts = if args.part == 1 { + 2017 + } else { + 50_000_000 + }; + + let mut buffer = Vec::with_capacity(inserts + 1); + buffer.push(0); + let mut position = 0; + + for i in 0..inserts as u32 { + let to_insert = i+1; + // the +1 is because they want it to insert AFTER the element + // that adding position ends on + position = ((position + step_size) % buffer.len()) + 1; + if args.part == 2 && position != 1 { + // for big vectors, push is MUCH more efficient than + // insert (O(C) vs O(n)). In part 2, we want the element + // after 0, which will always be index 1. It only needs to + // be inserted into the right place if it's actually going + // to be in position 1. + // + // If I wasn't meshing the solution with part 1, there + // probably wouldn't even be a vector, just tracking the + // length and index 1. + buffer.push(to_insert); + } else { + buffer.insert(position, to_insert); + } + } + + let answer_position = if args.part == 1 { + (position+1)%buffer.len() + } else { + 1 + }; + + let answer = buffer[answer_position]; + println!("{}", answer); +} diff --git a/2017/src/bin/day_18.rs b/2017/src/bin/day_18.rs new file mode 100644 index 0000000..f763f1f --- /dev/null +++ b/2017/src/bin/day_18.rs @@ -0,0 +1,207 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +use std::str::FromStr; +use std::collections::HashMap; +use std::sync::mpsc::*; + +fn main() { + let args = AdventArgs::init(); + + let instructions: Vec = args.input.iter() + .map(|line| line.parse().unwrap()) + .collect(); + + let (sender0, receiver0) = channel(); + let (sender1, receiver1) = channel(); + + let mut program0 = Program::new(0, instructions.clone(), sender0, receiver1, args.part == 1); + + if args.part == 1 { + program0.run(); + let mut answer = 0; + while let Ok(x) = receiver0.try_recv() { + answer = x; + } + + println!("Last sent value: {}", answer); + } else { + let mut program1 = Program::new(1, instructions.clone(), sender1, receiver0, args.part == 1); + + while !(program0.terminated && program1.terminated) && (program0.run() || program1.run()) { + } + + + println!("Program 0 sent {} messages", program0.sent_count); + println!("Program 1 sent {} messages", program1.sent_count); + } + + +} + +struct Program { + instructions: Vec, + registers: HashMap, + pc: i64, + terminated: bool, + sender: Sender, + sent_count: u64, + receiver: Receiver, + part1: bool +} + +impl Program { + fn new(process_id: i64, instructions: Vec, sender: Sender, receiver: Receiver, part1: bool) -> Program { + let mut reg = HashMap::new(); + if !part1 { + reg.insert('p', process_id); + } + Program { + instructions: instructions, + registers: reg, + pc: 0, + terminated: false, + sender: sender, + sent_count: 0, + receiver: receiver, + part1: part1 + } + } + fn run(&mut self) -> bool { + use Instruction::*; + + let mut blocked = false; + let mut did_something = false; + + while !blocked && !self.terminated { + if self.pc < 0 || self.pc as usize >= self.instructions.len() { + self.terminated = true; + } + else { + let ins = self.instructions[self.pc as usize].clone(); + + match ins { + Snd(x) => { + self.sent_count += 1; + self.sender.send(self.get(x)).ok(); + }, + Set(x, y) => { + let y_val = self.get(y); + self.set(x, y_val); + }, + Add(x, y) => { + let x_val = self.get(x); + let y_val = self.get(y); + self.set(x, x_val + y_val); + }, + Mul(x, y) => { + let x_val = self.get(x); + let y_val = self.get(y); + self.set(x, x_val * y_val); + }, + Mod(x, y) => { + let x_val = self.get(x); + let y_val = self.get(y); + self.set(x, x_val % y_val); + }, + Rcv(x) => { + if self.part1 { + blocked = self.get(x) != 0; + } else { + match self.receiver.try_recv() { + Ok(y) => { + self.set(x, y); + }, + Err(_) => { + blocked = true; + return did_something; + } + } + } + }, + Jgz(x, y) => { + if self.get(x) > 0 { + self.pc = self.pc + self.get(y) - 1; + } + }, + } + self.pc += 1; + did_something = true; + } + } + true + } + + fn get(&self, register: Data) -> i64 { + use Data::*; + match register { + Register(c) => self.registers.get(&c).cloned().unwrap_or(0), + Literal(i) => i + } + } + + fn set(&mut self, register: Data, value: i64) { + use Data::*; + match register { + Register(c) => { + self.registers.insert(c, value); + }, + _ => {} + } + } +} + +#[derive(Debug, Clone)] +enum Instruction { + Snd(Data), + Set(Data, Data), + Add(Data, Data), + Mul(Data, Data), + Mod(Data, Data), + Rcv(Data), + Jgz(Data, Data) +} + +impl FromStr for Instruction { + type Err = String; + + fn from_str(s: &str) -> Result { + use Instruction::*; + + let mut str_iter = s.split_whitespace(); + let ins = str_iter.next(); + let x = str_iter.next().map(|x| x.parse::()); + let y = str_iter.next().map(|x| x.parse::()); + + match (ins, x, y) { + (Some("snd"), Some(Ok(x)), _) => Ok(Snd(x)), + (Some("set"), Some(Ok(x)), Some(Ok(y))) => Ok(Set(x, y)), + (Some("add"), Some(Ok(x)), Some(Ok(y))) => Ok(Add(x, y)), + (Some("mul"), Some(Ok(x)), Some(Ok(y))) => Ok(Mul(x, y)), + (Some("mod"), Some(Ok(x)), Some(Ok(y))) => Ok(Mod(x, y)), + (Some("rcv"), Some(Ok(x)), _) => Ok(Rcv(x)), + (Some("jgz"), Some(Ok(x)), Some(Ok(y))) => Ok(Jgz(x, y)), + (_, _, _) => Err(format!("Unknown instruction {}", s)) + } + } +} + +#[derive(Debug, Clone, Copy)] +enum Data { + Literal(i64), + Register(char) +} + +impl FromStr for Data { + type Err = String; + + fn from_str(s: &str) -> Result { + use Data::*; + + match (s.parse(), s.chars().next()) { + (Ok(num), _) => Ok(Literal(num)), + (Err(_), Some(c)) => Ok(Register(c)), + (_, _) => Err(format!("Invalid data {}", s)) + } + } +} diff --git a/2017/src/bin/day_19.rs b/2017/src/bin/day_19.rs new file mode 100644 index 0000000..b333c98 --- /dev/null +++ b/2017/src/bin/day_19.rs @@ -0,0 +1,78 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + use Direction::*; + + let args = AdventArgs::init(); + + let input: Vec> = args.input.iter().map(|line| line.chars().collect()).collect(); + + let mut position = Point { + x: input[0].iter().position(|&c| c == '|').unwrap() as i32, + y: 0 + }; + + let mut direction = Down; + let mut path_ended = false; + let mut tokens = Vec::new(); + + // moving onto the map counts as one, but because of how I'm + // counting there's also an off the map step that I shouldn't be + // counting at the end. They cancel out. + let mut steps_moved = 0; + + while !path_ended { + position = position.shift(&direction); + steps_moved += 1; + + match char_at(&input, &position) { + '|' | '-' => { + //continue as is + }, + ' ' => { + path_ended = true; + }, + '+' => { + let left_option = char_at(&input, &position.shift(&direction.rotate_left())); + let right_option = char_at(&input, &position.shift(&direction.rotate_right())); + match (left_option, right_option) { + (' ', ' ') => { + path_ended = true; + }, + (_, ' ') => { + direction = direction.rotate_left(); + }, + (' ', _) => { + direction = direction.rotate_right(); + }, + _ => { + panic!("Don't know where to go from {:?}", position); + } + } + }, + token => { + tokens.push(token); + } + } + + } + + if args.part == 1 { + println!("{}", tokens.iter().collect::()); + } else { + println!("{}", steps_moved); + } +} + +fn char_at(input: &Vec>, position: &Point) -> char { + if position.y < 0 || + position.x < 0 || + position.y as usize >= input.len() || + position.x as usize >= input[position.y as usize].len() { + ' ' + } else { + input[position.y as usize][position.x as usize] + } + +} diff --git a/2017/src/bin/day_2.rs b/2017/src/bin/day_2.rs new file mode 100644 index 0000000..307029a --- /dev/null +++ b/2017/src/bin/day_2.rs @@ -0,0 +1,26 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + let sum = args.input.iter().map(|line| { + let splitline = parse_space_separated_ints(line).unwrap(); + + if args.part == 1 { + let max = splitline.iter().max().unwrap(); + let min = splitline.iter().min().unwrap(); + max-min + } else { + for i in 0..splitline.len() { + for j in 0..splitline.len() { + if i != j && splitline[i] % splitline[j] == 0 { + return splitline[i] / splitline[j]; + } + } + } + panic!("Didn't find a dividing one! {:?}", splitline) + } + }).sum::(); + + println!("Checksum is {}", sum); +} diff --git a/2017/src/bin/day_20.rs b/2017/src/bin/day_20.rs new file mode 100644 index 0000000..f528675 --- /dev/null +++ b/2017/src/bin/day_20.rs @@ -0,0 +1,89 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +extern crate regex; +use regex::Regex; + +#[macro_use] +extern crate lazy_static; + +use std::str::FromStr; + +fn main() { + let args = AdventArgs::init(); + + let mut particles: Vec = args.input.iter() + .map(|line| line.parse().unwrap()) + .collect(); + + // I took eventually to be after a largish number. Seemed to work + // out, but I'm sure there is a more mathematical way to work it + // out. + for _ in 0..1000 { + particles = particles.iter().map(|p| p.step()).collect(); + if args.part == 2 { + let before_collisions = particles.clone(); + particles.retain(|p| { + before_collisions.iter().filter(|p2| p2.position == p.position).count() == 1 + }); + } + } + + if args.part == 1 { + let (closest, _) = particles.iter().enumerate().min_by_key(|&(_, p)| p.position.manhattan_distance()).unwrap(); + println!("Closest to 0: {}", closest); + } else { + let remaining = particles.iter().count(); + println!("Remaining: {}", remaining); + } + +} + +#[derive(Debug, Clone)] +struct Particle { + position: Point3d, + velocity: Point3d, + acceleration: Point3d +} + + +impl Particle { + fn step(&self) -> Particle { + let v = self.velocity + self.acceleration; + Particle { + position: self.position + v, + velocity: v, + acceleration: self.acceleration + } + } +} + +impl FromStr for Particle { + type Err = String; + + fn from_str(s: &str) -> Result { + lazy_static!{ + static ref RE: Regex = Regex::new(r"p=<(-?\d+),(-?\d+),(-?\d+)>, v=<(-?\d+),(-?\d+),(-?\d+)>, a=<(-?\d+),(-?\d+),(-?\d+)>").unwrap(); + }; + + let caps = RE.captures(s).unwrap(); + Ok(Particle { + position: Point3d { + x: caps[1].parse().unwrap(), + y: caps[2].parse().unwrap(), + z: caps[3].parse().unwrap() + }, + velocity: Point3d { + x: caps[4].parse().unwrap(), + y: caps[5].parse().unwrap(), + z: caps[6].parse().unwrap() + }, + acceleration: Point3d { + x: caps[7].parse().unwrap(), + y: caps[8].parse().unwrap(), + z: caps[9].parse().unwrap() + } + }) + } +} + diff --git a/2017/src/bin/day_21.rs b/2017/src/bin/day_21.rs new file mode 100644 index 0000000..7f7ac79 --- /dev/null +++ b/2017/src/bin/day_21.rs @@ -0,0 +1,200 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +extern crate regex; +use regex::Regex; + +fn main() { + let args = AdventArgs::init(); + + let (t2, t3) = parse_transforms(&args.input); + + let mut picture = vec!( + vec!(false, true, false), + vec!(false, false, true), + vec!(true, true, true) + ); + + let iterations = if args.part == 1 { + 5 + } else { + 18 + }; + for _ in 0..iterations { + picture = expand(&picture, &t2, &t3); + } + + let ones: usize = picture.iter().map( + |row| row.iter().filter(|&&x| x).count() + ).sum(); + println!("{} ones", ones); +} + +fn print(picture: &Vec>) { + for row in picture { + for &c in row { + print!("{}", if c {"#"} else {"."}); + } + println!(); + } + println!(); +} + +fn expand(picture: &Vec>, t2: &Vec, t3: &Vec) -> Vec> { + let size = picture.len(); + let div = if size % 2 == 0 { 2 } else { 3 }; + let segments = size / div; + let new_size = size + segments; + + let mut result = vec!(vec!(false; new_size); new_size); + + for i in 0..segments { + let y = i*div; + let v = i*(div+1); + for j in 0..segments { + let x = j*div; + let u = j*(div+1); + if div == 2 { + let init = [ + [picture[y][x], picture[y][x+1]], + [picture[y+1][x], picture[y+1][x+1]] + ]; + let pattern = t2.iter().find(|p| p.matches(&init)).expect(&format!("No pattern matches {:?}", init)); + let to = pattern.to; + + for a in 0..div+1 { + for b in 0..div+1 { + result[v+a][u+b] = to[a][b]; + } + } + } else { + let init = [ + [picture[y][x], picture[y][x+1], picture[y][x+2]], + [picture[y+1][x], picture[y+1][x+1], picture[y+1][x+2]], + [picture[y+2][x], picture[y+2][x+1], picture[y+2][x+2]] + ]; + let pattern = t3.iter().find(|p| p.matches(&init)).expect(&format!("No pattern matches {:?}", init)); + let to = pattern.to; + + for a in 0..div+1 { + for b in 0..div+1 { + result[v+a][u+b] = to[a][b]; + } + } + } + } + } + + result +} + +fn parse_transforms(input: &Vec) -> (Vec, Vec) { + let t2_re = Regex::new(r"^(.)(.)/(.)(.) => (.)(.)(.)/(.)(.)(.)/(.)(.)(.)$").unwrap(); + let t3_re = Regex::new(r"^(.)(.)(.)/(.)(.)(.)/(.)(.)(.) => (.)(.)(.)(.)/(.)(.)(.)(.)/(.)(.)(.)(.)/(.)(.)(.)(.)$").unwrap(); + + let mut t2 = Vec::new(); + let mut t3 = Vec::new(); + for line in input { + if let Some(t2_caps) = t2_re.captures(line) { + t2.push(Transform2 { + from: [ + [&t2_caps[1] == "#", &t2_caps[2] == "#"], + [&t2_caps[3] == "#", &t2_caps[4] == "#"] + ], + to: [ + [&t2_caps[5] == "#", &t2_caps[6] == "#", &t2_caps[7] == "#"], + [&t2_caps[8] == "#", &t2_caps[9] == "#", &t2_caps[10] == "#"], + [&t2_caps[11] == "#", &t2_caps[12] == "#", &t2_caps[13] == "#"] + ] + }); + } else if let Some(t3_caps) = t3_re.captures(line) { + t3.push(Transform3 { + from: [ + [&t3_caps[1] == "#", &t3_caps[2] == "#", &t3_caps[3] == "#"], + [&t3_caps[4] == "#", &t3_caps[5] == "#", &t3_caps[6] == "#"], + [&t3_caps[7] == "#", &t3_caps[8] == "#", &t3_caps[9] == "#"] + ], + to: [ + [&t3_caps[10] == "#", &t3_caps[11] == "#", &t3_caps[12] == "#", &t3_caps[13] == "#"], + [&t3_caps[14] == "#", &t3_caps[15] == "#", &t3_caps[16] == "#", &t3_caps[17] == "#"], + [&t3_caps[18] == "#", &t3_caps[19] == "#", &t3_caps[20] == "#", &t3_caps[21] == "#"], + [&t3_caps[22] == "#", &t3_caps[23] == "#", &t3_caps[24] == "#", &t3_caps[25] == "#"] + ] + }); + } + } + + (t2, t3) +} + +#[derive(Debug)] +struct Transform2 { + from: [[bool; 2]; 2], + to: [[bool; 3]; 3] +} + +impl Transform2 { + fn rotate(from: &[[bool;2];2]) -> [[bool;2];2] { + [ + [from[1][0],from[0][0]], + [from[1][1],from[0][1]] + ] + } + + fn flip(from: &[[bool;2];2]) -> [[bool;2];2] { + [ + [from[0][1],from[0][0]], + [from[1][1],from[1][0]] + ] + } + + fn matches(&self, other: &[[bool; 2]; 2]) -> bool { + let mut any_match = false; + let mut spinning_other = other.clone(); + for _ in 0..4 { + any_match = any_match || + self.from == spinning_other || + self.from == Transform2::flip(&spinning_other); + + spinning_other = Transform2::rotate(&spinning_other); + } + any_match + } +} + +#[derive(Debug)] +struct Transform3 { + from: [[bool; 3]; 3], + to: [[bool; 4]; 4] +} + +impl Transform3 { + fn rotate(from: &[[bool;3];3]) -> [[bool;3];3] { + [ + [from[2][0],from[1][0],from[0][0]], + [from[2][1],from[1][1],from[0][1]], + [from[2][2],from[1][2],from[0][2]] + ] + } + + fn flip(from: &[[bool;3];3]) -> [[bool;3];3] { + [ + [from[0][2],from[0][1],from[0][0]], + [from[1][2],from[1][1],from[1][0]], + [from[2][2],from[2][1],from[2][0]] + ] + } + + fn matches(&self, other: &[[bool; 3]; 3]) -> bool { + let mut any_match = false; + let mut spinning_other = other.clone(); + for _ in 0..4 { + any_match = any_match || + self.from == spinning_other || + self.from == Transform3::flip(&spinning_other); + + spinning_other = Transform3::rotate(&spinning_other); + } + any_match + } +} diff --git a/2017/src/bin/day_22.rs b/2017/src/bin/day_22.rs new file mode 100644 index 0000000..917ed63 --- /dev/null +++ b/2017/src/bin/day_22.rs @@ -0,0 +1,73 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +use std::collections::HashSet; + +fn main() { + let args = AdventArgs::init(); + let input_width = args.input[0].len(); + let input_height = args.input.len(); + + let mut position = Point { + x: (input_width / 2) as i32, + y: (input_height / 2) as i32, + }; + let mut direction = Direction::Up; + + let mut weakened: HashSet = HashSet::new(); + let mut infected: HashSet = HashSet::new(); + let mut flagged: HashSet = HashSet::new(); + + for (y, line) in args.input.iter().enumerate() { + for (x, c) in line.chars().enumerate() { + if c == '#' { + infected.insert(Point { + x: x as i32, + y: y as i32 + }); + } + } + } + + let mut infections_caused = 0; + + let bursts = if args.part == 1 { + 10_000 + } else { + 10_000_000 + }; + + for _ in 0..bursts { + if args.part == 1 { + if infected.contains(&position) { + direction = direction.rotate_right(); + infected.remove(&position); + } else { + direction = direction.rotate_left(); + infected.insert(position); + infections_caused += 1; + } + } + else { + if weakened.contains(&position) { + infected.insert(position); + weakened.remove(&position); + infections_caused += 1; + } else if infected.contains(&position) { + direction = direction.rotate_right(); + flagged.insert(position); + infected.remove(&position); + } else if flagged.contains(&position) { + direction = direction.rotate_right().rotate_right(); + flagged.remove(&position); + } else { + direction = direction.rotate_left(); + weakened.insert(position); + } + } + position = position.shift(&direction); + } + + println!("Infections caused {}", infections_caused); + +} diff --git a/2017/src/bin/day_23.rs b/2017/src/bin/day_23.rs new file mode 100644 index 0000000..d199af0 --- /dev/null +++ b/2017/src/bin/day_23.rs @@ -0,0 +1,168 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +use std::str::FromStr; + +fn main() { + let args = AdventArgs::init(); + + if args.part == 1 { + let instructions: Vec = args.input.iter() + .map(|line| line.parse().unwrap()) + .collect(); + + let mut program = Program::new(instructions.clone(), args.part == 1); + let mul_called = program.run(); + println!("Mult called {} times", mul_called); + } else { + println!("Result is {}", run_as_rust()); + } + +} + +fn to_register(c: char) -> usize { + (c as u32 - 'a' as u32) as usize +} + +struct Program { + instructions: Vec, + registers: [i64; 8], + pc: i64 +} + +impl Program { + fn new(instructions: Vec, part1: bool) -> Program { + let mut reg = [0; 8]; + if part1 == false { + reg[0] = 1; + } + Program { + instructions: instructions, + registers: reg, + pc: 0 + } + } + fn run(&mut self) -> u32 { + use Instruction::*; + + let mut mul_called = 0; + + while self.pc >= 0 && (self.pc as usize) < self.instructions.len() { + let ins = self.instructions[self.pc as usize].clone(); + + match ins { + Set(x, y) => { + let y_val = self.get(y); + self.set(x, y_val); + }, + Sub(x, y) => { + let x_val = self.get(x); + let y_val = self.get(y); + self.set(x, x_val - y_val); + }, + Mul(x, y) => { + let x_val = self.get(x); + let y_val = self.get(y); + self.set(x, x_val * y_val); + mul_called += 1; + }, + Jnz(x, y) => { + if self.get(x) != 0 { + self.pc = self.pc + self.get(y) - 1; + } + }, + } + self.pc += 1; + } + + mul_called + } + + fn get(&self, register: Data) -> i64 { + use Data::*; + match register { + Register(c) => self.registers[c], + Literal(i) => i + } + } + + fn set(&mut self, register: Data, value: i64) { + use Data::*; + match register { + Register(c) => { + self.registers[c] = value; + }, + _ => {} + } + } +} + +#[derive(Debug, Clone)] +enum Instruction { + Set(Data, Data), + Sub(Data, Data), + Mul(Data, Data), + Jnz(Data, Data) +} + +impl FromStr for Instruction { + type Err = String; + + fn from_str(s: &str) -> Result { + use Instruction::*; + + let mut str_iter = s.split_whitespace(); + let ins = str_iter.next(); + let x = str_iter.next().map(|x| x.parse::()); + let y = str_iter.next().map(|x| x.parse::()); + + match (ins, x, y) { + (Some("set"), Some(Ok(x)), Some(Ok(y))) => Ok(Set(x, y)), + (Some("sub"), Some(Ok(x)), Some(Ok(y))) => Ok(Sub(x, y)), + (Some("mul"), Some(Ok(x)), Some(Ok(y))) => Ok(Mul(x, y)), + (Some("jnz"), Some(Ok(x)), Some(Ok(y))) => Ok(Jnz(x, y)), + (_, _, _) => Err(format!("Unknown instruction {}", s)) + } + } +} + +#[derive(Debug, Clone, Copy)] +enum Data { + Literal(i64), + Register(usize) +} + +impl FromStr for Data { + type Err = String; + + fn from_str(s: &str) -> Result { + use Data::*; + + match (s.parse(), s.chars().next()) { + (Ok(num), _) => Ok(Literal(num)), + (Err(_), Some(c)) => Ok(Register(to_register(c))), + (_, _) => Err(format!("Invalid data {}", s)) + } + } +} + + +fn run_as_rust() -> i64 { + let mut h: i64 = 0; + let mut b: i64 = 99 * 100 + 100000; + let c: i64 = b + 17000; + + while b <= c { + let f = (2..b).any(|d| { + b % d == 0 + }); + + if f { + h += 1; + } + + b += 17; + } + + h +} diff --git a/2017/src/bin/day_24.rs b/2017/src/bin/day_24.rs new file mode 100644 index 0000000..eb7fddd --- /dev/null +++ b/2017/src/bin/day_24.rs @@ -0,0 +1,60 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + let components: Vec = args.input.iter() + .map(|line| { + let mut split = line.split('/'); + Component { + a: split.next().unwrap().parse().unwrap(), + b: split.next().unwrap().parse().unwrap() + } + }) + .collect(); + + if args.part == 1 { + let strongest = build_strongest(0, components); + println!("{}", strongest); + } else { + let (strongest, longest) = build_longest(0, components); + println!("length: {}, strength: {}", longest, strongest); + } +} + +fn build_strongest(start: u32, components: Vec) -> u32 { + components.iter().enumerate() + .filter(|&(_, c)| c.a == start || c.b == start) + .map(|(i, c)| { + let end = if c.a == start { c.b } else { c.a }; + let mut subset = components.clone(); + subset.remove(i); + c.strength() + build_strongest(end, subset) + }).max().unwrap_or(0) +} + +fn build_longest(start: u32, components: Vec) -> (u32, u32) { + components.iter().enumerate() + .filter(|&(_, c)| c.a == start || c.b == start) + .map(|(i, c)| { + let end = if c.a == start { c.b } else { c.a }; + let mut subset = components.clone(); + subset.remove(i); + let (s, l) = build_longest(end, subset); + (c.strength() + s, 1 + l) + }).max_by(|&(s1, l1), &(s2, l2)| { + l1.cmp(&l2).then(s1.cmp(&s2)) + }).unwrap_or((0, 0)) +} + +#[derive(Debug, Clone)] +struct Component { + a: u32, + b: u32 +} + +impl Component { + fn strength(&self) -> u32 { + self.a + self.b + } +} diff --git a/2017/src/bin/day_25.rs b/2017/src/bin/day_25.rs new file mode 100644 index 0000000..8d7b0da --- /dev/null +++ b/2017/src/bin/day_25.rs @@ -0,0 +1,125 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +extern crate regex; +use regex::Regex; + +use std::slice::Iter; +use std::collections::HashSet; + +fn main() { + let args = AdventArgs::init(); + let program = parse(&args.input); + + let mut position: i32 = 0; + let mut state = program.state(program.start).expect("Started out of program bounds"); + let mut tape = HashSet::new(); + + for _ in 0..program.iterations { + let instruction = if tape.contains(&position) { + &state.if1 + } else { + &state.if0 + }; + if instruction.write { + tape.insert(position); + } else { + tape.remove(&position); + } + position += instruction.offset; + state = program.state(instruction.next).expect("Redirected to unknown state"); + } + + println!("{}", tape.len()); +} + +fn parse(input: &Vec) -> Program { + let state_re = Regex::new(r"state (\w)").unwrap(); + let iterations_re = Regex::new(r"(\d+) steps").unwrap(); + let write_re = Regex::new(r"Write the value (\d)").unwrap(); + let move_re = Regex::new(r"Move one slot to the (\w+)").unwrap(); + + let mut lines = input.iter(); + let start = parse_char(&mut lines, &state_re); + let iterations = parse_number(&mut lines, &iterations_re); + + let mut states = Vec::new(); + while let Some(heading) = lines.next() { + states.push(State { + id: state_re.captures(heading).unwrap()[1].chars().next().unwrap(), + if0: parse_instruction(&mut lines, &write_re, &move_re, &state_re), + if1: parse_instruction(&mut lines, &write_re, &move_re, &state_re) + }); + } + + Program { + start: start, + iterations: iterations, + states: states + } +} + +fn parse_char(lines: &mut Iter, re: &Regex) -> char { + re.captures( + lines.next().unwrap() + ).unwrap()[1].chars().next().unwrap() +} + +fn parse_number(lines: &mut Iter, re: &Regex) -> u32 { + re.captures( + lines.next().unwrap() + ).unwrap()[1].parse().unwrap() +} +fn parse_direction(lines: &mut Iter, re: &Regex) -> i32 { + if re.captures( + lines.next().unwrap() + ).unwrap()[1] == *"left" { + -1 + } else { + 1 + } +} + +fn parse_bool(lines: &mut Iter, re: &Regex) -> bool { + re.captures( + lines.next().unwrap() + ).unwrap()[1] == *"1" +} + +fn parse_instruction(lines: &mut Iter, write_re: &Regex, offset_re: &Regex, next_re: &Regex) -> Instruction { + lines.next(); + Instruction { + write: parse_bool(lines, &write_re), + offset: parse_direction(lines, &offset_re), + next: parse_char(lines, &next_re) + } +} + +#[derive(Debug)] +struct Program { + start: char, + iterations: u32, + states: Vec +} + +impl Program { + fn state(&self, i: char) -> Option<&State> { + self.states.iter().find(|s| s.id == i) + } +} + +#[derive(Debug)] +struct State { + id: char, + if0: Instruction, + if1: Instruction +} + +#[derive(Debug)] +struct Instruction { + write: bool, + offset: i32, + next: char +} + + diff --git a/2017/src/bin/day_3.rs b/2017/src/bin/day_3.rs new file mode 100644 index 0000000..69ded88 --- /dev/null +++ b/2017/src/bin/day_3.rs @@ -0,0 +1,62 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +use std::collections::HashMap; + +fn main() { + use Direction::*; + + let args = AdventArgs::init(); + let input = args.one_number_input().unwrap(); + + let mut memory: HashMap = HashMap::new(); + let mut last_allocated = 1; + + let mut current = Point { + x: 0, + y: 0 + }; + memory.insert(current, last_allocated); + + let mut steps_per_direction = 1; + let mut steps_to_next_turn = 1; + let mut turns_to_spiral_increase = 2; + + let mut current_index = 1; + let mut current_direction = Right; + + while (args.part == 1 && current_index != input) || (args.part == 2 && last_allocated < input) { + current = current.shift(¤t_direction); + current_index += 1; + + steps_to_next_turn -= 1; + if steps_to_next_turn == 0 { + current_direction = current_direction.rotate_left(); + turns_to_spiral_increase -= 1; + if turns_to_spiral_increase == 0 { + steps_per_direction += 1; + turns_to_spiral_increase = 2; + } + + steps_to_next_turn = steps_per_direction; + } + + if args.part == 2 { + last_allocated = memory.get(¤t.left()).cloned().unwrap_or(0) + + memory.get(¤t.right()).cloned().unwrap_or(0) + + memory.get(¤t.up()).cloned().unwrap_or(0) + + memory.get(¤t.down()).cloned().unwrap_or(0) + + memory.get(¤t.up().left()).cloned().unwrap_or(0) + + memory.get(¤t.up().right()).cloned().unwrap_or(0) + + memory.get(¤t.down().left()).cloned().unwrap_or(0) + + memory.get(¤t.down().right()).cloned().unwrap_or(0); + + memory.insert(current, last_allocated); + } + } + + println!("{:?}", current); + println!("Distance: {}", current.x.abs() + current.y.abs()); + println!("Last Allocated Value: {}", last_allocated); + +} diff --git a/2017/src/bin/day_4.rs b/2017/src/bin/day_4.rs new file mode 100644 index 0000000..a9a098a --- /dev/null +++ b/2017/src/bin/day_4.rs @@ -0,0 +1,37 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + + let valid_count = args.input.iter() + .map(|line| { + let words = line.split_whitespace().map(|x| x.to_string()).collect::>(); + if args.part == 1 { + let mut deduped_words = words.clone(); + deduped_words.sort(); + deduped_words.dedup(); + words.len() == deduped_words.len() + } else { + !words.iter().enumerate().any(|(i, word1)| { + words.iter().enumerate().any(|(j, word2)| { + i != j && is_anagram(word1, word2) + }) + }) + } + }) + .filter(|&valid| valid) + .count(); + + println!("Valid count: {}", valid_count); +} + +fn is_anagram(word1: &str, word2: &str) -> bool { + let mut chars1 = word1.chars().collect::>(); + chars1.sort(); + let mut chars2 = word2.chars().collect::>(); + chars2.sort(); + + chars1.len() == chars2.len() && + chars1.iter().zip(chars2.iter()).all(|(c1, c2)| c1 == c2) +} diff --git a/2017/src/bin/day_5.rs b/2017/src/bin/day_5.rs new file mode 100644 index 0000000..49bdbd1 --- /dev/null +++ b/2017/src/bin/day_5.rs @@ -0,0 +1,25 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + + let mut jumps: Vec = args.input.iter().map(|line| line.parse().unwrap()).collect(); + let mut steps_taken = 0; + let mut current_position: i32 = 0; + + while current_position >= 0 && (current_position as usize) < jumps.len() { + let previous_position = current_position; + current_position += jumps[current_position as usize]; + + if args.part == 1 || jumps[previous_position as usize] < 3 { + jumps[previous_position as usize] += 1; + } else { + jumps[previous_position as usize] -= 1; + } + + steps_taken += 1; + } + + println!("Escaped in {} jumps", steps_taken); +} diff --git a/2017/src/bin/day_6.rs b/2017/src/bin/day_6.rs new file mode 100644 index 0000000..be9a515 --- /dev/null +++ b/2017/src/bin/day_6.rs @@ -0,0 +1,61 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + + let init_layout = parse_space_separated_ints(&args.input[0]).unwrap(); + + let mut layouts = vec!(init_layout); + let mut balances = 0; + let mut cycle_found = false; + let mut cycle_size = 0; + + while !cycle_found { + balances += 1; + let new_layout = find_next_layout(&layouts); + + if let Some(index) = layouts.iter().position(|x| *x == new_layout) { + cycle_found = true; + cycle_size = layouts.len() - index; + }; + + layouts.push(new_layout); + } + + if args.part == 1 { + println!("Did {} rebalances", balances); + } else { + println!("Cycle was {} long", cycle_size); + } +} + +fn find_next_layout(layouts: &Vec>) -> Vec { + let previous_layout = layouts.last().unwrap(); + rebalance(&previous_layout) +} + +fn rebalance(layout: &Vec) -> Vec { + let biggest_container = layout.iter() + .enumerate() + .max_by(|&(ai, &asize), &(bi, &bsize)| { + asize.cmp(&bsize).then(bi.cmp(&ai)) + }) + .map(|(i, _)| i) + .unwrap(); + + + let mut new_layout = layout.clone(); + let mut to_redistribute = new_layout[biggest_container]; + new_layout[biggest_container] = 0; + let mut target = (biggest_container + 1) % layout.len(); + + while to_redistribute > 0 { + new_layout[target] += 1; + to_redistribute -= 1; + target = (target + 1) % layout.len(); + } + + new_layout +} + diff --git a/2017/src/bin/day_7.rs b/2017/src/bin/day_7.rs new file mode 100644 index 0000000..3c3b185 --- /dev/null +++ b/2017/src/bin/day_7.rs @@ -0,0 +1,62 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +extern crate regex; +use regex::Regex; + +fn main() { + let args = AdventArgs::init(); + + let names_re = Regex::new(r"[a-z]+").unwrap(); + let weight_re = Regex::new(r"\d+").unwrap(); + + let tree: Vec<(String, Vec, i32)> = args.input.iter() + .map(|line| { + let mut matches = names_re.find_iter(line); + let base = matches.next().unwrap().as_str().to_string(); + let leaves = matches.map(|m| m.as_str().to_string()).collect(); + let weight = weight_re.find(line).unwrap().as_str().parse().unwrap(); + (base, leaves, weight) + }).collect(); + + let mut possible_roots: Vec = tree.iter().map(|&(ref id, _, _)| id.clone()).collect(); + for &(_, ref leaves, _) in &tree { + for leaf in leaves { + let index = possible_roots.iter().position(|x| x == leaf).unwrap(); + possible_roots.remove(index); + } + } + let root = &possible_roots[0]; + + if args.part == 1 { + println!("{:?}", root); + } else { + find_unweighted_plate(&root, &tree); + } +} + +fn find_unweighted_plate(root: &String, tree: &Vec<(String, Vec, i32)>) -> i32 { + let root_node = find_node(&root, &tree); + let &(_, ref leaves, ref weight) = root_node; + let leaf_weights: Vec = leaves.iter().map(|leaf| { + find_unweighted_plate(&leaf, &tree) + }).collect(); + + if let Some(base_leaf_weight) = leaf_weights.first() { + if let Some(different_leaf_weight) = leaf_weights.iter().find(|&w| w != base_leaf_weight) { + println!("Unbalanced plate is off by {}", (different_leaf_weight-base_leaf_weight).abs()); + println!("Towers on plate: {:?} weigh {:?}", leaves, leaf_weights); + // This still needs some manual work to get to the puzzle + // output. Take the first unbalanced plate, figure out + // which is the unbalanced tower visually, find its + // individual weight in the file, and add/subtract as + // necessary. + } + } + + leaf_weights.iter().sum::() + weight +} + +fn find_node<'a>(name: &String, tree: &'a Vec<(String, Vec, i32)>) -> &'a (String, Vec, i32) { + tree.iter().find(|&&(ref id, _, _)| id == name).unwrap() +} diff --git a/2017/src/bin/day_8.rs b/2017/src/bin/day_8.rs new file mode 100644 index 0000000..0359747 --- /dev/null +++ b/2017/src/bin/day_8.rs @@ -0,0 +1,99 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +extern crate regex; +use regex::Regex; + +#[macro_use] +extern crate lazy_static; + +use std::str::FromStr; +use std::collections::HashMap; +use std::cmp; + +fn main() { + let args = AdventArgs::init(); + + let instructions: Vec = args.input.iter() + .map(|line| line.parse().unwrap()) + .collect(); + + let mut memory: HashMap = HashMap::new(); + let mut max_mem_ever = 0; + + for instruction in instructions { + if instruction.is_true(&memory) { + instruction.execute(&mut memory); + max_mem_ever = cmp::max(max_mem_ever, memory.values().max().cloned().unwrap_or(0)); + } + } + + let max_mem = memory.values().max().cloned().unwrap_or(0); + + if args.part == 1 { + println!("Highest value in memory is {}", max_mem); + } else { + println!("Highest value in memory ever is {}", max_mem_ever); + } +} + + +struct Instruction { + target_register: String, + action: String, + value: i32, + condition_register: String, + condition: String, + condition_value: i32 +} + +#[derive(Debug)] +struct InstructionParseError { + reason: String +} + +impl FromStr for Instruction { + type Err = InstructionParseError; + fn from_str(s: &str) -> Result { + lazy_static!{ + static ref INSTRUCTION_RE: Regex = Regex::new(r"^(\w+) (inc|dec) (-?\d+) if (\w+) (<|>|<=|>=|==|!=) (-?\d+)").unwrap(); + } + match INSTRUCTION_RE.captures(s) { + Some(caps) => Ok(Instruction{ + target_register: caps[1].to_string(), + action: caps[2].to_string(), + value: caps[3].parse().unwrap(), + condition_register: caps[4].to_string(), + condition: caps[5].to_string(), + condition_value: caps[6].parse().unwrap() + }), + None => Err(InstructionParseError { + reason: format!("{} did not match regex", s) + }) + } + } +} + +impl Instruction { + fn is_true(&self, memory: &HashMap) -> bool { + let mem = memory.get(&self.condition_register).cloned().unwrap_or(0); + match self.condition.as_ref() { + "<" => mem < self.condition_value, + ">" => mem > self.condition_value, + "<=" => mem <= self.condition_value, + ">=" => mem >= self.condition_value, + "==" => mem == self.condition_value, + "!=" => mem != self.condition_value, + _ => panic!("Unknown condition: {}", self.condition) + } + } + + fn execute(&self, memory: &mut HashMap) { + let modifier = if self.action == "inc" { + self.value + } else { + -self.value + }; + *memory.entry(self.target_register.clone()).or_insert(0) += modifier; + } +} diff --git a/2017/src/bin/day_9.rs b/2017/src/bin/day_9.rs new file mode 100644 index 0000000..e0ca0c0 --- /dev/null +++ b/2017/src/bin/day_9.rs @@ -0,0 +1,42 @@ +extern crate advent_of_code_2017; +use advent_of_code_2017::*; + +fn main() { + let args = AdventArgs::init(); + + let mut cancelled = false; + let mut in_garbage = false; + + let mut depth = 0; + let mut total_score = 0; + let mut total_garbage = 0; + + for c in args.input[0].chars() { + if cancelled { + cancelled = false; + } else if c == '!' { + cancelled = true; + } else if in_garbage { + if c == '>' { + in_garbage = false; + } else { + total_garbage += 1; + } + } else { + if c == '<' { + in_garbage = true; + } else if c == '{' { + depth += 1; + total_score += depth; + } else if c == '}' { + depth -= 1; + } + } + } + + if args.part == 1 { + println!("Total score is {}", total_score); + } else { + println!("Total garbage is {}", total_garbage); + } +} diff --git a/2017/src/lib.rs b/2017/src/lib.rs new file mode 100644 index 0000000..53d7d20 --- /dev/null +++ b/2017/src/lib.rs @@ -0,0 +1,225 @@ +extern crate structopt; +#[macro_use] +extern crate structopt_derive; +use structopt::StructOpt; + +use std::path::PathBuf; +use std::io::BufReader; +use std::io::prelude::*; +use std::fs::File; +use std::process; + +#[derive(StructOpt, Debug)] +#[structopt(name = "AOC2017", about = "An Advent of Code CLI arguments object.")] +struct AdventCli { + #[structopt(help = "Which part of the puzzle you are solving")] + part: u32, + + #[structopt(help = "Input file", parse(from_os_str))] + input: PathBuf +} + +pub struct AdventArgs { + pub part: u32, + pub input: Vec +} + +impl AdventArgs { + pub fn init() -> AdventArgs { + let opt = AdventCli::from_args(); + let input = match AdventArgs::read_file(&opt.input) { + Ok(input) => input, + Err(error) => { + // Typically I would think of exiting the program like + // this to be bad form, but in this case I'm matching the + // interface of StructOpt: if the input parameters were + // invalid, just quit now with a nice message. + eprintln!("Error reading file: {}", error); + process::exit(1); + } + }; + AdventArgs { + part: opt.part, + input: input + } + } + + fn read_file(file: &PathBuf) -> Result, std::io::Error> { + let file = File::open(file)?; + let file_reader = BufReader::new(file); + file_reader.lines() + .collect::, _>>() + .map(AdventArgs::preprocess_file_lines) + } + + fn preprocess_file_lines(lines: Vec) -> Vec { + lines.iter() + .filter(|line| line.len() > 0) + .map(|line| line.trim_right().to_string()) + .collect() + } + + pub fn one_number_input(&self) -> Result { + self.input[0].parse() + } + pub fn number_per_line_input(&self) -> Result, std::num::ParseIntError> { + self.input.iter().map(|line| line.parse()).collect() + } +} + +pub fn parse_space_separated_ints(line: &String) -> Result, std::num::ParseIntError> { + line.split_whitespace() + .map(|x| x.parse::()) + .collect() +} + + +#[derive(Hash, Eq, PartialEq, Debug, Clone, Copy)] +pub struct Point { + pub x: i32, + pub y: i32 +} + +impl Point { + pub fn up(&self) -> Point { + Point { + y: self.y-1, + ..*self + } + } + + pub fn down(&self) -> Point { + Point { + y: self.y+1, + ..*self + } + } + + pub fn left(&self) -> Point { + Point { + x: self.x-1, + ..*self + } + } + + pub fn right(&self) -> Point { + Point { + x: self.x+1, + ..*self + } + } + + pub fn shift(&self, dir: &Direction) -> Point { + use Direction::*; + + match *dir { + Right => self.right(), + Left => self.left(), + Up => self.up(), + Down => self.down() + } + } +} + +#[derive(Debug)] +pub enum Direction { + Left, + Up, + Down, + Right +} + +impl Direction { + pub fn rotate_left(&self) -> Direction { + use Direction::*; + match *self { + Right => Up, + Up => Left, + Left => Down, + Down => Right + } + } + + pub fn rotate_right(&self) -> Direction { + use Direction::*; + match *self { + Right => Down, + Up => Right, + Left => Up, + Down => Left + } + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct Point3d { + pub x: i32, + pub y: i32, + pub z: i32 +} + +impl std::ops::Add for Point3d { + type Output = Point3d; + + fn add(self, other: Point3d) -> Point3d { + Point3d { + x: self.x + other.x, + y: self.y + other.y, + z: self.z + other.z + } + } + +} + +impl Point3d { + pub fn manhattan_distance(&self) -> i32 { + self.x.abs() + self.y.abs() + self.z.abs() + } +} + +pub fn knot_hash(input: &String) -> String { + let suffix: [usize; 5] = [17, 31, 73, 47, 23]; + let lengths: Vec = input.as_bytes() + .iter().map(|&x| x as usize) + .chain(suffix.iter().cloned()) + .collect(); + + let mut position = 0; + let mut list: Vec = (0..256).collect(); + + for i in 0..64 { + let skip = lengths.len() * i; + knot_hash_round(&mut list, &lengths, &mut position, skip); + } + + let mut current_char = 0; + let mut result = String::new(); + for (i, l) in list.iter().enumerate() { + current_char = current_char ^ l; + if i % 16 == 15 { + result.push_str(&format!("{:02x}", current_char)); + current_char = 0; + } + } + result +} + +fn knot_hash_round(list: &mut Vec, lengths: &Vec, position: &mut usize, skip: usize) { + for (inner_skip, &length) in lengths.iter().enumerate() { + knot_hash_reverse_segment(list, *position, length); + *position = (*position + length + skip + inner_skip) % list.len(); + } +} + +fn knot_hash_reverse_segment(list: &mut Vec, position: usize, length: usize) { + let mut a = position; + let mut b = position + length - 1; + let len = list.len(); + while a < b { + list.swap(a%len, b%len); + + a += 1; + b -= 1; + } +} + -- cgit v1.2.3