Move to 2016 directory

23 files changed, 2660 insertions, 0 deletions

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<i32>) {
+    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<P: Pad>(input: &str) -> Vec<P> {
+    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::<Keypad>(&input));
+    println!("Part 2: {:?}", solve::<Wackypad>(&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<Self, ()> {
+        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<Triangle> = 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<Self, ()> {
+        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<u32> {
+    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<char, u32> {
+    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<String>,
+    hypernet: Vec<String>,
+}
+
+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<Ip, ()> {
+        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<Self, ()> {
+        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<Chunk<'a>>),
+}
+
+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::<usize>(),
+        }
+    }
+
+    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<Chunk<'a>>,
+}
+
+impl<'a> File<'a> {
+    fn len(&self) -> usize {
+        self.chunks.iter().map(Chunk::len).sum()
+    }
+
+    fn parse(mut s: &'a str) -> Result<Self, ()> {
+        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<Self, ()> {
+        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<Chip>, Option<Chip>);
+
+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<Self, ()> {
+        match ty {
+            "bot" => Ok(Destination::Bot(Bot(value))),
+            "output" => Ok(Destination::Output(Output(value))),
+            _ => Err(()),
+        }
+    }
+}
+
+#[derive(Default)]
+struct Instructions {
+    chips: HashMap<Chip, Bot>,
+    bots: HashMap<Bot, (Destination, Destination)>,
+}
+
+impl FromStr for Instructions {
+    type Err = ();
+    fn from_str(s: &str) -> Result<Self, ()> {
+        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<Output, Chip>,
+    bots: HashMap<Bot, BotChips>,
+    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<Bot> = 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<Bot> {
+    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<Object>,
+}
+
+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<State>) {
+        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<Floor>) -> 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<Self, ()> {
+        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<Self, ()> {
+        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<Operation>,
+    index: i32,
+}
+
+impl FromStr for Vm {
+    type Err = ();
+    fn from_str(s: &str) -> Result<Self, ()> {
+        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<Point> {
+        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<Point> {
+        if self.x == 0 {
+            None
+        } else {
+            Some(Point { x: self.x - 1, y: self.y })
+        }
+    }
+
+    fn neighbors(self) -> [Option<Point>; 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(&current).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(&current).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<H: Hash>(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::<Part1>(input.trim()));
+    println!("Part 2: {}", solve::<Part2>(input.trim()));
+}
+
+#[test]
+#[ignore]
+fn part1() {
+    assert_eq!(22728, solve::<Part1>("abc"));
+}
+
+#[test]
+#[ignore]
+fn part2() {
+    assert_eq!(22551, solve::<Part2>("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<Disc>,
+    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<u8> = 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<Direction> 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<Room> {
+        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<Direction>,
+}
+
+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<State>, 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<char> for Tile {
+    fn from(ch: char) -> Tile {
+        match ch {
+            '.' => Tile::Safe,
+            '^' => Tile::Trap,
+            _ => panic!("invalid tile char {}", ch),
+        }
+    }
+}
+
+struct Map {
+    rows: Vec<Box<[Tile]>>,
+}
+
+impl Map {
+    fn generate_row(&mut self) {
+        let mut next = Vec::new();
+
+        {
+            let previous = self.rows.last().unwrap();
+
+            for (i, &center) 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::<Vec<_>>().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<Elf> = (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<Operation>,
+    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<Operation>,
+    index: i32,
+    output: Vec<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;
+            },
+            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));
+}