From b5da2fa328ad63d683d66da65e656ed2ee64878c Mon Sep 17 00:00:00 2001 From: Curtis McEnroe Date: Mon, 27 Nov 2017 17:11:18 -0500 Subject: Move to 2016 directory --- 2016/src/bin/day01.rs | 78 ++++++++++++++++++++ 2016/src/bin/day02.rs | 156 ++++++++++++++++++++++++++++++++++++++++ 2016/src/bin/day03.rs | 62 ++++++++++++++++ 2016/src/bin/day04.rs | 123 ++++++++++++++++++++++++++++++++ 2016/src/bin/day05.rs | 71 ++++++++++++++++++ 2016/src/bin/day06.rs | 87 ++++++++++++++++++++++ 2016/src/bin/day07.rs | 119 +++++++++++++++++++++++++++++++ 2016/src/bin/day08.rs | 148 ++++++++++++++++++++++++++++++++++++++ 2016/src/bin/day09.rs | 124 ++++++++++++++++++++++++++++++++ 2016/src/bin/day10.rs | 180 ++++++++++++++++++++++++++++++++++++++++++++++ 2016/src/bin/day11.rs | 194 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2016/src/bin/day12.rs | 143 +++++++++++++++++++++++++++++++++++++ 2016/src/bin/day13.rs | 122 +++++++++++++++++++++++++++++++ 2016/src/bin/day14.rs | 87 ++++++++++++++++++++++ 2016/src/bin/day15.rs | 103 +++++++++++++++++++++++++++ 2016/src/bin/day16.rs | 51 +++++++++++++ 2016/src/bin/day17.rs | 148 ++++++++++++++++++++++++++++++++++++++ 2016/src/bin/day18.rs | 88 +++++++++++++++++++++++ 2016/src/bin/day19.rs | 35 +++++++++ 2016/src/bin/day20.rs | 77 ++++++++++++++++++++ 2016/src/bin/day21.rs | 144 +++++++++++++++++++++++++++++++++++++ 2016/src/bin/day23.rs | 157 ++++++++++++++++++++++++++++++++++++++++ 2016/src/bin/day25.rs | 163 ++++++++++++++++++++++++++++++++++++++++++ 23 files changed, 2660 insertions(+) create mode 100644 2016/src/bin/day01.rs create mode 100644 2016/src/bin/day02.rs create mode 100644 2016/src/bin/day03.rs create mode 100644 2016/src/bin/day04.rs create mode 100644 2016/src/bin/day05.rs create mode 100644 2016/src/bin/day06.rs create mode 100644 2016/src/bin/day07.rs create mode 100644 2016/src/bin/day08.rs create mode 100644 2016/src/bin/day09.rs create mode 100644 2016/src/bin/day10.rs create mode 100644 2016/src/bin/day11.rs create mode 100644 2016/src/bin/day12.rs create mode 100644 2016/src/bin/day13.rs create mode 100644 2016/src/bin/day14.rs create mode 100644 2016/src/bin/day15.rs create mode 100644 2016/src/bin/day16.rs create mode 100644 2016/src/bin/day17.rs create mode 100644 2016/src/bin/day18.rs create mode 100644 2016/src/bin/day19.rs create mode 100644 2016/src/bin/day20.rs create mode 100644 2016/src/bin/day21.rs create mode 100644 2016/src/bin/day23.rs create mode 100644 2016/src/bin/day25.rs (limited to '2016/src/bin') diff --git a/2016/src/bin/day01.rs b/2016/src/bin/day01.rs new file mode 100644 index 0000000..c596099 --- /dev/null +++ b/2016/src/bin/day01.rs @@ -0,0 +1,78 @@ +use std::collections::HashSet; +use std::io::{self, Read}; +use std::ops::Add; + +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +struct Point(i32, i32); + +impl Point { + fn left(self) -> Self { + Point(self.1, -self.0) + } + + fn right(self) -> Self { + Point(-self.1, self.0) + } + + fn distance(self) -> i32 { + self.0.abs() + self.1.abs() + } +} + +impl Add for Point { + type Output = Self; + + fn add(self, rhs: Self) -> Self { + Point(self.0 + rhs.0, self.1 + rhs.1) + } +} + +fn solve(input: &str) -> (i32, Option) { + let mut position = Point(0, 0); + let mut direction = Point(0, -1); + let mut visited = HashSet::new(); + let mut collision = None; + + for instruction in input.trim().split(", ") { + let (turn, count) = instruction.split_at(1); + + if turn == "L" { + direction = direction.left(); + } else { + direction = direction.right(); + } + + let count: i32 = count.parse().unwrap(); + for _ in 0..count { + position = position + direction; + if collision.is_none() && !visited.insert(position) { + collision = Some(position); + } + } + } + + (position.distance(), collision.map(Point::distance)) +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + let (part1, part2) = solve(&input); + println!("Part 1: {}", part1); + if let Some(part2) = part2 { + println!("Part 2: {}", part2); + } +} + +#[test] +fn part1() { + assert_eq!(5, solve("R2, L3").0); + assert_eq!(2, solve("R2, R2, R2").0); + assert_eq!(12, solve("R5, L5, R5, R3").0); +} + +#[test] +fn part2() { + assert_eq!(Some(4), solve("R8, R4, R4, R8").1); +} diff --git a/2016/src/bin/day02.rs b/2016/src/bin/day02.rs new file mode 100644 index 0000000..f7cc624 --- /dev/null +++ b/2016/src/bin/day02.rs @@ -0,0 +1,156 @@ +use std::io::{self, Read}; + +trait Pad: Copy + Default { + fn up(self) -> Self; + fn down(self) -> Self; + fn left(self) -> Self; + fn right(self) -> Self; +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum Keypad { + K1, K2, K3, + K4, K5, K6, + K7, K8, K9, +} + +impl Default for Keypad { + fn default() -> Self { Keypad::K5 } +} + +impl Pad for Keypad { + fn up(self) -> Self { + use Keypad::*; + match self { + K4 => K1, K5 => K2, K6 => K3, + K7 => K4, K8 => K5, K9 => K6, + _ => self, + } + } + + fn down(self) -> Self { + use Keypad::*; + match self { + K1 => K4, K2 => K5, K3 => K6, + K4 => K7, K5 => K8, K6 => K9, + _ => self, + } + } + + fn left(self) -> Self { + use Keypad::*; + match self { + K2 => K1, K3 => K2, + K5 => K4, K6 => K5, + K8 => K7, K9 => K8, + _ => self, + } + } + + fn right(self) -> Self { + use Keypad::*; + match self { + K1 => K2, K2 => K3, + K4 => K5, K5 => K6, + K7 => K8, K8 => K9, + _ => self, + } + } +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum Wackypad { + K1, + K2, K3, K4, + K5, K6, K7, K8, K9, + KA, KB, KC, + KD, +} + +impl Default for Wackypad { + fn default() -> Self { Wackypad::K5 } +} + +impl Pad for Wackypad { + fn up(self) -> Self { + use Wackypad::*; + match self { + K3 => K1, + K6 => K2, K7 => K3, K8 => K4, + KA => K6, KB => K7, KC => K8, + KD => KB, + _ => self, + } + } + + fn down(self) -> Self { + use Wackypad::*; + match self { + K1 => K3, + K2 => K6, K3 => K7, K4 => K8, + K6 => KA, K7 => KB, K8 => KC, + KB => KD, + _ => self, + } + } + + fn left(self) -> Self { + use Wackypad::*; + match self { + K3 => K2, K4 => K3, + K6 => K5, K7 => K6, K8 => K7, K9 => K8, + KB => KA, KC => KB, + _ => self, + } + } + + fn right(self) -> Self { + use Wackypad::*; + match self { + K2 => K3, K3 => K4, + K5 => K6, K6 => K7, K7 => K8, K8 => K9, + KA => KB, KB => KC, + _ => self, + } + } +} + +fn solve(input: &str) -> Vec

