refactor

48 files changed, 7249 insertions, 0 deletions

diff --git a/src/bin/2020/day1.rs b/src/bin/2020/day1.rs
new file mode 100644
index 0000000..8e582d8
--- /dev/null
+++ b/src/bin/2020/day1.rs
@@ -0,0 +1,41 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<Vec<u64>> {
+    Ok(parse::lines(fh).collect())
+}
+
+pub fn part1(ints: Vec<u64>) -> Result<u64> {
+    for i in &ints {
+        for j in &ints {
+            if i + j == 2020 {
+                return Ok(i * j);
+            }
+        }
+    }
+    Err(anyhow!("no numbers summing to 2020 found"))
+}
+
+pub fn part2(ints: Vec<u64>) -> Result<u64> {
+    for i in &ints {
+        for j in &ints {
+            for k in &ints {
+                if i + j + k == 2020 {
+                    return Ok(i * j * k);
+                }
+            }
+        }
+    }
+    Err(anyhow!("no numbers summing to 2020 found"))
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 1).unwrap()).unwrap()).unwrap(),
+        445536
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 1).unwrap()).unwrap()).unwrap(),
+        138688160
+    );
+}
diff --git a/src/bin/2020/day2.rs b/src/bin/2020/day2.rs
new file mode 100644
index 0000000..9d25860
--- /dev/null
+++ b/src/bin/2020/day2.rs
@@ -0,0 +1,79 @@
+use advent_of_code::prelude::*;
+
+pub struct Line {
+    c: char,
+    n1: usize,
+    n2: usize,
+    password: String,
+}
+
+impl std::str::FromStr for Line {
+    type Err = anyhow::Error;
+
+    fn from_str(line: &str) -> Result<Self, Self::Err> {
+        let captures =
+            regex_captures!(r"^([0-9]+)-([0-9]+) (.): (.*)$", line)
+                .context("line failed to match regex")?;
+        let c = captures
+            .get(3)
+            .unwrap()
+            .as_str()
+            .parse()
+            .context("invalid policy char")?;
+        let n1 = captures
+            .get(1)
+            .unwrap()
+            .as_str()
+            .parse()
+            .context("invalid policy lower bound")?;
+        let n2 = captures
+            .get(2)
+            .unwrap()
+            .as_str()
+            .parse()
+            .context("invalid policy upper bound")?;
+        let password = captures.get(4).unwrap().as_str().to_string();
+        Ok(Self {
+            c,
+            n1,
+            n2,
+            password,
+        })
+    }
+}
+
+impl Line {
+    fn valid_part_1(&self) -> bool {
+        let count = self.password.chars().filter(|c| *c == self.c).count();
+        count >= self.n1 && count <= self.n2
+    }
+
+    fn valid_part_2(&self) -> bool {
+        (self.password.chars().nth(self.n1 - 1) == Some(self.c))
+            ^ (self.password.chars().nth(self.n2 - 1) == Some(self.c))
+    }
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Line>> {
+    Ok(parse::lines(fh))
+}
+
+pub fn part1(lines: impl Iterator<Item = Line>) -> Result<usize> {
+    Ok(lines.filter(|l| l.valid_part_1()).count())
+}
+
+pub fn part2(lines: impl Iterator<Item = Line>) -> Result<usize> {
+    Ok(lines.filter(|l| l.valid_part_2()).count())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 2).unwrap()).unwrap()).unwrap(),
+        638
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 2).unwrap()).unwrap()).unwrap(),
+        699
+    );
+}
diff --git a/src/bin/2020/day3.rs b/src/bin/2020/day3.rs
new file mode 100644
index 0000000..a2314ee
--- /dev/null
+++ b/src/bin/2020/day3.rs
@@ -0,0 +1,64 @@
+use advent_of_code::prelude::*;
+
+pub struct Map {
+    grid: Grid<bool>,
+}
+
+impl Map {
+    fn new(grid: Grid<bool>) -> Self {
+        Self { grid }
+    }
+
+    fn rows(&self) -> usize {
+        self.grid.rows().0
+    }
+
+    fn tree_at(&self, row: Row, col: Col) -> Result<bool> {
+        // unwrap safe because cycle().nth() can never fail
+        Ok(*self.grid[row].iter().cycle().nth(col.0).unwrap())
+    }
+
+    fn trees_for_slope(
+        &self,
+        row_incr: usize,
+        col_incr: usize,
+    ) -> Result<u64> {
+        let mut trees = 0;
+        for r in 0..self.rows() / row_incr {
+            let row = r * row_incr;
+            let col = r * col_incr;
+            if self.tree_at(Row(row), Col(col))? {
+                trees += 1;
+            }
+        }
+        Ok(trees)
+    }
+}
+
+pub fn parse(fh: File) -> Result<Map> {
+    Ok(Map::new(parse::bool_grid(parse::raw_lines(fh), b'#', b'.')))
+}
+
+pub fn part1(map: Map) -> Result<u64> {
+    map.trees_for_slope(1, 3)
+}
+
+pub fn part2(map: Map) -> Result<u64> {
+    Ok(map.trees_for_slope(1, 1)?
+        * map.trees_for_slope(1, 3)?
+        * map.trees_for_slope(1, 5)?
+        * map.trees_for_slope(1, 7)?
+        * map.trees_for_slope(2, 1)?)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 3).unwrap()).unwrap()).unwrap(),
+        292
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 3).unwrap()).unwrap()).unwrap(),
+        9354744432
+    );
+}
diff --git a/src/bin/2020/day4.rs b/src/bin/2020/day4.rs
new file mode 100644
index 0000000..aed67cb
--- /dev/null
+++ b/src/bin/2020/day4.rs
@@ -0,0 +1,137 @@
+use advent_of_code::prelude::*;
+
+const REQUIRED_KEYS: &[&str] =
+    &["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"];
+
+pub fn parse(fh: File) -> Result<Vec<HashMap<String, String>>> {
+    let mut res = vec![];
+    let mut cur = HashMap::new();
+    let mut lines = parse::raw_lines(fh).peekable();
+    while lines.peek().is_some() {
+        for line in parse::chunk(&mut lines) {
+            for field in line.split(' ') {
+                let mut parts = field.split(':');
+                let key = parts.next().with_context(|| {
+                    format!("failed to parse field '{}'", field)
+                })?;
+                let value = parts.next().with_context(|| {
+                    format!("failed to parse field '{}'", field)
+                })?;
+                cur.insert(key.to_string(), value.to_string());
+            }
+        }
+        res.push(cur);
+        cur = HashMap::new();
+    }
+    if !cur.is_empty() {
+        res.push(cur);
+    }
+    Ok(res)
+}
+
+pub fn part1(passports: Vec<HashMap<String, String>>) -> Result<u64> {
+    let mut valid = 0;
+    for passport in passports {
+        let mut cur_valid = true;
+        for key in REQUIRED_KEYS {
+            if !passport.contains_key(&key.to_string()) {
+                cur_valid = false;
+                break;
+            }
+        }
+        if cur_valid {
+            valid += 1;
+        }
+    }
+    Ok(valid)
+}
+
+pub fn part2(passports: Vec<HashMap<String, String>>) -> Result<u64> {
+    let mut valid = 0;
+    for passport in passports {
+        let mut cur_valid = true;
+        for key in REQUIRED_KEYS {
+            match passport.get(&key.to_string()) {
+                Some(val) => {
+                    if !validate(key, val)? {
+                        cur_valid = false;
+                        break;
+                    }
+                }
+                None => {
+                    cur_valid = false;
+                    break;
+                }
+            }
+        }
+        if cur_valid {
+            valid += 1;
+        }
+    }
+    Ok(valid)
+}
+
+fn validate(key: &str, val: &str) -> Result<bool> {
+    match key {
+        "byr" => match val.parse::<i32>() {
+            Ok(year) => Ok((1920..=2002).contains(&year)),
+            Err(_) => Ok(false),
+        },
+        "iyr" => match val.parse::<i32>() {
+            Ok(year) => Ok((2010..=2020).contains(&year)),
+            Err(_) => Ok(false),
+        },
+        "eyr" => match val.parse::<i32>() {
+            Ok(year) => Ok((2020..=2030).contains(&year)),
+            Err(_) => Ok(false),
+        },
+        "hgt" => {
+            if val.len() < 3 {
+                Ok(false)
+            } else if val.ends_with("in") {
+                match val[0..val.len() - 2].parse::<i32>() {
+                    Ok(inches) => Ok((59..=76).contains(&inches)),
+                    Err(_) => Ok(false),
+                }
+            } else if val.ends_with("cm") {
+                match val[0..val.len() - 2].parse::<i32>() {
+                    Ok(inches) => Ok((150..=193).contains(&inches)),
+                    Err(_) => Ok(false),
+                }
+            } else {
+                Ok(false)
+            }
+        }
+        "hcl" => Ok(val.len() == 7
+            && val.starts_with('#')
+            && val[1..]
+                == val[1..]
+                    .matches(|c: char| c.is_ascii_hexdigit())
+                    .collect::<String>()),
+        "ecl" => Ok(val == "amb"
+            || val == "blu"
+            || val == "brn"
+            || val == "gry"
+            || val == "grn"
+            || val == "hzl"
+            || val == "oth"),
+        "pid" => Ok(val.len() == 9
+            && val
+                == val
+                    .matches(|c: char| c.is_ascii_digit())
+                    .collect::<String>()),
+        _ => Err(anyhow!("invalid key found: {}", key)),
+    }
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 4).unwrap()).unwrap()).unwrap(),
+        247
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 4).unwrap()).unwrap()).unwrap(),
+        145
+    );
+}
diff --git a/src/bin/2020/day5.rs b/src/bin/2020/day5.rs
new file mode 100644
index 0000000..abfd400
--- /dev/null
+++ b/src/bin/2020/day5.rs
@@ -0,0 +1,96 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = u64>> {
+    Ok(parse::raw_lines(fh).map(|line| seat_id(&line).unwrap()))
+}
+
+pub fn part1(ids: impl Iterator<Item = u64>) -> Result<u64> {
+    let mut max = 0;
+    for id in ids {
+        if id > max {
+            max = id;
+        }
+    }
+    Ok(max)
+}
+
+pub fn part2(ids: impl Iterator<Item = u64>) -> Result<u64> {
+    let mut seats = vec![false; 1024];
+    for id in ids {
+        seats[id as usize] = true;
+    }
+    let first = seats
+        .iter()
+        .position(|b| *b)
+        .context("failed to find taken seat")?;
+    let seat = seats
+        .iter()
+        .skip(first)
+        .position(|b| !*b)
+        .context("failed to find free seat")?
+        + first;
+    if !seats[seat - 1] || seats[seat] || !seats[seat + 1] {
+        return Err(anyhow!("invalid seat found"));
+    }
+    Ok(seat.try_into()?)
+}
+
+fn seat_id(desc: &str) -> Result<u64> {
+    if desc.len() != 10 {
+        return Err(anyhow!("invalid desc {}", desc));
+    }
+    let row_desc = &desc[0..7];
+    let col_desc = &desc[7..10];
+
+    let mut min_row = 0;
+    let mut max_row = 127;
+    for c in row_desc.chars() {
+        let mid = (max_row + min_row) / 2;
+        match c {
+            'F' => {
+                max_row = mid;
+            }
+            'B' => {
+                min_row = mid + 1;
+            }
+            _ => return Err(anyhow!("invalid desc {}", desc)),
+        }
+    }
+    if min_row != max_row {
+        return Err(anyhow!("bug"));
+    }
+    let row = min_row;
+
+    let mut min_col = 0;
+    let mut max_col = 7;
+    for c in col_desc.chars() {
+        let mid = (max_col + min_col) / 2;
+        match c {
+            'L' => {
+                max_col = mid;
+            }
+            'R' => {
+                min_col = mid + 1;
+            }
+            _ => return Err(anyhow!("invalid desc {}", desc)),
+        }
+    }
+    if min_col != max_col {
+        return Err(anyhow!("bug"));
+    }
+    let col = min_col;
+
+    Ok(row * 8 + col)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 5).unwrap()).unwrap()).unwrap(),
+        978
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 5).unwrap()).unwrap()).unwrap(),
+        727
+    );
+}
diff --git a/src/bin/2020/day6.rs b/src/bin/2020/day6.rs
new file mode 100644
index 0000000..114d05f
--- /dev/null
+++ b/src/bin/2020/day6.rs
@@ -0,0 +1,59 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = String>> {
+    Ok(parse::raw_lines(fh))
+}
+
+pub fn part1(lines: impl Iterator<Item = String>) -> Result<usize> {
+    let mut yes = HashSet::new();
+    let mut total = 0;
+    for line in lines {
+        if line.is_empty() {
+            total += yes.len();
+            yes = HashSet::new();
+        } else {
+            for c in line.chars() {
+                yes.insert(c);
+            }
+        }
+    }
+    total += yes.len();
+    Ok(total)
+}
+
+pub fn part2(lines: impl Iterator<Item = String>) -> Result<usize> {
+    let mut yes = HashSet::new();
+    for c in 'a'..='z' {
+        yes.insert(c);
+    }
+    let mut total = 0;
+    for line in lines {
+        if line.is_empty() {
+            total += yes.len();
+            yes = HashSet::new();
+            for c in 'a'..='z' {
+                yes.insert(c);
+            }
+        } else {
+            for c in 'a'..='z' {
+                if !line.contains(c) {
+                    yes.remove(&c);
+                }
+            }
+        }
+    }
+    total += yes.len();
+    Ok(total)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 6).unwrap()).unwrap()).unwrap(),
+        6930
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 6).unwrap()).unwrap()).unwrap(),
+        3585
+    );
+}
diff --git a/src/bin/2020/day7.rs b/src/bin/2020/day7.rs
new file mode 100644
index 0000000..ac6c74a
--- /dev/null
+++ b/src/bin/2020/day7.rs
@@ -0,0 +1,102 @@
+use advent_of_code::prelude::*;
+
+type Graph = HashMap<String, Vec<(u64, String)>>;
+
+pub fn parse(fh: File) -> Result<Graph> {
+    let input = parse::string(fh);
+    let mut graph = Graph::new();
+    for line in input.lines() {
+        let (k, v) = parse_line(line)?;
+        graph.insert(k, v);
+    }
+    Ok(graph)
+}
+
+pub fn part1(graph: Graph) -> Result<u64> {
+    let mut colors = 0;
+    for color in graph.keys() {
+        if bag_contains(&graph, color, "shiny gold")? {
+            colors += 1;
+        }
+    }
+    Ok(colors)
+}
+
+pub fn part2(graph: Graph) -> Result<u64> {
+    // subtract 1 to not count the shiny gold bag itself
+    count_bags(&graph, "shiny gold").map(|i| i - 1)
+}
+
+fn parse_line(line: &str) -> Result<(String, Vec<(u64, String)>)> {
+    let captures = regex_captures!(r"^(.*) bags contain (.*)\.$", line)
+        .context("line failed to match regex")?;
+    let color = captures.get(1).unwrap().as_str();
+    let contents = captures.get(2).unwrap().as_str();
+    if contents == "no other bags" {
+        Ok((color.to_string(), vec![]))
+    } else {
+        Ok((
+            color.to_string(),
+            contents
+                .split(", ")
+                .map(|s| {
+                    let captures =
+                        regex_captures!(r"^([0-9]+) (.*) bags?", s)
+                            .context("line failed to match regex")?;
+                    Ok((
+                        captures
+                            .get(1)
+                            .unwrap()
+                            .as_str()
+                            .parse()
+                            .context("invalid number of bags")?,
+                        captures.get(2).unwrap().as_str().to_string(),
+                    ))
+                })
+                .collect::<Result<_>>()?,
+        ))
+    }
+}
+
+fn bag_contains(graph: &Graph, start: &str, target: &str) -> Result<bool> {
+    let mut to_check = graph
+        .get(&start.to_string())
+        .context("failed to find starting color in graph")?
+        .clone();
+    while let Some((_, next)) = to_check.pop() {
+        if next == target {
+            return Ok(true);
+        }
+        to_check.extend(
+            graph
+                .get(&next)
+                .context("failed to find next color in graph")?
+                .iter()
+                .cloned(),
+        );
+    }
+    Ok(false)
+}
+
+fn count_bags(graph: &Graph, color: &str) -> Result<u64> {
+    Ok(1 + graph
+        .get(&color.to_string())
+        .context("failed to find starting color in graph")?
+        .iter()
+        .map(|(count, child)| Ok(count * count_bags(graph, child)?))
+        .collect::<Result<Vec<_>>>()?
+        .iter()
+        .sum::<u64>())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 7).unwrap()).unwrap()).unwrap(),
+        169
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 7).unwrap()).unwrap()).unwrap(),
+        82372
+    );
+}
diff --git a/src/bin/2020/day8.rs b/src/bin/2020/day8.rs
new file mode 100644
index 0000000..06861f5
--- /dev/null
+++ b/src/bin/2020/day8.rs
@@ -0,0 +1,133 @@
+use advent_of_code::prelude::*;
+
+#[derive(Clone, Copy)]
+enum OpType {
+    Nop,
+    Acc,
+    Jmp,
+}
+
+impl std::str::FromStr for OpType {
+    type Err = Error;
+
+    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
+        Ok(match s {
+            "nop" => Self::Nop,
+            "acc" => Self::Acc,
+            "jmp" => Self::Jmp,
+            _ => return Err(anyhow!("invalid optype {}", s)),
+        })
+    }
+}
+
+#[derive(Clone, Copy)]
+pub struct Op {
+    ty: OpType,
+    arg: i64,
+}
+
+impl std::str::FromStr for Op {
+    type Err = Error;
+
+    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
+        let captures = regex_captures!(r"^([^ ]*) ((?:-|\+)[0-9]+)$", s)
+            .context("failed to parse line")?;
+        let ty = captures.get(1).unwrap().as_str().parse()?;
+        let arg = captures
+            .get(2)
+            .unwrap()
+            .as_str()
+            .parse()
+            .context("invalid arg")?;
+        Ok(Self { ty, arg })
+    }
+}
+
+pub fn parse(fh: File) -> Result<Vec<Op>> {
+    Ok(parse::lines(fh).collect())
+}
+
+pub fn part1(opcodes: Vec<Op>) -> Result<i64> {
+    let (acc, success) = run(&opcodes)?;
+    if success {
+        return Err(anyhow!("unexpectedly succeeded"));
+    }
+    Ok(acc)
+}
+
+pub fn part2(opcodes: Vec<Op>) -> Result<i64> {
+    for i in 0..opcodes.len() {
+        match opcodes[i].ty {
+            OpType::Nop => {
+                let mut attempt = opcodes.clone();
+                attempt[i].ty = OpType::Jmp;
+                let (acc, success) = run(&attempt)?;
+                if success {
+                    return Ok(acc);
+                }
+            }
+            OpType::Acc => {}
+            OpType::Jmp => {
+                let mut attempt = opcodes.clone();
+                attempt[i].ty = OpType::Nop;
+                let (acc, success) = run(&attempt)?;
+                if success {
+                    return Ok(acc);
+                }
+            }
+        }
+    }
+    Err(anyhow!("failed to find corrupted opcode"))
+}
+
+fn run(opcodes: &[Op]) -> Result<(i64, bool)> {
+    let mut seen = vec![false; opcodes.len()];
+    let mut pc = 0;
+    let mut acc = 0;
+    loop {
+        if pc >= opcodes.len() {
+            return Ok((acc, true));
+        } else if seen[pc] {
+            return Ok((acc, false));
+        }
+        seen[pc] = true;
+
+        match opcodes[pc].ty {
+            OpType::Nop => {
+                pc += 1;
+            }
+            OpType::Acc => {
+                acc += opcodes[pc].arg;
+                pc += 1;
+            }
+            OpType::Jmp => {
+                let arg = opcodes[pc].arg;
+                if arg >= 0 {
+                    if arg as usize > opcodes.len()
+                        || pc > opcodes.len() - arg as usize
+                    {
+                        return Err(anyhow!("invalid jmp"));
+                    }
+                    pc += arg as usize;
+                } else {
+                    if pc < (-arg as usize) {
+                        return Err(anyhow!("invalid jmp"));
+                    }
+                    pc -= -arg as usize;
+                }
+            }
+        }
+    }
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 8).unwrap()).unwrap()).unwrap(),
+        1928
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 8).unwrap()).unwrap()).unwrap(),
+        1319
+    );
+}
diff --git a/src/bin/2020/day9.rs b/src/bin/2020/day9.rs
new file mode 100644
index 0000000..becae3b
--- /dev/null
+++ b/src/bin/2020/day9.rs
@@ -0,0 +1,74 @@
+use advent_of_code::prelude::*;
+
+const WINDOW: usize = 25;
+
+pub fn parse(fh: File) -> Result<Vec<u64>> {
+    Ok(parse::lines(fh).collect())
+}
+
+pub fn part1(list: Vec<u64>) -> Result<u64> {
+    for i in 0..(list.len() - WINDOW) {
+        let set = &list[i..i + WINDOW];
+        let n = list[i + WINDOW];
+        if !valid(set, n) {
+            return Ok(n);
+        }
+    }
+
+    Err(anyhow!("failed to find invalid number"))
+}
+
+pub fn part2(list: Vec<u64>) -> Result<u64> {
+    let mut invalid = None;
+    for i in 0..(list.len() - WINDOW) {
+        let set = &list[i..i + WINDOW];
+        let n = list[i + WINDOW];
+        if !valid(set, n) {
+            invalid = Some(n);
+        }
+    }
+    if invalid.is_none() {
+        return Err(anyhow!("failed to find invalid number"));
+    }
+    let invalid = invalid.unwrap();
+
+    for i in 0..list.len() {
+        for j in i..list.len() {
+            let seq = &list[i..=j];
+            if invalid == seq.iter().sum() {
+                return Ok(seq.iter().copied().min().unwrap()
+                    + seq.iter().copied().max().unwrap());
+            }
+        }
+    }
+
+    Err(anyhow!("failed to find sequence summing to invalid number"))
+}
+
+fn valid(set: &[u64], n: u64) -> bool {
+    for i in 0..set.len() {
+        for j in 0..set.len() {
+            if i == j {
+                continue;
+            }
+            let i = set[i];
+            let j = set[j];
+            if i + j == n {
+                return true;
+            }
+        }
+    }
+    false
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2020, 9).unwrap()).unwrap()).unwrap(),
+        373803594
+    );
+    assert_eq!(
+        part2(parse(parse::data(2020, 9).unwrap()).unwrap()).unwrap(),
+        51152360
+    );
+}
diff --git a/src/bin/2020/main.rs b/src/bin/2020/main.rs
new file mode 100644
index 0000000..354f6b0
--- /dev/null
+++ b/src/bin/2020/main.rs
@@ -0,0 +1,42 @@
+#![allow(clippy::cognitive_complexity)]
+#![allow(clippy::missing_const_for_fn)]
+#![allow(clippy::similar_names)]
+#![allow(clippy::struct_excessive_bools)]
+#![allow(clippy::too_many_arguments)]
+#![allow(clippy::too_many_lines)]
+#![allow(clippy::type_complexity)]
+#![allow(clippy::collapsible_else_if)]
+#![allow(clippy::collapsible_if)]
+#![allow(clippy::comparison_chain)]
+
+use advent_of_code::prelude::*;
+
+mod day1;
+mod day2;
+mod day3;
+mod day4;
+mod day5;
+mod day6;
+mod day7;
+mod day8;
+mod day9;
+// NEXT MOD
+
+#[paw::main]
+fn main(opt: Opt) -> Result<()> {
+    #[allow(clippy::match_single_binding)]
+    match opt.day {
+        1 => advent_of_code::day!(2020, opt.day, opt.puzzle, day1),
+        2 => advent_of_code::day!(2020, opt.day, opt.puzzle, day2),
+        3 => advent_of_code::day!(2020, opt.day, opt.puzzle, day3),
+        4 => advent_of_code::day!(2020, opt.day, opt.puzzle, day4),
+        5 => advent_of_code::day!(2020, opt.day, opt.puzzle, day5),
+        6 => advent_of_code::day!(2020, opt.day, opt.puzzle, day6),
+        7 => advent_of_code::day!(2020, opt.day, opt.puzzle, day7),
+        8 => advent_of_code::day!(2020, opt.day, opt.puzzle, day8),
+        9 => advent_of_code::day!(2020, opt.day, opt.puzzle, day9),
+        // NEXT PART
+        _ => panic!("unknown day {}", opt.day),
+    }
+    Ok(())
+}
diff --git a/src/bin/2021/day1.rs b/src/bin/2021/day1.rs
new file mode 100644
index 0000000..fce763c
--- /dev/null
+++ b/src/bin/2021/day1.rs
@@ -0,0 +1,36 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<Vec<i64>> {
+    Ok(parse::lines(fh).collect())
+}
+
+pub fn part1(ints: Vec<i64>) -> Result<usize> {
+    Ok(ints
+        .windows(2)
+        .map(|a| a[1] - a[0])
+        .filter(|x| *x > 0)
+        .count())
+}
+
+pub fn part2(ints: Vec<i64>) -> Result<usize> {
+    Ok(ints
+        .windows(3)
+        .map(|a| a[0] + a[1] + a[2])
+        .collect::<Vec<_>>()
+        .windows(2)
+        .map(|a| a[1] - a[0])
+        .filter(|x| *x > 0)
+        .count())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 1).unwrap()).unwrap()).unwrap(),
+        1602
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 1).unwrap()).unwrap()).unwrap(),
+        1633
+    );
+}
diff --git a/src/bin/2021/day10.rs b/src/bin/2021/day10.rs
new file mode 100644
index 0000000..d7b5f48
--- /dev/null
+++ b/src/bin/2021/day10.rs
@@ -0,0 +1,109 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = String>> {
+    Ok(parse::raw_lines(fh))
+}
+
+pub fn part1(lines: impl Iterator<Item = String>) -> Result<u64> {
+    let mut total = 0;
+    for line in lines {
+        let mut open = vec![];
+        for c in line.chars() {
+            match c {
+                '{' | '(' | '[' | '<' => {
+                    open.push(c);
+                }
+                '}' | ')' | ']' | '>' => {
+                    let c_open = open.pop();
+                    if let Some(c_open) = c_open {
+                        let expected = match c_open {
+                            '{' => '}',
+                            '(' => ')',
+                            '[' => ']',
+                            '<' => '>',
+                            _ => unreachable!(),
+                        };
+                        if c != expected {
+                            total += match c {
+                                '}' => 1197,
+                                ')' => 3,
+                                ']' => 57,
+                                '>' => 25137,
+                                _ => unreachable!(),
+                            };
+                            break;
+                        }
+                    } else {
+                        break;
+                    }
+                }
+                _ => break,
+            }
+        }
+    }
+    Ok(total)
+}
+
+pub fn part2(lines: impl Iterator<Item = String>) -> Result<u64> {
+    let mut scores = vec![];
+    for line in lines {
+        let mut open = vec![];
+        let mut skip = false;
+        for c in line.chars() {
+            match c {
+                '{' | '(' | '[' | '<' => {
+                    open.push(c);
+                }
+                '}' | ')' | ']' | '>' => {
+                    let c_open = open.pop();
+                    if let Some(c_open) = c_open {
+                        let expected = match c_open {
+                            '{' => '}',
+                            '(' => ')',
+                            '[' => ']',
+                            '<' => '>',
+                            _ => unreachable!(),
+                        };
+                        if c != expected {
+                            skip = true;
+                            break;
+                        }
+                    } else {
+                        skip = true;
+                        break;
+                    }
+                }
+                _ => {
+                    skip = true;
+                    break;
+                }
+            }
+        }
+        if !skip {
+            scores.push(open.iter().rev().fold(0, |acc, c| {
+                acc * 5
+                    + match c {
+                        '(' => 1,
+                        '[' => 2,
+                        '{' => 3,
+                        '<' => 4,
+                        _ => unreachable!(),
+                    }
+            }));
+        }
+    }
+    scores.sort_unstable();
+    Ok(scores[scores.len() / 2])
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 10).unwrap()).unwrap()).unwrap(),
+        166191
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 10).unwrap()).unwrap()).unwrap(),
+        1152088313
+    );
+}
diff --git a/src/bin/2021/day11.rs b/src/bin/2021/day11.rs
new file mode 100644
index 0000000..fac392e
--- /dev/null
+++ b/src/bin/2021/day11.rs
@@ -0,0 +1,82 @@
+use advent_of_code::prelude::*;
+
+fn iterate(grid: &mut Grid<(u8, bool)>) -> usize {
+    let mut flashes = 0;
+    for (cell, _) in grid.cells_mut() {
+        *cell += 1;
+    }
+
+    loop {
+        let mut new_flashes = 0;
+        let mut updates: Grid<u8> = Grid::default();
+        updates.grow(grid.rows(), grid.cols());
+        for ((row, col), (cell, flashed)) in grid.indexed_cells_mut() {
+            if *flashed {
+                continue;
+            }
+            if *cell > 9 {
+                *flashed = true;
+                new_flashes += 1;
+                for (row, col) in updates.adjacent(row, col, true) {
+                    updates[row][col] += 1;
+                }
+            }
+        }
+        if new_flashes > 0 {
+            flashes += new_flashes;
+            for ((row, col), val) in updates.indexed_cells() {
+                grid[row][col].0 += val;
+            }
+        } else {
+            break;
+        }
+    }
+
+    for (cell, flashed) in grid.cells_mut() {
+        if *flashed {
+            *cell = 0;
+            *flashed = false;
+        }
+    }
+
+    flashes
+}
+
+pub fn parse(fh: File) -> Result<Grid<(u8, bool)>> {
+    Ok(parse::digit_grid(parse::raw_lines(fh))
+        .indexed_cells()
+        .map(|((row, col), cell)| ((row, col), (*cell, false)))
+        .collect())
+}
+
+pub fn part1(mut map: Grid<(u8, bool)>) -> Result<usize> {
+    let mut flashes = 0;
+    for _ in 0..100 {
+        flashes += iterate(&mut map);
+    }
+    Ok(flashes)
+}
+
+pub fn part2(mut map: Grid<(u8, bool)>) -> Result<usize> {
+    let mut step = 1;
+    loop {
+        let flashes = iterate(&mut map);
+        if flashes == (map.rows().0 * map.cols().0) {
+            break;
+        }
+        step += 1;
+    }
+    Ok(step)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 11).unwrap()).unwrap()).unwrap(),
+        1673
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 11).unwrap()).unwrap()).unwrap(),
+        279
+    );
+}
diff --git a/src/bin/2021/day12.rs b/src/bin/2021/day12.rs
new file mode 100644
index 0000000..2770aa6
--- /dev/null
+++ b/src/bin/2021/day12.rs
@@ -0,0 +1,99 @@
+use advent_of_code::prelude::*;
+
+fn small(s: &str) -> bool {
+    s.bytes().all(|c| c.is_ascii_lowercase())
+}
+
+fn single_small<'a>(path: impl Iterator<Item = &'a str>) -> bool {
+    let mut set = HashSet::new();
+    for s in path {
+        if !small(s) {
+            continue;
+        }
+        if set.contains(s) {
+            return false;
+        }
+        set.insert(s);
+    }
+    true
+}
+
+fn paths_from1<'a>(
+    graph: &'a HashMap<String, HashSet<String>>,
+    path: &mut Vec<&'a str>,
+) -> u64 {
+    let mut total = 0;
+    for neighbor in graph[path[path.len() - 1]].iter() {
+        if small(neighbor) && path.contains(&neighbor.as_ref()) {
+            continue;
+        }
+        if neighbor == "end" {
+            total += 1;
+        } else {
+            path.push(neighbor);
+            total += paths_from1(graph, path);
+            path.pop();
+        }
+    }
+    total
+}
+
+fn paths_from2<'a>(
+    graph: &'a HashMap<String, HashSet<String>>,
+    path: &mut Vec<&'a str>,
+) -> u64 {
+    let mut total = 0;
+    for neighbor in graph[path[path.len() - 1]].iter() {
+        if neighbor == "start" {
+            continue;
+        }
+        if small(neighbor)
+            && path.contains(&neighbor.as_ref())
+            && !single_small(path.iter().copied())
+        {
+            continue;
+        }
+        if neighbor == "end" {
+            total += 1;
+        } else {
+            path.push(neighbor);
+            total += paths_from2(graph, path);
+            path.pop();
+        }
+    }
+    total
+}
+
+pub fn parse(fh: File) -> Result<HashMap<String, HashSet<String>>> {
+    let mut graph = HashMap::new();
+    for line in parse::raw_lines(fh) {
+        let nodes: Vec<_> = line.split('-').map(|s| s.to_string()).collect();
+        let edges =
+            graph.entry(nodes[0].clone()).or_insert_with(HashSet::new);
+        edges.insert(nodes[1].clone());
+        let edges =
+            graph.entry(nodes[1].clone()).or_insert_with(HashSet::new);
+        edges.insert(nodes[0].clone());
+    }
+    Ok(graph)
+}
+
+pub fn part1(graph: HashMap<String, HashSet<String>>) -> Result<u64> {
+    Ok(paths_from1(&graph, &mut vec!["start"]))
+}
+
+pub fn part2(graph: HashMap<String, HashSet<String>>) -> Result<u64> {
+    Ok(paths_from2(&graph, &mut vec!["start"]))
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 12).unwrap()).unwrap()).unwrap(),
+        3230
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 12).unwrap()).unwrap()).unwrap(),
+        83475
+    );
+}
diff --git a/src/bin/2021/day13.rs b/src/bin/2021/day13.rs
new file mode 100644
index 0000000..75e547b
--- /dev/null
+++ b/src/bin/2021/day13.rs
@@ -0,0 +1,144 @@
+use advent_of_code::prelude::*;
+
+#[derive(Default)]
+pub struct Paper {
+    grid: Grid<bool>,
+}
+
+impl Paper {
+    fn set(&mut self, row: Row, col: Col) {
+        self.grid.grow(Row(row.0 + 1), Col(col.0 + 1));
+        self.grid[row][col] = true;
+    }
+
+    fn fold(&mut self, horizontal: bool, coord: usize) {
+        let mut clone = Self::default();
+        if horizontal {
+            clone.grid.grow(
+                self.grid.rows(),
+                Col(coord.max(self.grid.cols().0 - coord - 1)),
+            );
+            for ((Row(row), Col(col)), cell) in self.grid.indexed_cells() {
+                if *cell {
+                    if coord > self.grid.cols().0 - coord - 1 {
+                        if col < coord {
+                            clone.set(Row(row), Col(col));
+                        } else if col > coord {
+                            clone.set(Row(row), Col(coord * 2 - col));
+                        }
+                    } else {
+                        if col < coord {
+                            clone.set(
+                                Row(row),
+                                Col(self.grid.cols().0 - coord * 2 - 1 + col),
+                            );
+                        } else if col > coord {
+                            clone.set(
+                                Row(row),
+                                Col(self.grid.cols().0 - col - 1),
+                            );
+                        }
+                    }
+                }
+            }
+        } else {
+            clone.grid.grow(
+                Row(coord.max(self.grid.rows().0 - coord - 1)),
+                self.grid.cols(),
+            );
+            for ((Row(row), Col(col)), cell) in self.grid.indexed_cells() {
+                if *cell {
+                    if coord > self.grid.rows().0 - coord - 1 {
+                        if row < coord {
+                            clone.set(Row(row), Col(col));
+                        } else if row > coord {
+                            clone.set(Row(coord * 2 - row), Col(col));
+                        }
+                    } else {
+                        if row < coord {
+                            clone.set(
+                                Row(self.grid.rows().0 - coord * 2 - 1 + row),
+                                Col(col),
+                            );
+                        } else if row > coord {
+                            clone.set(
+                                Row(self.grid.rows().0 - row - 1),
+                                Col(col),
+                            );
+                        }
+                    }
+                }
+            }
+        }
+        *self = clone;
+    }
+
+    fn total(&self) -> usize {
+        self.grid.cells().filter(|b| **b).count()
+    }
+}
+
+impl std::fmt::Display for Paper {
+    fn fmt(
+        &self,
+        f: &mut std::fmt::Formatter<'_>,
+    ) -> Result<(), std::fmt::Error> {
+        write!(
+            f,
+            "{}",
+            self.grid.display_packed(|b| if *b { '#' } else { '.' })
+        )
+    }
+}
+
+pub fn parse(fh: File) -> Result<(Paper, Vec<(bool, usize)>)> {
+    let mut paper = Paper::default();
+    let mut folds = vec![];
+    for line in parse::raw_lines(fh) {
+        if line.is_empty() {
+            continue;
+        }
+        if let Some(fold) = line.strip_prefix("fold along ") {
+            let mut fold = fold.split('=');
+            let horizontal = fold.next().unwrap() == "x";
+            let coord: usize = fold.next().unwrap().parse()?;
+            folds.push((horizontal, coord));
+        } else {
+            let mut coords = line.split(',');
+            let x: usize = coords.next().unwrap().parse()?;
+            let y: usize = coords.next().unwrap().parse()?;
+            paper.set(Row(y), Col(x));
+        }
+    }
+    Ok((paper, folds))
+}
+
+pub fn part1(
+    (mut paper, folds): (Paper, Vec<(bool, usize)>),
+) -> Result<usize> {
+    paper.fold(folds[0].0, folds[0].1);
+    Ok(paper.total())
+}
+
+pub fn part2(
+    (mut paper, folds): (Paper, Vec<(bool, usize)>),
+) -> Result<usize> {
+    for fold in folds {
+        paper.fold(fold.0, fold.1);
+    }
+
+    println!("{}", paper);
+    Ok(paper.total())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 13).unwrap()).unwrap()).unwrap(),
+        678
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 13).unwrap()).unwrap()).unwrap(),
+        95
+    );
+}
diff --git a/src/bin/2021/day14.rs b/src/bin/2021/day14.rs
new file mode 100644
index 0000000..0080015
--- /dev/null
+++ b/src/bin/2021/day14.rs
@@ -0,0 +1,94 @@
+use advent_of_code::prelude::*;
+
+fn process(polymer: &[u8], rules: &HashMap<Vec<u8>, u8>) -> Vec<u8> {
+    let mut insertions = vec![];
+    for (i, elements) in polymer.windows(2).enumerate() {
+        for (pattern, insert) in rules {
+            if pattern == elements {
+                insertions.push((i + 1, insert));
+            }
+        }
+    }
+    let mut polymer = polymer.to_vec();
+    for (idx, c) in insertions.iter().rev() {
+        polymer.insert(*idx, **c);
+    }
+    polymer
+}
+
+pub fn parse(fh: File) -> Result<(Vec<u8>, HashMap<Vec<u8>, u8>)> {
+    let mut lines = parse::raw_lines(fh);
+    let polymer = lines.next().unwrap();
+    lines.next();
+
+    let mut rules = HashMap::new();
+    for line in lines {
+        let rule: Vec<_> = line.split(" -> ").collect();
+        rules.insert(rule[0].as_bytes().to_vec(), rule[1].as_bytes()[0]);
+    }
+    Ok((polymer.as_bytes().to_vec(), rules))
+}
+
+pub fn part1(
+    (mut polymer, rules): (Vec<u8>, HashMap<Vec<u8>, u8>),
+) -> Result<u64> {
+    for _ in 0..10 {
+        polymer = process(&polymer, &rules);
+    }
+    let mut elements = HashMap::new();
+    for element in polymer {
+        let count = elements.entry(element).or_insert(0);
+        *count += 1;
+    }
+    Ok(elements.values().max().unwrap() - elements.values().min().unwrap())
+}
+
+pub fn part2(
+    (polymer, rules): (Vec<u8>, HashMap<Vec<u8>, u8>),
+) -> Result<u64> {
+    let mut pairs = HashMap::new();
+    for pair in polymer.windows(2) {
+        let count = pairs.entry([pair[0], pair[1]]).or_insert(0);
+        *count += 1;
+    }
+
+    for _ in 0..40 {
+        let mut next = HashMap::new();
+        for (pair, count) in &mut pairs {
+            let insert = rules[&pair[..]];
+            let new_pair1 = [pair[0], insert];
+            let new_pair2 = [insert, pair[1]];
+            let next_count = next.entry(new_pair1).or_insert(0);
+            *next_count += *count;
+            let next_count = next.entry(new_pair2).or_insert(0);
+            *next_count += *count;
+        }
+        pairs = next;
+    }
+    let mut elements = HashMap::new();
+    for (pair, count) in pairs {
+        let element_count = elements.entry(pair[0]).or_insert(0);
+        *element_count += count;
+        let element_count = elements.entry(pair[1]).or_insert(0);
+        *element_count += count;
+    }
+    let element_count = elements.entry(polymer[0]).or_insert(0);
+    *element_count += 1;
+    let element_count =
+        elements.entry(polymer[polymer.len() - 1]).or_insert(0);
+    *element_count += 1;
+    Ok(elements.values().max().unwrap() / 2
+        - elements.values().min().unwrap() / 2)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 14).unwrap()).unwrap()).unwrap(),
+        2874
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 14).unwrap()).unwrap()).unwrap(),
+        5208377027195
+    );
+}
diff --git a/src/bin/2021/day15.rs b/src/bin/2021/day15.rs
new file mode 100644
index 0000000..ca7a72f
--- /dev/null
+++ b/src/bin/2021/day15.rs
@@ -0,0 +1,68 @@
+use advent_of_code::prelude::*;
+
+pub struct Map {
+    grid: Grid<u8>,
+}
+
+impl advent_of_code::graph::Graph<(Row, Col), (Row, Col)> for Map {
+    type Edges = advent_of_code::grid::Adjacent;
+
+    fn edges(&self, v: (Row, Col)) -> Self::Edges {
+        self.grid.adjacent(v.0, v.1, false)
+    }
+
+    fn edge(&self, _v: (Row, Col), e: (Row, Col)) -> ((Row, Col), u64) {
+        (e, u64::from(self.grid[e.0][e.1]))
+    }
+}
+
+pub fn parse(fh: File) -> Result<Map> {
+    Ok(Map {
+        grid: parse::digit_grid(parse::raw_lines(fh)),
+    })
+}
+
+pub fn part1(map: Map) -> Result<u64> {
+    Ok(map
+        .dijkstra(
+            (Row(0), Col(0)),
+            (map.grid.rows() - 1, map.grid.cols() - 1),
+        )
+        .0)
+}
+
+pub fn part2(map: Map) -> Result<u64> {
+    let mut large_grid = Grid::default();
+    large_grid.grow(Row(map.grid.rows().0 * 5), Col(map.grid.cols().0 * 5));
+    for lrow in 0..5 {
+        for lcol in 0..5 {
+            for ((Row(row), Col(col)), val) in map.grid.indexed_cells() {
+                let mut val = val + lrow + lcol;
+                while val > 9 {
+                    val -= 9;
+                }
+                large_grid[Row(usize::from(lrow) * map.grid.rows().0 + row)]
+                    [Col(usize::from(lcol) * map.grid.cols().0 + col)] = val;
+            }
+        }
+    }
+    let large_map = Map { grid: large_grid };
+    Ok(large_map
+        .dijkstra(
+            (Row(0), Col(0)),
+            (large_map.grid.rows() - 1, large_map.grid.cols() - 1),
+        )
+        .0)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 15).unwrap()).unwrap()).unwrap(),
+        441
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 15).unwrap()).unwrap()).unwrap(),
+        2849
+    );
+}
diff --git a/src/bin/2021/day16.rs b/src/bin/2021/day16.rs
new file mode 100644
index 0000000..3177483
--- /dev/null
+++ b/src/bin/2021/day16.rs
@@ -0,0 +1,210 @@
+use advent_of_code::prelude::*;
+
+struct BitIter {
+    byte: u8,
+    pos: u8,
+}
+
+impl BitIter {
+    fn new(byte: u8) -> Self {
+        Self { byte, pos: 0 }
+    }
+}
+
+impl Iterator for BitIter {
+    type Item = bool;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.pos >= 8 {
+            return None;
+        }
+
+        let ret = self.byte.leading_ones() > 0;
+        self.byte <<= 1;
+        self.pos += 1;
+        Some(ret)
+    }
+}
+
+fn bits(bytes: impl Iterator<Item = u8>) -> impl Iterator<Item = bool> {
+    bytes.flat_map(BitIter::new)
+}
+
+struct LiteralU8(u8);
+
+impl FromIterator<bool> for LiteralU8 {
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = bool>,
+    {
+        let mut ret = 0;
+        for b in iter {
+            ret = (ret << 1) | u8::from(b);
+        }
+        Self(ret)
+    }
+}
+
+struct LiteralU16(u16);
+
+impl FromIterator<bool> for LiteralU16 {
+    fn from_iter<T>(iter: T) -> Self
+    where
+        T: IntoIterator<Item = bool>,
+    {
+        let mut ret = 0;
+        for b in iter {
+            ret = (ret << 1) | u16::from(b);
+        }
+        Self(ret)
+    }
+}
+
+pub struct Packet {
+    version: u8,
+    id: u8,
+    contents: PacketContents,
+}
+
+enum PacketContents {
+    Literal { value: u64 },
+    Operator { packets: Vec<Packet> },
+}
+
+impl Packet {
+    fn parse(bits: &mut impl Iterator<Item = bool>) -> (Self, usize) {
+        let LiteralU8(version) = bits.take(3).collect();
+        let LiteralU8(id) = bits.take(3).collect();
+        let mut nbits = 6;
+        let contents = if id == 4 {
+            let (value, size) = read_varnum(bits.by_ref());
+            nbits += size;
+            PacketContents::Literal { value }
+        } else {
+            let mut packets = vec![];
+            nbits += 1;
+            if bits.next().unwrap() {
+                let LiteralU16(subpacket_count) = bits.take(11).collect();
+                nbits += 11;
+                for _ in 0..subpacket_count {
+                    let (packet, size) = Self::parse(bits);
+                    packets.push(packet);
+                    nbits += size;
+                }
+            } else {
+                let LiteralU16(remaining_bits) = bits.take(15).collect();
+                nbits += 15;
+                let mut remaining_bits = usize::from(remaining_bits);
+                while remaining_bits > 0 {
+                    let (packet, size) = Self::parse(bits);
+                    packets.push(packet);
+                    nbits += size;
+                    remaining_bits -= size;
+                }
+            }
+            PacketContents::Operator { packets }
+        };
+        (
+            Self {
+                version,
+                id,
+                contents,
+            },
+            nbits,
+        )
+    }
+
+    fn subpackets(&self) -> impl Iterator<Item = &Self> {
+        let mut to_return = VecDeque::new();
+        to_return.push_back(self);
+        Subpackets { to_return }
+    }
+
+    fn eval(&self) -> u64 {
+        match &self.contents {
+            PacketContents::Literal { value } => *value,
+            PacketContents::Operator { packets } => match self.id {
+                0 => packets.iter().map(|packet| packet.eval()).sum(),
+                1 => packets.iter().map(|packet| packet.eval()).product(),
+                2 => {
+                    packets.iter().map(|packet| packet.eval()).min().unwrap()
+                }
+                3 => {
+                    packets.iter().map(|packet| packet.eval()).max().unwrap()
+                }
+                4 => unreachable!(),
+                5 => u64::from(packets[0].eval() > packets[1].eval()),
+                6 => u64::from(packets[0].eval() < packets[1].eval()),
+                7 => u64::from(packets[0].eval() == packets[1].eval()),
+                _ => unreachable!(),
+            },
+        }
+    }
+}
+
+fn read_varnum(bits: &mut impl Iterator<Item = bool>) -> (u64, usize) {
+    let mut ret = 0;
+    let mut nbits = 0;
+    while bits.next().unwrap() {
+        let LiteralU8(chunk) = bits.take(4).collect();
+        ret = (ret << 4) | u64::from(chunk);
+        nbits += 5;
+    }
+    let LiteralU8(chunk) = bits.take(4).collect();
+    ret = (ret << 4) | u64::from(chunk);
+    nbits += 5;
+    (ret, nbits)
+}
+
+struct Subpackets<'a> {
+    to_return: VecDeque<&'a Packet>,
+}
+
+impl<'a> Iterator for Subpackets<'a> {
+    type Item = &'a Packet;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let next = self.to_return.pop_front();
+        if let Some(next) = next {
+            match &next.contents {
+                PacketContents::Literal { .. } => {}
+                PacketContents::Operator { packets } => {
+                    self.to_return.extend(packets.iter());
+                }
+            }
+        }
+        next
+    }
+}
+
+pub fn parse(fh: File) -> Result<Packet> {
+    let line = parse::raw_lines(fh).next().unwrap();
+    let mut bits = bits(line.as_bytes().chunks(2).map(|bs| {
+        u8::from_str_radix(std::str::from_utf8(bs).unwrap(), 16).unwrap()
+    }));
+    let (packet, _) = Packet::parse(bits.by_ref());
+    Ok(packet)
+}
+
+pub fn part1(packet: Packet) -> Result<u64> {
+    Ok(packet
+        .subpackets()
+        .map(|packet| u64::from(packet.version))
+        .sum())
+}
+
+pub fn part2(packet: Packet) -> Result<u64> {
+    Ok(packet.eval())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 16).unwrap()).unwrap()).unwrap(),
+        979
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 16).unwrap()).unwrap()).unwrap(),
+        277110354175
+    );
+}
diff --git a/src/bin/2021/day17.rs b/src/bin/2021/day17.rs
new file mode 100644
index 0000000..54ee4bb
--- /dev/null
+++ b/src/bin/2021/day17.rs
@@ -0,0 +1,106 @@
+use advent_of_code::prelude::*;
+
+fn fire(
+    mut xv: i64,
+    mut yv: i64,
+    xrange: &std::ops::RangeInclusive<i64>,
+    yrange: &std::ops::RangeInclusive<i64>,
+) -> Option<i64> {
+    let mut xpos = 0;
+    let mut ypos = 0;
+    let mut max_height = 0;
+    loop {
+        if xrange.contains(&xpos) && yrange.contains(&ypos) {
+            return Some(max_height);
+        } else if (xv >= 0 && xpos > *xrange.end())
+            || (xv <= 0 && xpos < *xrange.start())
+            || (ypos < *yrange.start())
+        {
+            return None;
+        }
+
+        xpos += xv;
+        ypos += yv;
+        if ypos > max_height {
+            max_height = ypos;
+        }
+        match xv.cmp(&0) {
+            Ordering::Greater => {
+                xv -= 1;
+            }
+            Ordering::Less => {
+                xv += 1;
+            }
+            _ => {}
+        }
+        yv -= 1;
+    }
+}
+
+pub fn parse(
+    fh: File,
+) -> Result<(std::ops::RangeInclusive<i64>, std::ops::RangeInclusive<i64>)> {
+    let line = parse::raw_lines(fh).next().unwrap();
+    let captures = regex_captures!(
+        r"target area: x=(-?\d+)..(-?\d+), y=(-?\d+)..(-?\d+)",
+        &line,
+    )
+    .unwrap();
+    let xrange: std::ops::RangeInclusive<i64> =
+        captures[1].parse().unwrap()..=captures[2].parse().unwrap();
+    let yrange: std::ops::RangeInclusive<i64> =
+        captures[3].parse().unwrap()..=captures[4].parse().unwrap();
+    Ok((xrange, yrange))
+}
+
+pub fn part1(
+    (xrange, yrange): (
+        std::ops::RangeInclusive<i64>,
+        std::ops::RangeInclusive<i64>,
+    ),
+) -> Result<i64> {
+    let mut max_height = 0;
+    for xv in *xrange.start().min(&0)..=*xrange.end().max(&0) {
+        for yv in *yrange.start().min(&0)
+            ..=yrange.start().abs().max(yrange.end().abs())
+        {
+            if let Some(height) = fire(xv, yv, &xrange, &yrange) {
+                if height > max_height {
+                    max_height = height;
+                }
+            }
+        }
+    }
+    Ok(max_height)
+}
+
+pub fn part2(
+    (xrange, yrange): (
+        std::ops::RangeInclusive<i64>,
+        std::ops::RangeInclusive<i64>,
+    ),
+) -> Result<u64> {
+    let mut count = 0;
+    for xv in *xrange.start().min(&0)..=*xrange.end().max(&0) {
+        for yv in *yrange.start().min(&0)
+            ..=yrange.start().abs().max(yrange.end().abs())
+        {
+            if fire(xv, yv, &xrange, &yrange).is_some() {
+                count += 1;
+            }
+        }
+    }
+    Ok(count)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 17).unwrap()).unwrap()).unwrap(),
+        5886
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 17).unwrap()).unwrap()).unwrap(),
+        1806
+    );
+}
diff --git a/src/bin/2021/day18.rs b/src/bin/2021/day18.rs
new file mode 100644
index 0000000..6a7e73d
--- /dev/null
+++ b/src/bin/2021/day18.rs
@@ -0,0 +1,257 @@
+use advent_of_code::prelude::*;
+
+#[derive(Clone)]
+pub enum Number {
+    Value(u8),
+    Pair(Box<Number>, Box<Number>),
+}
+
+impl std::str::FromStr for Number {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        Ok(Self::parse(s))
+    }
+}
+
+impl Number {
+    fn parse(s: &str) -> Self {
+        if s.starts_with('[') {
+            Self::parse_pair(s)
+        } else {
+            Self::parse_number(s)
+        }
+    }
+
+    fn parse_pair(s: &str) -> Self {
+        let mut depth = 1;
+        let mut start = 1;
+        let mut children = vec![];
+        for (i, c) in s.chars().enumerate().skip(1) {
+            match c {
+                '[' => {
+                    depth += 1;
+                }
+                ',' => {
+                    if depth == 1 {
+                        children.push(Self::parse(&s[start..i]));
+                        start = i + 1;
+                    }
+                }
+                ']' => {
+                    depth -= 1;
+                }
+                _ => {}
+            }
+            if depth == 0 {
+                children.push(Self::parse(&s[start..i]));
+                break;
+            }
+        }
+        let right = children.pop().unwrap();
+        let left = children.pop().unwrap();
+        Self::Pair(Box::new(left), Box::new(right))
+    }
+
+    fn parse_number(s: &str) -> Self {
+        Self::Value(s.as_bytes()[0] - b'0')
+    }
+
+    fn reduce(&mut self) {
+        loop {
+            if !self.visit_explode() && !self.visit_split() {
+                break;
+            }
+        }
+    }
+
+    fn visit_explode(&mut self) -> bool {
+        let mut idx = 0;
+        if let Some((explode_idx, (left, right))) =
+            self.find_to_explode(0, &mut idx)
+        {
+            idx = 0;
+            self.explode(explode_idx, left, right, &mut idx);
+            true
+        } else {
+            false
+        }
+    }
+
+    fn find_to_explode(
+        &mut self,
+        depth: usize,
+        idx: &mut usize,
+    ) -> Option<(usize, (u8, u8))> {
+        match self {
+            Self::Value(_) => {
+                *idx += 1;
+                None
+            }
+            Self::Pair(left, right) => {
+                if depth == 4 {
+                    let left = if let Self::Value(n) = **left {
+                        n
+                    } else {
+                        panic!("unexpected pair")
+                    };
+                    let right = if let Self::Value(n) = **right {
+                        n
+                    } else {
+                        panic!("unexpected pair")
+                    };
+                    *self = Self::Value(0);
+                    Some((*idx, (left, right)))
+                } else {
+                    left.find_to_explode(depth + 1, idx)
+                        .or_else(|| right.find_to_explode(depth + 1, idx))
+                }
+            }
+        }
+    }
+
+    fn explode(
+        &mut self,
+        explode_idx: usize,
+        left_val: u8,
+        right_val: u8,
+        idx: &mut usize,
+    ) {
+        match self {
+            Self::Value(ref mut n) => {
+                if *idx + 1 == explode_idx {
+                    *n += left_val;
+                } else if *idx == explode_idx + 1 {
+                    *n += right_val;
+                }
+                *idx += 1;
+            }
+            Self::Pair(left, right) => {
+                left.explode(explode_idx, left_val, right_val, idx);
+                right.explode(explode_idx, left_val, right_val, idx);
+            }
+        }
+    }
+
+    fn visit_split(&mut self) -> bool {
+        match self {
+            Self::Value(n) => {
+                if *n >= 10 {
+                    *self = Self::Pair(
+                        Box::new(Self::Value(*n / 2)),
+                        Box::new(Self::Value(*n - *n / 2)),
+                    );
+                    true
+                } else {
+                    false
+                }
+            }
+            Self::Pair(left, right) => {
+                left.visit_split() || right.visit_split()
+            }
+        }
+    }
+
+    fn magnitude(&self) -> u64 {
+        match self {
+            Self::Value(n) => u64::from(*n),
+            Self::Pair(left, right) => {
+                left.magnitude() * 3 + right.magnitude() * 2
+            }
+        }
+    }
+}
+
+impl std::ops::Add for Number {
+    type Output = Number;
+    fn add(self, other: Number) -> Self::Output {
+        let mut ret = Number::Pair(Box::new(self), Box::new(other));
+        ret.reduce();
+        ret
+    }
+}
+
+impl std::ops::Add for &Number {
+    type Output = Number;
+    fn add(self, other: &Number) -> Self::Output {
+        let mut ret =
+            Number::Pair(Box::new(self.clone()), Box::new(other.clone()));
+        ret.reduce();
+        ret
+    }
+}
+
+impl std::ops::AddAssign for Number {
+    fn add_assign(&mut self, other: Number) {
+        *self = self.clone() + other;
+    }
+}
+
+impl std::iter::Sum for Number {
+    fn sum<I>(mut iter: I) -> Self
+    where
+        I: Iterator<Item = Self>,
+    {
+        if let Some(first) = iter.next() {
+            let mut sum = first;
+            for num in iter {
+                sum += num;
+            }
+            sum
+        } else {
+            Number::Value(0)
+        }
+    }
+}
+
+impl std::fmt::Display for Number {
+    fn fmt(
+        &self,
+        f: &mut std::fmt::Formatter<'_>,
+    ) -> Result<(), std::fmt::Error> {
+        match self {
+            Self::Value(n) => write!(f, "{}", n),
+            Self::Pair(left, right) => {
+                write!(f, "[{},{}]", left, right)
+            }
+        }
+    }
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Number>> {
+    Ok(parse::lines(fh))
+}
+
+pub fn part1(numbers: impl Iterator<Item = Number>) -> Result<u64> {
+    let sum: Number = numbers.sum();
+    Ok(sum.magnitude())
+}
+
+pub fn part2(numbers: impl Iterator<Item = Number>) -> Result<u64> {
+    let nums: Vec<_> = numbers.collect();
+    let mut max = 0;
+    for (i, n1) in nums.iter().enumerate() {
+        for (j, n2) in nums.iter().enumerate() {
+            if i == j {
+                continue;
+            }
+            let magnitude = (n1 + n2).magnitude();
+            if magnitude > max {
+                max = magnitude;
+            }
+        }
+    }
+    Ok(max)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 18).unwrap()).unwrap()).unwrap(),
+        3806
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 18).unwrap()).unwrap()).unwrap(),
+        4727
+    );
+}
diff --git a/src/bin/2021/day19.rs b/src/bin/2021/day19.rs
new file mode 100644
index 0000000..735cb19
--- /dev/null
+++ b/src/bin/2021/day19.rs
@@ -0,0 +1,293 @@
+use advent_of_code::prelude::*;
+
+const ORIENTATIONS: &[&dyn Fn(Point) -> Point] = &[
+    &|p| Point::new(p.y, p.z, p.x),
+    &|p| Point::new(-p.y, -p.z, p.x),
+    &|p| Point::new(p.z, -p.y, p.x),
+    &|p| Point::new(-p.z, p.y, p.x),
+    &|p| Point::new(p.y, -p.z, -p.x),
+    &|p| Point::new(-p.y, p.z, -p.x),
+    &|p| Point::new(p.z, p.y, -p.x),
+    &|p| Point::new(-p.z, -p.y, -p.x),
+    &|p| Point::new(p.x, -p.z, p.y),
+    &|p| Point::new(-p.x, p.z, p.y),
+    &|p| Point::new(p.z, p.x, p.y),
+    &|p| Point::new(-p.z, -p.x, p.y),
+    &|p| Point::new(p.x, p.z, -p.y),
+    &|p| Point::new(-p.x, -p.z, -p.y),
+    &|p| Point::new(p.z, -p.x, -p.y),
+    &|p| Point::new(-p.z, p.x, -p.y),
+    &|p| Point::new(p.x, p.y, p.z),
+    &|p| Point::new(-p.x, -p.y, p.z),
+    &|p| Point::new(p.y, -p.x, p.z),
+    &|p| Point::new(-p.y, p.x, p.z),
+    &|p| Point::new(p.x, -p.y, -p.z),
+    &|p| Point::new(-p.x, p.y, -p.z),
+    &|p| Point::new(p.y, p.x, -p.z),
+    &|p| Point::new(-p.y, -p.x, -p.z),
+];
+
+#[derive(Debug, Clone, Copy, Hash, Eq, PartialEq)]
+struct Point {
+    x: i16,
+    y: i16,
+    z: i16,
+}
+
+impl Point {
+    fn new(x: i16, y: i16, z: i16) -> Self {
+        Self { x, y, z }
+    }
+}
+
+impl std::ops::Add for Point {
+    type Output = Point;
+    fn add(self, other: Point) -> Self::Output {
+        Point {
+            x: self.x + other.x,
+            y: self.y + other.y,
+            z: self.z + other.z,
+        }
+    }
+}
+
+impl std::ops::AddAssign for Point {
+    fn add_assign(&mut self, other: Point) {
+        self.x += other.x;
+        self.y += other.y;
+        self.z += other.z;
+    }
+}
+
+impl std::ops::Sub for Point {
+    type Output = Point;
+    fn sub(self, other: Point) -> Self::Output {
+        Point {
+            x: self.x - other.x,
+            y: self.y - other.y,
+            z: self.z - other.z,
+        }
+    }
+}
+
+impl std::ops::SubAssign for Point {
+    fn sub_assign(&mut self, other: Point) {
+        self.x -= other.x;
+        self.y -= other.y;
+        self.z -= other.z;
+    }
+}
+
+impl std::fmt::Display for Point {
+    fn fmt(
+        &self,
+        f: &mut std::fmt::Formatter<'_>,
+    ) -> Result<(), std::fmt::Error> {
+        write!(f, "({},{},{})", self.x, self.y, self.z)
+    }
+}
+
+#[derive(Debug, Clone)]
+struct Scanner {
+    beacons: Vec<Point>,
+}
+
+impl Scanner {
+    fn parse(lines: impl Iterator<Item = String>) -> Self {
+        let mut beacons = vec![];
+        for line in lines {
+            let mut parts = line.split(',').map(|i| i.parse().unwrap());
+            let x = parts.next().unwrap();
+            let y = parts.next().unwrap();
+            let z = parts.next().unwrap();
+            beacons.push(Point::new(x, y, z))
+        }
+        Self { beacons }
+    }
+
+    fn matches(&self, other: &HashSet<Point>) -> Option<(usize, Point)> {
+        for (i, beacons) in self.each_orientation().enumerate() {
+            let mut offsets = vec![];
+            for beacon1 in &beacons {
+                for beacon2 in other {
+                    offsets.push(*beacon2 - *beacon1);
+                }
+            }
+            for offset in offsets {
+                let matches = beacons
+                    .iter()
+                    .filter(|beacon| other.contains(&(**beacon + offset)))
+                    .count();
+                if matches == 0 {
+                    panic!("bug");
+                }
+                if matches >= 12 {
+                    return Some((i, offset));
+                }
+            }
+        }
+        None
+    }
+
+    fn each_orientation(&self) -> impl Iterator<Item = Vec<Point>> {
+        let beacons = self.beacons.clone();
+        ORIENTATIONS.iter().map(move |orientation| {
+            beacons.iter().map(|beacon| orientation(*beacon)).collect()
+        })
+    }
+
+    fn at_orientation<F: Fn(Point) -> Point>(
+        &self,
+        orientation: F,
+        offset: Point,
+    ) -> Self {
+        Self {
+            beacons: self
+                .beacons
+                .iter()
+                .map(|beacon| orientation(*beacon) + offset)
+                .collect(),
+        }
+    }
+}
+
+#[derive(Debug)]
+pub struct Scan {
+    scanners: Vec<Scanner>,
+}
+
+impl Scan {
+    fn parse(mut lines: impl Iterator<Item = String>) -> Self {
+        let mut scanners = vec![];
+        while lines.next().is_some() {
+            scanners.push(Scanner::parse(parse::chunk(&mut lines)));
+        }
+        Self { scanners }
+    }
+
+    fn scanners(&self) -> &[Scanner] {
+        &self.scanners
+    }
+}
+
+pub fn parse(fh: File) -> Result<Scan> {
+    Ok(Scan::parse(parse::raw_lines(fh)))
+}
+
+pub fn part1(scan: Scan) -> Result<usize> {
+    let mut beacons: HashSet<Point> = HashSet::new();
+    let mut skip = None;
+    for (i, scanner1) in scan.scanners().iter().enumerate() {
+        for (j, scanner2) in scan.scanners().iter().enumerate().skip(i + 1) {
+            if let Some((orientation, offset)) =
+                scanner2.matches(&scanner1.beacons.iter().copied().collect())
+            {
+                let scanner2 = scanner2
+                    .at_orientation(ORIENTATIONS[orientation], offset);
+                beacons.extend(scanner1.beacons.iter());
+                beacons.extend(scanner2.beacons.iter());
+                skip = Some((i, j));
+                break;
+            }
+        }
+        if skip.is_some() {
+            break;
+        }
+    }
+    let skip = skip.unwrap();
+    let mut scanners = scan.scanners().to_vec();
+    scanners.remove(skip.1);
+    scanners.remove(skip.0);
+
+    let mut found = None;
+    loop {
+        for (i, scanner) in scanners.iter().enumerate() {
+            if let Some((orientation, offset)) = scanner.matches(&beacons) {
+                let scanner =
+                    scanner.at_orientation(ORIENTATIONS[orientation], offset);
+                beacons.extend(scanner.beacons.iter());
+                found = Some(i);
+                break;
+            }
+        }
+        if let Some(idx) = found {
+            scanners.remove(idx);
+            found = None;
+        } else {
+            break;
+        }
+    }
+    Ok(beacons.len())
+}
+
+pub fn part2(scan: Scan) -> Result<i16> {
+    let mut beacons: HashSet<Point> = HashSet::new();
+    let mut skip = None;
+    let mut offsets = vec![];
+    for (i, scanner1) in scan.scanners().iter().enumerate() {
+        for (j, scanner2) in scan.scanners().iter().enumerate().skip(i + 1) {
+            if let Some((orientation, offset)) =
+                scanner2.matches(&scanner1.beacons.iter().copied().collect())
+            {
+                let scanner2 = scanner2
+                    .at_orientation(ORIENTATIONS[orientation], offset);
+                beacons.extend(scanner1.beacons.iter());
+                beacons.extend(scanner2.beacons.iter());
+                skip = Some((i, j));
+                offsets.push(Point::new(0, 0, 0));
+                offsets.push(offset);
+                break;
+            }
+        }
+        if skip.is_some() {
+            break;
+        }
+    }
+    let skip = skip.unwrap();
+    let mut scanners = scan.scanners().to_vec();
+    scanners.remove(skip.1);
+    scanners.remove(skip.0);
+
+    let mut found = None;
+    loop {
+        for (i, scanner) in scanners.iter().enumerate() {
+            if let Some((orientation, offset)) = scanner.matches(&beacons) {
+                let scanner =
+                    scanner.at_orientation(ORIENTATIONS[orientation], offset);
+                beacons.extend(scanner.beacons.iter());
+                offsets.push(offset);
+                found = Some(i);
+                break;
+            }
+        }
+        if let Some(idx) = found {
+            scanners.remove(idx);
+            found = None;
+        } else {
+            break;
+        }
+    }
+    let mut max = 0;
+    for offset1 in &offsets {
+        for offset2 in &offsets {
+            let dist = *offset1 - *offset2;
+            let dist = dist.x.abs() + dist.y.abs() + dist.z.abs();
+            if dist > max {
+                max = dist;
+            }
+        }
+    }
+    Ok(max)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 19).unwrap()).unwrap()).unwrap(),
+        338
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 19).unwrap()).unwrap()).unwrap(),
+        9862
+    );
+}
diff --git a/src/bin/2021/day2.rs b/src/bin/2021/day2.rs
new file mode 100644
index 0000000..5ae3596
--- /dev/null
+++ b/src/bin/2021/day2.rs
@@ -0,0 +1,73 @@
+use advent_of_code::prelude::*;
+
+pub enum Command {
+    Forward(i64),
+    Down(i64),
+    Up(i64),
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Command>> {
+    Ok(parse::raw_lines(fh).map(|line| {
+        if let Some(n) = line.strip_prefix("forward ") {
+            Command::Forward(n.parse().unwrap())
+        } else if let Some(n) = line.strip_prefix("down ") {
+            Command::Down(n.parse().unwrap())
+        } else if let Some(n) = line.strip_prefix("up ") {
+            Command::Up(n.parse().unwrap())
+        } else {
+            panic!("couldn't parse line: {}", line);
+        }
+    }))
+}
+
+pub fn part1(commands: impl Iterator<Item = Command>) -> Result<i64> {
+    let mut horizontal = 0;
+    let mut vertical = 0;
+    for command in commands {
+        match command {
+            Command::Forward(n) => {
+                horizontal += n;
+            }
+            Command::Down(n) => {
+                vertical += n;
+            }
+            Command::Up(n) => {
+                vertical -= n;
+            }
+        }
+    }
+    Ok(horizontal * vertical)
+}
+
+pub fn part2(commands: impl Iterator<Item = Command>) -> Result<i64> {
+    let mut aim = 0;
+    let mut horizontal = 0;
+    let mut vertical = 0;
+    for command in commands {
+        match command {
+            Command::Forward(n) => {
+                horizontal += n;
+                vertical += aim * n;
+            }
+            Command::Down(n) => {
+                aim += n;
+            }
+            Command::Up(n) => {
+                aim -= n;
+            }
+        }
+    }
+    Ok(horizontal * vertical)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 2).unwrap()).unwrap()).unwrap(),
+        1694130
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 2).unwrap()).unwrap()).unwrap(),
+        1698850445
+    );
+}
diff --git a/src/bin/2021/day20.rs b/src/bin/2021/day20.rs
new file mode 100644
index 0000000..4ff8b7d
--- /dev/null
+++ b/src/bin/2021/day20.rs
@@ -0,0 +1,108 @@
+use advent_of_code::prelude::*;
+
+pub struct Image {
+    algorithm: Vec<bool>,
+    map: Grid<bool>,
+    outer: bool,
+}
+
+impl Image {
+    fn new(algorithm: Vec<bool>, map: Grid<bool>) -> Self {
+        Self {
+            algorithm,
+            map,
+            outer: false,
+        }
+    }
+
+    fn enhance(&mut self) {
+        let mut new_map: Grid<bool> = Grid::default();
+        new_map.grow(self.map.rows() + 2, self.map.cols() + 2);
+        for row in 0..new_map.rows().0 {
+            for col in 0..new_map.cols().0 {
+                let neighbors: &[(Option<usize>, Option<usize>)] = &[
+                    (row.checked_sub(2), col.checked_sub(2)),
+                    (row.checked_sub(2), col.checked_sub(1)),
+                    (row.checked_sub(2), Some(col)),
+                    (row.checked_sub(1), col.checked_sub(2)),
+                    (row.checked_sub(1), col.checked_sub(1)),
+                    (row.checked_sub(1), Some(col)),
+                    (Some(row), col.checked_sub(2)),
+                    (Some(row), col.checked_sub(1)),
+                    (Some(row), Some(col)),
+                ];
+                let neighbors = neighbors.iter().map(|neighbor| {
+                    if let (Some(row), Some(col)) = neighbor {
+                        self.map
+                            .get(Row(*row))
+                            .and_then(|row| row.get(Col(*col)).copied())
+                            .unwrap_or(self.outer)
+                    } else {
+                        self.outer
+                    }
+                });
+                let mut idx = 0;
+                for neighbor in neighbors {
+                    idx = idx * 2 + usize::from(neighbor);
+                }
+                new_map[Row(row)][Col(col)] = self.algorithm[idx]
+            }
+        }
+        self.map = new_map;
+        if self.outer {
+            self.outer = self.algorithm[511];
+        } else {
+            self.outer = self.algorithm[0];
+        }
+    }
+
+    fn count_true(&self) -> usize {
+        if self.outer {
+            panic!("infinite");
+        }
+        self.map.cells().filter(|c| **c).count()
+    }
+}
+
+pub fn parse(fh: File) -> Result<Image> {
+    let mut lines = parse::raw_lines(fh);
+    let algorithm = lines.next().unwrap();
+    let algorithm: Vec<_> = algorithm
+        .as_bytes()
+        .iter()
+        .map(|b| match b {
+            b'#' => true,
+            b'.' => false,
+            _ => panic!("bad algorithm"),
+        })
+        .collect();
+    lines.next().unwrap();
+    let map = parse::bool_grid(lines, b'#', b'.');
+    Ok(Image::new(algorithm, map))
+}
+
+pub fn part1(mut image: Image) -> Result<usize> {
+    for _ in 0..2 {
+        image.enhance();
+    }
+    Ok(image.count_true())
+}
+
+pub fn part2(mut image: Image) -> Result<usize> {
+    for _ in 0..50 {
+        image.enhance();
+    }
+    Ok(image.count_true())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 20).unwrap()).unwrap()).unwrap(),
+        5306
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 20).unwrap()).unwrap()).unwrap(),
+        17497
+    );
+}
diff --git a/src/bin/2021/day21.rs b/src/bin/2021/day21.rs
new file mode 100644
index 0000000..2cf6bfe
--- /dev/null
+++ b/src/bin/2021/day21.rs
@@ -0,0 +1,215 @@
+use advent_of_code::prelude::*;
+
+#[derive(Clone)]
+pub struct Game {
+    p1_pos: i64,
+    p2_pos: i64,
+    p1_score: i64,
+    p2_score: i64,
+    rolls: i64,
+    die_state: i64,
+}
+
+impl Game {
+    fn new(p1: i64, p2: i64) -> Self {
+        Self {
+            p1_pos: p1,
+            p2_pos: p2,
+            p1_score: 0,
+            p2_score: 0,
+            rolls: 0,
+            die_state: 0,
+        }
+    }
+
+    fn roll_deterministic(&mut self) -> i64 {
+        self.die_state += 3;
+        self.rolls += 3;
+        self.die_state * 3 - 3
+    }
+
+    fn score(&mut self, score: i64, p1: bool) {
+        if p1 {
+            self.p1_pos += score;
+            while self.p1_pos > 10 {
+                self.p1_pos -= 10;
+            }
+            self.p1_score += self.p1_pos;
+        } else {
+            self.p2_pos += score;
+            while self.p2_pos > 10 {
+                self.p2_pos -= 10;
+            }
+            self.p2_score += self.p2_pos;
+        }
+    }
+
+    fn value(&self, threshold: i64) -> Option<i64> {
+        if self.p1_score >= threshold {
+            Some(self.p2_score * self.rolls)
+        } else if self.p2_score >= threshold {
+            Some(self.p1_score * self.rolls)
+        } else {
+            None
+        }
+    }
+
+    fn run_dirac(&self, p1: bool) -> (i64, i64) {
+        let mut p1_wins = 0;
+        let mut p2_wins = 0;
+        {
+            let mut clone = self.clone();
+            clone.score(3, p1);
+            if clone.value(21).is_some() {
+                if p1 {
+                    p1_wins += 1;
+                } else {
+                    p2_wins += 1;
+                }
+            } else {
+                let wins = clone.run_dirac(!p1);
+                p1_wins += wins.0;
+                p2_wins += wins.1;
+            }
+        }
+        {
+            let mut clone = self.clone();
+            clone.score(4, p1);
+            if clone.value(21).is_some() {
+                if p1 {
+                    p1_wins += 3;
+                } else {
+                    p2_wins += 3;
+                }
+            } else {
+                let wins = clone.run_dirac(!p1);
+                p1_wins += wins.0 * 3;
+                p2_wins += wins.1 * 3;
+            }
+        }
+        {
+            let mut clone = self.clone();
+            clone.score(5, p1);
+            if clone.value(21).is_some() {
+                if p1 {
+                    p1_wins += 6;
+                } else {
+                    p2_wins += 6;
+                }
+            } else {
+                let wins = clone.run_dirac(!p1);
+                p1_wins += wins.0 * 6;
+                p2_wins += wins.1 * 6;
+            }
+        }
+        {
+            let mut clone = self.clone();
+            clone.score(6, p1);
+            if clone.value(21).is_some() {
+                if p1 {
+                    p1_wins += 7;
+                } else {
+                    p2_wins += 7;
+                }
+            } else {
+                let wins = clone.run_dirac(!p1);
+                p1_wins += wins.0 * 7;
+                p2_wins += wins.1 * 7;
+            }
+        }
+        {
+            let mut clone = self.clone();
+            clone.score(7, p1);
+            if clone.value(21).is_some() {
+                if p1 {
+                    p1_wins += 6;
+                } else {
+                    p2_wins += 6;
+                }
+            } else {
+                let wins = clone.run_dirac(!p1);
+                p1_wins += wins.0 * 6;
+                p2_wins += wins.1 * 6;
+            }
+        }
+        {
+            let mut clone = self.clone();
+            clone.score(8, p1);
+            if clone.value(21).is_some() {
+                if p1 {
+                    p1_wins += 3;
+                } else {
+                    p2_wins += 3;
+                }
+            } else {
+                let wins = clone.run_dirac(!p1);
+                p1_wins += wins.0 * 3;
+                p2_wins += wins.1 * 3;
+            }
+        }
+        {
+            let mut clone = self.clone();
+            clone.score(9, p1);
+            if clone.value(21).is_some() {
+                if p1 {
+                    p1_wins += 1;
+                } else {
+                    p2_wins += 1;
+                }
+            } else {
+                let wins = clone.run_dirac(!p1);
+                p1_wins += wins.0;
+                p2_wins += wins.1;
+            }
+        }
+        (p1_wins, p2_wins)
+    }
+}
+
+pub fn parse(fh: File) -> Result<Game> {
+    let mut lines = parse::raw_lines(fh);
+    let p1 = lines
+        .next()
+        .unwrap()
+        .strip_prefix("Player 1 starting position: ")
+        .unwrap()
+        .parse()
+        .unwrap();
+    let p2 = lines
+        .next()
+        .unwrap()
+        .strip_prefix("Player 2 starting position: ")
+        .unwrap()
+        .parse()
+        .unwrap();
+    Ok(Game::new(p1, p2))
+}
+
+pub fn part1(mut game: Game) -> Result<i64> {
+    let mut p1 = true;
+    loop {
+        if let Some(value) = game.value(1000) {
+            return Ok(value);
+        }
+        let score = game.roll_deterministic();
+        game.score(score, p1);
+        p1 = !p1;
+    }
+}
+
+pub fn part2(game: Game) -> Result<i64> {
+    let (p1, p2) = game.run_dirac(true);
+    Ok(p1.max(p2))
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 21).unwrap()).unwrap()).unwrap(),
+        1004670
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 21).unwrap()).unwrap()).unwrap(),
+        492043106122795
+    );
+}
diff --git a/src/bin/2021/day22.rs b/src/bin/2021/day22.rs
new file mode 100644
index 0000000..ed8a0de
--- /dev/null
+++ b/src/bin/2021/day22.rs
@@ -0,0 +1,216 @@
+use advent_of_code::prelude::*;
+
+#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)]
+struct Point3D {
+    x: i64,
+    y: i64,
+    z: i64,
+}
+
+impl Point3D {
+    fn new(x: i64, y: i64, z: i64) -> Self {
+        Self { x, y, z }
+    }
+}
+
+#[derive(Debug, Clone, Hash, PartialEq, Eq)]
+struct Range3D {
+    x: std::ops::RangeInclusive<i64>,
+    y: std::ops::RangeInclusive<i64>,
+    z: std::ops::RangeInclusive<i64>,
+}
+
+impl Range3D {
+    fn new(
+        x: std::ops::RangeInclusive<i64>,
+        y: std::ops::RangeInclusive<i64>,
+        z: std::ops::RangeInclusive<i64>,
+    ) -> Self {
+        Self { x, y, z }
+    }
+
+    fn contains(&self, point: &Point3D) -> bool {
+        self.x.contains(&point.x)
+            && self.y.contains(&point.y)
+            && self.z.contains(&point.z)
+    }
+
+    fn intersects(&self, other: &Self) -> bool {
+        (self.x.contains(other.x.start())
+            || self.x.contains(other.x.end())
+            || other.x.contains(self.x.start())
+            || other.x.contains(self.x.end()))
+            && (self.y.contains(other.y.start())
+                || self.y.contains(other.y.end())
+                || other.y.contains(self.y.start())
+                || other.y.contains(self.y.end()))
+            && (self.z.contains(other.z.start())
+                || self.z.contains(other.z.end())
+                || other.z.contains(self.z.start())
+                || other.z.contains(self.z.end()))
+    }
+
+    fn intersected_ranges(&self, other: &Self) -> Vec<Self> {
+        let mut ret = vec![];
+        let mut found = false;
+        for x in Self::split_dimension(&self.x, &other.x) {
+            for y in Self::split_dimension(&self.y, &other.y) {
+                for z in Self::split_dimension(&self.z, &other.z) {
+                    let new = Self::new(x.clone(), y.clone(), z.clone());
+                    if other.intersects(&new) {
+                        if found {
+                            panic!("bug 1");
+                        }
+                        found = true;
+                    } else {
+                        ret.push(new);
+                    }
+                }
+            }
+        }
+        if !found {
+            panic!("bug 2");
+        }
+        ret
+    }
+
+    fn split_dimension(
+        to_split: &std::ops::RangeInclusive<i64>,
+        split_by: &std::ops::RangeInclusive<i64>,
+    ) -> Vec<std::ops::RangeInclusive<i64>> {
+        if split_by.start() <= to_split.start() {
+            if split_by.end() < to_split.start() {
+                panic!("bug 3");
+            } else if split_by.end() >= to_split.end() {
+                vec![to_split.clone()]
+            } else {
+                vec![
+                    *to_split.start()..=*split_by.end(),
+                    (*split_by.end() + 1)..=*to_split.end(),
+                ]
+            }
+        } else if split_by.start() > to_split.end() {
+            panic!("bug 4");
+        } else {
+            if split_by.end() >= to_split.end() {
+                vec![
+                    *to_split.start()..=(*split_by.start() - 1),
+                    *split_by.start()..=*to_split.end(),
+                ]
+            } else {
+                vec![
+                    *to_split.start()..=(*split_by.start() - 1),
+                    split_by.clone(),
+                    (*split_by.end() + 1)..=*to_split.end(),
+                ]
+            }
+        }
+    }
+
+    fn size(&self) -> i64 {
+        (self.x.end() - self.x.start() + 1)
+            * (self.y.end() - self.y.start() + 1)
+            * (self.z.end() - self.z.start() + 1)
+    }
+}
+
+#[derive(Debug, Clone)]
+struct Rule {
+    on: bool,
+    range: Range3D,
+}
+
+impl Rule {
+    fn parse(line: &str) -> Self {
+        let captures = regex_captures!(
+            r"^(\w+) x=(-?\d+)..(-?\d+),y=(-?\d+)..(-?\d+),z=(-?\d+)..(-?\d+)$",
+            line
+        )
+        .unwrap();
+        Self {
+            on: &captures[1] == "on",
+            range: Range3D::new(
+                captures[2].parse().unwrap()..=captures[3].parse().unwrap(),
+                captures[4].parse().unwrap()..=captures[5].parse().unwrap(),
+                captures[6].parse().unwrap()..=captures[7].parse().unwrap(),
+            ),
+        }
+    }
+
+    fn contains(&self, point: &Point3D) -> Option<bool> {
+        if self.range.contains(point) {
+            Some(self.on)
+        } else {
+            None
+        }
+    }
+}
+
+#[derive(Debug)]
+pub struct Reactor {
+    rules: Vec<Rule>,
+}
+
+impl Reactor {
+    fn parse(lines: impl Iterator<Item = String>) -> Self {
+        Self {
+            rules: lines.map(|line| Rule::parse(&line)).collect(),
+        }
+    }
+
+    fn on(&self, point: &Point3D) -> bool {
+        for rule in self.rules.iter().rev() {
+            if let Some(on) = rule.contains(point) {
+                return on;
+            }
+        }
+        false
+    }
+}
+
+pub fn parse(fh: File) -> Result<Reactor> {
+    Ok(Reactor::parse(parse::raw_lines(fh)))
+}
+
+pub fn part1(reactor: Reactor) -> Result<u64> {
+    let mut total = 0;
+    for x in -50..=50 {
+        for y in -50..=50 {
+            for z in -50..=50 {
+                if reactor.on(&Point3D::new(x, y, z)) {
+                    total += 1;
+                }
+            }
+        }
+    }
+    Ok(total)
+}
+
+pub fn part2(reactor: Reactor) -> Result<i64> {
+    let mut on: HashSet<Range3D> = HashSet::new();
+    for rule in reactor.rules {
+        let (intersected, nonintersected) = on
+            .into_iter()
+            .partition(|range| rule.range.intersects(range));
+        on = nonintersected;
+        for range in intersected {
+            on.extend(range.intersected_ranges(&rule.range));
+        }
+        if rule.on {
+            on.insert(rule.range);
+        }
+    }
+    Ok(on.iter().map(|range| range.size()).sum())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 22).unwrap()).unwrap()).unwrap(),
+        570915
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 22).unwrap()).unwrap()).unwrap(),
+        1268313839428137
+    );
+}
diff --git a/src/bin/2021/day23.rs b/src/bin/2021/day23.rs
new file mode 100644
index 0000000..c86f7c0
--- /dev/null
+++ b/src/bin/2021/day23.rs
@@ -0,0 +1,1736 @@
+use advent_of_code::prelude::*;
+
+static CONNECTIVITY1: &[&[&[usize]]] = &[
+    &[
+        &[],
+        &[1],
+        &[1, 2],
+        &[1, 2, 3],
+        &[1, 2, 3, 4],
+        &[1, 2, 3, 4, 5],
+        &[1, 2, 3, 4, 5, 6],
+        &[1, 2, 3, 4, 5, 6, 7],
+        &[1, 2, 3, 4, 5, 6, 7, 8],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 9],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[1, 2, 11],
+        &[1, 2, 3, 4, 12],
+        &[1, 2, 3, 4, 5, 6, 13],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 14],
+        &[1, 2, 11, 15],
+        &[1, 2, 3, 4, 12, 16],
+        &[1, 2, 3, 4, 5, 6, 13, 17],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[0],
+        &[],
+        &[2],
+        &[2, 3],
+        &[2, 3, 4],
+        &[2, 3, 4, 5],
+        &[2, 3, 4, 5, 6],
+        &[2, 3, 4, 5, 6, 7],
+        &[2, 3, 4, 5, 6, 7, 8],
+        &[2, 3, 4, 5, 6, 7, 8, 9],
+        &[2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[2, 11],
+        &[2, 3, 4, 12],
+        &[2, 3, 4, 5, 6, 13],
+        &[2, 3, 4, 5, 6, 7, 8, 14],
+        &[2, 11, 15],
+        &[2, 3, 4, 12, 16],
+        &[2, 3, 4, 5, 6, 13, 17],
+        &[2, 3, 4, 5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[1, 0],
+        &[1],
+        &[],
+        &[3],
+        &[3, 4],
+        &[3, 4, 5],
+        &[3, 4, 5, 6],
+        &[3, 4, 5, 6, 7],
+        &[3, 4, 5, 6, 7, 8],
+        &[3, 4, 5, 6, 7, 8, 9],
+        &[3, 4, 5, 6, 7, 8, 9, 10],
+        &[11],
+        &[3, 4, 12],
+        &[3, 4, 5, 6, 13],
+        &[3, 4, 5, 6, 7, 8, 14],
+        &[11, 15],
+        &[3, 4, 12, 16],
+        &[3, 4, 5, 6, 13, 17],
+        &[3, 4, 5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[2, 1, 0],
+        &[2, 1],
+        &[2],
+        &[],
+        &[4],
+        &[4, 5],
+        &[4, 5, 6],
+        &[4, 5, 6, 7],
+        &[4, 5, 6, 7, 8],
+        &[4, 5, 6, 7, 8, 9],
+        &[4, 5, 6, 7, 8, 9, 10],
+        &[2, 11],
+        &[4, 12],
+        &[4, 5, 6, 13],
+        &[4, 5, 6, 7, 8, 14],
+        &[2, 11, 15],
+        &[4, 12, 16],
+        &[4, 5, 6, 13, 17],
+        &[4, 5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[3, 2, 1, 0],
+        &[3, 2, 1],
+        &[3, 2],
+        &[3],
+        &[],
+        &[5],
+        &[5, 6],
+        &[5, 6, 7],
+        &[5, 6, 7, 8],
+        &[5, 6, 7, 8, 9],
+        &[5, 6, 7, 8, 9, 10],
+        &[3, 2, 11],
+        &[12],
+        &[5, 6, 13],
+        &[5, 6, 7, 8, 14],
+        &[3, 2, 11, 15],
+        &[12, 16],
+        &[5, 6, 13, 17],
+        &[5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[4, 3, 2, 1, 0],
+        &[4, 3, 2, 1],
+        &[4, 3, 2],
+        &[4, 3],
+        &[4],
+        &[],
+        &[6],
+        &[6, 7],
+        &[6, 7, 8],
+        &[6, 7, 8, 9],
+        &[6, 7, 8, 9, 10],
+        &[4, 3, 2, 11],
+        &[4, 12],
+        &[6, 13],
+        &[6, 7, 8, 14],
+        &[4, 3, 2, 11, 15],
+        &[4, 12, 16],
+        &[6, 13, 17],
+        &[6, 7, 8, 14, 18],
+    ],
+    &[
+        &[5, 4, 3, 2, 1, 0],
+        &[5, 4, 3, 2, 1],
+        &[5, 4, 3, 2],
+        &[5, 4, 3],
+        &[5, 4],
+        &[5],
+        &[],
+        &[7],
+        &[7, 8],
+        &[7, 8, 9],
+        &[7, 8, 9, 10],
+        &[5, 4, 3, 2, 11],
+        &[5, 4, 12],
+        &[13],
+        &[7, 8, 14],
+        &[5, 4, 3, 2, 11, 15],
+        &[5, 4, 12, 16],
+        &[13, 17],
+        &[7, 8, 14, 18],
+    ],
+    &[
+        &[6, 5, 4, 3, 2, 1, 0],
+        &[6, 5, 4, 3, 2, 1],
+        &[6, 5, 4, 3, 2],
+        &[6, 5, 4, 3],
+        &[6, 5, 4],
+        &[6, 5],
+        &[6],
+        &[],
+        &[8],
+        &[8, 9],
+        &[8, 9, 10],
+        &[6, 5, 4, 3, 2, 11],
+        &[6, 5, 4, 12],
+        &[6, 13],
+        &[8, 14],
+        &[6, 5, 4, 3, 2, 11, 15],
+        &[6, 5, 4, 12, 16],
+        &[6, 13, 17],
+        &[8, 14, 18],
+    ],
+    &[
+        &[7, 6, 5, 4, 3, 2, 1, 0],
+        &[7, 6, 5, 4, 3, 2, 1],
+        &[7, 6, 5, 4, 3, 2],
+        &[7, 6, 5, 4, 3],
+        &[7, 6, 5, 4],
+        &[7, 6, 5],
+        &[7, 6],
+        &[7],
+        &[],
+        &[9],
+        &[9, 10],
+        &[7, 6, 5, 4, 3, 2, 11],
+        &[7, 6, 5, 4, 12],
+        &[7, 6, 13],
+        &[14],
+        &[7, 6, 5, 4, 3, 2, 11, 15],
+        &[7, 6, 5, 4, 12, 16],
+        &[7, 6, 13, 17],
+        &[14, 18],
+    ],
+    &[
+        &[8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[8, 7, 6, 5, 4, 3, 2, 1],
+        &[8, 7, 6, 5, 4, 3, 2],
+        &[8, 7, 6, 5, 4, 3],
+        &[8, 7, 6, 5, 4],
+        &[8, 7, 6, 5],
+        &[8, 7, 6],
+        &[8, 7],
+        &[8],
+        &[],
+        &[10],
+        &[8, 7, 6, 5, 4, 3, 2, 11],
+        &[8, 7, 6, 5, 4, 12],
+        &[8, 7, 6, 13],
+        &[8, 14],
+        &[8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[8, 7, 6, 5, 4, 12, 16],
+        &[8, 7, 6, 13, 17],
+        &[8, 14, 18],
+    ],
+    &[
+        &[9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[9, 8, 7, 6, 5, 4, 3, 2, 1],
+        &[9, 8, 7, 6, 5, 4, 3, 2],
+        &[9, 8, 7, 6, 5, 4, 3],
+        &[9, 8, 7, 6, 5, 4],
+        &[9, 8, 7, 6, 5],
+        &[9, 8, 7, 6],
+        &[9, 8, 7],
+        &[9, 8],
+        &[9],
+        &[],
+        &[9, 8, 7, 6, 5, 4, 3, 2, 11],
+        &[9, 8, 7, 6, 5, 4, 12],
+        &[9, 8, 7, 6, 13],
+        &[9, 8, 14],
+        &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[9, 8, 7, 6, 5, 4, 12, 16],
+        &[9, 8, 7, 6, 13, 17],
+        &[9, 8, 14, 18],
+    ],
+    &[
+        &[2, 1, 0],
+        &[2, 1],
+        &[2],
+        &[2, 3],
+        &[2, 3, 4],
+        &[2, 3, 4, 5],
+        &[2, 3, 4, 5, 6],
+        &[2, 3, 4, 5, 6, 7],
+        &[2, 3, 4, 5, 6, 7, 8],
+        &[2, 3, 4, 5, 6, 7, 8, 9],
+        &[2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[],
+        &[2, 3, 4, 12],
+        &[2, 3, 4, 5, 6, 13],
+        &[2, 3, 4, 5, 6, 7, 8, 14],
+        &[15],
+        &[2, 3, 4, 12, 16],
+        &[2, 3, 4, 5, 6, 13, 17],
+        &[2, 3, 4, 5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[4, 3, 2, 1, 0],
+        &[4, 3, 2, 1],
+        &[4, 3, 2],
+        &[4, 3],
+        &[4],
+        &[4, 5],
+        &[4, 5, 6],
+        &[4, 5, 6, 7],
+        &[4, 5, 6, 7, 8],
+        &[4, 5, 6, 7, 8, 9],
+        &[4, 5, 6, 7, 8, 9, 10],
+        &[4, 3, 2, 11],
+        &[],
+        &[4, 5, 6, 13],
+        &[4, 5, 6, 7, 8, 14],
+        &[4, 3, 2, 11, 15],
+        &[16],
+        &[4, 5, 6, 13, 17],
+        &[4, 5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[6, 5, 4, 3, 2, 1, 0],
+        &[6, 5, 4, 3, 2, 1],
+        &[6, 5, 4, 3, 2],
+        &[6, 5, 4, 3],
+        &[6, 5, 4],
+        &[6, 5],
+        &[6],
+        &[6, 7],
+        &[6, 7, 8],
+        &[6, 7, 8, 9],
+        &[6, 7, 8, 9, 10],
+        &[6, 5, 4, 3, 2, 11],
+        &[6, 5, 4, 12],
+        &[],
+        &[6, 7, 8, 14],
+        &[6, 5, 4, 3, 2, 11, 15],
+        &[6, 5, 4, 12, 16],
+        &[17],
+        &[6, 7, 8, 14, 18],
+    ],
+    &[
+        &[8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[8, 7, 6, 5, 4, 3, 2, 1],
+        &[8, 7, 6, 5, 4, 3, 2],
+        &[8, 7, 6, 5, 4, 3],
+        &[8, 7, 6, 5, 4],
+        &[8, 7, 6, 5],
+        &[8, 7, 6],
+        &[8, 7],
+        &[8],
+        &[8, 9],
+        &[8, 9, 10],
+        &[8, 7, 6, 5, 4, 3, 2, 11],
+        &[8, 7, 6, 5, 4, 12],
+        &[8, 7, 6, 13],
+        &[],
+        &[8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[8, 7, 6, 5, 4, 12, 16],
+        &[8, 7, 6, 13, 17],
+        &[18],
+    ],
+    &[
+        &[11, 2, 1, 0],
+        &[11, 2, 1],
+        &[11, 2],
+        &[11, 2, 3],
+        &[11, 2, 3, 4],
+        &[11, 2, 3, 4, 5],
+        &[11, 2, 3, 4, 5, 6],
+        &[11, 2, 3, 4, 5, 6, 7],
+        &[11, 2, 3, 4, 5, 6, 7, 8],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 9],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[11],
+        &[11, 2, 3, 4, 12],
+        &[11, 2, 3, 4, 5, 6, 13],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 14],
+        &[],
+        &[11, 2, 3, 4, 12, 16],
+        &[11, 2, 3, 4, 5, 6, 13, 17],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[12, 4, 3, 2, 1, 0],
+        &[12, 4, 3, 2, 1],
+        &[12, 4, 3, 2],
+        &[12, 4, 3],
+        &[12, 4],
+        &[12, 4, 5],
+        &[12, 4, 5, 6],
+        &[12, 4, 5, 6, 7],
+        &[12, 4, 5, 6, 7, 8],
+        &[12, 4, 5, 6, 7, 8, 9],
+        &[12, 4, 5, 6, 7, 8, 9, 10],
+        &[12, 4, 3, 2, 11],
+        &[12],
+        &[12, 4, 5, 6, 13],
+        &[12, 4, 5, 6, 7, 8, 14],
+        &[12, 4, 3, 2, 11, 15],
+        &[],
+        &[12, 4, 5, 6, 13, 17],
+        &[12, 4, 5, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[13, 6, 5, 4, 3, 2, 1, 0],
+        &[13, 6, 5, 4, 3, 2, 1],
+        &[13, 6, 5, 4, 3, 2],
+        &[13, 6, 5, 4, 3],
+        &[13, 6, 5, 4],
+        &[13, 6, 5],
+        &[13, 6],
+        &[13, 6, 7],
+        &[13, 6, 7, 8],
+        &[13, 6, 7, 8, 9],
+        &[13, 6, 7, 8, 9, 10],
+        &[13, 6, 5, 4, 3, 2, 11],
+        &[13, 6, 5, 4, 12],
+        &[13],
+        &[13, 6, 7, 8, 14],
+        &[13, 6, 5, 4, 3, 2, 11, 15],
+        &[13, 6, 5, 4, 12, 16],
+        &[],
+        &[13, 6, 7, 8, 14, 18],
+    ],
+    &[
+        &[14, 8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[14, 8, 7, 6, 5, 4, 3, 2, 1],
+        &[14, 8, 7, 6, 5, 4, 3, 2],
+        &[14, 8, 7, 6, 5, 4, 3],
+        &[14, 8, 7, 6, 5, 4],
+        &[14, 8, 7, 6, 5],
+        &[14, 8, 7, 6],
+        &[14, 8, 7],
+        &[14, 8],
+        &[14, 8, 9],
+        &[14, 8, 9, 10],
+        &[14, 8, 7, 6, 5, 4, 3, 2, 11],
+        &[14, 8, 7, 6, 5, 4, 12],
+        &[14, 8, 7, 6, 13],
+        &[14],
+        &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[14, 8, 7, 6, 5, 4, 12, 16],
+        &[14, 8, 7, 6, 13, 17],
+        &[],
+    ],
+];
+
+static CONNECTIVITY2: &[&[&[usize]]] = &[
+    &[
+        &[],
+        &[1],
+        &[1, 2],
+        &[1, 2, 3],
+        &[1, 2, 3, 4],
+        &[1, 2, 3, 4, 5],
+        &[1, 2, 3, 4, 5, 6],
+        &[1, 2, 3, 4, 5, 6, 7],
+        &[1, 2, 3, 4, 5, 6, 7, 8],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 9],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[1, 2, 11],
+        &[1, 2, 3, 4, 12],
+        &[1, 2, 3, 4, 5, 6, 13],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 14],
+        &[1, 2, 11, 15],
+        &[1, 2, 3, 4, 12, 16],
+        &[1, 2, 3, 4, 5, 6, 13, 17],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18],
+        &[1, 2, 11, 15, 19],
+        &[1, 2, 3, 4, 12, 16, 20],
+        &[1, 2, 3, 4, 5, 6, 13, 17, 21],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[1, 2, 11, 15, 19, 23],
+        &[1, 2, 3, 4, 12, 16, 20, 24],
+        &[1, 2, 3, 4, 5, 6, 13, 17, 21, 25],
+        &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[0],
+        &[],
+        &[2],
+        &[2, 3],
+        &[2, 3, 4],
+        &[2, 3, 4, 5],
+        &[2, 3, 4, 5, 6],
+        &[2, 3, 4, 5, 6, 7],
+        &[2, 3, 4, 5, 6, 7, 8],
+        &[2, 3, 4, 5, 6, 7, 8, 9],
+        &[2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[2, 11],
+        &[2, 3, 4, 12],
+        &[2, 3, 4, 5, 6, 13],
+        &[2, 3, 4, 5, 6, 7, 8, 14],
+        &[2, 11, 15],
+        &[2, 3, 4, 12, 16],
+        &[2, 3, 4, 5, 6, 13, 17],
+        &[2, 3, 4, 5, 6, 7, 8, 14, 18],
+        &[2, 11, 15, 19],
+        &[2, 3, 4, 12, 16, 20],
+        &[2, 3, 4, 5, 6, 13, 17, 21],
+        &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[2, 11, 15, 19, 23],
+        &[2, 3, 4, 12, 16, 20, 24],
+        &[2, 3, 4, 5, 6, 13, 17, 21, 25],
+        &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[1, 0],
+        &[1],
+        &[],
+        &[3],
+        &[3, 4],
+        &[3, 4, 5],
+        &[3, 4, 5, 6],
+        &[3, 4, 5, 6, 7],
+        &[3, 4, 5, 6, 7, 8],
+        &[3, 4, 5, 6, 7, 8, 9],
+        &[3, 4, 5, 6, 7, 8, 9, 10],
+        &[11],
+        &[3, 4, 12],
+        &[3, 4, 5, 6, 13],
+        &[3, 4, 5, 6, 7, 8, 14],
+        &[11, 15],
+        &[3, 4, 12, 16],
+        &[3, 4, 5, 6, 13, 17],
+        &[3, 4, 5, 6, 7, 8, 14, 18],
+        &[11, 15, 19],
+        &[3, 4, 12, 16, 20],
+        &[3, 4, 5, 6, 13, 17, 21],
+        &[3, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[11, 15, 19, 23],
+        &[3, 4, 12, 16, 20, 24],
+        &[3, 4, 5, 6, 13, 17, 21, 25],
+        &[3, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[2, 1, 0],
+        &[2, 1],
+        &[2],
+        &[],
+        &[4],
+        &[4, 5],
+        &[4, 5, 6],
+        &[4, 5, 6, 7],
+        &[4, 5, 6, 7, 8],
+        &[4, 5, 6, 7, 8, 9],
+        &[4, 5, 6, 7, 8, 9, 10],
+        &[2, 11],
+        &[4, 12],
+        &[4, 5, 6, 13],
+        &[4, 5, 6, 7, 8, 14],
+        &[2, 11, 15],
+        &[4, 12, 16],
+        &[4, 5, 6, 13, 17],
+        &[4, 5, 6, 7, 8, 14, 18],
+        &[2, 11, 15, 19],
+        &[4, 12, 16, 20],
+        &[4, 5, 6, 13, 17, 21],
+        &[4, 5, 6, 7, 8, 14, 18, 22],
+        &[2, 11, 15, 19, 23],
+        &[4, 12, 16, 20, 24],
+        &[4, 5, 6, 13, 17, 21, 25],
+        &[4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[3, 2, 1, 0],
+        &[3, 2, 1],
+        &[3, 2],
+        &[3],
+        &[],
+        &[5],
+        &[5, 6],
+        &[5, 6, 7],
+        &[5, 6, 7, 8],
+        &[5, 6, 7, 8, 9],
+        &[5, 6, 7, 8, 9, 10],
+        &[3, 2, 11],
+        &[12],
+        &[5, 6, 13],
+        &[5, 6, 7, 8, 14],
+        &[3, 2, 11, 15],
+        &[12, 16],
+        &[5, 6, 13, 17],
+        &[5, 6, 7, 8, 14, 18],
+        &[3, 2, 11, 15, 19],
+        &[12, 16, 20],
+        &[5, 6, 13, 17, 21],
+        &[5, 6, 7, 8, 14, 18, 22],
+        &[3, 2, 11, 15, 19, 23],
+        &[12, 16, 20, 24],
+        &[5, 6, 13, 17, 21, 25],
+        &[5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[4, 3, 2, 1, 0],
+        &[4, 3, 2, 1],
+        &[4, 3, 2],
+        &[4, 3],
+        &[4],
+        &[],
+        &[6],
+        &[6, 7],
+        &[6, 7, 8],
+        &[6, 7, 8, 9],
+        &[6, 7, 8, 9, 10],
+        &[4, 3, 2, 11],
+        &[4, 12],
+        &[6, 13],
+        &[6, 7, 8, 14],
+        &[4, 3, 2, 11, 15],
+        &[4, 12, 16],
+        &[6, 13, 17],
+        &[6, 7, 8, 14, 18],
+        &[4, 3, 2, 11, 15, 19],
+        &[4, 12, 16, 20],
+        &[6, 13, 17, 21],
+        &[6, 7, 8, 14, 18, 22],
+        &[4, 3, 2, 11, 15, 19, 23],
+        &[4, 12, 16, 20, 24],
+        &[6, 13, 17, 21, 25],
+        &[6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[5, 4, 3, 2, 1, 0],
+        &[5, 4, 3, 2, 1],
+        &[5, 4, 3, 2],
+        &[5, 4, 3],
+        &[5, 4],
+        &[5],
+        &[],
+        &[7],
+        &[7, 8],
+        &[7, 8, 9],
+        &[7, 8, 9, 10],
+        &[5, 4, 3, 2, 11],
+        &[5, 4, 12],
+        &[13],
+        &[7, 8, 14],
+        &[5, 4, 3, 2, 11, 15],
+        &[5, 4, 12, 16],
+        &[13, 17],
+        &[7, 8, 14, 18],
+        &[5, 4, 3, 2, 11, 15, 19],
+        &[5, 4, 12, 16, 20],
+        &[13, 17, 21],
+        &[7, 8, 14, 18, 22],
+        &[5, 4, 3, 2, 11, 15, 19, 23],
+        &[5, 4, 12, 16, 20, 24],
+        &[13, 17, 21, 25],
+        &[7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[6, 5, 4, 3, 2, 1, 0],
+        &[6, 5, 4, 3, 2, 1],
+        &[6, 5, 4, 3, 2],
+        &[6, 5, 4, 3],
+        &[6, 5, 4],
+        &[6, 5],
+        &[6],
+        &[],
+        &[8],
+        &[8, 9],
+        &[8, 9, 10],
+        &[6, 5, 4, 3, 2, 11],
+        &[6, 5, 4, 12],
+        &[6, 13],
+        &[8, 14],
+        &[6, 5, 4, 3, 2, 11, 15],
+        &[6, 5, 4, 12, 16],
+        &[6, 13, 17],
+        &[8, 14, 18],
+        &[6, 5, 4, 3, 2, 11, 15, 19],
+        &[6, 5, 4, 12, 16, 20],
+        &[6, 13, 17, 21],
+        &[8, 14, 18, 22],
+        &[6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[6, 5, 4, 12, 16, 20, 24],
+        &[6, 13, 17, 21, 25],
+        &[8, 14, 18, 22, 26],
+    ],
+    &[
+        &[7, 6, 5, 4, 3, 2, 1, 0],
+        &[7, 6, 5, 4, 3, 2, 1],
+        &[7, 6, 5, 4, 3, 2],
+        &[7, 6, 5, 4, 3],
+        &[7, 6, 5, 4],
+        &[7, 6, 5],
+        &[7, 6],
+        &[7],
+        &[],
+        &[9],
+        &[9, 10],
+        &[7, 6, 5, 4, 3, 2, 11],
+        &[7, 6, 5, 4, 12],
+        &[7, 6, 13],
+        &[14],
+        &[7, 6, 5, 4, 3, 2, 11, 15],
+        &[7, 6, 5, 4, 12, 16],
+        &[7, 6, 13, 17],
+        &[14, 18],
+        &[7, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[7, 6, 5, 4, 12, 16, 20],
+        &[7, 6, 13, 17, 21],
+        &[14, 18, 22],
+        &[7, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[7, 6, 5, 4, 12, 16, 20, 24],
+        &[7, 6, 13, 17, 21, 25],
+        &[14, 18, 22, 26],
+    ],
+    &[
+        &[8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[8, 7, 6, 5, 4, 3, 2, 1],
+        &[8, 7, 6, 5, 4, 3, 2],
+        &[8, 7, 6, 5, 4, 3],
+        &[8, 7, 6, 5, 4],
+        &[8, 7, 6, 5],
+        &[8, 7, 6],
+        &[8, 7],
+        &[8],
+        &[],
+        &[10],
+        &[8, 7, 6, 5, 4, 3, 2, 11],
+        &[8, 7, 6, 5, 4, 12],
+        &[8, 7, 6, 13],
+        &[8, 14],
+        &[8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[8, 7, 6, 5, 4, 12, 16],
+        &[8, 7, 6, 13, 17],
+        &[8, 14, 18],
+        &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[8, 7, 6, 5, 4, 12, 16, 20],
+        &[8, 7, 6, 13, 17, 21],
+        &[8, 14, 18, 22],
+        &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[8, 7, 6, 5, 4, 12, 16, 20, 24],
+        &[8, 7, 6, 13, 17, 21, 25],
+        &[8, 14, 18, 22, 26],
+    ],
+    &[
+        &[9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[9, 8, 7, 6, 5, 4, 3, 2, 1],
+        &[9, 8, 7, 6, 5, 4, 3, 2],
+        &[9, 8, 7, 6, 5, 4, 3],
+        &[9, 8, 7, 6, 5, 4],
+        &[9, 8, 7, 6, 5],
+        &[9, 8, 7, 6],
+        &[9, 8, 7],
+        &[9, 8],
+        &[9],
+        &[],
+        &[9, 8, 7, 6, 5, 4, 3, 2, 11],
+        &[9, 8, 7, 6, 5, 4, 12],
+        &[9, 8, 7, 6, 13],
+        &[9, 8, 14],
+        &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[9, 8, 7, 6, 5, 4, 12, 16],
+        &[9, 8, 7, 6, 13, 17],
+        &[9, 8, 14, 18],
+        &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[9, 8, 7, 6, 5, 4, 12, 16, 20],
+        &[9, 8, 7, 6, 13, 17, 21],
+        &[9, 8, 14, 18, 22],
+        &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[9, 8, 7, 6, 5, 4, 12, 16, 20, 24],
+        &[9, 8, 7, 6, 13, 17, 21, 25],
+        &[9, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[2, 1, 0],
+        &[2, 1],
+        &[2],
+        &[2, 3],
+        &[2, 3, 4],
+        &[2, 3, 4, 5],
+        &[2, 3, 4, 5, 6],
+        &[2, 3, 4, 5, 6, 7],
+        &[2, 3, 4, 5, 6, 7, 8],
+        &[2, 3, 4, 5, 6, 7, 8, 9],
+        &[2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[],
+        &[2, 3, 4, 12],
+        &[2, 3, 4, 5, 6, 13],
+        &[2, 3, 4, 5, 6, 7, 8, 14],
+        &[15],
+        &[2, 3, 4, 12, 16],
+        &[2, 3, 4, 5, 6, 13, 17],
+        &[2, 3, 4, 5, 6, 7, 8, 14, 18],
+        &[15, 19],
+        &[2, 3, 4, 12, 16, 20],
+        &[2, 3, 4, 5, 6, 13, 17, 21],
+        &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[15, 19, 23],
+        &[2, 3, 4, 12, 16, 20, 24],
+        &[2, 3, 4, 5, 6, 13, 17, 21, 25],
+        &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[4, 3, 2, 1, 0],
+        &[4, 3, 2, 1],
+        &[4, 3, 2],
+        &[4, 3],
+        &[4],
+        &[4, 5],
+        &[4, 5, 6],
+        &[4, 5, 6, 7],
+        &[4, 5, 6, 7, 8],
+        &[4, 5, 6, 7, 8, 9],
+        &[4, 5, 6, 7, 8, 9, 10],
+        &[4, 3, 2, 11],
+        &[],
+        &[4, 5, 6, 13],
+        &[4, 5, 6, 7, 8, 14],
+        &[4, 3, 2, 11, 15],
+        &[16],
+        &[4, 5, 6, 13, 17],
+        &[4, 5, 6, 7, 8, 14, 18],
+        &[4, 3, 2, 11, 15, 19],
+        &[16, 20],
+        &[4, 5, 6, 13, 17, 21],
+        &[4, 5, 6, 7, 8, 14, 18, 22],
+        &[4, 3, 2, 11, 15, 19, 23],
+        &[16, 20, 24],
+        &[4, 5, 6, 13, 17, 21, 25],
+        &[4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[6, 5, 4, 3, 2, 1, 0],
+        &[6, 5, 4, 3, 2, 1],
+        &[6, 5, 4, 3, 2],
+        &[6, 5, 4, 3],
+        &[6, 5, 4],
+        &[6, 5],
+        &[6],
+        &[6, 7],
+        &[6, 7, 8],
+        &[6, 7, 8, 9],
+        &[6, 7, 8, 9, 10],
+        &[6, 5, 4, 3, 2, 11],
+        &[6, 5, 4, 12],
+        &[],
+        &[6, 7, 8, 14],
+        &[6, 5, 4, 3, 2, 11, 15],
+        &[6, 5, 4, 12, 16],
+        &[17],
+        &[6, 7, 8, 14, 18],
+        &[6, 5, 4, 3, 2, 11, 15, 19],
+        &[6, 5, 4, 12, 16, 20],
+        &[17, 21],
+        &[6, 7, 8, 14, 18, 22],
+        &[6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[6, 5, 4, 12, 16, 20, 24],
+        &[17, 21, 25],
+        &[6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[8, 7, 6, 5, 4, 3, 2, 1],
+        &[8, 7, 6, 5, 4, 3, 2],
+        &[8, 7, 6, 5, 4, 3],
+        &[8, 7, 6, 5, 4],
+        &[8, 7, 6, 5],
+        &[8, 7, 6],
+        &[8, 7],
+        &[8],
+        &[8, 9],
+        &[8, 9, 10],
+        &[8, 7, 6, 5, 4, 3, 2, 11],
+        &[8, 7, 6, 5, 4, 12],
+        &[8, 7, 6, 13],
+        &[],
+        &[8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[8, 7, 6, 5, 4, 12, 16],
+        &[8, 7, 6, 13, 17],
+        &[18],
+        &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[8, 7, 6, 5, 4, 12, 16, 20],
+        &[8, 7, 6, 13, 17, 21],
+        &[18, 22],
+        &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[8, 7, 6, 5, 4, 12, 16, 20, 24],
+        &[8, 7, 6, 13, 17, 21, 25],
+        &[18, 22, 26],
+    ],
+    &[
+        &[11, 2, 1, 0],
+        &[11, 2, 1],
+        &[11, 2],
+        &[11, 2, 3],
+        &[11, 2, 3, 4],
+        &[11, 2, 3, 4, 5],
+        &[11, 2, 3, 4, 5, 6],
+        &[11, 2, 3, 4, 5, 6, 7],
+        &[11, 2, 3, 4, 5, 6, 7, 8],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 9],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[11],
+        &[11, 2, 3, 4, 12],
+        &[11, 2, 3, 4, 5, 6, 13],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 14],
+        &[],
+        &[11, 2, 3, 4, 12, 16],
+        &[11, 2, 3, 4, 5, 6, 13, 17],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18],
+        &[19],
+        &[11, 2, 3, 4, 12, 16, 20],
+        &[11, 2, 3, 4, 5, 6, 13, 17, 21],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[19, 23],
+        &[11, 2, 3, 4, 12, 16, 20, 24],
+        &[11, 2, 3, 4, 5, 6, 13, 17, 21, 25],
+        &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[12, 4, 3, 2, 1, 0],
+        &[12, 4, 3, 2, 1],
+        &[12, 4, 3, 2],
+        &[12, 4, 3],
+        &[12, 4],
+        &[12, 4, 5],
+        &[12, 4, 5, 6],
+        &[12, 4, 5, 6, 7],
+        &[12, 4, 5, 6, 7, 8],
+        &[12, 4, 5, 6, 7, 8, 9],
+        &[12, 4, 5, 6, 7, 8, 9, 10],
+        &[12, 4, 3, 2, 11],
+        &[12],
+        &[12, 4, 5, 6, 13],
+        &[12, 4, 5, 6, 7, 8, 14],
+        &[12, 4, 3, 2, 11, 15],
+        &[],
+        &[12, 4, 5, 6, 13, 17],
+        &[12, 4, 5, 6, 7, 8, 14, 18],
+        &[12, 4, 3, 2, 11, 15, 19],
+        &[20],
+        &[12, 4, 5, 6, 13, 17, 21],
+        &[12, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[12, 4, 3, 2, 11, 15, 19, 23],
+        &[20, 24],
+        &[12, 4, 5, 6, 13, 17, 21, 25],
+        &[12, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[13, 6, 5, 4, 3, 2, 1, 0],
+        &[13, 6, 5, 4, 3, 2, 1],
+        &[13, 6, 5, 4, 3, 2],
+        &[13, 6, 5, 4, 3],
+        &[13, 6, 5, 4],
+        &[13, 6, 5],
+        &[13, 6],
+        &[13, 6, 7],
+        &[13, 6, 7, 8],
+        &[13, 6, 7, 8, 9],
+        &[13, 6, 7, 8, 9, 10],
+        &[13, 6, 5, 4, 3, 2, 11],
+        &[13, 6, 5, 4, 12],
+        &[13],
+        &[13, 6, 7, 8, 14],
+        &[13, 6, 5, 4, 3, 2, 11, 15],
+        &[13, 6, 5, 4, 12, 16],
+        &[],
+        &[13, 6, 7, 8, 14, 18],
+        &[13, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[13, 6, 5, 4, 12, 16, 20],
+        &[21],
+        &[13, 6, 7, 8, 14, 18, 22],
+        &[13, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[13, 6, 5, 4, 12, 16, 20, 24],
+        &[21, 25],
+        &[13, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[14, 8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[14, 8, 7, 6, 5, 4, 3, 2, 1],
+        &[14, 8, 7, 6, 5, 4, 3, 2],
+        &[14, 8, 7, 6, 5, 4, 3],
+        &[14, 8, 7, 6, 5, 4],
+        &[14, 8, 7, 6, 5],
+        &[14, 8, 7, 6],
+        &[14, 8, 7],
+        &[14, 8],
+        &[14, 8, 9],
+        &[14, 8, 9, 10],
+        &[14, 8, 7, 6, 5, 4, 3, 2, 11],
+        &[14, 8, 7, 6, 5, 4, 12],
+        &[14, 8, 7, 6, 13],
+        &[14],
+        &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[14, 8, 7, 6, 5, 4, 12, 16],
+        &[14, 8, 7, 6, 13, 17],
+        &[],
+        &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[14, 8, 7, 6, 5, 4, 12, 16, 20],
+        &[14, 8, 7, 6, 13, 17, 21],
+        &[22],
+        &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[14, 8, 7, 6, 5, 4, 12, 16, 20, 24],
+        &[14, 8, 7, 6, 13, 17, 21, 25],
+        &[22, 26],
+    ],
+    &[
+        &[15, 11, 2, 1, 0],
+        &[15, 11, 2, 1],
+        &[15, 11, 2],
+        &[15, 11, 2, 3],
+        &[15, 11, 2, 3, 4],
+        &[15, 11, 2, 3, 4, 5],
+        &[15, 11, 2, 3, 4, 5, 6],
+        &[15, 11, 2, 3, 4, 5, 6, 7],
+        &[15, 11, 2, 3, 4, 5, 6, 7, 8],
+        &[15, 11, 2, 3, 4, 5, 6, 7, 8, 9],
+        &[15, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[15, 11],
+        &[15, 11, 2, 3, 4, 12],
+        &[15, 11, 2, 3, 4, 5, 6, 13],
+        &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14],
+        &[15],
+        &[15, 11, 2, 3, 4, 12, 16],
+        &[15, 11, 2, 3, 4, 5, 6, 13, 17],
+        &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18],
+        &[],
+        &[15, 11, 2, 3, 4, 12, 16, 20],
+        &[15, 11, 2, 3, 4, 5, 6, 13, 17, 21],
+        &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[23],
+        &[15, 11, 2, 3, 4, 12, 16, 20, 24],
+        &[15, 11, 2, 3, 4, 5, 6, 13, 17, 21, 25],
+        &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[16, 12, 4, 3, 2, 1, 0],
+        &[16, 12, 4, 3, 2, 1],
+        &[16, 12, 4, 3, 2],
+        &[16, 12, 4, 3],
+        &[16, 12, 4],
+        &[16, 12, 4, 5],
+        &[16, 12, 4, 5, 6],
+        &[16, 12, 4, 5, 6, 7],
+        &[16, 12, 4, 5, 6, 7, 8],
+        &[16, 12, 4, 5, 6, 7, 8, 9],
+        &[16, 12, 4, 5, 6, 7, 8, 9, 10],
+        &[16, 12, 4, 3, 2, 11],
+        &[16, 12],
+        &[16, 12, 4, 5, 6, 13],
+        &[16, 12, 4, 5, 6, 7, 8, 14],
+        &[16, 12, 4, 3, 2, 11, 15],
+        &[16],
+        &[16, 12, 4, 5, 6, 13, 17],
+        &[16, 12, 4, 5, 6, 7, 8, 14, 18],
+        &[16, 12, 4, 3, 2, 11, 15, 19],
+        &[],
+        &[16, 12, 4, 5, 6, 13, 17, 21],
+        &[16, 12, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[16, 12, 4, 3, 2, 11, 15, 19, 23],
+        &[24],
+        &[16, 12, 4, 5, 6, 13, 17, 21, 25],
+        &[16, 12, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[17, 13, 6, 5, 4, 3, 2, 1, 0],
+        &[17, 13, 6, 5, 4, 3, 2, 1],
+        &[17, 13, 6, 5, 4, 3, 2],
+        &[17, 13, 6, 5, 4, 3],
+        &[17, 13, 6, 5, 4],
+        &[17, 13, 6, 5],
+        &[17, 13, 6],
+        &[17, 13, 6, 7],
+        &[17, 13, 6, 7, 8],
+        &[17, 13, 6, 7, 8, 9],
+        &[17, 13, 6, 7, 8, 9, 10],
+        &[17, 13, 6, 5, 4, 3, 2, 11],
+        &[17, 13, 6, 5, 4, 12],
+        &[17, 13],
+        &[17, 13, 6, 7, 8, 14],
+        &[17, 13, 6, 5, 4, 3, 2, 11, 15],
+        &[17, 13, 6, 5, 4, 12, 16],
+        &[17],
+        &[17, 13, 6, 7, 8, 14, 18],
+        &[17, 13, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[17, 13, 6, 5, 4, 12, 16, 20],
+        &[],
+        &[17, 13, 6, 7, 8, 14, 18, 22],
+        &[17, 13, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[17, 13, 6, 5, 4, 12, 16, 20, 24],
+        &[25],
+        &[17, 13, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[18, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[18, 14, 8, 7, 6, 5, 4, 3, 2, 1],
+        &[18, 14, 8, 7, 6, 5, 4, 3, 2],
+        &[18, 14, 8, 7, 6, 5, 4, 3],
+        &[18, 14, 8, 7, 6, 5, 4],
+        &[18, 14, 8, 7, 6, 5],
+        &[18, 14, 8, 7, 6],
+        &[18, 14, 8, 7],
+        &[18, 14, 8],
+        &[18, 14, 8, 9],
+        &[18, 14, 8, 9, 10],
+        &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11],
+        &[18, 14, 8, 7, 6, 5, 4, 12],
+        &[18, 14, 8, 7, 6, 13],
+        &[18, 14],
+        &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[18, 14, 8, 7, 6, 5, 4, 12, 16],
+        &[18, 14, 8, 7, 6, 13, 17],
+        &[18],
+        &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[18, 14, 8, 7, 6, 5, 4, 12, 16, 20],
+        &[18, 14, 8, 7, 6, 13, 17, 21],
+        &[],
+        &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[18, 14, 8, 7, 6, 5, 4, 12, 16, 20, 24],
+        &[18, 14, 8, 7, 6, 13, 17, 21, 25],
+        &[26],
+    ],
+    &[
+        &[19, 15, 11, 2, 1, 0],
+        &[19, 15, 11, 2, 1],
+        &[19, 15, 11, 2],
+        &[19, 15, 11, 2, 3],
+        &[19, 15, 11, 2, 3, 4],
+        &[19, 15, 11, 2, 3, 4, 5],
+        &[19, 15, 11, 2, 3, 4, 5, 6],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 7],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 9],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+        &[19, 15, 11],
+        &[19, 15, 11, 2, 3, 4, 12],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 13],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14],
+        &[19, 15],
+        &[19, 15, 11, 2, 3, 4, 12, 16],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18],
+        &[19],
+        &[19, 15, 11, 2, 3, 4, 12, 16, 20],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17, 21],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[],
+        &[19, 15, 11, 2, 3, 4, 12, 16, 20, 24],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17, 21, 25],
+        &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[20, 16, 12, 4, 3, 2, 1, 0],
+        &[20, 16, 12, 4, 3, 2, 1],
+        &[20, 16, 12, 4, 3, 2],
+        &[20, 16, 12, 4, 3],
+        &[20, 16, 12, 4],
+        &[20, 16, 12, 4, 5],
+        &[20, 16, 12, 4, 5, 6],
+        &[20, 16, 12, 4, 5, 6, 7],
+        &[20, 16, 12, 4, 5, 6, 7, 8],
+        &[20, 16, 12, 4, 5, 6, 7, 8, 9],
+        &[20, 16, 12, 4, 5, 6, 7, 8, 9, 10],
+        &[20, 16, 12, 4, 3, 2, 11],
+        &[20, 16, 12],
+        &[20, 16, 12, 4, 5, 6, 13],
+        &[20, 16, 12, 4, 5, 6, 7, 8, 14],
+        &[20, 16, 12, 4, 3, 2, 11, 15],
+        &[20, 16],
+        &[20, 16, 12, 4, 5, 6, 13, 17],
+        &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18],
+        &[20, 16, 12, 4, 3, 2, 11, 15, 19],
+        &[20],
+        &[20, 16, 12, 4, 5, 6, 13, 17, 21],
+        &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18, 22],
+        &[20, 16, 12, 4, 3, 2, 11, 15, 19, 23],
+        &[],
+        &[20, 16, 12, 4, 5, 6, 13, 17, 21, 25],
+        &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[21, 17, 13, 6, 5, 4, 3, 2, 1, 0],
+        &[21, 17, 13, 6, 5, 4, 3, 2, 1],
+        &[21, 17, 13, 6, 5, 4, 3, 2],
+        &[21, 17, 13, 6, 5, 4, 3],
+        &[21, 17, 13, 6, 5, 4],
+        &[21, 17, 13, 6, 5],
+        &[21, 17, 13, 6],
+        &[21, 17, 13, 6, 7],
+        &[21, 17, 13, 6, 7, 8],
+        &[21, 17, 13, 6, 7, 8, 9],
+        &[21, 17, 13, 6, 7, 8, 9, 10],
+        &[21, 17, 13, 6, 5, 4, 3, 2, 11],
+        &[21, 17, 13, 6, 5, 4, 12],
+        &[21, 17, 13],
+        &[21, 17, 13, 6, 7, 8, 14],
+        &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15],
+        &[21, 17, 13, 6, 5, 4, 12, 16],
+        &[21, 17],
+        &[21, 17, 13, 6, 7, 8, 14, 18],
+        &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[21, 17, 13, 6, 5, 4, 12, 16, 20],
+        &[21],
+        &[21, 17, 13, 6, 7, 8, 14, 18, 22],
+        &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[21, 17, 13, 6, 5, 4, 12, 16, 20, 24],
+        &[],
+        &[21, 17, 13, 6, 7, 8, 14, 18, 22, 26],
+    ],
+    &[
+        &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 1],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 3],
+        &[22, 18, 14, 8, 7, 6, 5, 4],
+        &[22, 18, 14, 8, 7, 6, 5],
+        &[22, 18, 14, 8, 7, 6],
+        &[22, 18, 14, 8, 7],
+        &[22, 18, 14, 8],
+        &[22, 18, 14, 8, 9],
+        &[22, 18, 14, 8, 9, 10],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 12],
+        &[22, 18, 14, 8, 7, 6, 13],
+        &[22, 18, 14],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16],
+        &[22, 18, 14, 8, 7, 6, 13, 17],
+        &[22, 18],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16, 20],
+        &[22, 18, 14, 8, 7, 6, 13, 17, 21],
+        &[22],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23],
+        &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16, 20, 24],
+        &[22, 18, 14, 8, 7, 6, 13, 17, 21, 25],
+        &[],
+    ],
+];
+
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
+enum Amphipod {
+    A,
+    B,
+    C,
+    D,
+}
+use Amphipod::*;
+
+impl Amphipod {
+    fn step_cost(&self) -> u64 {
+        match self {
+            A => 1,
+            B => 10,
+            C => 100,
+            D => 1000,
+        }
+    }
+}
+
+impl std::str::FromStr for Amphipod {
+    type Err = anyhow::Error;
+    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
+        match s {
+            "A" => Ok(A),
+            "B" => Ok(B),
+            "C" => Ok(C),
+            "D" => Ok(D),
+            _ => Err(anyhow::anyhow!(s.to_string())),
+        }
+    }
+}
+
+impl std::fmt::Display for Amphipod {
+    fn fmt(
+        &self,
+        f: &mut std::fmt::Formatter<'_>,
+    ) -> std::result::Result<(), std::fmt::Error> {
+        match self {
+            A => write!(f, "A"),
+            B => write!(f, "B"),
+            C => write!(f, "C"),
+            D => write!(f, "D"),
+        }
+    }
+}
+
+// #############
+// #abcdefghijk#
+// ###l#m#n#o###
+//   #p#q#r#s#
+//   #########
+#[derive(Debug, Clone, Copy, Default, Hash, PartialEq, Eq)]
+pub struct Burrow {
+    spaces: [Option<Amphipod>; 27],
+    big: bool,
+}
+
+impl Burrow {
+    fn to_big(self) -> Self {
+        let mut big = self;
+
+        big.spaces[23] = self.spaces[15];
+        big.spaces[24] = self.spaces[16];
+        big.spaces[25] = self.spaces[17];
+        big.spaces[26] = self.spaces[18];
+
+        big.spaces[15] = Some(D);
+        big.spaces[16] = Some(C);
+        big.spaces[17] = Some(B);
+        big.spaces[18] = Some(A);
+        big.spaces[19] = Some(D);
+        big.spaces[20] = Some(B);
+        big.spaces[21] = Some(A);
+        big.spaces[22] = Some(C);
+
+        big.big = true;
+
+        big
+    }
+
+    fn path(&self, from: usize, to: usize) -> &[usize] {
+        if self.big {
+            CONNECTIVITY2[from][to]
+        } else {
+            CONNECTIVITY1[from][to]
+        }
+    }
+
+    fn done(big: bool) -> Self {
+        let mut done = Self::default();
+
+        done.spaces[11] = Some(A);
+        done.spaces[15] = Some(A);
+        done.spaces[12] = Some(B);
+        done.spaces[16] = Some(B);
+        done.spaces[13] = Some(C);
+        done.spaces[17] = Some(C);
+        done.spaces[14] = Some(D);
+        done.spaces[18] = Some(D);
+
+        if big {
+            done.spaces[19] = Some(A);
+            done.spaces[23] = Some(A);
+            done.spaces[20] = Some(B);
+            done.spaces[24] = Some(B);
+            done.spaces[21] = Some(C);
+            done.spaces[25] = Some(C);
+            done.spaces[22] = Some(D);
+            done.spaces[26] = Some(D);
+            done.big = true;
+        }
+
+        done
+    }
+
+    fn move_cost(&self, mv: Move) -> u64 {
+        self.spaces[mv.from].unwrap().step_cost()
+            * u64::try_from(self.path(mv.from, mv.to).len()).unwrap()
+    }
+
+    fn make_move(&self, mv: Move) -> Self {
+        let mut new = *self;
+        let a = new.spaces[mv.from].take().unwrap();
+        assert!(new.spaces[mv.to].is_none());
+        new.spaces[mv.to] = Some(a);
+        new
+    }
+
+    fn legal_moves(&self) -> Vec<Move> {
+        let mut ret = vec![];
+        let size = if self.big { 27 } else { 19 };
+        for (from, space) in self.spaces.iter().enumerate().take(size) {
+            if let Some(a) = space {
+                for to in 0..size {
+                    if self.can_move(*a, from, to) {
+                        ret.push(Move::new(from, to));
+                    }
+                }
+            }
+        }
+        ret
+    }
+
+    fn can_move(&self, a: Amphipod, from: usize, to: usize) -> bool {
+        if !self.big && (from >= 19 || to >= 19) {
+            return false;
+        }
+
+        // Amphipods will never stop on the space immediately outside any
+        // room.
+        if to == 2 || to == 4 || to == 6 || to == 8 {
+            return false;
+        }
+
+        // Amphipods will never move from the hallway into a room unless that
+        // room is their destination room and that room contains no amphipods
+        // which do not also have that room as their own destination.
+        match a {
+            A => {
+                if to == 12
+                    || to == 13
+                    || to == 14
+                    || to == 16
+                    || to == 17
+                    || to == 18
+                    || to == 20
+                    || to == 21
+                    || to == 22
+                    || to == 24
+                    || to == 25
+                    || to == 26
+                {
+                    return false;
+                }
+                if self.big {
+                    if to == 11
+                        && (self.spaces[15] != Some(A)
+                            || self.spaces[19] != Some(A)
+                            || self.spaces[23] != Some(A))
+                    {
+                        return false;
+                    }
+                    if to == 15
+                        && (self.spaces[19] != Some(A)
+                            || self.spaces[23] != Some(A))
+                    {
+                        return false;
+                    }
+                    if to == 19 && self.spaces[23] != Some(A) {
+                        return false;
+                    }
+                    if from == 23
+                        || (from == 19 && self.spaces[23] == Some(A))
+                        || (from == 15
+                            && self.spaces[23] == Some(A)
+                            && self.spaces[19] == Some(A))
+                        || (from == 11
+                            && self.spaces[23] == Some(A)
+                            && self.spaces[19] == Some(A)
+                            && self.spaces[15] == Some(A))
+                    {
+                        return false;
+                    }
+                } else {
+                    if to == 11 && self.spaces[15] != Some(A) {
+                        return false;
+                    }
+                    if from == 15
+                        || (from == 11 && self.spaces[15] == Some(A))
+                    {
+                        return false;
+                    }
+                }
+            }
+            B => {
+                if to == 11
+                    || to == 13
+                    || to == 14
+                    || to == 15
+                    || to == 17
+                    || to == 18
+                    || to == 19
+                    || to == 21
+                    || to == 22
+                    || to == 23
+                    || to == 25
+                    || to == 26
+                {
+                    return false;
+                }
+                if self.big {
+                    if to == 12
+                        && (self.spaces[16] != Some(B)
+                            || self.spaces[20] != Some(B)
+                            || self.spaces[24] != Some(B))
+                    {
+                        return false;
+                    }
+                    if to == 16
+                        && (self.spaces[20] != Some(B)
+                            || self.spaces[24] != Some(B))
+                    {
+                        return false;
+                    }
+                    if to == 20 && self.spaces[24] != Some(B) {
+                        return false;
+                    }
+                    if from == 24
+                        || (from == 20 && self.spaces[24] == Some(B))
+                        || (from == 16
+                            && self.spaces[24] == Some(B)
+                            && self.spaces[20] == Some(B))
+                        || (from == 12
+                            && self.spaces[24] == Some(B)
+                            && self.spaces[20] == Some(B)
+                            && self.spaces[16] == Some(B))
+                    {
+                        return false;
+                    }
+                } else {
+                    if to == 12 && self.spaces[16] != Some(B) {
+                        return false;
+                    }
+                    if from == 16
+                        || (from == 12 && self.spaces[16] == Some(B))
+                    {
+                        return false;
+                    }
+                }
+            }
+            C => {
+                if to == 11
+                    || to == 12
+                    || to == 14
+                    || to == 15
+                    || to == 16
+                    || to == 18
+                    || to == 19
+                    || to == 20
+                    || to == 22
+                    || to == 23
+                    || to == 24
+                    || to == 26
+                {
+                    return false;
+                }
+                if self.big {
+                    if to == 13
+                        && (self.spaces[17] != Some(C)
+                            || self.spaces[21] != Some(C)
+                            || self.spaces[25] != Some(C))
+                    {
+                        return false;
+                    }
+                    if to == 17
+                        && (self.spaces[21] != Some(C)
+                            || self.spaces[25] != Some(C))
+                    {
+                        return false;
+                    }
+                    if to == 21 && self.spaces[25] != Some(C) {
+                        return false;
+                    }
+                    if from == 25
+                        || (from == 21 && self.spaces[25] == Some(C))
+                        || (from == 17
+                            && self.spaces[25] == Some(C)
+                            && self.spaces[21] == Some(C))
+                        || (from == 13
+                            && self.spaces[25] == Some(C)
+                            && self.spaces[21] == Some(C)
+                            && self.spaces[17] == Some(C))
+                    {
+                        return false;
+                    }
+                } else {
+                    if to == 13 && self.spaces[17] != Some(C) {
+                        return false;
+                    }
+                    if from == 17
+                        || (from == 13 && self.spaces[17] == Some(C))
+                    {
+                        return false;
+                    }
+                }
+            }
+            D => {
+                if to == 11
+                    || to == 12
+                    || to == 13
+                    || to == 15
+                    || to == 16
+                    || to == 17
+                    || to == 19
+                    || to == 20
+                    || to == 21
+                    || to == 23
+                    || to == 24
+                    || to == 25
+                {
+                    return false;
+                }
+                if self.big {
+                    if to == 14
+                        && (self.spaces[18] != Some(D)
+                            || self.spaces[22] != Some(D)
+                            || self.spaces[26] != Some(D))
+                    {
+                        return false;
+                    }
+                    if to == 18
+                        && (self.spaces[22] != Some(D)
+                            || self.spaces[26] != Some(D))
+                    {
+                        return false;
+                    }
+                    if to == 22 && self.spaces[26] != Some(D) {
+                        return false;
+                    }
+                    if from == 26
+                        || (from == 22 && self.spaces[26] == Some(D))
+                        || (from == 18
+                            && self.spaces[26] == Some(D)
+                            && self.spaces[22] == Some(D))
+                        || (from == 14
+                            && self.spaces[26] == Some(D)
+                            && self.spaces[22] == Some(D)
+                            && self.spaces[18] == Some(D))
+                    {
+                        return false;
+                    }
+                } else {
+                    if to == 14 && self.spaces[18] != Some(D) {
+                        return false;
+                    }
+                    if from == 18
+                        || (from == 14 && self.spaces[18] == Some(D))
+                    {
+                        return false;
+                    }
+                }
+            }
+        }
+
+        // Once an amphipod stops moving in the hallway, it will stay in that
+        // spot until it can move into a room.
+        if from < 11 && to < 11 {
+            return false;
+        }
+
+        // not actually a move
+        if from == to {
+            return false;
+        }
+
+        // we don't have an unblocked path
+        for space in self.path(from, to) {
+            if self.spaces[*space].is_some() {
+                return false;
+            }
+        }
+
+        true
+    }
+}
+
+impl std::fmt::Display for Burrow {
+    fn fmt(
+        &self,
+        f: &mut std::fmt::Formatter<'_>,
+    ) -> std::result::Result<(), std::fmt::Error> {
+        writeln!(f, "#############")?;
+
+        write!(f, "#")?;
+        for i in 0..11 {
+            if let Some(a) = &self.spaces[i] {
+                write!(f, "{}", a)?;
+            } else {
+                write!(f, ".")?;
+            }
+        }
+        writeln!(f, "#")?;
+
+        write!(f, "###")?;
+        for i in 11..15 {
+            if let Some(a) = &self.spaces[i] {
+                write!(f, "{}#", a)?;
+            } else {
+                write!(f, ".#")?;
+            }
+        }
+        writeln!(f, "##")?;
+
+        write!(f, "  #")?;
+        for i in 15..19 {
+            if let Some(a) = &self.spaces[i] {
+                write!(f, "{}#", a)?;
+            } else {
+                write!(f, ".#")?;
+            }
+        }
+        writeln!(f)?;
+
+        if self.big {
+            write!(f, "  #")?;
+            for i in 19..23 {
+                if let Some(a) = &self.spaces[i] {
+                    write!(f, "{}#", a)?;
+                } else {
+                    write!(f, ".#")?;
+                }
+            }
+            writeln!(f)?;
+            write!(f, "  #")?;
+            for i in 23..27 {
+                if let Some(a) = &self.spaces[i] {
+                    write!(f, "{}#", a)?;
+                } else {
+                    write!(f, ".#")?;
+                }
+            }
+            writeln!(f)?;
+        }
+
+        write!(f, "  #########")?;
+
+        Ok(())
+    }
+}
+
+#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
+struct Move {
+    from: usize,
+    to: usize,
+}
+
+impl Move {
+    fn new(from: usize, to: usize) -> Self {
+        Self { from, to }
+    }
+}
+
+struct Pathfinder;
+
+impl advent_of_code::graph::Graph<Burrow, Move> for Pathfinder {
+    type Edges = Vec<Move>;
+
+    fn edges(&self, v: Burrow) -> Self::Edges {
+        v.legal_moves()
+    }
+
+    fn edge(&self, v: Burrow, e: Move) -> (Burrow, u64) {
+        (v.make_move(e), v.move_cost(e))
+    }
+}
+
+pub fn parse(fh: File) -> Result<Burrow> {
+    let mut burrow = Burrow::default();
+    let lines: Vec<_> = parse::raw_lines(fh).collect();
+
+    let captures =
+        regex_captures!(r"###(.)#(.)#(.)#(.)###", &lines[2]).unwrap();
+    burrow.spaces[11] = Some(captures[1].parse()?);
+    burrow.spaces[12] = Some(captures[2].parse()?);
+    burrow.spaces[13] = Some(captures[3].parse()?);
+    burrow.spaces[14] = Some(captures[4].parse()?);
+
+    let captures =
+        regex_captures!(r"  #(.)#(.)#(.)#(.)#", &lines[3]).unwrap();
+    burrow.spaces[15] = Some(captures[1].parse()?);
+    burrow.spaces[16] = Some(captures[2].parse()?);
+    burrow.spaces[17] = Some(captures[3].parse()?);
+    burrow.spaces[18] = Some(captures[4].parse()?);
+
+    Ok(burrow)
+}
+
+pub fn part1(burrow: Burrow) -> Result<u64> {
+    let (cost, _path) = Pathfinder.dijkstra(burrow, Burrow::done(false));
+    // for burrow in path {
+    //     eprintln!("{}", burrow);
+    // }
+    Ok(cost)
+}
+
+pub fn part2(burrow: Burrow) -> Result<u64> {
+    let (cost, _path) =
+        Pathfinder.dijkstra(burrow.to_big(), Burrow::done(true));
+    // for burrow in path {
+    //     eprintln!("{}", burrow);
+    // }
+    Ok(cost)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 23).unwrap()).unwrap()).unwrap(),
+        10607
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 23).unwrap()).unwrap()).unwrap(),
+        59071
+    );
+}
diff --git a/src/bin/2021/day24.rs b/src/bin/2021/day24.rs
new file mode 100644
index 0000000..54788ec
--- /dev/null
+++ b/src/bin/2021/day24.rs
@@ -0,0 +1,337 @@
+use advent_of_code::prelude::*;
+
+#[derive(Debug, Clone, Copy)]
+pub enum Op {
+    Inp(Register),
+    Add(Register, Value),
+    Mul(Register, Value),
+    Div(Register, Value),
+    Mod(Register, Value),
+    Eql(Register, Value),
+}
+
+#[derive(Debug, Clone, Copy)]
+pub enum Register {
+    W,
+    X,
+    Y,
+    Z,
+}
+use Register::*;
+
+impl Register {
+    fn lvalue<'a>(&self, alu: &'a mut Alu) -> &'a mut i64 {
+        match self {
+            W => &mut alu.w,
+            X => &mut alu.x,
+            Y => &mut alu.y,
+            Z => &mut alu.z,
+        }
+    }
+
+    fn rvalue(&self, alu: &Alu) -> i64 {
+        match self {
+            W => alu.w,
+            X => alu.x,
+            Y => alu.y,
+            Z => alu.z,
+        }
+    }
+}
+
+impl std::str::FromStr for Register {
+    type Err = anyhow::Error;
+    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
+        match s {
+            "w" => Ok(W),
+            "x" => Ok(X),
+            "y" => Ok(Y),
+            "z" => Ok(Z),
+            _ => Err(anyhow::anyhow!(s.to_string())),
+        }
+    }
+}
+
+#[derive(Debug, Clone, Copy)]
+pub enum Value {
+    Register(Register),
+    Number(i64),
+}
+
+impl Value {
+    fn rvalue(&self, alu: &Alu) -> i64 {
+        match self {
+            Self::Register(r) => r.rvalue(alu),
+            Self::Number(n) => *n,
+        }
+    }
+}
+
+impl std::str::FromStr for Value {
+    type Err = anyhow::Error;
+    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
+        match s {
+            "w" => Ok(Self::Register(W)),
+            "x" => Ok(Self::Register(X)),
+            "y" => Ok(Self::Register(Y)),
+            "z" => Ok(Self::Register(Z)),
+            _ => Ok(Self::Number(s.parse()?)),
+        }
+    }
+}
+
+#[derive(Debug)]
+pub struct Alu {
+    w: i64,
+    x: i64,
+    y: i64,
+    z: i64,
+}
+
+impl Alu {
+    fn new() -> Self {
+        Self {
+            w: 0,
+            x: 0,
+            y: 0,
+            z: 0,
+        }
+    }
+
+    fn run(&mut self, ops: impl IntoIterator<Item = Op>, inp: i64) {
+        self.inp(W, Value::Number(inp));
+        for op in ops {
+            match op {
+                Op::Inp(_) => {
+                    break;
+                }
+                Op::Add(a, b) => {
+                    self.add(a, b);
+                }
+                Op::Mul(a, b) => {
+                    self.mul(a, b);
+                }
+                Op::Div(a, b) => {
+                    self.div(a, b);
+                }
+                Op::Mod(a, b) => {
+                    self.modulo(a, b);
+                }
+                Op::Eql(a, b) => {
+                    self.eql(a, b);
+                }
+            }
+        }
+    }
+
+    fn inp(&mut self, a: Register, b: Value) {
+        *a.lvalue(self) = b.rvalue(self)
+    }
+
+    fn add(&mut self, a: Register, b: Value) {
+        *a.lvalue(self) += b.rvalue(self);
+    }
+
+    fn mul(&mut self, a: Register, b: Value) {
+        *a.lvalue(self) *= b.rvalue(self);
+    }
+
+    fn div(&mut self, a: Register, b: Value) {
+        *a.lvalue(self) /= b.rvalue(self);
+    }
+
+    fn modulo(&mut self, a: Register, b: Value) {
+        *a.lvalue(self) %= b.rvalue(self);
+    }
+
+    fn eql(&mut self, a: Register, b: Value) {
+        *a.lvalue(self) = i64::from(a.rvalue(self) == b.rvalue(self));
+    }
+}
+
+impl std::fmt::Display for Alu {
+    fn fmt(
+        &self,
+        f: &mut std::fmt::Formatter<'_>,
+    ) -> std::result::Result<(), std::fmt::Error> {
+        writeln!(f, "Alu {{")?;
+        writeln!(f, "    w: {}", self.w)?;
+        writeln!(f, "    x: {}", self.x)?;
+        writeln!(f, "    y: {}", self.y)?;
+        writeln!(f, "    z: {}", self.z)?;
+        write!(f, "}}")?;
+        Ok(())
+    }
+}
+
+fn step(
+    alu: &mut Alu,
+    ops: &mut impl Iterator<Item = Op>,
+    val: &mut i64,
+    inp: i64,
+) -> bool {
+    if !(1..=9).contains(&inp) {
+        return false;
+    }
+    *val *= 10;
+    *val += inp;
+    alu.run(ops, inp);
+    true
+}
+
+fn run(inp: &[i64], ops: &[Op]) -> Option<i64> {
+    let mut val = 0;
+    let mut alu = Alu::new();
+    let mut ops = ops.iter().copied().skip(1);
+    let mut ops = ops.by_ref();
+
+    if !step(&mut alu, &mut ops, &mut val, inp[0]) {
+        return None;
+    }
+    if !step(&mut alu, &mut ops, &mut val, inp[1]) {
+        return None;
+    }
+    if !step(&mut alu, &mut ops, &mut val, inp[2]) {
+        return None;
+    }
+    let z = alu.z;
+    if !step(&mut alu, &mut ops, &mut val, (z % 26) - 6) {
+        return None;
+    }
+    if !step(&mut alu, &mut ops, &mut val, inp[3]) {
+        return None;
+    }
+    let z = alu.z;
+    if !step(&mut alu, &mut ops, &mut val, (z % 26) - 4) {
+        return None;
+    }
+    if !step(&mut alu, &mut ops, &mut val, inp[4]) {
+        return None;
+    }
+    if !step(&mut alu, &mut ops, &mut val, inp[5]) {
+        return None;
+    }
+    if !step(&mut alu, &mut ops, &mut val, inp[6]) {
+        return None;
+    }
+    let z = alu.z;
+    if !step(&mut alu, &mut ops, &mut val, z % 26) {
+        return None;
+    }
+    let z = alu.z;
+    if !step(&mut alu, &mut ops, &mut val, z % 26) {
+        return None;
+    }
+    let z = alu.z;
+    if !step(&mut alu, &mut ops, &mut val, (z % 26) - 3) {
+        return None;
+    }
+    let z = alu.z;
+    if !step(&mut alu, &mut ops, &mut val, (z % 26) - 9) {
+        return None;
+    }
+    let z = alu.z;
+    if !step(&mut alu, &mut ops, &mut val, (z % 26) - 9) {
+        return None;
+    }
+
+    if alu.z == 0 {
+        Some(val)
+    } else {
+        None
+    }
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Op>> {
+    Ok(parse::raw_lines(fh).map(|line| {
+        let captures = regex_captures!(
+            r"(inp|add|mul|div|mod|eql) ([wxyz])(?: ([wxyz]|-?\d+))?",
+            &line
+        )
+        .unwrap();
+        match &captures[1] {
+            "inp" => Op::Inp(captures[2].parse().unwrap()),
+            "add" => Op::Add(
+                captures[2].parse().unwrap(),
+                captures[3].parse().unwrap(),
+            ),
+            "mul" => Op::Mul(
+                captures[2].parse().unwrap(),
+                captures[3].parse().unwrap(),
+            ),
+            "div" => Op::Div(
+                captures[2].parse().unwrap(),
+                captures[3].parse().unwrap(),
+            ),
+            "mod" => Op::Mod(
+                captures[2].parse().unwrap(),
+                captures[3].parse().unwrap(),
+            ),
+            "eql" => Op::Eql(
+                captures[2].parse().unwrap(),
+                captures[3].parse().unwrap(),
+            ),
+            _ => panic!("unknown opcode: {}", &captures[1]),
+        }
+    }))
+}
+
+pub fn part1(ops: impl Iterator<Item = Op>) -> Result<i64> {
+    let ops: Vec<_> = ops.collect();
+    for d1 in (1..=9).rev() {
+        for d2 in (1..=9).rev() {
+            for d3 in (1..=9).rev() {
+                for d5 in (1..=9).rev() {
+                    for d7 in (1..=9).rev() {
+                        for d8 in (1..=9).rev() {
+                            for d9 in (1..=9).rev() {
+                                let inp = &[d1, d2, d3, d5, d7, d8, d9];
+                                let ret = run(inp, &ops);
+                                if let Some(n) = ret {
+                                    return Ok(n);
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+    panic!("not found");
+}
+
+pub fn part2(ops: impl Iterator<Item = Op>) -> Result<i64> {
+    let ops: Vec<_> = ops.collect();
+    for d1 in 1..=9 {
+        for d2 in 1..=9 {
+            for d3 in 1..=9 {
+                for d5 in 1..=9 {
+                    for d7 in 1..=9 {
+                        for d8 in 1..=9 {
+                            for d9 in 1..=9 {
+                                let inp = &[d1, d2, d3, d5, d7, d8, d9];
+                                let ret = run(inp, &ops);
+                                if let Some(n) = ret {
+                                    return Ok(n);
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+    panic!("not found");
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 24).unwrap()).unwrap()).unwrap(),
+        99299513899971
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 24).unwrap()).unwrap()).unwrap(),
+        93185111127911
+    );
+}
diff --git a/src/bin/2021/day25.rs b/src/bin/2021/day25.rs
new file mode 100644
index 0000000..ed396c6
--- /dev/null
+++ b/src/bin/2021/day25.rs
@@ -0,0 +1,96 @@
+use advent_of_code::prelude::*;
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub enum Cell {
+    Down,
+    Right,
+    None,
+}
+
+impl Default for Cell {
+    fn default() -> Self {
+        Self::None
+    }
+}
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct Map {
+    grid: Grid<Cell>,
+}
+
+impl Map {
+    fn step(&self) -> Self {
+        self.step_east().step_south()
+    }
+
+    fn step_east(&self) -> Self {
+        let mut step = self.clone();
+        for ((Row(row), Col(col)), cell) in self.grid.indexed_cells() {
+            if *cell == Cell::Right {
+                let mut next = col + 1;
+                if next >= self.grid.cols().0 {
+                    next = 0;
+                }
+                if self.grid[Row(row)][Col(next)] == Cell::None {
+                    step.grid[Row(row)][Col(next)] = Cell::Right;
+                    step.grid[Row(row)][Col(col)] = Cell::None;
+                }
+            }
+        }
+        step
+    }
+
+    fn step_south(&self) -> Self {
+        let mut step = self.clone();
+        for ((Row(row), Col(col)), cell) in self.grid.indexed_cells() {
+            if *cell == Cell::Down {
+                let mut next = row + 1;
+                if next >= self.grid.rows().0 {
+                    next = 0;
+                }
+                if self.grid[Row(next)][Col(col)] == Cell::None {
+                    step.grid[Row(next)][Col(col)] = Cell::Down;
+                    step.grid[Row(row)][Col(col)] = Cell::None;
+                }
+            }
+        }
+        step
+    }
+}
+
+pub fn parse(fh: File) -> Result<Map> {
+    Ok(Map {
+        grid: parse::grid(parse::raw_lines(fh), |b| match b {
+            b'v' => Cell::Down,
+            b'>' => Cell::Right,
+            b'.' => Cell::None,
+            _ => panic!("unknown cell {}", b),
+        }),
+    })
+}
+
+pub fn part1(map: Map) -> Result<u64> {
+    let mut prev = map;
+    let mut i = 0;
+    loop {
+        i += 1;
+        let next = prev.step();
+        if next == prev {
+            break;
+        }
+        prev = next;
+    }
+    Ok(i)
+}
+
+pub fn part2(_: Map) -> Result<i64> {
+    todo!()
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 25).unwrap()).unwrap()).unwrap(),
+        482
+    );
+}
diff --git a/src/bin/2021/day3.rs b/src/bin/2021/day3.rs
new file mode 100644
index 0000000..70a3085
--- /dev/null
+++ b/src/bin/2021/day3.rs
@@ -0,0 +1,102 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = String>> {
+    Ok(parse::raw_lines(fh))
+}
+
+pub fn part1(lines: impl Iterator<Item = String>) -> Result<u64> {
+    let (total_lines, by_pos) = pos_counts(lines)?;
+    let gamma: String = by_pos
+        .iter()
+        .map(|pos| if pos * 2 >= total_lines { '1' } else { '0' })
+        .collect();
+    let epsilon: String = by_pos
+        .iter()
+        .map(|pos| if pos * 2 >= total_lines { '0' } else { '1' })
+        .collect();
+    Ok(bin_str_to_int(&gamma) * bin_str_to_int(&epsilon))
+}
+
+pub fn part2(lines: impl Iterator<Item = String>) -> Result<u64> {
+    let mut oxygen: Vec<_> = lines.collect();
+    let mut co2 = oxygen.clone();
+
+    for i in 0..oxygen[0].len() {
+        if oxygen.len() == 1 {
+            break;
+        }
+        let (total_lines, by_pos) = pos_counts(oxygen.iter().cloned())?;
+        let keep = if by_pos[i] * 2 >= total_lines {
+            '1'
+        } else {
+            '0'
+        };
+        let new_oxygen = oxygen
+            .iter()
+            .filter(|l| l.chars().nth(i).unwrap() == keep)
+            .cloned()
+            .collect();
+        oxygen = new_oxygen;
+    }
+
+    for i in 0..co2[0].len() {
+        if co2.len() == 1 {
+            break;
+        }
+        let (total_lines, by_pos) = pos_counts(co2.iter().cloned())?;
+        let keep = if by_pos[i] * 2 >= total_lines {
+            '0'
+        } else {
+            '1'
+        };
+        let new_co2 = co2
+            .iter()
+            .filter(|l| l.chars().nth(i).unwrap() == keep)
+            .cloned()
+            .collect();
+        co2 = new_co2;
+    }
+
+    Ok(bin_str_to_int(&oxygen[0]) * bin_str_to_int(&co2[0]))
+}
+
+fn pos_counts(
+    lines: impl Iterator<Item = String>,
+) -> Result<(i64, Vec<i64>)> {
+    let mut by_pos = vec![];
+    let mut total_lines = 0;
+    for line in lines {
+        total_lines += 1;
+        if by_pos.is_empty() {
+            by_pos.resize(line.len(), 0);
+        }
+        for (i, c) in line.chars().enumerate() {
+            if c == '1' {
+                by_pos[i] += 1;
+            }
+        }
+    }
+    Ok((total_lines, by_pos))
+}
+
+fn bin_str_to_int(s: &str) -> u64 {
+    let mut ret = 0;
+    for (i, c) in s.chars().rev().enumerate() {
+        if c == '1' {
+            ret += 2u64.pow(i.try_into().unwrap());
+        }
+    }
+    ret
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 3).unwrap()).unwrap()).unwrap(),
+        3009600
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 3).unwrap()).unwrap()).unwrap(),
+        6940518
+    );
+}
diff --git a/src/bin/2021/day4.rs b/src/bin/2021/day4.rs
new file mode 100644
index 0000000..f733078
--- /dev/null
+++ b/src/bin/2021/day4.rs
@@ -0,0 +1,167 @@
+use advent_of_code::prelude::*;
+
+#[derive(Debug)]
+struct Board {
+    numbers: Vec<u8>,
+    marked: Vec<bool>,
+}
+
+impl Board {
+    fn new(numbers: Vec<u8>) -> Self {
+        let len = numbers.len();
+        Self {
+            numbers,
+            marked: vec![false; len],
+        }
+    }
+
+    fn won(&self) -> bool {
+        let wins = [
+            [0, 1, 2, 3, 4],
+            [5, 6, 7, 8, 9],
+            [10, 11, 12, 13, 14],
+            [15, 16, 17, 18, 19],
+            [20, 21, 22, 23, 24],
+            [0, 5, 10, 15, 20],
+            [1, 6, 11, 16, 21],
+            [2, 7, 12, 17, 22],
+            [3, 8, 13, 18, 23],
+            [4, 9, 14, 19, 24],
+        ];
+        wins.iter().any(|win| win.iter().all(|i| self.marked[*i]))
+    }
+
+    fn mark(&mut self, called: u8) {
+        for (i, n) in self.numbers.iter().enumerate() {
+            if called == *n {
+                self.marked[i] = true;
+            }
+        }
+    }
+
+    fn value(&self) -> u64 {
+        self.marked
+            .iter()
+            .zip(self.numbers.iter())
+            .filter_map(
+                |(marked, n)| {
+                    if !*marked {
+                        Some(u64::from(*n))
+                    } else {
+                        None
+                    }
+                },
+            )
+            .sum()
+    }
+}
+
+#[derive(Debug)]
+pub struct Game {
+    inputs: Vec<u8>,
+    boards: Vec<Board>,
+}
+
+impl Game {
+    fn parse<T: std::io::Read>(input: T) -> Result<Self> {
+        let mut lines = parse::raw_lines(input).peekable();
+
+        let line = lines.next().ok_or_else(|| anyhow!("missing line"))?;
+        let inputs = line
+            .trim()
+            .split(',')
+            .map(|s| s.parse())
+            .collect::<Result<Vec<u8>, _>>()?;
+        lines.next();
+
+        let mut boards = vec![];
+        while lines.peek().is_some() {
+            let mut numbers = vec![];
+            for line in parse::chunk(&mut lines) {
+                numbers.extend(
+                    line.split_whitespace()
+                        .map(|s| s.parse())
+                        .collect::<Result<Vec<u8>, _>>()?,
+                );
+            }
+            boards.push(Board::new(numbers));
+        }
+
+        Ok(Self { inputs, boards })
+    }
+
+    fn find_first_winner(self) -> Option<(u8, Board)> {
+        let Self { inputs, mut boards } = self;
+        let mut won = None;
+        for n in inputs {
+            for (i, board) in boards.iter_mut().enumerate() {
+                board.mark(n);
+                if board.won() {
+                    won = Some((n, i));
+                    break;
+                }
+            }
+            if won.is_some() {
+                break;
+            }
+        }
+        won.map(|(n, i)| (n, boards.swap_remove(i)))
+    }
+
+    fn find_last_winner(self) -> Option<(u8, Board)> {
+        let Self { inputs, mut boards } = self;
+        let mut last_won = None;
+        for n in inputs {
+            let mut won = vec![];
+            for (i, board) in boards.iter_mut().enumerate() {
+                board.mark(n);
+                if board.won() {
+                    won.push(i);
+                }
+            }
+            if boards.len() == won.len() {
+                last_won = Some((n, won[0]));
+                break;
+            }
+            for i in won.into_iter().rev() {
+                boards.swap_remove(i);
+            }
+            if boards.is_empty() {
+                break;
+            }
+        }
+        last_won.map(|(n, i)| (n, boards.swap_remove(i)))
+    }
+}
+
+pub fn parse(fh: File) -> Result<Game> {
+    Game::parse(fh)
+}
+
+pub fn part1(game: Game) -> Result<u64> {
+    if let Some((n, board)) = game.find_first_winner() {
+        Ok(u64::from(n) * board.value())
+    } else {
+        bail!("couldn't find winner")
+    }
+}
+
+pub fn part2(game: Game) -> Result<u64> {
+    if let Some((n, board)) = game.find_last_winner() {
+        Ok(u64::from(n) * board.value())
+    } else {
+        bail!("couldn't find winner")
+    }
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 4).unwrap()).unwrap()).unwrap(),
+        2745
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 4).unwrap()).unwrap()).unwrap(),
+        6594
+    );
+}
diff --git a/src/bin/2021/day5.rs b/src/bin/2021/day5.rs
new file mode 100644
index 0000000..68bca56
--- /dev/null
+++ b/src/bin/2021/day5.rs
@@ -0,0 +1,123 @@
+use advent_of_code::prelude::*;
+
+#[derive(Default, Clone)]
+struct Map {
+    grid: Grid<i64>,
+}
+
+impl Map {
+    fn mark_horizontal(
+        &mut self,
+        x1: usize,
+        y1: usize,
+        x2: usize,
+        y2: usize,
+    ) -> bool {
+        self.grid
+            .grow(Row((y1 + 1).max(y2 + 1)), Col((x1 + 1).max(x2 + 1)));
+        if x1 == x2 {
+            for y in y1.min(y2)..=y1.max(y2) {
+                self.grid[Row(y)][Col(x1)] += 1;
+            }
+            true
+        } else {
+            false
+        }
+    }
+
+    fn mark_vertical(
+        &mut self,
+        x1: usize,
+        y1: usize,
+        x2: usize,
+        y2: usize,
+    ) -> bool {
+        self.grid
+            .grow(Row((y1 + 1).max(y2 + 1)), Col((x1 + 1).max(x2 + 1)));
+        if y1 == y2 {
+            for x in x1.min(x2)..=x1.max(x2) {
+                self.grid[Row(y1)][Col(x)] += 1;
+            }
+            true
+        } else {
+            false
+        }
+    }
+
+    fn mark_diagonal(
+        &mut self,
+        x1: usize,
+        y1: usize,
+        x2: usize,
+        y2: usize,
+    ) -> bool {
+        if x1.max(x2) - x1.min(x2) == y1.max(y2) - y1.min(y2) {
+            for i in 0..=(x1.max(x2) - x1.min(x2)) {
+                if x1 > x2 && y1 > y2 || x1 < x2 && y1 < y2 {
+                    self.grid[Row(y1.min(y2) + i)][Col(x1.min(x2) + i)] += 1;
+                } else if x1 > x2 {
+                    self.grid[Row(y2 - i)][Col(x2 + i)] += 1;
+                } else {
+                    self.grid[Row(y1 - i)][Col(x1 + i)] += 1;
+                }
+            }
+            true
+        } else {
+            false
+        }
+    }
+
+    fn count_overlapping(&self) -> usize {
+        self.grid.cells().filter(|x| **x >= 2).count()
+    }
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Vec<usize>>> {
+    Ok(parse::raw_lines(fh).map(move |line| {
+        regex_captures!(r"^(\d+),(\d+) -> (\d+),(\d+)$", &line)
+            .unwrap()
+            .iter()
+            .skip(1)
+            .map(|s| s.unwrap().as_str().parse())
+            .collect::<Result<_, _>>()
+            .unwrap()
+    }))
+}
+
+pub fn part1(coords: impl Iterator<Item = Vec<usize>>) -> Result<usize> {
+    let mut map = Map::default();
+    for nums in coords {
+        let _ = map.mark_horizontal(nums[0], nums[1], nums[2], nums[3])
+            || map.mark_vertical(nums[0], nums[1], nums[2], nums[3]);
+    }
+    Ok(map.count_overlapping())
+}
+
+pub fn part2(coords: impl Iterator<Item = Vec<usize>>) -> Result<usize> {
+    let mut map = Map::default();
+    for nums in coords {
+        if map.mark_horizontal(nums[0], nums[1], nums[2], nums[3]) {
+            continue;
+        }
+        if map.mark_vertical(nums[0], nums[1], nums[2], nums[3]) {
+            continue;
+        }
+        if map.mark_diagonal(nums[0], nums[1], nums[2], nums[3]) {
+            continue;
+        }
+        unreachable!();
+    }
+    Ok(map.count_overlapping())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 5).unwrap()).unwrap()).unwrap(),
+        6311
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 5).unwrap()).unwrap()).unwrap(),
+        19929
+    );
+}
diff --git a/src/bin/2021/day6.rs b/src/bin/2021/day6.rs
new file mode 100644
index 0000000..039209e
--- /dev/null
+++ b/src/bin/2021/day6.rs
@@ -0,0 +1,47 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<Vec<usize>> {
+    Ok(parse::split(fh, b',').collect())
+}
+
+pub fn part1(mut fishes: Vec<usize>) -> Result<usize> {
+    for _ in 0..80 {
+        let mut new = 0;
+        for fish in fishes.iter_mut() {
+            if *fish == 0 {
+                *fish = 6;
+                new += 1;
+            } else {
+                *fish -= 1;
+            }
+        }
+        fishes.resize(fishes.len() + new, 8);
+    }
+    Ok(fishes.len())
+}
+
+pub fn part2(fishes: Vec<usize>) -> Result<usize> {
+    let mut by_age = VecDeque::new();
+    by_age.resize(9, 0);
+    for fish in fishes {
+        by_age[fish] += 1;
+    }
+    for _ in 0..256 {
+        let new = by_age.pop_front().unwrap();
+        by_age[6] += new;
+        by_age.push_back(new);
+    }
+    Ok(by_age.iter().sum())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 6).unwrap()).unwrap()).unwrap(),
+        379114
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 6).unwrap()).unwrap()).unwrap(),
+        1702631502303
+    );
+}
diff --git a/src/bin/2021/day7.rs b/src/bin/2021/day7.rs
new file mode 100644
index 0000000..56eaeb1
--- /dev/null
+++ b/src/bin/2021/day7.rs
@@ -0,0 +1,42 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<Vec<usize>> {
+    Ok(parse::split(fh, b',').collect())
+}
+
+pub fn part1(crabs: Vec<usize>) -> Result<usize> {
+    Ok((0..=crabs.iter().copied().max().unwrap())
+        .map(|start| {
+            crabs.iter().copied().map(|crab| crab.abs_diff(start)).sum()
+        })
+        .min()
+        .unwrap())
+}
+
+pub fn part2(crabs: Vec<usize>) -> Result<usize> {
+    Ok((0..=crabs.iter().copied().max().unwrap())
+        .map(|start| {
+            crabs
+                .iter()
+                .copied()
+                .map(|crab| {
+                    let diff = crab.abs_diff(start);
+                    diff * (diff + 1) / 2
+                })
+                .sum()
+        })
+        .min()
+        .unwrap())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 7).unwrap()).unwrap()).unwrap(),
+        333755
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 7).unwrap()).unwrap()).unwrap(),
+        94017638
+    );
+}
diff --git a/src/bin/2021/day8.rs b/src/bin/2021/day8.rs
new file mode 100644
index 0000000..ca101ef
--- /dev/null
+++ b/src/bin/2021/day8.rs
@@ -0,0 +1,185 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(
+    fh: File,
+) -> Result<impl Iterator<Item = (Vec<String>, Vec<String>)>> {
+    Ok(parse::raw_lines(fh).map(|line| {
+        let parts: Vec<_> = line.split(" | ").collect();
+        (
+            parts[0].split(' ').map(str::to_string).collect(),
+            parts[1].split(' ').map(str::to_string).collect(),
+        )
+    }))
+}
+
+pub fn part1(
+    lines: impl Iterator<Item = (Vec<String>, Vec<String>)>,
+) -> Result<usize> {
+    let mut count = 0;
+    for (_, output) in lines {
+        let line_count = output
+            .iter()
+            .filter(|s| [2, 3, 4, 7].contains(&s.len()))
+            .count();
+        count += line_count;
+    }
+    Ok(count)
+}
+
+//  00
+// 1  2
+// 1  2
+//  33
+// 4  5
+// 4  5
+//  66
+pub fn part2(
+    lines: impl Iterator<Item = (Vec<String>, Vec<String>)>,
+) -> Result<usize> {
+    let mut total = 0;
+    for (numbers, output) in lines {
+        let mut segments = ['x'; 7];
+
+        // zero: 6
+        let one = numbers.iter().find(|s| s.len() == 2).unwrap();
+        let one: HashSet<char> = one.chars().collect();
+        // two: 5
+        // three: 5
+        let four = numbers.iter().find(|s| s.len() == 4).unwrap();
+        let four: HashSet<char> = four.chars().collect();
+        // five: 5
+        // six: 6
+        let seven = numbers.iter().find(|s| s.len() == 3).unwrap();
+        let seven: HashSet<char> = seven.chars().collect();
+        let eight = numbers.iter().find(|s| s.len() == 7).unwrap();
+        let eight: HashSet<char> = eight.chars().collect();
+        // nine: 6
+
+        let mut length_five: Vec<_> = numbers
+            .iter()
+            .filter_map(|s| {
+                if s.len() == 5 {
+                    Some(s.chars().collect::<HashSet<_>>())
+                } else {
+                    None
+                }
+            })
+            .collect();
+        let mut length_six: Vec<_> = numbers
+            .iter()
+            .filter_map(|s| {
+                if s.len() == 6 {
+                    Some(s.chars().collect::<HashSet<_>>())
+                } else {
+                    None
+                }
+            })
+            .collect();
+
+        let idx = length_five
+            .iter()
+            .position(|set| set.difference(&one).count() == 3)
+            .unwrap();
+        let three = length_five.swap_remove(idx);
+        let idx = length_five
+            .iter()
+            .position(|set| set.difference(&four).count() == 2)
+            .unwrap();
+        let five = length_five.swap_remove(idx);
+        let two = length_five.remove(0);
+
+        segments[0] = *seven.difference(&one).next().unwrap();
+        segments[6] = three
+            .iter()
+            .copied()
+            .find(|c| {
+                !one.contains(c) && !four.contains(c) && !seven.contains(c)
+            })
+            .unwrap();
+        segments[3] = three
+            .iter()
+            .copied()
+            .find(|c| {
+                !one.contains(c) && *c != segments[0] && *c != segments[6]
+            })
+            .unwrap();
+        segments[4] = two
+            .iter()
+            .copied()
+            .find(|c| {
+                !one.contains(c)
+                    && *c != segments[0]
+                    && *c != segments[3]
+                    && *c != segments[6]
+            })
+            .unwrap();
+        segments[2] = two
+            .iter()
+            .copied()
+            .find(|c| {
+                *c != segments[0]
+                    && *c != segments[3]
+                    && *c != segments[4]
+                    && *c != segments[6]
+            })
+            .unwrap();
+        segments[1] = four
+            .iter()
+            .copied()
+            .find(|c| !one.contains(c) && *c != segments[3])
+            .unwrap();
+        segments[5] = eight
+            .iter()
+            .copied()
+            .find(|c| {
+                *c != segments[0]
+                    && *c != segments[1]
+                    && *c != segments[2]
+                    && *c != segments[3]
+                    && *c != segments[4]
+                    && *c != segments[6]
+            })
+            .unwrap();
+
+        let idx = length_six
+            .iter()
+            .position(|set| !set.contains(&segments[3]))
+            .unwrap();
+        let zero = length_six.swap_remove(idx);
+        let idx = length_six
+            .iter()
+            .position(|set| !set.contains(&segments[2]))
+            .unwrap();
+        let six = length_six.swap_remove(idx);
+        let idx = length_six
+            .iter()
+            .position(|set| !set.contains(&segments[4]))
+            .unwrap();
+        let nine = length_six.swap_remove(idx);
+
+        let numbers =
+            [zero, one, two, three, four, five, six, seven, eight, nine];
+
+        let value: Vec<_> = output
+            .iter()
+            .map(|s| s.chars().collect::<HashSet<_>>())
+            .map(|set| numbers.iter().position(|num| &set == num).unwrap())
+            .collect();
+        let value =
+            value[0] * 1000 + value[1] * 100 + value[2] * 10 + value[3];
+        total += value;
+    }
+    Ok(total)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 8).unwrap()).unwrap()).unwrap(),
+        355
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 8).unwrap()).unwrap()).unwrap(),
+        983030
+    );
+}
diff --git a/src/bin/2021/day9.rs b/src/bin/2021/day9.rs
new file mode 100644
index 0000000..c0c1b47
--- /dev/null
+++ b/src/bin/2021/day9.rs
@@ -0,0 +1,71 @@
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<Grid<u8>> {
+    Ok(parse::digit_grid(parse::raw_lines(fh)))
+}
+
+pub fn part1(map: Grid<u8>) -> Result<u64> {
+    let mut risk = 0;
+    for ((row, col), pos) in map.indexed_cells() {
+        if map
+            .adjacent(row, col, false)
+            .map(|(row, col)| map[row][col])
+            .all(|n| *pos < n)
+        {
+            risk += 1 + u64::from(*pos);
+        }
+    }
+    Ok(risk)
+}
+
+pub fn part2(map: Grid<u8>) -> Result<u64> {
+    let mut low = vec![];
+    for ((row, col), pos) in map.indexed_cells() {
+        if map
+            .adjacent(row, col, false)
+            .map(|(row, col)| map[row][col])
+            .all(|n| *pos < n)
+        {
+            low.push((row, col));
+        }
+    }
+
+    let mut sizes = vec![];
+    for (row, col) in low {
+        let mut basin: Grid<bool> = Grid::default();
+        basin.grow(map.rows(), map.cols());
+        let mut check = vec![(row, col)];
+        let mut count = 0;
+        while let Some((row, col)) = check.pop() {
+            if basin[row][col] || map[row][col] == 9 {
+                continue;
+            }
+
+            basin[row][col] = true;
+            count += 1;
+
+            for (row, col) in basin.adjacent(row, col, false) {
+                if !basin[row][col] {
+                    check.push((row, col));
+                }
+            }
+        }
+        sizes.push(count);
+    }
+    sizes.sort_unstable();
+    Ok(sizes[sizes.len() - 1]
+        * sizes[sizes.len() - 2]
+        * sizes[sizes.len() - 3])
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2021, 9).unwrap()).unwrap()).unwrap(),
+        570
+    );
+    assert_eq!(
+        part2(parse(parse::data(2021, 9).unwrap()).unwrap()).unwrap(),
+        899392
+    );
+}
diff --git a/src/bin/2021/main.rs b/src/bin/2021/main.rs
new file mode 100644
index 0000000..1d571dc
--- /dev/null
+++ b/src/bin/2021/main.rs
@@ -0,0 +1,74 @@
+#![allow(clippy::cognitive_complexity)]
+#![allow(clippy::missing_const_for_fn)]
+#![allow(clippy::similar_names)]
+#![allow(clippy::struct_excessive_bools)]
+#![allow(clippy::too_many_arguments)]
+#![allow(clippy::too_many_lines)]
+#![allow(clippy::type_complexity)]
+#![allow(clippy::collapsible_else_if)]
+#![allow(clippy::collapsible_if)]
+#![allow(clippy::comparison_chain)]
+
+use advent_of_code::prelude::*;
+
+mod day1;
+mod day10;
+mod day11;
+mod day12;
+mod day13;
+mod day14;
+mod day15;
+mod day16;
+mod day17;
+mod day18;
+mod day19;
+mod day2;
+mod day20;
+mod day21;
+mod day22;
+mod day23;
+mod day24;
+mod day25;
+mod day3;
+mod day4;
+mod day5;
+mod day6;
+mod day7;
+mod day8;
+mod day9;
+// NEXT MOD
+
+#[paw::main]
+fn main(opt: Opt) -> Result<()> {
+    #[allow(clippy::match_single_binding)]
+    match opt.day {
+        1 => advent_of_code::day!(2021, opt.day, opt.puzzle, day1),
+        2 => advent_of_code::day!(2021, opt.day, opt.puzzle, day2),
+        3 => advent_of_code::day!(2021, opt.day, opt.puzzle, day3),
+        4 => advent_of_code::day!(2021, opt.day, opt.puzzle, day4),
+        5 => advent_of_code::day!(2021, opt.day, opt.puzzle, day5),
+        6 => advent_of_code::day!(2021, opt.day, opt.puzzle, day6),
+        7 => advent_of_code::day!(2021, opt.day, opt.puzzle, day7),
+        8 => advent_of_code::day!(2021, opt.day, opt.puzzle, day8),
+        9 => advent_of_code::day!(2021, opt.day, opt.puzzle, day9),
+        10 => advent_of_code::day!(2021, opt.day, opt.puzzle, day10),
+        11 => advent_of_code::day!(2021, opt.day, opt.puzzle, day11),
+        12 => advent_of_code::day!(2021, opt.day, opt.puzzle, day12),
+        13 => advent_of_code::day!(2021, opt.day, opt.puzzle, day13),
+        14 => advent_of_code::day!(2021, opt.day, opt.puzzle, day14),
+        15 => advent_of_code::day!(2021, opt.day, opt.puzzle, day15),
+        16 => advent_of_code::day!(2021, opt.day, opt.puzzle, day16),
+        17 => advent_of_code::day!(2021, opt.day, opt.puzzle, day17),
+        18 => advent_of_code::day!(2021, opt.day, opt.puzzle, day18),
+        19 => advent_of_code::day!(2021, opt.day, opt.puzzle, day19),
+        20 => advent_of_code::day!(2021, opt.day, opt.puzzle, day20),
+        21 => advent_of_code::day!(2021, opt.day, opt.puzzle, day21),
+        22 => advent_of_code::day!(2021, opt.day, opt.puzzle, day22),
+        23 => advent_of_code::day!(2021, opt.day, opt.puzzle, day23),
+        24 => advent_of_code::day!(2021, opt.day, opt.puzzle, day24),
+        25 => advent_of_code::day!(2021, opt.day, opt.puzzle, day25),
+        // NEXT PART
+        _ => panic!("unknown day {}", opt.day),
+    }
+    Ok(())
+}
diff --git a/src/bin/2022/day1.rs b/src/bin/2022/day1.rs
new file mode 100644
index 0000000..1b48b29
--- /dev/null
+++ b/src/bin/2022/day1.rs
@@ -0,0 +1,38 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<Vec<u64>> {
+    let mut elves = vec![];
+    let mut lines = parse::raw_lines(fh).peekable();
+    while lines.peek().is_some() {
+        let mut calories = 0;
+        for line in parse::chunk(&mut lines) {
+            calories += line.parse::<u64>()?;
+        }
+        elves.push(calories);
+    }
+    Ok(elves)
+}
+
+pub fn part1(elves: Vec<u64>) -> Result<u64> {
+    Ok(elves.iter().copied().max().unwrap_or(0))
+}
+
+pub fn part2(mut elves: Vec<u64>) -> Result<u64> {
+    elves.sort();
+    Ok(elves.iter().rev().copied().take(3).sum())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 1).unwrap()).unwrap()).unwrap(),
+        67658
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 1).unwrap()).unwrap()).unwrap(),
+        200158
+    );
+}
diff --git a/src/bin/2022/day10.rs b/src/bin/2022/day10.rs
new file mode 100644
index 0000000..8f7b617
--- /dev/null
+++ b/src/bin/2022/day10.rs
@@ -0,0 +1,93 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub struct Cpu {
+    x: i64,
+    history: Vec<i64>,
+}
+
+impl Cpu {
+    fn new() -> Self {
+        Self {
+            x: 1,
+            history: vec![1],
+        }
+    }
+
+    fn step(&mut self, op: Op) {
+        match op {
+            Op::Noop => {
+                self.history.push(self.x);
+            }
+            Op::Addx(v) => {
+                self.history.push(self.x);
+                self.x += v;
+                self.history.push(self.x);
+            }
+        }
+    }
+}
+
+#[derive(Clone, Copy)]
+pub enum Op {
+    Noop,
+    Addx(i64),
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Op>> {
+    Ok(parse::raw_lines(fh).map(|line| {
+        if line == "noop" {
+            Op::Noop
+        } else if let Some(v) = line.strip_prefix("addx ") {
+            Op::Addx(v.parse().unwrap())
+        } else {
+            panic!("failed to parse {}", line)
+        }
+    }))
+}
+
+pub fn part1(ops: impl Iterator<Item = Op>) -> Result<i64> {
+    let mut cpu = Cpu::new();
+    for op in ops {
+        cpu.step(op);
+    }
+
+    let mut total = 0;
+    for cycle in [20, 60, 100, 140, 180, 220] {
+        let strength = i64::try_from(cycle).unwrap() * cpu.history[cycle - 1];
+        total += strength;
+    }
+    Ok(total)
+}
+
+pub fn part2(ops: impl Iterator<Item = Op>) -> Result<i64> {
+    let mut cpu = Cpu::new();
+    for op in ops {
+        cpu.step(op);
+    }
+    for (y, row) in cpu.history.chunks(40).enumerate() {
+        for (x, pos) in row.iter().enumerate() {
+            if i64::try_from(x).unwrap().abs_diff(*pos) <= 1 {
+                print!("#");
+            } else {
+                print!(".");
+            }
+        }
+        println!();
+    }
+    Ok(0)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 10).unwrap()).unwrap()).unwrap(),
+        15680
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 10).unwrap()).unwrap()).unwrap(),
+        0
+    );
+}
diff --git a/src/bin/2022/day11.rs b/src/bin/2022/day11.rs
new file mode 100644
index 0000000..faef195
--- /dev/null
+++ b/src/bin/2022/day11.rs
@@ -0,0 +1,181 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub struct Monkey {
+    items: VecDeque<u64>,
+    op: Box<dyn Fn(u64) -> u64>,
+    divisor: u64,
+    modulo: u64,
+    test: u64,
+    if_true: usize,
+    if_false: usize,
+
+    count: u64,
+}
+
+impl std::fmt::Debug for Monkey {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        f.debug_struct("Monkey")
+            .field("items", &self.items)
+            .finish()
+    }
+}
+
+impl Monkey {
+    fn parse(mut it: impl Iterator<Item = String>) -> Monkey {
+        let line = it.next().unwrap();
+        let cap = regex_captures!(r"^  Starting items: ([0-9, ]*)$", &line)
+            .unwrap();
+        let items = cap[1].split(", ").map(|s| s.parse().unwrap()).collect();
+
+        let line = it.next().unwrap();
+        let cap = regex_captures!(
+            r"^  Operation: new = old ([+*]) (\d+|old)$",
+            &line
+        )
+        .unwrap();
+        let op = if &cap[2] == "old" {
+            match &cap[1] {
+                "+" => Box::new(move |x| x + x) as Box<dyn Fn(u64) -> u64>,
+                "*" => Box::new(move |x| x * x),
+                _ => unreachable!(),
+            }
+        } else {
+            let n: u64 = cap[2].parse().unwrap();
+            match &cap[1] {
+                "+" => Box::new(move |x| x + n) as Box<dyn Fn(u64) -> u64>,
+                "*" => Box::new(move |x| x * n),
+                _ => unreachable!(),
+            }
+        };
+
+        let line = it.next().unwrap();
+        let cap =
+            regex_captures!(r"^  Test: divisible by (\d+)$", &line).unwrap();
+        let test = cap[1].parse().unwrap();
+
+        let line = it.next().unwrap();
+        let cap =
+            regex_captures!(r"^    If true: throw to monkey (\d+)$", &line)
+                .unwrap();
+        let if_true = cap[1].parse().unwrap();
+
+        let line = it.next().unwrap();
+        let cap =
+            regex_captures!(r"^    If false: throw to monkey (\d+)$", &line)
+                .unwrap();
+        let if_false = cap[1].parse().unwrap();
+
+        assert!(it.next().is_none());
+
+        Self {
+            items,
+            op,
+            divisor: 0,
+            modulo: 0,
+            test,
+            if_true,
+            if_false,
+            count: 0,
+        }
+    }
+
+    fn inspect(&mut self) -> Option<(u64, usize)> {
+        let Some(item) = self.items.pop_front()
+        else { return None };
+        self.count += 1;
+        let item = (self.op)(item);
+        let item = item / self.divisor;
+        let item = item % self.modulo;
+        if item % self.test == 0 {
+            Some((item, self.if_true))
+        } else {
+            Some((item, self.if_false))
+        }
+    }
+
+    fn catch(&mut self, item: u64) {
+        self.items.push_back(item);
+    }
+
+    fn set_reduce(&mut self, divisor: u64, modulo: u64) {
+        self.divisor = divisor;
+        self.modulo = modulo;
+    }
+}
+
+#[derive(Debug)]
+pub struct Monkeys {
+    monkeys: Vec<Monkey>,
+}
+
+impl Monkeys {
+    fn parse(it: impl Iterator<Item = String>) -> Self {
+        let mut monkeys = vec![];
+        let mut it = it.peekable();
+        while it.peek().is_some() {
+            let header = it.next().unwrap();
+            let cap = regex_captures!(r"^Monkey (\d+):$", &header).unwrap();
+            let monkey_idx: usize = cap[1].parse().unwrap();
+            assert_eq!(monkey_idx, monkeys.len());
+            monkeys.push(Monkey::parse(parse::chunk(&mut it)));
+        }
+        Self { monkeys }
+    }
+
+    fn round(&mut self) {
+        for i in 0..self.monkeys.len() {
+            while let Some((item, to)) = self.monkeys[i].inspect() {
+                self.monkeys[to].catch(item);
+            }
+        }
+    }
+
+    fn monkey_business(&self) -> u64 {
+        let mut counts: Vec<_> =
+            self.monkeys.iter().map(|m| m.count).collect();
+        counts.sort_unstable();
+        counts[counts.len() - 1] * counts[counts.len() - 2]
+    }
+
+    fn set_reduce(&mut self, divisor: u64) {
+        let modulo = self.monkeys.iter().map(|m| m.test).product();
+        for monkey in &mut self.monkeys {
+            monkey.set_reduce(divisor, modulo);
+        }
+    }
+}
+
+pub fn parse(fh: File) -> Result<Monkeys> {
+    Ok(Monkeys::parse(parse::raw_lines(fh)))
+}
+
+pub fn part1(mut monkeys: Monkeys) -> Result<u64> {
+    monkeys.set_reduce(3);
+    for i in 0..20 {
+        monkeys.round();
+    }
+    Ok(monkeys.monkey_business())
+}
+
+pub fn part2(mut monkeys: Monkeys) -> Result<u64> {
+    monkeys.set_reduce(1);
+    for i in 0..10_000 {
+        monkeys.round();
+    }
+    Ok(monkeys.monkey_business())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 11).unwrap()).unwrap()).unwrap(),
+        51075
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 11).unwrap()).unwrap()).unwrap(),
+        11741456163
+    );
+}
diff --git a/src/bin/2022/day2.rs b/src/bin/2022/day2.rs
new file mode 100644
index 0000000..03a5360
--- /dev/null
+++ b/src/bin/2022/day2.rs
@@ -0,0 +1,136 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+#[derive(Copy, Clone, Eq, PartialEq)]
+enum Outcome {
+    Lose,
+    Draw,
+    Win,
+}
+
+impl Outcome {
+    fn score(self) -> u64 {
+        match self {
+            Self::Lose => 0,
+            Self::Draw => 3,
+            Self::Win => 6,
+        }
+    }
+}
+
+impl std::str::FromStr for Outcome {
+    type Err = ();
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        Ok(match s {
+            "X" => Self::Lose,
+            "Y" => Self::Draw,
+            "Z" => Self::Win,
+            _ => return Err(()),
+        })
+    }
+}
+
+#[derive(Copy, Clone)]
+enum Shape {
+    Rock,
+    Paper,
+    Scissors,
+}
+
+impl Shape {
+    fn score(self) -> u64 {
+        match self {
+            Self::Rock => 1,
+            Self::Paper => 2,
+            Self::Scissors => 3,
+        }
+    }
+
+    fn outcome(self, other: Self) -> Outcome {
+        match self {
+            Self::Rock => match other {
+                Self::Rock => Outcome::Draw,
+                Self::Paper => Outcome::Lose,
+                Self::Scissors => Outcome::Win,
+            },
+            Self::Paper => match other {
+                Self::Rock => Outcome::Win,
+                Self::Paper => Outcome::Draw,
+                Self::Scissors => Outcome::Lose,
+            },
+            Self::Scissors => match other {
+                Self::Rock => Outcome::Lose,
+                Self::Paper => Outcome::Win,
+                Self::Scissors => Outcome::Draw,
+            },
+        }
+    }
+
+    fn shape_for(self, outcome: Outcome) -> Self {
+        if Self::Rock.outcome(self) == outcome {
+            return Self::Rock;
+        }
+        if Self::Paper.outcome(self) == outcome {
+            return Self::Paper;
+        }
+        if Self::Scissors.outcome(self) == outcome {
+            return Self::Scissors;
+        }
+        unreachable!()
+    }
+}
+
+impl std::str::FromStr for Shape {
+    type Err = ();
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        Ok(match s {
+            "A" | "X" => Self::Rock,
+            "B" | "Y" => Self::Paper,
+            "C" | "Z" => Self::Scissors,
+            _ => return Err(()),
+        })
+    }
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = String>> {
+    Ok(parse::raw_lines(fh))
+}
+
+pub fn part1(lines: impl Iterator<Item = String>) -> Result<u64> {
+    Ok(lines
+        .map(|line| {
+            let mut parts = line.split(' ');
+            let them: Shape = parts.next().unwrap().parse().unwrap();
+            let me: Shape = parts.next().unwrap().parse().unwrap();
+            me.score() + me.outcome(them).score()
+        })
+        .sum())
+}
+
+pub fn part2(lines: impl Iterator<Item = String>) -> Result<u64> {
+    Ok(lines
+        .map(|line| {
+            let mut parts = line.split(' ');
+            let them: Shape = parts.next().unwrap().parse().unwrap();
+            let outcome: Outcome = parts.next().unwrap().parse().unwrap();
+            let me = them.shape_for(outcome);
+            me.score() + outcome.score()
+        })
+        .sum())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 2).unwrap()).unwrap()).unwrap(),
+        13565
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 2).unwrap()).unwrap()).unwrap(),
+        12424
+    );
+}
diff --git a/src/bin/2022/day3.rs b/src/bin/2022/day3.rs
new file mode 100644
index 0000000..a56baf4
--- /dev/null
+++ b/src/bin/2022/day3.rs
@@ -0,0 +1,62 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub fn parse(
+    fh: File,
+) -> Result<impl Iterator<Item = (HashSet<char>, HashSet<char>)>> {
+    Ok(parse::raw_lines(fh).map(|line| {
+        let (first, second) = line.split_at(line.len() / 2);
+        let first: HashSet<char> = first.chars().collect();
+        let second: HashSet<char> = second.chars().collect();
+        (first, second)
+    }))
+}
+
+pub fn part1(
+    sacks: impl Iterator<Item = (HashSet<char>, HashSet<char>)>,
+) -> Result<u32> {
+    Ok(sacks
+        .map(|(first, second)| {
+            priority(*first.intersection(&second).next().unwrap())
+        })
+        .sum())
+}
+
+pub fn part2(
+    mut sacks: impl Iterator<Item = (HashSet<char>, HashSet<char>)>,
+) -> Result<u32> {
+    let mut total = 0;
+    while let (Some(first), Some(second), Some(third)) =
+        (sacks.next(), sacks.next(), sacks.next())
+    {
+        let first: HashSet<char> = first.0.union(&first.1).copied().collect();
+        let second: HashSet<char> =
+            second.0.union(&second.1).copied().collect();
+        let third: HashSet<char> = third.0.union(&third.1).copied().collect();
+        total +=
+            priority(*(&(&first & &second) & &third).iter().next().unwrap());
+    }
+    Ok(total)
+}
+
+fn priority(c: char) -> u32 {
+    match c {
+        'a'..='z' => u32::from(c) - u32::from('a') + 1,
+        'A'..='Z' => u32::from(c) - u32::from('A') + 27,
+        _ => unreachable!(),
+    }
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 3).unwrap()).unwrap()).unwrap(),
+        8493
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 3).unwrap()).unwrap()).unwrap(),
+        2552
+    );
+}
diff --git a/src/bin/2022/day4.rs b/src/bin/2022/day4.rs
new file mode 100644
index 0000000..2fe98c5
--- /dev/null
+++ b/src/bin/2022/day4.rs
@@ -0,0 +1,69 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub struct Pair {
+    first: (i64, i64),
+    second: (i64, i64),
+}
+
+impl Pair {
+    fn contains(&self) -> bool {
+        range_contains(self.first, self.second)
+            || range_contains(self.second, self.first)
+    }
+
+    fn overlaps(&self) -> bool {
+        range_overlaps(self.first, self.second)
+            || range_overlaps(self.second, self.first)
+    }
+}
+
+fn range_contains(a: (i64, i64), b: (i64, i64)) -> bool {
+    (a.0..=a.1).contains(&b.0) && (a.0..=a.1).contains(&b.1)
+}
+
+fn range_overlaps(a: (i64, i64), b: (i64, i64)) -> bool {
+    (a.0..=a.1).contains(&b.0) || (a.0..=a.1).contains(&b.1)
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Pair>> {
+    Ok(parse::raw_lines(fh).map(|line| {
+        let mut parts = line.split(',');
+        let first = parts.next().unwrap();
+        let mut first_parts = first.split('-');
+        let second = parts.next().unwrap();
+        let mut second_parts = second.split('-');
+        Pair {
+            first: (
+                first_parts.next().unwrap().parse().unwrap(),
+                first_parts.next().unwrap().parse().unwrap(),
+            ),
+            second: (
+                second_parts.next().unwrap().parse().unwrap(),
+                second_parts.next().unwrap().parse().unwrap(),
+            ),
+        }
+    }))
+}
+
+pub fn part1(pairs: impl Iterator<Item = Pair>) -> Result<usize> {
+    Ok(pairs.filter(|pair| pair.contains()).count())
+}
+
+pub fn part2(pairs: impl Iterator<Item = Pair>) -> Result<usize> {
+    Ok(pairs.filter(|pair| pair.overlaps()).count())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 4).unwrap()).unwrap()).unwrap(),
+        515
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 4).unwrap()).unwrap()).unwrap(),
+        883
+    );
+}
diff --git a/src/bin/2022/day5.rs b/src/bin/2022/day5.rs
new file mode 100644
index 0000000..da1e5a2
--- /dev/null
+++ b/src/bin/2022/day5.rs
@@ -0,0 +1,141 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+#[derive(Default)]
+pub struct Pile(Vec<char>);
+
+impl Pile {
+    fn move_from(&mut self, other: &mut Self, n: usize) {
+        for _ in 0..n {
+            self.0.push(other.0.pop().unwrap());
+        }
+    }
+
+    fn unshift(&mut self, c: char) {
+        self.0.insert(0, c);
+    }
+
+    fn push(&mut self, c: char) {
+        self.0.push(c);
+    }
+
+    fn pop(&mut self) -> Option<char> {
+        self.0.pop()
+    }
+
+    fn top(&self) -> Option<char> {
+        self.0.last().copied()
+    }
+}
+
+struct Instruction {
+    count: usize,
+    from: usize,
+    to: usize,
+}
+
+pub struct Crates {
+    piles: Vec<Pile>,
+    instructions: Vec<Instruction>,
+}
+
+pub fn parse(fh: File) -> Result<Crates> {
+    let mut lines = parse::raw_lines(fh);
+    let mut piles: Vec<Pile> = vec![];
+
+    for line in lines.by_ref() {
+        if line.starts_with(" 1 ") {
+            break;
+        }
+
+        let pile_count = (line.len() + 1) / 4;
+        piles.resize_with(pile_count, Default::default);
+
+        for (pile_idx, pile) in piles.iter_mut().enumerate() {
+            let idx = pile_idx * 4;
+            assert!([' ', '['].contains(&line.chars().nth(idx).unwrap()));
+            let crate_name = line.chars().nth(idx + 1).unwrap();
+            if crate_name != ' ' {
+                pile.unshift(crate_name);
+            }
+            assert!([' ', ']'].contains(&line.chars().nth(idx + 2).unwrap()));
+            assert!([Some(' '), None].contains(&line.chars().nth(idx + 3)));
+        }
+    }
+
+    assert_eq!(lines.next().unwrap(), "");
+
+    let mut instructions = vec![];
+    for line in lines {
+        let captures = regex_captures!(
+            r"^move ([0-9]+) from ([0-9]+) to ([0-9]+)$",
+            &line
+        )
+        .unwrap();
+        let count = captures[1].parse().unwrap();
+        let from = captures[2].parse().unwrap();
+        let to = captures[3].parse().unwrap();
+        instructions.push(Instruction { count, from, to });
+    }
+
+    Ok(Crates {
+        piles,
+        instructions,
+    })
+}
+
+fn part1_str(mut crates: Crates) -> Result<String> {
+    for Instruction { count, from, to } in crates.instructions {
+        for _ in 0..count {
+            let c = crates.piles[from - 1].pop().unwrap();
+            crates.piles[to - 1].push(c);
+        }
+    }
+    Ok(crates
+        .piles
+        .iter()
+        .map(|pile| pile.top().unwrap())
+        .collect())
+}
+
+pub fn part1(crates: Crates) -> Result<i64> {
+    println!("{}", part1_str(crates)?);
+    Ok(0)
+}
+
+fn part2_str(mut crates: Crates) -> Result<String> {
+    for Instruction { count, from, to } in crates.instructions {
+        let mut tmp = vec![];
+        for _ in 0..count {
+            let c = crates.piles[from - 1].pop().unwrap();
+            tmp.push(c);
+        }
+        for c in tmp.iter().copied().rev() {
+            crates.piles[to - 1].push(c);
+        }
+    }
+    Ok(crates
+        .piles
+        .iter()
+        .map(|pile| pile.top().unwrap())
+        .collect())
+}
+
+pub fn part2(crates: Crates) -> Result<i64> {
+    println!("{}", part2_str(crates)?);
+    Ok(0)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1_str(parse(parse::data(2022, 5).unwrap()).unwrap()).unwrap(),
+        "PSNRGBTFT"
+    );
+    assert_eq!(
+        part2_str(parse(parse::data(2022, 5).unwrap()).unwrap()).unwrap(),
+        "BNTZFPMMW"
+    );
+}
diff --git a/src/bin/2022/day6.rs b/src/bin/2022/day6.rs
new file mode 100644
index 0000000..6fe154f
--- /dev/null
+++ b/src/bin/2022/day6.rs
@@ -0,0 +1,38 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<String> {
+    Ok(parse::string(fh))
+}
+
+pub fn part1(s: String) -> Result<usize> {
+    for (i, slice) in s.as_bytes().windows(4).enumerate() {
+        if slice.iter().copied().collect::<HashSet<u8>>().len() == 4 {
+            return Ok(i + 4);
+        }
+    }
+    Err(anyhow!("couldn't find marker"))
+}
+
+pub fn part2(s: String) -> Result<usize> {
+    for (i, slice) in s.as_bytes().windows(14).enumerate() {
+        if slice.iter().copied().collect::<HashSet<u8>>().len() == 14 {
+            return Ok(i + 14);
+        }
+    }
+    Err(anyhow!("couldn't find marker"))
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 6).unwrap()).unwrap()).unwrap(),
+        1155
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 6).unwrap()).unwrap()).unwrap(),
+        2789
+    );
+}
diff --git a/src/bin/2022/day7.rs b/src/bin/2022/day7.rs
new file mode 100644
index 0000000..d0101c9
--- /dev/null
+++ b/src/bin/2022/day7.rs
@@ -0,0 +1,136 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub enum Node {
+    Dir,
+    File(u64),
+}
+
+impl Node {
+    fn new_dir() -> Self {
+        Self::Dir
+    }
+
+    fn new_file(size: u64) -> Self {
+        Self::File(size)
+    }
+
+    fn size(&self) -> u64 {
+        match self {
+            Self::Dir => 0,
+            Self::File(size) => *size,
+        }
+    }
+}
+
+fn tree_size(tree: &Tree<String, Node>) -> u64 {
+    tree.bfs().map(|(_, tree)| tree.data().size()).sum()
+}
+
+pub fn parse(fh: File) -> Result<Tree<String, Node>> {
+    let mut lines = parse::raw_lines(fh).peekable();
+    let mut root = Tree::new(Node::Dir);
+    let mut path = vec![];
+
+    while let Some(cmdline) = lines.by_ref().next() {
+        let Some(captures) = &regex_captures!(
+            r"^\$ (cd|ls)(?: (.*))?$",
+            &cmdline
+        )
+        else { bail!("didn't match cmdline: '{}'", cmdline) };
+        let Some(cmd) = captures.get(1)
+        else { bail!("no cmd found in cmdline: '{}'", cmdline) };
+
+        let pwd = root.at_mut(&path).unwrap();
+
+        match cmd.as_str() {
+            "cd" => {
+                let Some(arg) = captures.get(2)
+                else { bail!("no arg found for cd: '{}'", cmdline) };
+                match arg.as_str() {
+                    ".." => {
+                        path.pop();
+                    }
+                    "/" => path = vec![],
+                    dirname => {
+                        if pwd.at(&[dirname.to_string()]).is_none() {
+                            pwd.add_child(
+                                dirname.to_string(),
+                                Node::new_dir(),
+                            );
+                        }
+                        path.push(dirname.to_string());
+                    }
+                }
+            }
+            "ls" => loop {
+                let Some(lsline) = lines.peek()
+                    else { break };
+                let Some(captures) = &regex_captures!(
+                        r"^(dir|[0-9]+) (.*)$",
+                        lsline
+                    )
+                    else { break };
+                let Some(data) = captures.get(1)
+                    else { break };
+                let Some(name) = captures.get(2)
+                    else { break };
+
+                let node = match data.as_str() {
+                    "dir" => Node::new_dir(),
+                    size => Node::new_file(size.parse().unwrap()),
+                };
+                pwd.add_child(name.as_str().to_string(), node);
+                lines.next();
+            },
+            _ => unreachable!(),
+        }
+    }
+
+    Ok(root)
+}
+
+pub fn part1(tree: Tree<String, Node>) -> Result<u64> {
+    let mut total = 0;
+    for (_, tree) in tree.bfs() {
+        if matches!(tree.data(), Node::File(_)) {
+            continue;
+        }
+        let size = tree_size(tree);
+        if size <= 100_000 {
+            total += size;
+        }
+    }
+    Ok(total)
+}
+
+pub fn part2(tree: Tree<String, Node>) -> Result<u64> {
+    let total = tree_size(&tree);
+    let free = 70_000_000 - total;
+    let needed = 30_000_000 - free;
+    let mut possible = vec![];
+    for (_, tree) in tree.bfs() {
+        if matches!(tree.data(), Node::File(_)) {
+            continue;
+        }
+        let size = tree_size(tree);
+        if size > needed {
+            possible.push(size);
+        }
+    }
+    Ok(possible.iter().copied().min().unwrap())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 7).unwrap()).unwrap()).unwrap(),
+        1297683
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 7).unwrap()).unwrap()).unwrap(),
+        5756764
+    );
+}
diff --git a/src/bin/2022/day8.rs b/src/bin/2022/day8.rs
new file mode 100644
index 0000000..6ec110e
--- /dev/null
+++ b/src/bin/2022/day8.rs
@@ -0,0 +1,156 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+pub fn parse(fh: File) -> Result<Grid<u8>> {
+    Ok(parse::digit_grid(parse::raw_lines(fh)))
+}
+
+pub fn part1(trees: Grid<u8>) -> Result<u64> {
+    let mut total = 0;
+    for row in trees.each_row() {
+        'tree: for col in trees.each_col() {
+            let tree = trees[row][col];
+
+            if trees
+                .each_col()
+                .take(col.0)
+                .all(|col| trees[row][col] < tree)
+            {
+                total += 1;
+                continue 'tree;
+            }
+            if trees
+                .each_col()
+                .skip(col.0 + 1)
+                .all(|col| trees[row][col] < tree)
+            {
+                total += 1;
+                continue 'tree;
+            }
+            if trees
+                .each_row()
+                .take(row.0)
+                .all(|row| trees[row][col] < tree)
+            {
+                total += 1;
+                continue 'tree;
+            }
+            if trees
+                .each_row()
+                .skip(row.0 + 1)
+                .all(|row| trees[row][col] < tree)
+            {
+                total += 1;
+                continue 'tree;
+            }
+        }
+    }
+    Ok(total)
+}
+
+pub fn part2(trees: Grid<u8>) -> Result<usize> {
+    let mut max = 0;
+    for row in trees.each_row() {
+        for col in trees.each_col() {
+            let tree = trees[row][col];
+
+            let mut seen = false;
+            let left = trees
+                .each_col()
+                .take(col.0)
+                .rev()
+                .take_while(|col| {
+                    if seen {
+                        return false;
+                    }
+
+                    let other = trees[row][*col];
+                    if other < tree {
+                        true
+                    } else {
+                        seen = true;
+                        true
+                    }
+                })
+                .count();
+
+            let mut seen = false;
+            let right = trees
+                .each_col()
+                .skip(col.0 + 1)
+                .take_while(|col| {
+                    if seen {
+                        return false;
+                    }
+
+                    let other = trees[row][*col];
+                    if other < tree {
+                        true
+                    } else {
+                        seen = true;
+                        true
+                    }
+                })
+                .count();
+
+            let mut seen = false;
+            let up = trees
+                .each_row()
+                .take(row.0)
+                .rev()
+                .take_while(|row| {
+                    if seen {
+                        return false;
+                    }
+
+                    let other = trees[*row][col];
+                    if other < tree {
+                        true
+                    } else {
+                        seen = true;
+                        true
+                    }
+                })
+                .count();
+
+            let mut seen = false;
+            let down = trees
+                .each_row()
+                .skip(row.0 + 1)
+                .take_while(|row| {
+                    if seen {
+                        return false;
+                    }
+
+                    let other = trees[*row][col];
+                    if other < tree {
+                        true
+                    } else {
+                        seen = true;
+                        true
+                    }
+                })
+                .count();
+
+            let scenic = left * right * up * down;
+            if scenic > max {
+                max = scenic;
+            }
+        }
+    }
+    Ok(max)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 8).unwrap()).unwrap()).unwrap(),
+        1851
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 8).unwrap()).unwrap()).unwrap(),
+        574080
+    );
+}
diff --git a/src/bin/2022/day9.rs b/src/bin/2022/day9.rs
new file mode 100644
index 0000000..235ec44
--- /dev/null
+++ b/src/bin/2022/day9.rs
@@ -0,0 +1,236 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+#[derive(Debug)]
+enum Direction {
+    Up,
+    Down,
+    Left,
+    Right,
+}
+
+impl std::str::FromStr for Direction {
+    type Err = ();
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        Ok(match s {
+            "U" => Self::Up,
+            "D" => Self::Down,
+            "L" => Self::Left,
+            "R" => Self::Right,
+            _ => return Err(()),
+        })
+    }
+}
+
+#[derive(Debug)]
+pub struct Move {
+    dir: Direction,
+    count: usize,
+}
+
+impl Move {
+    fn parse(line: &str) -> Self {
+        let mut parts = line.split_whitespace();
+        let dir = parts.next().unwrap().parse().unwrap();
+        let count = parts.next().unwrap().parse().unwrap();
+        Self { dir, count }
+    }
+}
+
+pub struct Rope {
+    knots: Vec<(Row, Col)>,
+}
+
+impl Rope {
+    pub fn new(len: usize) -> Self {
+        Self {
+            knots: vec![Default::default(); len],
+        }
+    }
+
+    pub fn at(&self, pos: (Row, Col)) -> Option<usize> {
+        for (i, knot) in self.knots.iter().enumerate() {
+            if knot == &pos {
+                return Some(i);
+            }
+        }
+        None
+    }
+}
+
+pub struct Map {
+    grid: std::collections::VecDeque<std::collections::VecDeque<bool>>,
+    size: (Row, Col),
+    rope: Rope,
+}
+
+impl std::fmt::Debug for Map {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        writeln!(f, "({}, {})", self.size.0 .0, self.size.1 .0)?;
+        for row in (0..self.size.0 .0).rev() {
+            for col in 0..self.size.1 .0 {
+                write!(
+                    f,
+                    "{}",
+                    if let Some(idx) = self.rope.at((Row(row), Col(col))) {
+                        char::from(b'0' + u8::try_from(idx).unwrap())
+                    } else if self.grid[row][col] {
+                        '#'
+                    } else {
+                        '.'
+                    }
+                )?;
+            }
+            writeln!(f)?;
+        }
+        Ok(())
+    }
+}
+
+impl Map {
+    fn new(len: usize) -> Self {
+        let mut grid = std::collections::VecDeque::new();
+        grid.push_back(std::collections::VecDeque::new());
+        grid[0].push_back(true);
+        Self {
+            grid,
+            size: (Row(1), Col(1)),
+            rope: Rope::new(len),
+        }
+    }
+
+    fn mv(&mut self, mv: &Move) {
+        // println!("{:?}", mv);
+        for _ in 0..mv.count {
+            self.step(&mv.dir);
+        }
+    }
+
+    fn step(&mut self, dir: &Direction) {
+        let (Row(row), Col(col)) = self.rope.knots[0];
+        match dir {
+            Direction::Up => {
+                if row == self.size.0 .0 - 1 {
+                    let mut row_contents = std::collections::VecDeque::new();
+                    row_contents
+                        .resize_with(self.size.1 .0, Default::default);
+                    self.grid.push_back(row_contents);
+                    self.size.0 = Row(self.size.0 .0 + 1);
+                }
+                self.rope.knots[0].0 = Row(self.rope.knots[0].0 .0 + 1);
+            }
+            Direction::Down => {
+                if row == 0 {
+                    let mut row_contents = std::collections::VecDeque::new();
+                    row_contents
+                        .resize_with(self.size.1 .0, Default::default);
+                    self.grid.push_front(row_contents);
+                    for knot in &mut self.rope.knots {
+                        knot.0 = Row(knot.0 .0 + 1);
+                    }
+                    self.size.0 = Row(self.size.0 .0 + 1);
+                }
+                self.rope.knots[0].0 = Row(self.rope.knots[0].0 .0 - 1);
+            }
+            Direction::Left => {
+                if col == 0 {
+                    for i in 0..self.size.0 .0 {
+                        self.grid[i].push_front(Default::default());
+                    }
+                    for knot in &mut self.rope.knots {
+                        knot.1 = Col(knot.1 .0 + 1);
+                    }
+                    self.size.1 = Col(self.size.1 .0 + 1);
+                }
+                self.rope.knots[0].1 = Col(self.rope.knots[0].1 .0 - 1);
+            }
+            Direction::Right => {
+                if col == self.size.1 .0 - 1 {
+                    for i in 0..self.size.0 .0 {
+                        self.grid[i].push_back(Default::default());
+                    }
+                    self.size.1 = Col(self.size.1 .0 + 1);
+                }
+                self.rope.knots[0].1 = Col(self.rope.knots[0].1 .0 + 1);
+            }
+        }
+
+        for i in 0..(self.rope.knots.len() - 1) {
+            if self.rope.knots[i + 1]
+                .0
+                 .0
+                .abs_diff(self.rope.knots[i].0 .0)
+                > 1
+                || self.rope.knots[i + 1]
+                    .1
+                     .0
+                    .abs_diff(self.rope.knots[i].1 .0)
+                    > 1
+            {
+                if self.rope.knots[i + 1].0 .0 < self.rope.knots[i].0 .0 {
+                    self.rope.knots[i + 1].0 .0 += 1;
+                }
+                if self.rope.knots[i + 1].0 .0 > self.rope.knots[i].0 .0 {
+                    self.rope.knots[i + 1].0 .0 -= 1;
+                }
+                if self.rope.knots[i + 1].1 .0 < self.rope.knots[i].1 .0 {
+                    self.rope.knots[i + 1].1 .0 += 1;
+                }
+                if self.rope.knots[i + 1].1 .0 > self.rope.knots[i].1 .0 {
+                    self.rope.knots[i + 1].1 .0 -= 1;
+                }
+            }
+        }
+        self.grid[self.rope.knots.last().unwrap().0 .0]
+            [self.rope.knots.last().unwrap().1 .0] = true;
+    }
+}
+
+pub fn parse(fh: File) -> Result<impl Iterator<Item = Move>> {
+    Ok(parse::raw_lines(fh).map(|line| Move::parse(&line)))
+}
+
+pub fn part1(moves: impl Iterator<Item = Move>) -> Result<usize> {
+    let mut map = Map::new(2);
+    for mv in moves {
+        // println!("{:?}", map);
+        map.mv(&mv);
+    }
+    // println!("{:?}", map);
+    Ok(map
+        .grid
+        .iter()
+        .flat_map(|row| row.iter().copied())
+        .filter(|cell| *cell)
+        .count())
+}
+
+pub fn part2(moves: impl Iterator<Item = Move>) -> Result<usize> {
+    let mut map = Map::new(10);
+    for mv in moves {
+        // println!("{:?}", map);
+        map.mv(&mv);
+    }
+    // println!("{:?}", map);
+    Ok(map
+        .grid
+        .iter()
+        .flat_map(|row| row.iter().copied())
+        .filter(|cell| *cell)
+        .count())
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 9).unwrap()).unwrap()).unwrap(),
+        6037
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 9).unwrap()).unwrap()).unwrap(),
+        2485
+    );
+}
diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs
new file mode 100644
index 0000000..09a9248
--- /dev/null
+++ b/src/bin/2022/main.rs
@@ -0,0 +1,46 @@
+#![allow(clippy::cognitive_complexity)]
+#![allow(clippy::missing_const_for_fn)]
+#![allow(clippy::similar_names)]
+#![allow(clippy::struct_excessive_bools)]
+#![allow(clippy::too_many_arguments)]
+#![allow(clippy::too_many_lines)]
+#![allow(clippy::type_complexity)]
+#![allow(clippy::collapsible_else_if)]
+#![allow(clippy::collapsible_if)]
+#![allow(clippy::comparison_chain)]
+
+use advent_of_code::prelude::*;
+
+mod day1;
+mod day10;
+mod day11;
+mod day2;
+mod day3;
+mod day4;
+mod day5;
+mod day6;
+mod day7;
+mod day8;
+mod day9;
+// NEXT MOD
+
+#[paw::main]
+fn main(opt: Opt) -> Result<()> {
+    #[allow(clippy::match_single_binding)]
+    match opt.day {
+        1 => advent_of_code::day!(2022, opt.day, opt.puzzle, day1),
+        2 => advent_of_code::day!(2022, opt.day, opt.puzzle, day2),
+        3 => advent_of_code::day!(2022, opt.day, opt.puzzle, day3),
+        4 => advent_of_code::day!(2022, opt.day, opt.puzzle, day4),
+        5 => advent_of_code::day!(2022, opt.day, opt.puzzle, day5),
+        6 => advent_of_code::day!(2022, opt.day, opt.puzzle, day6),
+        7 => advent_of_code::day!(2022, opt.day, opt.puzzle, day7),
+        8 => advent_of_code::day!(2022, opt.day, opt.puzzle, day8),
+        9 => advent_of_code::day!(2022, opt.day, opt.puzzle, day9),
+        10 => advent_of_code::day!(2022, opt.day, opt.puzzle, day10),
+        11 => advent_of_code::day!(2022, opt.day, opt.puzzle, day11),
+        // NEXT PART
+        _ => panic!("unknown day {}", opt.day),
+    }
+    Ok(())
+}