{ + let mut code = Vec::new(); + let mut key = P::default(); + + for line in input.lines() { + for direction in line.chars() { + key = match direction { + 'U' => key.up(), + 'D' => key.down(), + 'L' => key.left(), + 'R' => key.right(), + _ => panic!("{} is not a direction", direction), + } + } + code.push(key); + } + + code +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {:?}", solve::(&input)); + println!("Part 2: {:?}", solve::(&input)); +} + +#[test] +fn part1() { + use Keypad::*; + assert_eq!(vec![K1, K9, K8, K5], solve("ULL\nRRDDD\nLURDL\nUUUUD")); +} + +#[test] +fn part2() { + use Wackypad::*; + assert_eq!(vec![K5, KD, KB, K3], solve("ULL\nRRDDD\nLURDL\nUUUUD")); +} diff --git a/2016/src/bin/day03.rs b/2016/src/bin/day03.rs new file mode 100644 index 0000000..76b5aa5 --- /dev/null +++ b/2016/src/bin/day03.rs @@ -0,0 +1,62 @@ +use std::io::{self, Read}; +use std::str::FromStr; + +struct Triangle(u32, u32, u32); + +impl Triangle { + fn valid(&self) -> bool { + self.0 + self.1 > self.2 + && self.1 + self.2 > self.0 + && self.0 + self.2 > self.1 + } +} + +impl FromStr for Triangle { + type Err = (); + fn from_str(s: &str) -> Result { + let mut iter = s.split_whitespace().map(str::parse); + match (iter.next(), iter.next(), iter.next()) { + (Some(Ok(a)), Some(Ok(b)), Some(Ok(c))) => Ok(Triangle(a, b, c)), + _ => Err(()), + } + } +} + +fn solve1(input: &str) -> usize { + input.lines() + .map(str::parse) + .map(Result::unwrap) + .filter(Triangle::valid) + .count() +} + +fn solve2(input: &str) -> usize { + let triangles: Vec = input.lines() + .map(str::parse) + .map(Result::unwrap) + .collect(); + + triangles.chunks(3) + .flat_map(|triple| { + vec![ + Triangle(triple[0].0, triple[1].0, triple[2].0), + Triangle(triple[0].1, triple[1].1, triple[2].1), + Triangle(triple[0].2, triple[1].2, triple[2].2), + ] + }) + .filter(Triangle::valid) + .count() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(&input)); + println!("Part 2: {}", solve2(&input)); +} + +#[test] +fn part1() { + assert_eq!(0, solve1("5 10 25")); +} diff --git a/2016/src/bin/day04.rs b/2016/src/bin/day04.rs new file mode 100644 index 0000000..8e724c2 --- /dev/null +++ b/2016/src/bin/day04.rs @@ -0,0 +1,123 @@ +use std::io::{self, Read}; +use std::str::FromStr; + +struct Room { + name: String, + sector_id: u32, + checksum: String, +} + +impl FromStr for Room { + type Err = (); + fn from_str(s: &str) -> Result { + let mut iter = s.trim_right_matches(']') + .rsplitn(3, |c| c == '-' || c == '['); + + let checksum = iter.next().ok_or(())?; + let sector_id = iter.next().ok_or(())?; + let name = iter.next().ok_or(())?; + + Ok(Room { + name: name.into(), + sector_id: sector_id.parse().map_err(|_| ())?, + checksum: checksum.into(), + }) + } +} + +impl Room { + fn checksum(&self) -> String { + let mut letters = [ + (0, 'a'), (0, 'b'), (0, 'c'), (0, 'd'), (0, 'e'), (0, 'f'), (0, 'g'), (0, 'h'), + (0, 'i'), (0, 'j'), (0, 'k'), (0, 'l'), (0, 'm'), (0, 'n'), (0, 'o'), (0, 'p'), + (0, 'q'), (0, 'r'), (0, 's'), (0, 't'), (0, 'u'), (0, 'v'), (0, 'w'), (0, 'x'), + (0, 'y'), (0, 'z'), + ]; + + for letter in self.name.chars().filter(|c| c.is_alphabetic()) { + let index = letter as u8 - b'a'; + letters[index as usize].0 -= 1; + } + + letters.sort(); + + letters.into_iter() + .map(|l| l.1) + .take(5) + .collect() + } + + fn verify_checksum(&self) -> bool { + self.checksum == self.checksum() + } + + fn decrypt_name(&self) -> String { + self.name.chars() + .map(|c| { + match c { + '-' => ' ', + _ => rotate(c, self.sector_id), + } + }) + .collect() + } +} + +fn rotate(c: char, n: u32) -> char { + let c = c as u8 + (n % 26) as u8; + if c > b'z' { + (c - 26) as char + } else { + c as char + } +} + +fn solve1(input: &str) -> u32 { + input.lines() + .map(str::parse) + .map(Result::unwrap) + .filter(Room::verify_checksum) + .map(|room| room.sector_id) + .sum() +} + +fn solve2(input: &str) -> Option { + input.lines() + .map(str::parse) + .map(Result::unwrap) + .filter(Room::verify_checksum) + .filter_map(|r| { + match r.decrypt_name().as_str() { + "northpole object storage" => Some(r.sector_id), + _ => None, + } + }) + .next() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(&input)); + if let Some(sector_id) = solve2(&input) { + println!("Part 2: {}", sector_id); + } +} + +#[test] +fn part1() { + let input = " +aaaaa-bbb-z-y-x-123[abxyz] +a-b-c-d-e-f-g-h-987[abcde] +not-a-real-room-404[oarel] +totally-real-room-200[decoy] +"; + assert_eq!(1514, solve1(&input[1..])); +} + +#[test] +fn part2() { + let room: Room = "qzmt-zixmtkozy-ivhz-343[zimth]".parse().unwrap(); + assert_eq!("very encrypted name", room.decrypt_name()); +} diff --git a/2016/src/bin/day05.rs b/2016/src/bin/day05.rs new file mode 100644 index 0000000..eefa3df --- /dev/null +++ b/2016/src/bin/day05.rs @@ -0,0 +1,71 @@ +extern crate crypto; + +use std::io::{self, Read}; + +use crypto::digest::Digest; +use crypto::md5::Md5; + +fn solve1(input: &str) -> String { + let mut password = String::new(); + let mut index = 0u64; + + while password.len() < 8 { + let mut md5 = Md5::new(); + md5.input_str(input); + md5.input_str(&index.to_string()); + let digest = md5.result_str(); + + if &digest[0..5] == "00000" { + password.push_str(&digest[5..6]); + } + + index += 1; + } + + password +} + +fn solve2(input: &str) -> String { + let mut password = [None; 8]; + let mut index = 0u64; + + while !password.iter().all(Option::is_some) { + let mut md5 = Md5::new(); + md5.input_str(input); + md5.input_str(&index.to_string()); + let digest = md5.result_str(); + + if &digest[0..5] == "00000" { + if let Some(pos @ 0 ... 7) = digest[5..6].parse().ok() { + password[pos] = password[pos].or(digest[6..7].chars().next()); + } + } + + index += 1; + } + + password.iter() + .cloned() + .map(Option::unwrap) + .collect() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(input.trim())); + println!("Part 2: {}", solve2(input.trim())); +} + +#[test] +#[ignore] +fn part1() { + assert_eq!("18f47a30", solve1("abc")); +} + +#[test] +#[ignore] +fn part2() { + assert_eq!("05ace8e3", solve2("abc")); +} diff --git a/2016/src/bin/day06.rs b/2016/src/bin/day06.rs new file mode 100644 index 0000000..7f8a516 --- /dev/null +++ b/2016/src/bin/day06.rs @@ -0,0 +1,87 @@ +use std::collections::HashMap; +use std::io::{self, Read}; + +fn frequencies(chars: &[char]) -> HashMap { + let mut map = HashMap::new(); + for &ch in chars { + *map.entry(ch).or_insert(0) += 1; + } + map +} + +fn solve1(input: &str) -> String { + let len = input.find('\n').unwrap_or(input.len()); + let mut columns = vec![Vec::new(); len]; + + for line in input.lines() { + for (i, ch) in line.chars().enumerate() { + columns[i].push(ch); + } + } + + columns.into_iter() + .map(|column| frequencies(&column)) + .map(IntoIterator::into_iter) + .map(|iter| iter.max_by_key(|&(_, v)| v)) + .map(Option::unwrap) + .map(|(ch, _)| ch) + .collect() +} + +fn solve2(input: &str) -> String { + let len = input.find('\n').unwrap_or(input.len()); + let mut columns = vec![Vec::new(); len]; + + for line in input.lines() { + for (i, ch) in line.chars().enumerate() { + columns[i].push(ch); + } + } + + columns.into_iter() + .map(|column| frequencies(&column)) + .map(IntoIterator::into_iter) + .map(|iter| iter.min_by_key(|&(_, v)| v)) + .map(Option::unwrap) + .map(|(ch, _)| ch) + .collect() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(&input)); + println!("Part 2: {}", solve2(&input)); +} + +#[cfg(test)] +const TEST_INPUT: &'static str = " +eedadn +drvtee +eandsr +raavrd +atevrs +tsrnev +sdttsa +rasrtv +nssdts +ntnada +svetve +tesnvt +vntsnd +vrdear +dvrsen +enarar +"; + + +#[test] +fn part1() { + assert_eq!("easter", solve1(TEST_INPUT.trim())); +} + +#[test] +fn part2() { + assert_eq!("advent", solve2(TEST_INPUT.trim())); +} diff --git a/2016/src/bin/day07.rs b/2016/src/bin/day07.rs new file mode 100644 index 0000000..b4967ff --- /dev/null +++ b/2016/src/bin/day07.rs @@ -0,0 +1,119 @@ +use std::io::{self, Read}; +use std::str::FromStr; + +fn has_abba(s: &str) -> bool { + s.as_bytes() + .windows(4) + .any(|window| { + window[0] == window[3] + && window[1] == window[2] + && window[0] != window[1] + }) +} + +fn abas(s: &str) -> Vec<&[u8]> { + s.as_bytes() + .windows(3) + .filter(|window| { + window[0] == window[2] + && window[0] != window[1] + }) + .collect() +} + +fn has_bab(s: &str, aba: &[u8]) -> bool { + s.as_bytes() + .windows(3) + .any(|window| { + window[0] == aba[1] + && window[1] == aba[0] + && window[2] == aba[1] + }) +} + +#[derive(Default)] +struct Ip { + supernet: Vec, + hypernet: Vec, +} + +impl Ip { + fn supports_tls(&self) -> bool { + self.supernet.iter().any(|s| has_abba(s)) + && !self.hypernet.iter().any(|s| has_abba(s)) + } + + fn supports_ssl(&self) -> bool { + self.supernet + .iter() + .flat_map(|s| abas(s)) + .any(|aba| { + self.hypernet + .iter() + .any(|s| has_bab(s, aba)) + }) + } +} + +impl FromStr for Ip { + type Err = (); + fn from_str(s: &str) -> Result { + let mut ip = Ip::default(); + + for (i, seq) in s.split(|ch| ch == '[' || ch == ']').enumerate() { + if i % 2 == 0 { + ip.supernet.push(seq.to_owned()); + } else { + ip.hypernet.push(seq.to_owned()); + } + } + + Ok(ip) + } +} + +fn solve1(input: &str) -> usize { + input.lines() + .map(str::parse) + .map(Result::unwrap) + .filter(Ip::supports_tls) + .count() +} + +fn solve2(input: &str) -> usize { + input.lines() + .map(str::parse) + .map(Result::unwrap) + .filter(Ip::supports_ssl) + .count() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(&input)); + println!("Part 2: {}", solve2(&input)); +} + +#[test] +fn part1() { + let input = " +abba[mnop]qrst +abcd[bddb]xyyx +aaaa[qwer]tyui +ioxxoj[asdfgh]zxcvbn +"; + assert_eq!(2, solve1(input.trim())); +} + +#[test] +fn part2() { + let input = " +aba[bab]xyz +xyx[xyx]xyx +aaa[kek]eke +zazbz[bzb]cdb +"; + assert_eq!(3, solve2(input.trim())); +} diff --git a/2016/src/bin/day08.rs b/2016/src/bin/day08.rs new file mode 100644 index 0000000..1443ec3 --- /dev/null +++ b/2016/src/bin/day08.rs @@ -0,0 +1,148 @@ +use std::fmt::{Display as FmtDisplay, Error as FmtError, Formatter}; +use std::io::{self, Read}; +use std::ops::{Index, IndexMut}; +use std::str::FromStr; + +enum Operation { + Rect(usize, usize), + RotateRow(usize, usize), + RotateColumn(usize, usize), +} + +impl FromStr for Operation { + type Err = (); + fn from_str(s: &str) -> Result { + if s.starts_with("rect") { + let mut iter = s[5..].split('x'); + let width = iter.next().ok_or(())?.parse().map_err(|_| ())?; + let height = iter.next().ok_or(())?.parse().map_err(|_| ())?; + Ok(Operation::Rect(width, height)) + + } else if s.starts_with("rotate row") { + let mut iter = s[13..].split(" by "); + let y = iter.next().ok_or(())?.parse().map_err(|_| ())?; + let count = iter.next().ok_or(())?.parse().map_err(|_| ())?; + Ok(Operation::RotateRow(y, count)) + + } else if s.starts_with("rotate column") { + let mut iter = s[16..].split(" by "); + let x = iter.next().ok_or(())?.parse().map_err(|_| ())?; + let count = iter.next().ok_or(())?.parse().map_err(|_| ())?; + Ok(Operation::RotateColumn(x, count)) + + } else { + Err(()) + } + } +} + +struct Display { + width: usize, + height: usize, + pixels: Box<[bool]>, +} + +impl Index<(usize, usize)> for Display { + type Output = bool; + fn index(&self, index: (usize, usize)) -> &bool { + &self.pixels[index.1 * self.width + index.0] + } +} + +impl IndexMut<(usize, usize)> for Display { + fn index_mut(&mut self, index: (usize, usize)) -> &mut bool { + &mut self.pixels[index.1 * self.width + index.0] + } +} + +impl Display { + fn new(width: usize, height: usize) -> Self { + Display { + width: width, + height: height, + pixels: vec![false; width * height].into_boxed_slice(), + } + } + + fn apply(&mut self, operation: Operation) { + match operation { + Operation::Rect(width, height) => { + for y in 0..height { + for x in 0..width { + self[(x, y)] = true; + } + } + }, + + Operation::RotateRow(y, count) => { + for _ in 0..count { + let last = self[(self.width - 1, y)]; + for x in (1..self.width).rev() { + self[(x, y)] = self[(x - 1, y)]; + } + self[(0, y)] = last; + } + }, + + Operation::RotateColumn(x, count) => { + for _ in 0..count { + let last = self[(x, self.height - 1)]; + for y in (1..self.height).rev() { + self[(x, y)] = self[(x, y - 1)]; + } + self[(x, 0)] = last; + } + }, + } + } + + fn pixels_lit(&self) -> usize { + self.pixels.iter().filter(|&&p| p).count() + } +} + +impl FmtDisplay for Display { + fn fmt(&self, f: &mut Formatter) -> Result<(), FmtError> { + for y in 0..self.height { + for x in 0..self.width { + if self[(x, y)] { + write!(f, "#")?; + } else { + write!(f, " ")?; + } + } + write!(f, "\n")?; + } + Ok(()) + } +} + +fn solve(width: usize, height: usize, input: &str) -> Display { + let mut display = Display::new(width, height); + + for line in input.lines() { + display.apply(line.parse().unwrap()); + } + + display +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + let display = solve(50, 6, &input); + println!("Part 1: {}", display.pixels_lit()); + println!("Part 2:\n{}", display); +} + +#[test] +fn part1() { + let input = " +rect 3x2 +rotate column x=1 by 1 +rotate row y=0 by 4 +rotate row x=1 by 1 +"; + assert_eq!(6, solve(7, 3, input.trim()).pixels_lit()); +} diff --git a/2016/src/bin/day09.rs b/2016/src/bin/day09.rs new file mode 100644 index 0000000..f559b47 --- /dev/null +++ b/2016/src/bin/day09.rs @@ -0,0 +1,124 @@ +use std::io::{self, Read}; + +enum Chunk<'a> { + Literal(&'a str), + Repeat(u32, &'a str), + Recursive(u32, Vec>), +} + +impl<'a> Chunk<'a> { + fn len(&self) -> usize { + match *self { + Chunk::Literal(s) => s.len(), + Chunk::Repeat(n, s) => n as usize * s.len(), + Chunk::Recursive(n, ref cs) => n as usize * cs.iter().map(Chunk::len).sum::(), + } + } + + fn parse(s: &'a str) -> Result<(Self, &'a str), ()> { + if s.starts_with('(') { + let mut iter = s[1..].splitn(3, |ch| ch == 'x' || ch == ')'); + + let len = iter.next().ok_or(())?.parse().map_err(|_| ())?; + let repeat = iter.next().ok_or(())?.parse().map_err(|_| ())?; + let (data, rest) = iter.next().ok_or(())?.split_at(len); + + Ok((Chunk::Repeat(repeat, data), rest)) + } else { + let paren = s.find('(').unwrap_or(s.len()); + Ok((Chunk::Literal(&s[..paren]), &s[paren..])) + } + } + + fn parse_v2(s: &'a str) -> Result<(Self, &'a str), ()> { + if s.starts_with('(') { + let mut iter = s[1..].splitn(3, |ch| ch == 'x' || ch == ')'); + + let len = iter.next().ok_or(())?.parse().map_err(|_| ())?; + let repeat = iter.next().ok_or(())?.parse().map_err(|_| ())?; + let (mut data, rest) = iter.next().ok_or(())?.split_at(len); + + let mut chunks = Vec::new(); + while !data.is_empty() { + let (chunk, data_rest) = Chunk::parse_v2(data)?; + chunks.push(chunk); + data = data_rest; + } + + Ok((Chunk::Recursive(repeat, chunks), rest)) + } else { + let paren = s.find('(').unwrap_or(s.len()); + Ok((Chunk::Literal(&s[..paren]), &s[paren..])) + } + } +} + +struct File<'a> { + chunks: Vec>, +} + +impl<'a> File<'a> { + fn len(&self) -> usize { + self.chunks.iter().map(Chunk::len).sum() + } + + fn parse(mut s: &'a str) -> Result { + let mut chunks = Vec::new(); + + while !s.is_empty() { + let (chunk, rest) = Chunk::parse(s)?; + chunks.push(chunk); + s = rest; + } + + Ok(File { chunks: chunks }) + } + + fn parse_v2(mut s: &'a str) -> Result { + let mut chunks = Vec::new(); + + while !s.is_empty() { + let (chunk, rest) = Chunk::parse_v2(s)?; + chunks.push(chunk); + s = rest; + } + + Ok(File { chunks: chunks }) + } +} + +fn solve1(input: &str) -> usize { + let file = File::parse(input).unwrap(); + file.len() +} + +fn solve2(input: &str) -> usize { + let file = File::parse_v2(input).unwrap(); + file.len() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(&input)); + println!("Part 2: {}", solve2(&input)); +} + +#[test] +fn part1() { + assert_eq!(6, solve1("ADVENT")); + assert_eq!(7, solve1("A(1x5)BC")); + assert_eq!(9, solve1("(3x3)XYZ")); + assert_eq!(11, solve1("A(2x2)BCD(2x2)EFG")); + assert_eq!(6, solve1("(6x1)(1x3)A")); + assert_eq!(18, solve1("X(8x2)(3x3)ABCY")); +} + +#[test] +fn part2() { + assert_eq!(9, solve2("(3x3)XYZ")); + assert_eq!(20, solve2("X(8x2)(3x3)ABCY")); + assert_eq!(241920, solve2("(27x12)(20x12)(13x14)(7x10)(1x12)A")); + assert_eq!(445, solve2("(25x3)(3x3)ABC(2x3)XY(5x2)PQRSTX(18x9)(3x2)TWO(5x7)SEVEN")); +} diff --git a/2016/src/bin/day10.rs b/2016/src/bin/day10.rs new file mode 100644 index 0000000..a824f56 --- /dev/null +++ b/2016/src/bin/day10.rs @@ -0,0 +1,180 @@ +use std::collections::HashMap; +use std::io::{self, Read}; +use std::str::FromStr; + +#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)] +struct Chip(u32); + +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +struct Bot(u32); + +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +struct Output(u32); + +#[derive(Clone, Copy, Default)] +struct BotChips(Option, Option); + +impl BotChips { + fn add(&mut self, chip: Chip) { + match (self.0, self.1) { + (None, None) => { + self.0 = Some(chip); + }, + (Some(low), None) if low < chip => { + self.1 = Some(chip); + }, + (Some(high), None) => { + self.0 = Some(chip); + self.1 = Some(high); + }, + _ => panic!("bot has too many chips"), + } + } + + fn has_two(&self) -> bool { + self.0.is_some() && self.1.is_some() + } +} + +#[derive(Clone, Copy)] +enum Destination { + Bot(Bot), + Output(Output), +} + +impl Destination { + fn from_pair(ty: &str, value: u32) -> Result { + match ty { + "bot" => Ok(Destination::Bot(Bot(value))), + "output" => Ok(Destination::Output(Output(value))), + _ => Err(()), + } + } +} + +#[derive(Default)] +struct Instructions { + chips: HashMap, + bots: HashMap, +} + +impl FromStr for Instructions { + type Err = (); + fn from_str(s: &str) -> Result { + let mut instructions = Instructions::default(); + + for line in s.lines() { + let mut words = line.split(' '); + if words.next() == Some("value") { + let value = words.next().ok_or(())?.parse().map_err(|_| ())?; + let bot = words.nth(3).ok_or(())?.parse().map_err(|_| ())?; + + instructions.chips.insert(Chip(value), Bot(bot)); + } else { + let bot = words.next().ok_or(())?.parse().map_err(|_| ())?; + let low_type = words.nth(3).ok_or(())?; + let low_value = words.next().ok_or(())?.parse().map_err(|_| ())?; + let high_type = words.nth(3).ok_or(())?; + let high_value = words.next().ok_or(())?.parse().map_err(|_| ())?; + + let low = Destination::from_pair(low_type, low_value)?; + let high = Destination::from_pair(high_type, high_value)?; + + instructions.bots.insert(Bot(bot), (low, high)); + } + } + + Ok(instructions) + } +} + +#[derive(Default)] +struct State { + outputs: HashMap, + bots: HashMap, + comparisons: HashMap<(Chip, Chip), Bot>, +} + +impl State { + fn initialize(&mut self, instructions: &Instructions) { + for (&chip, &bot) in &instructions.chips { + self.bots.entry(bot).or_insert_with(Default::default).add(chip); + } + } + + fn step(&mut self, instructions: &Instructions) -> bool { + let active_bots: Vec = self.bots.iter() + .filter(|&(_, ref chips)| chips.has_two()) + .map(|(&bot, _)| bot) + .collect(); + + if active_bots.is_empty() { + return false; + } + + for bot in active_bots { + let (low, high) = { + let chips = self.bots.get_mut(&bot).unwrap(); + (chips.0.take().unwrap(), chips.1.take().unwrap()) + }; + self.comparisons.insert((low, high), bot); + + let &(low_dest, high_dest) = instructions.bots.get(&bot).unwrap(); + self.give_to(low_dest, low); + self.give_to(high_dest, high); + } + + true + } + + fn give_to(&mut self, destination: Destination, chip: Chip) { + match destination { + Destination::Bot(bot) => { + self.bots.entry(bot).or_insert_with(Default::default).add(chip); + }, + Destination::Output(output) => { + self.outputs.insert(output, chip); + }, + } + } +} + +fn solve1(comparison: (Chip, Chip), input: &str) -> Option { + let instructions = input.parse().unwrap(); + let mut state = State::default(); + state.initialize(&instructions); + while state.step(&instructions) { } + state.comparisons.get(&comparison).cloned() +} + +fn solve2(input: &str) -> u32 { + let instructions = input.parse().unwrap(); + let mut state = State::default(); + state.initialize(&instructions); + while state.step(&instructions) { } + + state.outputs.get(&Output(0)).unwrap().0 + * state.outputs.get(&Output(1)).unwrap().0 + * state.outputs.get(&Output(2)).unwrap().0 +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {:?}", solve1((Chip(17), Chip(61)), &input)); + println!("Part 2: {}", solve2(&input)); +} + +#[test] +fn part1() { + let input = " +value 5 goes to bot 2 +bot 2 gives low to bot 1 and high to bot 0 +value 3 goes to bot 1 +bot 1 gives low to output 1 and high to bot 0 +bot 0 gives low to output 2 and high to output 0 +value 2 goes to bot 2 +"; + assert_eq!(Some(Bot(2)), solve1((Chip(2), Chip(5)), input.trim())); +} diff --git a/2016/src/bin/day11.rs b/2016/src/bin/day11.rs new file mode 100644 index 0000000..c033766 --- /dev/null +++ b/2016/src/bin/day11.rs @@ -0,0 +1,194 @@ +use std::collections::{HashSet, VecDeque}; + +#[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)] +enum Object { + Microchip(u8), + Generator(u8), +} + +impl Object { + fn is_microchip(self) -> bool { + match self { + Object::Microchip(_) => true, + _ => false, + } + } + + fn is_generator(self) -> bool { + match self { + Object::Generator(_) => true, + _ => false, + } + } + + fn generator(self) -> Self { + match self { + Object::Microchip(k) => Object::Generator(k), + _ => self, + } + } +} + +#[derive(Default, Clone)] +struct Floor { + objects: HashSet, +} + +impl Floor { + fn is_empty(&self) -> bool { + self.objects.is_empty() + } + + fn is_safe(&self) -> bool { + for &chip in self.objects.iter().filter(|&&o| o.is_microchip()) { + let accompanied = self.objects.contains(&chip.generator()); + let generator = self.objects.iter().any(|&o| o.is_generator()); + if !accompanied && generator { return false } + } + true + } +} + +#[derive(Clone)] +struct State { + steps: u32, + floors: Box<[Floor]>, + elevator: usize, +} + +impl State { + fn is_goal(&self) -> bool { + self.floors[0..3].iter().all(Floor::is_empty) + } + + fn is_safe(&self) -> bool { + self.floors.iter().all(Floor::is_safe) + } + + fn clone_up(&self) -> Self { + let mut state = self.clone(); + state.steps += 1; + state.elevator += 1; + state + } + + fn clone_down(&self) -> Self { + let mut state = self.clone(); + state.steps += 1; + state.elevator -= 1; + state + } + + fn generate_states(&self, states: &mut VecDeque) { + for &object in &self.floors[self.elevator].objects { + for &other in &self.floors[self.elevator].objects { + if other == object { continue } + if self.elevator != 3 { + let mut state = self.clone_up(); + state.floors[self.elevator].objects.remove(&object); + state.floors[self.elevator].objects.remove(&other); + state.floors[state.elevator].objects.insert(object); + state.floors[state.elevator].objects.insert(other); + if state.is_safe() { states.push_back(state) } + } + if self.elevator != 0 { + let mut state = self.clone_down(); + state.floors[self.elevator].objects.remove(&object); + state.floors[self.elevator].objects.remove(&other); + state.floors[state.elevator].objects.insert(object); + state.floors[state.elevator].objects.insert(other); + if state.is_safe() { states.push_back(state) } + } + } + + if self.elevator != 3 { + let mut state = self.clone_up(); + state.floors[self.elevator].objects.remove(&object); + state.floors[state.elevator].objects.insert(object); + if state.is_safe() { states.push_back(state) } + } + if self.elevator != 0 { + let mut state = self.clone_down(); + state.floors[self.elevator].objects.remove(&object); + state.floors[state.elevator].objects.insert(object); + if state.is_safe() { states.push_back(state) } + } + } + } +} + +fn solve(floors: Vec) -> u32 { + let mut visited = HashSet::new(); + let mut states = VecDeque::new(); + states.push_back(State { steps: 0, floors: floors.into_boxed_slice(), elevator: 0 }); + + while let Some(state) = states.pop_front() { + if state.is_goal() { + return state.steps; + } + let visit_floors: Vec<_> = state.floors.iter().map(|floor| { + let mut vec: Vec<_> = floor.objects.iter().cloned().collect(); + vec.sort(); + vec + }).collect(); + if visited.insert((state.elevator, visit_floors)) { + state.generate_states(&mut states); + } + } + + unreachable!() +} + +fn main() { + // The first floor contains a promethium generator and a promethium-compatible microchip. + // The second floor contains a cobalt generator, a curium generator, a ruthenium generator, and a plutonium generator. + // The third floor contains a cobalt-compatible microchip, a curium-compatible microchip, a ruthenium-compatible microchip, and a plutonium-compatible microchip. + // The fourth floor contains nothing relevant. + const PROMETHIUM: u8 = 0; + const COBALT: u8 = 1; + const CURIUM: u8 = 2; + const RUTHENIUM: u8 = 3; + const PLUTONIUM: u8 = 4; + let mut floors = vec![Floor::default(); 4]; + floors[0].objects.insert(Object::Generator(PROMETHIUM)); + floors[0].objects.insert(Object::Microchip(PROMETHIUM)); + floors[1].objects.insert(Object::Generator(COBALT)); + floors[1].objects.insert(Object::Generator(CURIUM)); + floors[1].objects.insert(Object::Generator(RUTHENIUM)); + floors[1].objects.insert(Object::Generator(PLUTONIUM)); + floors[2].objects.insert(Object::Microchip(COBALT)); + floors[2].objects.insert(Object::Microchip(CURIUM)); + floors[2].objects.insert(Object::Microchip(RUTHENIUM)); + floors[2].objects.insert(Object::Microchip(PLUTONIUM)); + + println!("Part 1: {}", solve(floors.clone())); + + + // An elerium generator. + // An elerium-compatible microchip. + // A dilithium generator. + // A dilithium-compatible microchip. + const ELERIUM: u8 = 5; + const DILITHIUM: u8 = 6; + floors[0].objects.insert(Object::Generator(ELERIUM)); + floors[0].objects.insert(Object::Microchip(ELERIUM)); + floors[0].objects.insert(Object::Generator(DILITHIUM)); + floors[0].objects.insert(Object::Microchip(DILITHIUM)); + println!("Part 2: {}", solve(floors)); +} + +#[test] +#[ignore] +fn part1() { + // The first floor contains a hydrogen-compatible microchip and a lithium-compatible microchip. + // The second floor contains a hydrogen generator. + // The third floor contains a lithium generator. + // The fourth floor contains nothing relevant. + let mut floors = vec![Floor::default(); 4]; + floors[0].objects.insert(Object::Microchip(0)); + floors[0].objects.insert(Object::Microchip(1)); + floors[1].objects.insert(Object::Generator(0)); + floors[2].objects.insert(Object::Generator(1)); + + assert_eq!(11, solve(floors)); +} diff --git a/2016/src/bin/day12.rs b/2016/src/bin/day12.rs new file mode 100644 index 0000000..6655947 --- /dev/null +++ b/2016/src/bin/day12.rs @@ -0,0 +1,143 @@ +use std::io::{self, Read}; +use std::str::FromStr; + +#[derive(Clone, Copy)] +enum Operand { + Register(u8), + Immediate(i32), +} + +impl FromStr for Operand { + type Err = (); + fn from_str(s: &str) -> Result { + match s { + "a" => Ok(Operand::Register(0)), + "b" => Ok(Operand::Register(1)), + "c" => Ok(Operand::Register(2)), + "d" => Ok(Operand::Register(3)), + _ => Ok(Operand::Immediate(s.parse().map_err(|_| ())?)), + } + } +} + +#[derive(Clone, Copy)] +enum Operation { + Cpy(Operand, Operand), + Inc(Operand), + Dec(Operand), + Jnz(Operand, Operand), +} + +impl FromStr for Operation { + type Err = (); + fn from_str(s: &str) -> Result { + let mut iter = s.split(' '); + match iter.next() { + Some("cpy") => { + let src = iter.next().ok_or(())?.parse()?; + let dest = iter.next().ok_or(())?.parse()?; + Ok(Operation::Cpy(src, dest)) + }, + Some("inc") => Ok(Operation::Inc(iter.next().ok_or(())?.parse()?)), + Some("dec") => Ok(Operation::Dec(iter.next().ok_or(())?.parse()?)), + Some("jnz") => { + let cond = iter.next().ok_or(())?.parse()?; + let jump = iter.next().ok_or(())?.parse()?; + Ok(Operation::Jnz(cond, jump)) + }, + _ => Err(()), + } + } +} + +#[derive(Default)] +struct Vm { + registers: [i32; 4], + operations: Vec, + index: i32, +} + +impl FromStr for Vm { + type Err = (); + fn from_str(s: &str) -> Result { + let mut vm = Self::default(); + for line in s.lines() { + vm.operations.push(line.parse()?); + } + Ok(vm) + } +} + +impl Vm { + fn step(&mut self) -> bool { + match self.operations[self.index as usize] { + Operation::Cpy(Operand::Immediate(imm), Operand::Register(reg)) => { + self.registers[reg as usize] = imm; + self.index += 1; + }, + Operation::Cpy(Operand::Register(src), Operand::Register(dest)) => { + self.registers[dest as usize] = self.registers[src as usize]; + self.index += 1; + }, + Operation::Inc(Operand::Register(reg)) => { + self.registers[reg as usize] += 1; + self.index += 1; + }, + Operation::Dec(Operand::Register(reg)) => { + self.registers[reg as usize] -= 1; + self.index += 1; + }, + Operation::Jnz(Operand::Immediate(cond), Operand::Immediate(jump)) => { + if cond != 0 { + self.index += jump; + } else { + self.index += 1; + } + }, + Operation::Jnz(Operand::Register(reg), Operand::Immediate(jump)) => { + if self.registers[reg as usize] != 0 { + self.index += jump; + } else { + self.index += 1; + } + }, + _ => panic!("invalid operation"), + } + + (self.index as usize) < self.operations.len() + } +} + +fn solve1(input: &str) -> i32 { + let mut vm: Vm = input.parse().unwrap(); + while vm.step() { } + vm.registers[0] +} + +fn solve2(input: &str) -> i32 { + let mut vm: Vm = input.parse().unwrap(); + vm.registers[2] = 1; + while vm.step() { } + vm.registers[0] +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(&input)); + println!("Part 2: {}", solve2(&input)); +} + +#[test] +fn part1() { + let input = " +cpy 41 a +inc a +inc a +dec a +jnz a 2 +dec a +"; + assert_eq!(42, solve1(input.trim())); +} diff --git a/2016/src/bin/day13.rs b/2016/src/bin/day13.rs new file mode 100644 index 0000000..060f571 --- /dev/null +++ b/2016/src/bin/day13.rs @@ -0,0 +1,122 @@ +use std::collections::{HashMap, VecDeque}; +use std::io::{self, Read}; + +#[derive(Clone, Copy, PartialEq, Eq, Hash)] +struct Point { + x: u32, + y: u32, +} + +const START: Point = Point { x: 1, y: 1 }; + +impl Point { + fn north(self) -> Option { + if self.y == 0 { + None + } else { + Some(Point { x: self.x, y: self.y - 1 }) + } + } + + fn east(self) -> Point { + Point { x: self.x + 1, y: self.y } + } + + fn south(self) -> Point { + Point { x: self.x, y: self.y + 1 } + } + + fn west(self) -> Option { + if self.x == 0 { + None + } else { + Some(Point { x: self.x - 1, y: self.y }) + } + } + + fn neighbors(self) -> [Option; 4] { + [self.north(), Some(self.east()), Some(self.south()), self.west()] + } +} + +#[derive(Clone, Copy)] +struct Layout { + constant: u32, +} + +impl Layout { + fn is_open(&self, point: Point) -> bool { + let Point { x, y } = point; + let sum = x * x + 3 * x + 2 * x * y + y + y * y + self.constant; + sum.count_ones() % 2 == 0 + } +} + +fn solve1(goal: Point, constant: u32) -> u32 { + let layout = Layout { constant: constant }; + + let mut distance = HashMap::new(); + let mut frontier = VecDeque::new(); + frontier.push_back(START); + distance.insert(START, 0); + + while let Some(current) = frontier.pop_front() { + if current == goal { break; } + let current_distance = *distance.get(¤t).unwrap(); + + let neighbors = current.neighbors(); + let iter = neighbors.iter() + .filter_map(|&p| p) + .filter(|&p| layout.is_open(p)); + + for next in iter { + if !distance.contains_key(&next) { + frontier.push_back(next); + distance.insert(next, current_distance + 1); + } + } + } + + *distance.get(&goal).unwrap() +} + +fn solve2(limit: u32, constant: u32) -> usize { + let layout = Layout { constant: constant }; + + let mut distance = HashMap::new(); + let mut frontier = VecDeque::new(); + frontier.push_back(START); + distance.insert(START, 0); + + while let Some(current) = frontier.pop_front() { + let current_distance = *distance.get(¤t).unwrap(); + if current_distance == limit { continue; } + + let neighbors = current.neighbors(); + let iter = neighbors.iter() + .filter_map(|&p| p) + .filter(|&p| layout.is_open(p)); + + for next in iter { + if !distance.contains_key(&next) { + frontier.push_back(next); + distance.insert(next, current_distance + 1); + } + } + } + + distance.len() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(Point { x: 31, y: 39 }, input.trim().parse().unwrap())); + println!("Part 2: {}", solve2(50, input.trim().parse().unwrap())); +} + +#[test] +fn part1() { + assert_eq!(11, solve1(Point { x: 7, y: 4 }, 10)); +} diff --git a/2016/src/bin/day14.rs b/2016/src/bin/day14.rs new file mode 100644 index 0000000..352982d --- /dev/null +++ b/2016/src/bin/day14.rs @@ -0,0 +1,87 @@ +extern crate crypto; + +use std::collections::VecDeque; +use std::io::{self, Read}; +use std::iter; + +use crypto::digest::Digest; +use crypto::md5::Md5; + +trait Hash { + fn hash(salt: &str, index: u32) -> String; +} + +struct Part1; +impl Hash for Part1 { + fn hash(salt: &str, index: u32) -> String { + let mut md5 = Md5::new(); + md5.input_str(salt); + md5.input_str(&index.to_string()); + md5.result_str() + } +} + +struct Part2; +impl Hash for Part2 { + fn hash(salt: &str, index: u32) -> String { + let mut hash = Part1::hash(salt, index); + for _ in 0..2016 { + let mut md5 = Md5::new(); + md5.input_str(&hash); + hash = md5.result_str(); + } + hash + } +} + +fn solve(salt: &str) -> u32 { + let mut hashes = VecDeque::new(); + for i in 0..1001 { + hashes.push_back(H::hash(salt, i)); + } + + let mut keys = 0; + let mut index = 0; + while let Some(hash) = hashes.pop_front() { + let triple = hash.as_bytes() + .windows(3) + .filter(|w| w[0] == w[1] && w[1] == w[2]) + .map(|w| w[0]) + .next(); + + if let Some(ch) = triple { + let quintuple: String = iter::repeat(ch as char).take(5).collect(); + if hashes.iter().any(|hash| hash.contains(&quintuple)) { + keys += 1; + if keys == 64 { + return index; + } + } + } + + index += 1; + hashes.push_back(H::hash(salt, 1000 + index)); + } + + unreachable!() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve::(input.trim())); + println!("Part 2: {}", solve::(input.trim())); +} + +#[test] +#[ignore] +fn part1() { + assert_eq!(22728, solve::("abc")); +} + +#[test] +#[ignore] +fn part2() { + assert_eq!(22551, solve::("abc")); +} diff --git a/2016/src/bin/day15.rs b/2016/src/bin/day15.rs new file mode 100644 index 0000000..ec9df7a --- /dev/null +++ b/2016/src/bin/day15.rs @@ -0,0 +1,103 @@ +use std::io::{self, Read}; + +#[derive(Clone, Copy)] +struct Disc { + positions: u32, + position: u32, +} + +impl Disc { + fn rotate(&mut self) { + self.position = (self.position + 1) % self.positions; + } + + fn is_open(&self) -> bool { + self.position == 0 + } +} + +impl<'a> From<&'a str> for Disc { + fn from(s: &'a str) -> Disc { + let mut iter = s.trim_right_matches('.').split_whitespace(); + Disc { + positions: iter.nth(3).unwrap().parse().unwrap(), + position: iter.last().unwrap().parse().unwrap(), + } + } +} + +#[derive(Clone)] +struct Sculpture { + discs: Vec, + time: u32, + capsule: usize, +} + +impl Sculpture { + fn tick(&mut self) { + self.time += 1; + for disc in &mut self.discs { + disc.rotate() + } + } + + fn drop_capsule(&mut self) -> bool { + while self.capsule < self.discs.len() { + self.tick(); + if self.discs[self.capsule].is_open() { + self.capsule += 1; + } else { + return false; + } + } + true + } +} + +impl<'a> From<&'a str> for Sculpture { + fn from(s: &'a str) -> Sculpture { + Sculpture { + discs: s.lines().map(Disc::from).collect(), + time: 0, + capsule: 0, + } + } +} + +fn solve1(input: &str) -> u32 { + let mut sculpture = Sculpture::from(input); + loop { + if sculpture.clone().drop_capsule() { + return sculpture.time; + } + sculpture.tick(); + } +} + +fn solve2(input: &str) -> u32 { + let mut sculpture = Sculpture::from(input); + sculpture.discs.push(Disc { positions: 11, position: 0 }); + loop { + if sculpture.clone().drop_capsule() { + return sculpture.time; + } + sculpture.tick(); + } +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(&input)); + println!("Part 2: {}", solve2(&input)); +} + +#[test] +fn part1() { + let input = " +Disc #1 has 5 positions; at time=0, it is at position 4. +Disc #2 has 2 positions; at time=0, it is at position 1. +"; + assert_eq!(5, solve1(input.trim())); +} diff --git a/2016/src/bin/day16.rs b/2016/src/bin/day16.rs new file mode 100644 index 0000000..247d9fd --- /dev/null +++ b/2016/src/bin/day16.rs @@ -0,0 +1,51 @@ +use std::io::{self, Read}; + +fn fill_disk(initial_state: &str, len: usize) -> String { + let mut state = String::from(initial_state); + while state.len() < len { + let mut b: Vec = state.bytes() + .map(|b| { + match b { + b'0' => b'1', + b'1' => b'0', + _ => b, + } + }) + .collect(); + b.reverse(); + let b = String::from_utf8(b).unwrap(); + state.push('0'); + state.push_str(&b); + } + state.truncate(len); + state +} + +fn checksum(data: &str) -> String { + let mut sum = String::from(data); + while sum.len() % 2 == 0 { + sum = sum.as_bytes() + .chunks(2) + .map(|c| if c[0] == c[1] { '1' } else { '0' }) + .collect(); + } + sum +} + +fn solve(len: usize, initial_state: &str) -> String { + let data = fill_disk(initial_state, len); + checksum(&data) +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve(272, input.trim())); + println!("Part 2: {}", solve(35651584, input.trim())); +} + +#[test] +fn part1() { + assert_eq!("01100", solve(20, "10000")); +} diff --git a/2016/src/bin/day17.rs b/2016/src/bin/day17.rs new file mode 100644 index 0000000..c769f32 --- /dev/null +++ b/2016/src/bin/day17.rs @@ -0,0 +1,148 @@ +extern crate crypto; + +use std::collections::VecDeque; +use std::io::{self, Read}; + +use crypto::digest::Digest; +use crypto::md5::Md5; + +#[derive(Clone, Copy)] +enum Direction { + Up, + Down, + Left, + Right, +} + +const DIRECTIONS: &'static [Direction] = &[ + Direction::Up, + Direction::Down, + Direction::Left, + Direction::Right, +]; + +impl From for char { + fn from(direction: Direction) -> Self { + match direction { + Direction::Up => 'U', + Direction::Down => 'D', + Direction::Left => 'L', + Direction::Right => 'R', + } + } +} + +#[derive(Default, Clone, Copy)] +struct Room { + x: u8, + y: u8, +} + +impl Room { + fn neighbor(self, direction: Direction) -> Option { + match direction { + Direction::Up if self.y != 0 => Some(Room { x: self.x, y: self.y - 1 }), + Direction::Down if self.y != 3 => Some(Room { x: self.x, y: self.y + 1 }), + Direction::Left if self.x != 0 => Some(Room { x: self.x - 1, y: self.y }), + Direction::Right if self.x != 3 => Some(Room { x: self.x + 1, y: self.y }), + _ => None, + } + } + + fn is_vault(self) -> bool { + self.x == 3 && self.y == 3 + } +} + +#[derive(Default, Clone)] +struct State { + room: Room, + path: Vec, +} + +impl<'a> From<&'a State> for String { + fn from(state: &'a State) -> String { + state.path.iter().cloned().map(char::from).collect() + } +} + +impl State { + fn is_vault(&self) -> bool { + self.room.is_vault() + } + + fn generate_states(&self, states: &mut VecDeque, passcode: &str) { + let mut md5 = Md5::new(); + md5.input_str(passcode); + md5.input_str(&String::from(self)); + let hash = md5.result_str(); + + for (direction, ch) in DIRECTIONS.iter().cloned().zip(hash.chars()) { + if ch < 'b' || ch > 'f' { continue } + + let room = match self.room.neighbor(direction) { + Some(r) => r, + None => continue, + }; + + let mut path = self.path.clone(); + path.push(direction); + + states.push_back(State { room: room, path: path }); + } + } +} + +fn solve1(passcode: &str) -> String { + let mut states = VecDeque::new(); + states.push_back(State::default()); + + while let Some(state) = states.pop_front() { + if state.is_vault() { + return String::from(&state); + } + state.generate_states(&mut states, passcode); + } + + panic!("no path to vault") +} + +fn solve2(passcode: &str) -> usize { + let mut states = VecDeque::new(); + states.push_back(State::default()); + + let mut longest = None; + + while let Some(state) = states.pop_front() { + if state.is_vault() { + longest = Some(state.clone()); + } else { + state.generate_states(&mut states, passcode); + } + } + + longest.unwrap().path.len() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(input.trim())); + println!("Part 2: {}", solve2(input.trim())); +} + +#[test] +fn part1() { + assert_eq!("DDRRRD", solve1("ihgpwlah")); + assert_eq!("DDUDRLRRUDRD", solve1("kglvqrro")); + assert_eq!("DRURDRUDDLLDLUURRDULRLDUUDDDRR", solve1("ulqzkmiv")); +} + +#[test] +#[ignore] +fn part2() { + assert_eq!(370, solve2("ihgpwlah")); + assert_eq!(492, solve2("kglvqrro")); + assert_eq!(830, solve2("ulqzkmiv")); +} diff --git a/2016/src/bin/day18.rs b/2016/src/bin/day18.rs new file mode 100644 index 0000000..19f8c91 --- /dev/null +++ b/2016/src/bin/day18.rs @@ -0,0 +1,88 @@ +use std::io::{self, Read}; + +#[derive(Clone, Copy, PartialEq, Eq)] +enum Tile { + Safe, + Trap, +} + +impl From for Tile { + fn from(ch: char) -> Tile { + match ch { + '.' => Tile::Safe, + '^' => Tile::Trap, + _ => panic!("invalid tile char {}", ch), + } + } +} + +struct Map { + rows: Vec>, +} + +impl Map { + fn generate_row(&mut self) { + let mut next = Vec::new(); + + { + let previous = self.rows.last().unwrap(); + + for (i, ¢er) in self.rows.last().unwrap().iter().enumerate() { + let left = previous.get(i.wrapping_sub(1)).cloned().unwrap_or(Tile::Safe); + let right = previous.get(i + 1).cloned().unwrap_or(Tile::Safe); + + let tile = match (left, center, right) { + (Tile::Trap, Tile::Trap, Tile::Safe) => Tile::Trap, + (Tile::Safe, Tile::Trap, Tile::Trap) => Tile::Trap, + (Tile::Trap, Tile::Safe, Tile::Safe) => Tile::Trap, + (Tile::Safe, Tile::Safe, Tile::Trap) => Tile::Trap, + _ => Tile::Safe, + }; + next.push(tile); + } + } + + self.rows.push(next.into_boxed_slice()); + } + + fn count_safe(&self) -> usize { + self.rows.iter() + .map(|row| { + row.iter() + .filter(|&&t| t == Tile::Safe) + .count() + }) + .sum() + } +} + +impl<'a> From<&'a str> for Map { + fn from(s: &'a str) -> Map { + let rows = s.lines() + .map(|l| l.chars().map(Tile::from).collect::>().into_boxed_slice()) + .collect(); + Map { rows: rows } + } +} + +fn solve(rows: u32, input: &str) -> usize { + let mut map = Map::from(input); + for _ in 1..rows { + map.generate_row(); + } + map.count_safe() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve(40, &input)); + println!("Part 2: {}", solve(400000, &input)); +} + +#[test] +fn part1() { + assert_eq!(6, solve(3, "..^^.")); + assert_eq!(38, solve(10, ".^^.^.^^^^")); +} diff --git a/2016/src/bin/day19.rs b/2016/src/bin/day19.rs new file mode 100644 index 0000000..9afbf39 --- /dev/null +++ b/2016/src/bin/day19.rs @@ -0,0 +1,35 @@ +use std::collections::VecDeque; +use std::io::{self, Read}; + +#[derive(Clone, Copy)] +struct Elf { + position: usize, + gifts: usize, +} + +fn solve(count: usize) -> usize { + let mut circle: VecDeque = (0..count) + .map(|i| Elf { position: i + 1, gifts: 1 }) + .collect(); + + while circle.len() > 1 { + let mut current = circle.pop_front().unwrap(); + let next = circle.pop_front().unwrap(); + current.gifts += next.gifts; + circle.push_back(current); + } + + circle.pop_front().unwrap().position +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve(input.trim().parse().unwrap())); +} + +#[test] +fn part1() { + assert_eq!(3, solve(5)); +} diff --git a/2016/src/bin/day20.rs b/2016/src/bin/day20.rs new file mode 100644 index 0000000..0416ced --- /dev/null +++ b/2016/src/bin/day20.rs @@ -0,0 +1,77 @@ +use std::io::{self, Read}; +use std::u32; + +fn parse_ranges(input: &str) -> Vec<(u32, u32)> { + let mut ranges = vec![]; + for line in input.lines() { + let hyphen = line.find('-').unwrap(); + let (start, end) = line.split_at(hyphen); + let start = start.parse().unwrap(); + let end = end[1..].parse().unwrap(); + ranges.push((start, end)); + } + ranges.sort(); + ranges +} + +fn solve1(input: &str) -> u32 { + let ranges = parse_ranges(input); + let mut lowest = 0; + + for &(start, end) in &ranges { + if lowest >= start && lowest <= end { + lowest = end + 1; + } + } + + lowest +} + +fn solve2(input: &str) -> u32 { + let ranges = parse_ranges(input); + let mut merged = vec![]; + + for &(start, end) in &ranges { + if let Some(&mut (ref mut last_start, ref mut last_end)) = merged.last_mut() { + if start >= *last_start && end <= *last_end { + continue; + } else if start >= *last_start && start <= *last_end + 1 && end > *last_end { + *last_end = end; + continue; + } + } + merged.push((start, end)); + } + + let blocked: u32 = merged.iter().map(|&(start, end)| end - start + 1).sum(); + + u32::MAX - blocked + 1 +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1(&input)); + println!("Part 2: {}", solve2(&input)); +} + +#[test] +fn part1() { + let input = " +5-8 +0-2 +4-7 +"; + assert_eq!(3, solve1(input.trim())); +} + +#[test] +fn part2() { + let input = " +5-8 +0-2 +4-7 +"; + assert_eq!(u32::MAX - 7, solve2(input.trim())); +} diff --git a/2016/src/bin/day21.rs b/2016/src/bin/day21.rs new file mode 100644 index 0000000..982bf8a --- /dev/null +++ b/2016/src/bin/day21.rs @@ -0,0 +1,144 @@ +use std::io::{self, Read}; + +#[derive(Clone, Copy)] +enum Operation { + SwapPosition(usize, usize), + SwapLetter(u8, u8), + RotateLeft(usize), + RotateRight(usize), + RotateLetter(u8), + Reverse(usize, usize), + Move(usize, usize), +} + +impl Operation { + fn apply(self, slice: &mut [u8]) { + match self { + Operation::SwapPosition(i, j) => slice.swap(i, j), + Operation::SwapLetter(a, b) => { + let i = slice.iter().position(|&x| x == a).unwrap(); + let j = slice.iter().position(|&x| x == b).unwrap(); + slice.swap(i, j); + }, + Operation::RotateLeft(n) => { + let n = n % slice.len(); + slice[0..n].reverse(); + slice[n..].reverse(); + slice.reverse(); + }, + Operation::RotateRight(n) => { + let n = n % slice.len(); + slice.reverse(); + slice[0..n].reverse(); + slice[n..].reverse(); + }, + Operation::RotateLetter(a) => { + let mut n = 1 + slice.iter().position(|&x| x == a).unwrap(); + if n >= 5 { n += 1 } + n %= slice.len(); + slice.reverse(); + slice[0..n].reverse(); + slice[n..].reverse(); + }, + Operation::Reverse(i, j) => slice[i..(j + 1)].reverse(), + Operation::Move(i, j) if i < j => { + let a = slice[i]; + for k in i..j { + slice[k] = slice[k + 1]; + } + slice[j] = a; + }, + Operation::Move(i, j) => { + let a = slice[i]; + for k in (j..i).rev() { + slice[k + 1] = slice[k]; + } + slice[j] = a; + }, + } + } +} + +impl<'a> From<&'a str> for Operation { + fn from(s: &'a str) -> Self { + let mut iter = s.split_whitespace(); + match (iter.next().unwrap(), iter.next().unwrap()) { + ("swap", "position") => Operation::SwapPosition( + iter.next().unwrap().parse().unwrap(), + iter.nth(2).unwrap().parse().unwrap(), + ), + ("swap", "letter") => Operation::SwapLetter( + iter.next().unwrap().as_bytes()[0], + iter.nth(2).unwrap().as_bytes()[0], + ), + ("rotate", "left") => Operation::RotateLeft(iter.next().unwrap().parse().unwrap()), + ("rotate", "right") => Operation::RotateRight(iter.next().unwrap().parse().unwrap()), + ("rotate", "based") => Operation::RotateLetter(iter.nth(4).unwrap().as_bytes()[0]), + ("reverse", _) => Operation::Reverse( + iter.next().unwrap().parse().unwrap(), + iter.nth(1).unwrap().parse().unwrap(), + ), + ("move", _) => Operation::Move( + iter.next().unwrap().parse().unwrap(), + iter.nth(2).unwrap().parse().unwrap(), + ), + (x, y) => panic!("invalid operation {} {}", x, y), + } + } +} + +fn solve1(password: &str, input: &str) -> String { + let mut password = password.as_bytes().to_owned(); + + for operation in input.lines().map(Operation::from) { + operation.apply(&mut password); + } + + String::from_utf8(password).unwrap() +} + +fn solve2(scrambled: &str, input: &str) -> String { + let operations: Vec<_> = input.lines().map(Operation::from).collect(); + + let mut password = "abcdefgh".as_bytes().to_owned(); + let len = password.len(); + + loop { + let k = (0..(len - 1)).rev().find(|&k| password[k] < password [k + 1]).unwrap(); + let l = ((k + 1)..len).rev().find(|&l| password[k] < password[l]).unwrap(); + password.swap(k, l); + password[(k + 1)..].reverse(); + + let mut candidate = password.clone(); + for operation in &operations { + operation.apply(&mut candidate); + } + + if candidate == scrambled.as_bytes() { + return String::from_utf8(password).unwrap(); + } + } +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve1("abcdefgh", &input)); + println!("Part 2: {}", solve2("fbgdceah", &input)); +} + +#[test] +fn part1() { + let input = " +swap position 4 with position 0 +swap letter d with letter b +reverse positions 0 through 4 +rotate left 1 step +move position 1 to position 4 +move position 3 to position 0 +rotate based on position of letter b +rotate based on position of letter d +"; + assert_eq!("decab", solve1("abcde", input.trim())); +} diff --git a/2016/src/bin/day23.rs b/2016/src/bin/day23.rs new file mode 100644 index 0000000..4a54983 --- /dev/null +++ b/2016/src/bin/day23.rs @@ -0,0 +1,157 @@ +use std::io::{self, Read}; + +#[derive(Clone, Copy)] +enum Operand { + Register(u8), + Immediate(i32), +} + +impl<'a> From<&'a str> for Operand { + fn from(s: &'a str) -> Self { + match s { + "a" => Operand::Register(0), + "b" => Operand::Register(1), + "c" => Operand::Register(2), + "d" => Operand::Register(3), + _ => Operand::Immediate(s.parse().unwrap()), + } + } +} + +#[derive(Clone, Copy)] +enum Operation { + Cpy(Operand, Operand), + Inc(Operand), + Dec(Operand), + Jnz(Operand, Operand), + Tgl(Operand), +} + +impl<'a> From<&'a str> for Operation { + fn from(s: &'a str) -> Self { + let mut iter = s.split_whitespace(); + match (iter.next().unwrap(), iter.next().unwrap()) { + ("cpy", a) => Operation::Cpy(Operand::from(a), Operand::from(iter.next().unwrap())), + ("inc", a) => Operation::Inc(Operand::from(a)), + ("dec", a) => Operation::Dec(Operand::from(a)), + ("jnz", a) => Operation::Jnz(Operand::from(a), Operand::from(iter.next().unwrap())), + ("tgl", a) => Operation::Tgl(Operand::from(a)), + _ => panic!("invalid instruction {}", s), + } + } +} + +impl Operation { + fn toggle(self) -> Self { + match self { + Operation::Inc(a) => Operation::Dec(a), + Operation::Dec(a) | Operation::Tgl(a) => Operation::Inc(a), + Operation::Jnz(a, b) => Operation::Cpy(a, b), + Operation::Cpy(a, b) => Operation::Jnz(a, b), + } + } +} + +#[derive(Default)] +struct Vm { + registers: [i32; 4], + operations: Vec, + index: i32, +} + +impl<'a> From<&'a str> for Vm { + fn from(s: &'a str) -> Self { + let mut vm = Self::default(); + for line in s.lines() { + vm.operations.push(Operation::from(line)); + } + vm + } +} + +impl Vm { + fn step(&mut self) -> bool { + match self.operations[self.index as usize] { + Operation::Cpy(Operand::Immediate(imm), Operand::Register(reg)) => { + self.registers[reg as usize] = imm; + self.index += 1; + }, + Operation::Cpy(Operand::Register(src), Operand::Register(dest)) => { + self.registers[dest as usize] = self.registers[src as usize]; + self.index += 1; + }, + Operation::Inc(Operand::Register(reg)) => { + self.registers[reg as usize] += 1; + self.index += 1; + }, + Operation::Dec(Operand::Register(reg)) => { + self.registers[reg as usize] -= 1; + self.index += 1; + }, + Operation::Jnz(Operand::Immediate(cond), Operand::Immediate(jump)) => { + if cond != 0 { + self.index += jump; + } else { + self.index += 1; + } + }, + Operation::Jnz(Operand::Register(reg), Operand::Immediate(jump)) => { + if self.registers[reg as usize] != 0 { + self.index += jump; + } else { + self.index += 1; + } + }, + Operation::Jnz(Operand::Immediate(cond), Operand::Register(reg)) => { + if cond != 0 { + self.index += self.registers[reg as usize]; + } else { + self.index += 1; + } + }, + Operation::Tgl(Operand::Register(reg)) => { + let index = self.index + self.registers[reg as usize]; + if let Some(operation) = self.operations.get_mut(index as usize) { + *operation = operation.toggle(); + } + self.index += 1; + }, + _ => { + self.index += 1; + }, + } + + (self.index as usize) < self.operations.len() + } +} + +fn solve(initial: i32, input: &str) -> i32 { + let mut vm = Vm::from(input); + vm.registers[0] = initial; + while vm.step() { } + vm.registers[0] +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve(7, &input)); + println!("Part 2: {}", solve(12, &input)); +} + +#[test] +fn part1() { + let input = " +cpy 2 a +tgl a +tgl a +tgl a +cpy 1 a +dec a +dec a +"; + let mut vm = Vm::from(input.trim()); + while vm.step() { } + assert_eq!(3, vm.registers[0]); +} diff --git a/2016/src/bin/day25.rs b/2016/src/bin/day25.rs new file mode 100644 index 0000000..9ecf487 --- /dev/null +++ b/2016/src/bin/day25.rs @@ -0,0 +1,163 @@ +use std::io::{self, Read}; +use std::iter; + +#[derive(Clone, Copy)] +enum Operand { + Register(u8), + Immediate(i32), +} + +impl<'a> From<&'a str> for Operand { + fn from(s: &'a str) -> Self { + match s { + "a" => Operand::Register(0), + "b" => Operand::Register(1), + "c" => Operand::Register(2), + "d" => Operand::Register(3), + _ => Operand::Immediate(s.parse().unwrap()), + } + } +} + +#[derive(Clone, Copy)] +enum Operation { + Cpy(Operand, Operand), + Inc(Operand), + Dec(Operand), + Jnz(Operand, Operand), + Tgl(Operand), + Out(Operand), +} + +impl<'a> From<&'a str> for Operation { + fn from(s: &'a str) -> Self { + let mut iter = s.split_whitespace(); + match (iter.next().unwrap(), iter.next().unwrap()) { + ("cpy", a) => Operation::Cpy(Operand::from(a), Operand::from(iter.next().unwrap())), + ("inc", a) => Operation::Inc(Operand::from(a)), + ("dec", a) => Operation::Dec(Operand::from(a)), + ("jnz", a) => Operation::Jnz(Operand::from(a), Operand::from(iter.next().unwrap())), + ("tgl", a) => Operation::Tgl(Operand::from(a)), + ("out", a) => Operation::Out(Operand::from(a)), + _ => panic!("invalid instruction {}", s), + } + } +} + +impl Operation { + fn toggle(self) -> Self { + match self { + Operation::Inc(a) => Operation::Dec(a), + Operation::Dec(a) | Operation::Tgl(a) => Operation::Inc(a), + Operation::Jnz(a, b) => Operation::Cpy(a, b), + Operation::Cpy(a, b) => Operation::Jnz(a, b), + _ => unimplemented!(), + } + } +} + +#[derive(Default)] +struct Vm { + registers: [i32; 4], + operations: Vec, + index: i32, + output: Vec, +} + +impl<'a> From<&'a str> for Vm { + fn from(s: &'a str) -> Self { + let mut vm = Self::default(); + for line in s.lines() { + vm.operations.push(Operation::from(line)); + } + vm + } +} + +impl Vm { + fn step(&mut self) -> bool { + match self.operations[self.index as usize] { + Operation::Cpy(Operand::Immediate(imm), Operand::Register(reg)) => { + self.registers[reg as usize] = imm; + self.index += 1; + }, + Operation::Cpy(Operand::Register(src), Operand::Register(dest)) => { + self.registers[dest as usize] = self.registers[src as usize]; + self.index += 1; + }, + Operation::Inc(Operand::Register(reg)) => { + self.registers[reg as usize] += 1; + self.index += 1; + }, + Operation::Dec(Operand::Register(reg)) => { + self.registers[reg as usize] -= 1; + self.index += 1; + }, + Operation::Jnz(Operand::Immediate(cond), Operand::Immediate(jump)) => { + if cond != 0 { + self.index += jump; + } else { + self.index += 1; + } + }, + Operation::Jnz(Operand::Register(reg), Operand::Immediate(jump)) => { + if self.registers[reg as usize] != 0 { + self.index += jump; + } else { + self.index += 1; + } + }, + Operation::Jnz(Operand::Immediate(cond), Operand::Register(reg)) => { + if cond != 0 { + self.index += self.registers[reg as usize]; + } else { + self.index += 1; + } + }, + Operation::Tgl(Operand::Register(reg)) => { + let index = self.index + self.registers[reg as usize]; + if let Some(operation) = self.operations.get_mut(index as usize) { + *operation = operation.toggle(); + } + self.index += 1; + }, + Operation::Out(Operand::Immediate(imm)) => { + self.output.push(imm); + self.index += 1; + }, + Operation::Out(Operand::Register(reg)) => { + self.output.push(self.registers[reg as usize]); + self.index += 1; + }, + _ => { + self.index += 1; + }, + } + + (self.index as usize) < self.operations.len() + } +} + +fn solve(input: &str) -> i32 { + for i in 0.. { + let mut vm = Vm::from(input); + vm.registers[0] = i; + while vm.output.len() < 50 { + assert!(vm.step()); + } + + let target = iter::once(0).chain(iter::once(1)).cycle().take(50); + if vm.output.into_iter().eq(target) { + return i; + } + } + + unreachable!() +} + +fn main() { + let mut input = String::new(); + io::stdin().read_to_string(&mut input).unwrap(); + + println!("Part 1: {}", solve(&input)); +} -- cgit 1.4.1