use std::collections::{HashMap, HashSet, VecDeque};
use std::env;
use std::fmt::Debug;
use std::fs;
use std::ops::{Range, RangeInclusive};
use std::path;
use std::{cmp::Ordering, fmt::Display};

use anyhow::{Error, Result};
use chrono::{Datelike, Local};
use itertools::Itertools;
use pico_args::Arguments;
use scraper::{Html, Selector};
use ureq::get;

fn get_aoc(suffix: impl Display) -> Result<String> {
    let url = format!("https://adventofcode.com/2022/day/{suffix}");
    let cookie = env::var("AOC_COOKIE")?;
    get(&url)
        .set("Cookie", &cookie)
        .call()?
        .into_string()
        .map_err(Error::new)
}

fn load_input(day: u32, small: bool) -> Result<String> {
    let suffix = if small { ".small" } else { "" };
    let path = format!("inputs/{day}{suffix}.txt");
    let path = path::Path::new(&path);
    if path.exists() {
        fs::read_to_string(path).map_err(Error::new)
    } else if small {
        let content = get_aoc(day)?;
        let dom = Html::parse_document(&content);
        let selector = Selector::parse("p + pre code").unwrap();
        for item in dom.select(&selector) {
            if item
                .parent()
                .unwrap()
                .prev_siblings()
                .nth(1)
                .unwrap()
                .children()
                .next()
                .unwrap()
                .value()
                .as_text()
                .unwrap()
                .contains("For example")
            {
                let content = item.text().collect();
                println!("downloaded and parsed example input for {day}");
                fs::write(path, &content)?;
                return Ok(content);
            }
        }
        Err(Error::msg(
            "had an oopsie parsing the example input for {day}",
        ))
    } else {
        let content = get_aoc(format!("{day}/input"))?;
        println!("downloaded input for day {day}");
        fs::write(path, &content)?;
        Ok(content)
    }
}

fn main() -> Result<()> {
    let mut args = Arguments::from_env();
    let small = args.contains("--small");
    let part = args.opt_free_from_str()?.unwrap_or(1);
    let day = args
        .opt_free_from_str()?
        .unwrap_or_else(|| Local::now().day());
    let input = load_input(day, small)?;
    println!("running day {day} part {part}");
    let result = SOLUTIONS[day as usize - 1][part as usize - 1](input);
    println!("{result}");
    Ok(())
}

macro_rules! solutions {
    ($($all:expr),*) => {
        const DAYS: usize = 0 $( + solutions!(@expand $all 1) )*;
        const SOLUTIONS: [Day; DAYS] = [
            $($all),*
        ];
    };
    (@expand $ignore:tt $e:expr) => {$e};
}

enum Output {
    Num(u64),
    Str(String),
}

impl Display for Output {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Output::Num(n) => write!(f, "{n}"),
            Output::Str(s) => write!(f, "{s}"),
        }
    }
}

impl From<u64> for Output {
    fn from(n: u64) -> Self {
        Self::Num(n)
    }
}

impl From<String> for Output {
    fn from(s: String) -> Self {
        Self::Str(s)
    }
}

type Part = fn(String) -> Output;
type Day = [Part; 2];
solutions! {
    [
        // day 1 part 1
        |input| {
            let lines = input.lines();
            let (max, _) = lines.fold((0, 0), |(max, sum), line| {
                if line.is_empty() {
                    (max.max(sum), 0)
                } else {
                    let cal = line.parse::<u64>().expect("Got bad line");
                    (max, sum + cal)
                }
            });
            max.into()
        },
        // day 1 part 2
        |input| {
            let lines = input.lines();
            let (a, b, c, _) = lines.fold((0, 0, 0, 0), |(a, b, c, sum), line| {
                if line.trim().is_empty() {
                    if sum > a {
                        (sum, a, b, 0)
                    } else if sum > b {
                        (a, sum, b, 0)
                    } else if sum > c {
                        (a, b, sum, 0)
                    } else {
                        (a, b, c, 0)
                    }
                } else {
                    let cal = line.trim().parse::<u64>().expect("Got bad line");
                    (a, b, c, sum + cal)
                }
            });
            (a + b + c).into()
        },
    ],
    [
        // day 2 part 1
        |input| {
            input
                .lines()
                .map(|line| {
                    let (you, me) = line.split_once(' ').expect("oof");
                    let (you, me) = (RPS::from_str(you), RPS::from_str(me));
                    RPS::score(you, me)
                })
                .sum::<u64>().into()
        },
        // day 2 part 2
        |input| {
            input
                .lines()
                .map(|line| {
                    let (you, out) = line.split_once(' ').expect("oof");
                    let (you, out) = (RPS::from_str(you), Outcome::from_str(out));
                    let me = out.requires(you);
                    RPS::score(you, me)
                })
                .sum::<u64>().into()
        },
    ],
    [
        // day 3 part 1
        |input| {
            input
                .lines()
                .map(|line| {
                    let line = String::from(line);
                    let rs = Rucksack::new(line);
                    rs.score()
                })
                .sum::<u64>().into()
        },
        // day 3 part 2
        |input| {
            let lines: Vec<_> = input.lines().collect();
            lines
                .chunks(3)
                .map(|chunks| match chunks {
                    [f, s, t] => {
                        let rs =
                            Rucksacks::new(String::from(*f), String::from(*s), String::from(*t));
                        rs.score()
                    }
                    _ => unreachable!("fooey"),
                })
                .sum::<u64>().into()
        },
    ],
    [
        // day 4 part 1
        |input| {
            (make_ranges(input)
                .iter()
                .filter(|(first, second)| {
                    range_contains(first, second) || range_contains(second, first)
                })
                .count() as u64).into()
        },
        // day 4 part 2
        |input| {
            (make_ranges(input)
                .iter()
                .filter(|(first, second)| range_overlaps(first, second) || range_overlaps(second, first))
                .count() as u64).into()
        },
    ],
    [
        // day 5 part 1
        |input| {
            let midpt = input.find("\n\n").unwrap();
            let stacks = make_stacks(&input[..=midpt]);
            let rules = make_rules(&input[midpt + 2..]);
            run_rules(stacks, rules).into()
        },
        // day 5 part 2
        |input| {
            let midpt = input.find("\n\n").unwrap();
            let stacks = make_stacks(&input[..=midpt]);
            let rules = make_rules(&input[midpt + 2..]);
            run_rules_9001(stacks, rules).into()
        },
    ],
    [
        // day 6 part 1
        |input| find_start_marker(input, 4).into(),
        // day 6 part 2
        |input| find_start_marker(input, 14).into(),
    ],
    [
        // day 7 part 1
        |input| {
            let cmds = make_commands(input);
            let dirs = produce_dirs(cmds);
            sum_dirs_at_most_100k(dirs).into()
        },
        // day 7 part 2
        |input| {
            let cmds = make_commands(input);
            let dirs = produce_dirs(cmds);
            find_smallest_big_dir(dirs).into()
        },
    ],
    [
        // day 8 part 1
        |input| {
            let map = map_trees(input);
            let len = map.len();
            let mut count: u64 = 4 * len as u64 - 4;
            for x in 1..len - 1 {
                for y in 1..len - 1 {
                    if is_visible(&map, x, y, len) {
                        count += 1;
                    }
                }
            }
            count.into()
        },
        // day 8 part 2
        |input| {
            let map = map_trees(input);
            let len = map.len();
            let mut max = 0;
            for x in 0..len {
                for y in 0..len {
                    let score = view_score(&map, x, y, len);
                    if score > max {
                        max = score;
                    }
                }
            }
            max.into()
        },
    ],
    [
        // day 9 part 1
        |input| {
            let motions = parse_motions(input);
            let visits = motion_visits(motions, 2);
            (visits.len() as u64).into()
        },
        // day 9 part 2
        |input| {
            let motions = parse_motions(input);
            let visits = motion_visits(motions, 10);
            (visits.len() as u64).into()
        },
    ],
    [
        // day 10 part 1
        |input| {
            let cmds = input.lines().map(Cmd::from_str).collect();
            Screen::new().get_signal_strength(cmds).into()
        },
        // day 10 part 2
        |input| {
            let cmds = input.lines().map(Cmd::from_str).collect();
            Screen::new().draw(cmds).to_string().into()
        }
    ],
    [
        // day 11 part 1
        |input| {
            let monkeys = input.split("\n\n").map(|s| Monkey::from_str(s, false)).collect();
            run_rounds(monkeys, 20).into()
        },
        // day 11 part 2
        |input| {
            let monkeys = input.split("\n\n").map(|s| Monkey::from_str(s, true)).collect();
            run_rounds(monkeys, 10000).into()
        }
    ],
    [
        // day 12 part 1
        |input| {
            let map = Map::from_string(input);
            map.navigate(map.start).unwrap().into()
        },
        // day 12 part 1
        |input| {
            let map = Map::from_string(input);
            map.best_navigate().into()
        },
    ],
    [
        // day 13 part 1
        |input| {
            let pairs = Value::make_value_pairs(input);
            sum_matching_pairs(pairs).into()
        },
        // day 13 part 2
        |input| {
            let values = input.lines().filter(|line| !line.is_empty()).map(Value::from_str).collect_vec();
            find_decoder_key(values).into()
        },
    ],
    [
        // day 14 part 1
        |input| {
            let lines = input.lines().map(make_points).flat_map(make_lines).collect_vec();
            Sandmap::from_lines(lines, false).drop_sand().into()
        },
        // day 14 part 2
        |input| {
            let lines = input.lines().map(make_points).flat_map(make_lines).collect_vec();
            Sandmap::from_lines(lines, true).fill_sand().into()
        }
    ],
    [
        // day 15 part 1
        |input| {
            todo!()
        },
        // day 15 part 2
        |input| {
            todo!()
        },
    ],
    [
        // day 16 part 1
        |input| {
            todo!()
        },
        // day 16 part 2
        |input| {
            todo!()
        },
    ]
}

fn make_points(line: &str) -> Vec<(usize, usize)> {
    line.split(" -> ")
        .map(|pair| {
            pair.split(',')
                .map(|n| n.parse::<usize>().unwrap())
                .collect_tuple()
                .unwrap()
        })
        .collect()
}

#[derive(Debug, Clone)]
enum Line {
    V { x: usize, ys: RangeInclusive<usize> },
    H { xs: RangeInclusive<usize>, y: usize },
}

fn make_range(start: usize, end: usize) -> RangeInclusive<usize> {
    if start > end {
        end..=start
    } else {
        start..=end
    }
}

fn make_lines(pts: Vec<(usize, usize)>) -> Vec<Line> {
    pts.into_iter()
        .tuple_windows()
        .map(|((start_x, start_y), (end_x, end_y))| {
            if start_x == end_x {
                Line::V {
                    x: start_x,
                    ys: make_range(start_y, end_y),
                }
            } else {
                Line::H {
                    xs: make_range(start_x, end_x),
                    y: start_y,
                }
            }
        })
        .collect()
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Tile {
    Rock,
    Empty,
    Sand,
}

impl Display for Tile {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let c = match self {
            Tile::Rock => '#',
            Tile::Empty => '.',
            Tile::Sand => 'o',
        };
        write!(f, "{c}")
    }
}

struct Sandmap {
    map: Vec<Vec<Tile>>,
    depth: usize,
    start: usize,
    entry: usize,
    end: usize,
}

impl Sandmap {
    fn _draw(&self) {
        for y in 0..self.map[0].len() {
            for x in 0..(self.end - self.start) + 1 {
                let tile = self.map[x][y];
                print!("{tile}")
            }
            println!()
        }
    }

    fn fill_sand(mut self) -> u64 {
        let mut n = 0;
        let (mut x, mut y) = self.drop_one_fill();
        while (x, y) != (self.entry, 0) {
            self.map[x][y] = Tile::Sand;
            n += 1;
            (x, y) = self.drop_one_fill();
        }
        n + 1
    }

    fn drop_sand(mut self) -> u64 {
        let mut n = 0;
        while let Some((x, y)) = self.drop_one() {
            self.map[x][y] = Tile::Sand;
            n += 1
        }
        n
    }

    fn drop_one_fill(&mut self) -> (usize, usize) {
        let mut sand = (self.entry, 0);
        while let Some(next) = self.gravity(sand) {
            if next == sand {
                return sand;
            }
            sand = next
        }
        let (x, _) = sand;
        let mut col = vec![Tile::Empty; self.depth + 1];
        col[self.depth] = Tile::Rock;
        if x < self.entry {
            self.map.insert(0, col);
            self.start -= 1;
            self.entry += 1;
            (0, self.depth - 1)
        } else {
            self.map.push(col);
            self.end += 1;
            (x + 1, self.depth - 1)
        }
    }

    fn drop_one(&self) -> Option<(usize, usize)> {
        let mut sand = (self.entry, 0);
        while let Some(next) = self.gravity(sand) {
            if next == sand {
                return Some(sand);
            }
            sand = next
        }
        None
    }

    fn gravity(&self, (x, y): (usize, usize)) -> Option<(usize, usize)> {
        if y == self.depth {
            None
        } else if self.map[x][y + 1] == Tile::Empty {
            Some((x, y + 1))
        } else if x == 0 {
            None
        } else if self.map[x - 1][y + 1] == Tile::Empty {
            Some((x - 1, y + 1))
        } else if x >= (self.end - self.start) {
            None
        } else if self.map[x + 1][y + 1] == Tile::Empty {
            Some((x + 1, y + 1))
        } else {
            Some((x, y))
        }
    }

    fn from_lines(mut lines: Vec<Line>, with_floor: bool) -> Self {
        let (min_x, max_x, mut max_y) =
            lines
                .iter()
                .cloned()
                .fold((500, 500, 0), |(min_x, max_x, max_y), line| match line {
                    Line::V { x, ys } => (min_x.min(x), max_x.max(x), max_y.max(*ys.end())),
                    Line::H { xs, y } => {
                        (min_x.min(*xs.start()), max_x.max(*xs.end()), max_y.max(y))
                    }
                });
        if with_floor {
            max_y += 2;
            lines.push(Line::H {
                xs: min_x..=max_x,
                y: max_y,
            })
        }
        let mut map = vec![vec![Tile::Empty; max_y + 1]; max_x - min_x + 1];
        for line in lines {
            match line {
                Line::V { x, ys } => {
                    for y in ys {
                        map[x - min_x][y] = Tile::Rock;
                    }
                }
                Line::H { xs, y } => {
                    for x in xs {
                        map[x - min_x][y] = Tile::Rock;
                    }
                }
            }
        }
        Self {
            map,
            depth: max_y,
            start: min_x,
            entry: 500 - min_x,
            end: max_x,
        }
    }
}

fn find_decoder_key(mut values: Vec<Value>) -> u64 {
    let (p1, p2) = Value::divider_packets();
    values.extend([p1.clone(), p2.clone()]);
    values.sort();
    let k1 = values.iter().position(|v| *v == p1).unwrap() + 1;
    let k2 = values.iter().position(|v| *v == p2).unwrap() + 1;
    (k1 * k2) as u64
}

fn sum_matching_pairs(pairs: Vec<(Value, Value)>) -> u64 {
    pairs
        .iter()
        .map(|(left, right)| left.is_ordered(right))
        .enumerate()
        .filter_map(|(i, ob)| {
            if ob.is_some() && ob.unwrap() {
                Some(1 + i as u64)
            } else {
                None
            }
        })
        .sum()
}

fn split_list(input: &str) -> Vec<&str> {
    let mut items = vec![];
    let mut start = 1;
    let mut list_depth = 0;
    for i in 1..input.len() {
        match &input[i..i + 1] {
            "," if list_depth == 0 => {
                items.push(&input[start..i]);
                start = i + 1;
            }
            "[" => list_depth += 1,
            "]" => list_depth -= 1,
            _ => {}
        }
    }
    items.push(&input[start..input.len() - 1]);
    items
}

#[derive(Debug, Clone, PartialEq, Eq)]
enum Value {
    List(Vec<Value>),
    Number(u64),
}

impl PartialOrd for Value {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        if self == other {
            Some(Ordering::Equal)
        } else if self
            .is_ordered(other)
            .expect("Bad is_ordered in partial_cmp")
        {
            Some(Ordering::Less)
        } else {
            Some(Ordering::Greater)
        }
    }
}

impl Ord for Value {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

impl Value {
    fn wrap_list(self) -> Value {
        Value::List(vec![self])
    }

    fn divider_packets() -> (Value, Value) {
        (
            Value::Number(2).wrap_list().wrap_list(),
            Value::Number(6).wrap_list().wrap_list(),
        )
    }

    fn make_value_pairs(input: String) -> Vec<(Value, Value)> {
        input
            .trim()
            .split("\n\n")
            .map(|pair| {
                pair.split('\n')
                    .filter(|s| !s.is_empty())
                    .map(Value::from_str)
                    .next_tuple()
                    .unwrap()
            })
            .collect()
    }

    fn from_str(input: &str) -> Value {
        if input.starts_with('[') {
            let items = if input == "[]" {
                Vec::new()
            } else {
                split_list(input).into_iter().map(Self::from_str).collect()
            };
            Value::List(items)
        } else {
            let n = input.parse::<u64>().expect(input);
            Value::Number(n)
        }
    }

    fn is_ordered(&self, right: &Value) -> Option<bool> {
        match (self, right) {
            (Value::Number(left), Value::Number(right)) => {
                if left == right {
                    None
                } else {
                    Some(left < right)
                }
            }
            (Value::List(left), Value::List(right)) => {
                let mut left = left.iter();
                let mut right = right.iter();
                loop {
                    match (left.next(), right.next()) {
                        (None, None) => return None,
                        (None, Some(_)) => return Some(true),
                        (Some(_), None) => return Some(false),
                        (Some(left), Some(right)) => {
                            if let Some(b) = left.is_ordered(right) {
                                return Some(b);
                            }
                        }
                    }
                }
            }
            (Value::List(_), Value::Number(_)) => self.is_ordered(&right.clone().wrap_list()),
            (Value::Number(_), Value::List(_)) => self.clone().wrap_list().is_ordered(right),
        }
    }
}

#[derive(Debug)]
struct Map {
    map: Vec<Vec<isize>>,
    start: (usize, usize),
    end: (usize, usize),
}

impl Map {
    fn best_navigate(self) -> u64 {
        self.map
            .iter()
            .enumerate()
            .flat_map(|(x, row)| {
                row.iter()
                    .enumerate()
                    .map(move |(y, level)| (x, y, *level))
                    .filter_map(|(x, y, level)| if level == 0 { Some((x, y)) } else { None })
            })
            .flat_map(|start| self.navigate(start))
            .min()
            .unwrap()
    }

    fn navigate(&self, start: (usize, usize)) -> Option<u64> {
        let mut q = VecDeque::new();
        let mut visited = HashSet::new();
        visited.insert(start);
        q.push_back((start, 0));
        while !q.is_empty() {
            let ((x, y), steps) = q.pop_front().unwrap();
            let level = self.map[x][y];
            if (x, y) == self.end {
                return Some(steps);
            }
            for (nx, ny, nlevel) in self.neighbors(x, y) {
                if !visited.contains(&(nx, ny)) && nlevel <= level + 1 {
                    visited.insert((nx, ny));
                    q.push_back(((nx, ny), steps + 1))
                }
            }
        }
        None
    }

    fn neighbors(&self, x: usize, y: usize) -> impl Iterator<Item = (usize, usize, isize)> {
        let mut ns = vec![];
        if x > 0 {
            ns.push((x - 1, y, self.map[x - 1][y]))
        }
        if x < self.map.len() - 1 {
            ns.push((x + 1, y, self.map[x + 1][y]))
        }
        if y > 0 {
            ns.push((x, y - 1, self.map[x][y - 1]))
        }
        if y < self.map[0].len() - 1 {
            ns.push((x, y + 1, self.map[x][y + 1]))
        }
        ns.into_iter()
    }

    fn from_string(input: String) -> Self {
        let mut map = vec![];
        let mut start = (0, 0);
        let mut end = (0, 0);
        for (row, line) in input.trim().lines().enumerate() {
            let new_row = line
                .chars()
                .enumerate()
                .map(|(col, c)| match c {
                    'S' => {
                        start = (row, col);
                        0
                    }
                    'E' => {
                        end = (row, col);
                        25
                    }
                    _ => c as isize - 'a' as isize,
                })
                .collect();
            map.push(new_row);
        }
        Map { map, start, end }
    }
}

fn run_rounds(mut monkeys: Vec<Monkey>, n: usize) -> u64 {
    let mod_factor: usize = monkeys.iter().map(|m| m.test).product();
    let mut counts = vec![0; monkeys.len()];
    for round in 1..=n {
        let next = run_round(&mut monkeys, mod_factor);
        counts = next.iter().zip(counts).map(|(x, y)| x + y).collect();
        if round % 1000 == 0 || round == 20 || round == 1 {}
    }
    counts.sort();
    counts[counts.len() - 1] * counts[counts.len() - 2]
}

fn run_round(monkeys: &mut Vec<Monkey>, mod_factor: usize) -> Vec<u64> {
    let mut inspects = vec![];
    for i in 0..monkeys.len() {
        let monkey = &mut monkeys[i];
        let throws = monkey.take_turn(mod_factor);
        inspects.push(throws.len() as u64);
        for (to, item) in throws {
            monkeys[to].items.push(item)
        }
    }
    inspects
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
enum OpType {
    Add,
    Mul,
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Op {
    op_type: OpType,
    operand: Option<usize>,
}

impl Op {
    fn operand(s: &str) -> Option<usize> {
        match s {
            "old" => None,
            _ => Some(s.parse::<usize>().unwrap()),
        }
    }

    fn from_str(s: &str) -> Self {
        let (op_type, y) = s.split_once(' ').unwrap();
        Self {
            op_type: match op_type {
                "+" => OpType::Add,
                "*" => OpType::Mul,
                _ => unreachable!("whoa"),
            },
            operand: Self::operand(y),
        }
    }

    fn apply(&self, old: usize) -> usize {
        let operand = self.operand.unwrap_or(old);
        match self.op_type {
            OpType::Add => old.wrapping_add(operand),
            OpType::Mul => old.wrapping_mul(operand),
        }
    }
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Monkey {
    items: Vec<usize>,
    operation: Op,
    test: usize,
    throw_true: usize,
    throw_false: usize,
    part_two: bool,
}

impl Monkey {
    fn from_str(s: &str, part_two: bool) -> Self {
        let (_, s) = s.split_once('\n').unwrap();
        let (items, s) = s.split_once('\n').unwrap();
        let (operation, s) = s.split_once('\n').unwrap();
        let (test, s) = s.split_once('\n').unwrap();
        let (throw_true, throw_false) = s.split_once('\n').unwrap();
        Monkey {
            items: items
                .strip_prefix("  Starting items: ")
                .unwrap()
                .split(", ")
                .map(|n| n.parse::<usize>().unwrap())
                .collect(),
            operation: Op::from_str(operation.strip_prefix("  Operation: new = old ").unwrap()),
            test: test
                .strip_prefix("  Test: divisible by ")
                .unwrap()
                .parse::<usize>()
                .unwrap(),
            throw_true: throw_true
                .strip_prefix("    If true: throw to monkey ")
                .unwrap()
                .parse::<usize>()
                .unwrap(),
            throw_false: throw_false
                .strip_prefix("    If false: throw to monkey ")
                .unwrap()
                .trim()
                .parse::<usize>()
                .unwrap(),
            part_two,
        }
    }

    fn take_turn(&mut self, mod_factor: usize) -> Vec<(usize, usize)> {
        self.items
            .drain(..)
            .map(|item| {
                let level = self.operation.apply(item);
                let level = if self.part_two {
                    level % mod_factor
                } else {
                    level / 3
                };
                if level % self.test == 0 {
                    (self.throw_true, level)
                } else {
                    (self.throw_false, level)
                }
            })
            .collect()
    }
}

struct Screen {
    x: isize,
    cycle: isize,
    strength: isize,
    output: String,
}

impl Screen {
    fn new() -> Self {
        Screen {
            x: 1,
            cycle: 1,
            strength: 0,
            output: String::new(),
        }
    }

    fn step_cycle(&mut self) {
        println!("cycle {}, x={}", self.cycle, self.x);
        self.cycle += 1;
        if (self.cycle - 20) % 40 == 0 {
            println!(
                "cycle {}, x={}, signal={}",
                self.cycle,
                self.x,
                self.x * self.cycle
            );
            self.strength += self.x * self.cycle;
        }
    }

    fn get_signal_strength(&mut self, cmds: Vec<Cmd>) -> u64 {
        for cmd in cmds {
            match cmd {
                Cmd::Noop => self.step_cycle(),
                Cmd::Addx(n) => {
                    self.step_cycle();
                    self.x += n;
                    self.step_cycle();
                }
            }
        }
        self.strength as u64
    }

    fn draw_cycle(&mut self) {
        let coord = (self.cycle - 1) % 40;
        let sprite = self.x - 1..=self.x + 1;
        if sprite.contains(&coord) {
            self.output.push('#');
        } else {
            self.output.push('.');
        }
        if self.cycle % 40 == 0 {
            self.output.push('\n')
        }
        self.cycle += 1
    }

    fn draw(&mut self, cmds: Vec<Cmd>) -> &str {
        for cmd in cmds {
            match cmd {
                Cmd::Noop => self.draw_cycle(),
                Cmd::Addx(n) => {
                    self.draw_cycle();
                    self.draw_cycle();
                    self.x += n;
                }
            }
        }
        &self.output
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum Cmd {
    Noop,
    Addx(isize),
}

impl Cmd {
    fn from_str(s: &str) -> Self {
        match s {
            "noop" => Cmd::Noop,
            _ => Cmd::Addx(s[5..].parse::<isize>().unwrap()),
        }
    }
}

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Pos {
    x: isize,
    y: isize,
}

struct Rope {
    knots: Vec<Pos>,
    tail: usize,
}

impl Rope {
    fn head(&mut self) -> &mut Pos {
        &mut self.knots[0]
    }

    fn tail(&mut self) -> &mut Pos {
        &mut self.knots[self.tail]
    }

    fn pull(&mut self) {
        for i in 0..self.tail {
            let head = self.knots[i];
            let tail = self.knots[i + 1];
            self.knots[i + 1] = move_tail(head, tail);
        }
    }
}

fn move_tail(head: Pos, tail: Pos) -> Pos {
    let diff_x = head.x - tail.x;
    let diff_y = head.y - tail.y;
    if diff_x.abs() < 2 && diff_y.abs() < 2 {
        tail
    } else if diff_y == 0 {
        Pos {
            x: tail.x + (diff_x / diff_x.abs()),
            ..tail
        }
    } else if diff_x == 0 {
        Pos {
            y: tail.y + (diff_y / diff_y.abs()),
            ..tail
        }
    } else {
        Pos {
            x: tail.x + (diff_x / diff_x.abs()),
            y: tail.y + (diff_y / diff_y.abs()),
        }
    }
}

fn motion_visits(motions: Vec<Motion>, n_knots: usize) -> HashMap<Pos, u64> {
    let mut map = HashMap::new();
    let pos = Pos { x: 0, y: 0 };
    let mut rope = Rope {
        knots: vec![pos; n_knots],
        tail: n_knots - 1,
    };
    map.insert(pos, 1);
    for motion in motions {
        for _ in 0..motion.len {
            match motion.dir {
                Dir::U => rope.head().y += 1,
                Dir::D => rope.head().y -= 1,
                Dir::L => rope.head().x -= 1,
                Dir::R => rope.head().x += 1,
            }
            rope.pull();
            if let Some(n) = map.get(&pos) {
                map.insert(*rope.tail(), *n + 1);
            } else {
                map.insert(*rope.tail(), 1);
            }
        }
    }
    map
}

fn parse_motions(input: String) -> Vec<Motion> {
    input
        .lines()
        .map(|line| {
            let (dir, len) = line.split_once(' ').unwrap();
            let dir = match dir {
                "U" => Dir::U,
                "D" => Dir::D,
                "L" => Dir::L,
                "R" => Dir::R,
                _ => unreachable!("ohno"),
            };
            let len = len.parse::<isize>().unwrap();
            Motion { dir, len }
        })
        .collect()
}

struct Motion {
    dir: Dir,
    len: isize,
}

#[derive(Debug)]
enum Dir {
    U,
    D,
    L,
    R,
}

fn view_length(
    me: u8,
    map: &[Vec<u8>],
    xs: impl Iterator<Item = usize> + Debug,
    ys: impl Iterator<Item = usize> + Clone + Debug,
) -> u64 {
    let mut len = 0;
    for x in xs {
        for y in ys.clone() {
            if map[x][y] >= me {
                return len + 1;
            }
            len += 1;
        }
    }
    len
}

fn view_score(map: &[Vec<u8>], x: usize, y: usize, len: usize) -> u64 {
    let me = map[x][y];
    view_length(me, map, (0..x).rev(), y..y + 1)
        * view_length(me, map, x + 1..len, y..y + 1)
        * view_length(me, map, x..x + 1, (0..y).rev())
        * view_length(me, map, x..x + 1, y + 1..len)
}

fn is_visible_single(me: u8, map: &[Vec<u8>], xs: Range<usize>, ys: Range<usize>) -> bool {
    for x in xs {
        for y in ys.clone() {
            if map[x][y] >= me {
                return false;
            }
        }
    }
    true
}

fn is_visible(map: &[Vec<u8>], x: usize, y: usize, len: usize) -> bool {
    let me = map[x][y];
    is_visible_single(me, map, 0..x, y..y + 1)
        || is_visible_single(me, map, x + 1..len, y..y + 1)
        || is_visible_single(me, map, x..x + 1, 0..y)
        || is_visible_single(me, map, x..x + 1, y + 1..len)
}

fn map_trees(input: String) -> Vec<Vec<u8>> {
    input
        .lines()
        .map(|line| line.chars().map(to_digit).collect())
        .collect()
}

fn to_digit(c: char) -> u8 {
    c as u8 - 48
}

fn find_smallest_big_dir(mut dirs: HashMap<String, u64>) -> u64 {
    let total = 70_000_000;
    let wants = 30_000_000;
    let used = dirs.remove("").unwrap();
    let free = total - used;
    let diff = wants - free;
    dirs.into_iter()
        .filter_map(|(_, v)| if v > diff { Some(v) } else { None })
        .min()
        .unwrap()
}

fn sum_dirs_at_most_100k(dirs: HashMap<String, u64>) -> u64 {
    dirs.into_iter()
        .filter_map(|(_, v)| if v < 100_000 { Some(v) } else { None })
        .sum()
}

fn produce_dirs(commands: Vec<Command>) -> HashMap<String, u64> {
    let mut map = HashMap::new();
    let mut path = vec![String::new()];
    for command in commands {
        match command {
            Command::Cd(cd) => match cd {
                Path::Root => path = vec![String::new()],
                Path::Parent => {
                    path.pop();
                }
                Path::Named(dir) => path.push(dir),
            },
            Command::Ls(entries) => {
                for Entry::File(size) in entries {
                    let mut new_path = String::new();
                    for part in path.iter() {
                        new_path.push_str(part);
                        if let Some(n) = map.get(&new_path) {
                            map.insert(new_path.clone(), n + size);
                        } else {
                            map.insert(new_path.clone(), size);
                        }
                        new_path.push('/')
                    }
                }
            }
        }
    }
    map
}

fn make_commands(input: String) -> Vec<Command> {
    let mut commands = vec![];
    let mut lines = input.lines().peekable();
    while lines.peek().is_some() {
        let next = lines.next().unwrap();
        commands.push(match &next[2..4] {
            "cd" => {
                let path = match &next[5..] {
                    "/" => Path::Root,
                    ".." => Path::Parent,
                    name => Path::Named(name.into()),
                };
                Command::Cd(path)
            }
            "ls" => {
                let mut entries = vec![];
                while let Some(line) = lines.peek() {
                    if line.starts_with('$') {
                        break;
                    }
                    let line = lines.next().unwrap();
                    if line.starts_with("dir") {
                        // woop
                    } else {
                        let (size, _) = line.split_once(' ').unwrap();
                        entries.push(Entry::File(size.parse::<u64>().unwrap()))
                    }
                }
                Command::Ls(entries)
            }
            erg => unreachable!("{erg}"),
        })
    }
    commands
}

#[derive(Debug)]
enum Command {
    Cd(Path),
    Ls(Vec<Entry>),
}

#[derive(Debug)]
enum Path {
    Root,
    Parent,
    Named(String),
}

#[derive(Debug)]
enum Entry {
    File(u64),
}

fn find_start_marker(input: String, window_size: usize) -> u64 {
    for i in 0..input.len() - window_size {
        let window = &input[i..i + window_size];
        let set: HashSet<char> = HashSet::from_iter(window.chars());
        if set.len() == window_size {
            return (i + window_size) as u64;
        }
    }
    unreachable!()
}

fn run_rules_9001(mut stacks: Vec<Vec<char>>, rules: Vec<Rule>) -> String {
    for rule in rules {
        let total = stacks[rule.from - 1].len();
        let mut moved = stacks[rule.from - 1].drain((total - rule.n)..).collect();
        stacks[rule.to - 1].append(&mut moved);
    }
    let mut s = String::new();
    for stack in stacks {
        s.push(*stack.last().unwrap())
    }
    s
}

fn run_rules(mut stacks: Vec<Vec<char>>, rules: Vec<Rule>) -> String {
    for rule in rules {
        for _ in 0..rule.n {
            let c = stacks[rule.from - 1].pop().unwrap();
            stacks[rule.to - 1].push(c);
        }
    }
    let mut s = String::new();
    for stack in stacks {
        s.push(*stack.last().unwrap())
    }
    s
}

fn make_stacks(input: &str) -> Vec<Vec<char>> {
    let n = (input.find('\n').unwrap()) / 4 + 1;
    let mut stacks = vec![vec![]; n];
    input
        .lines()
        .rev()
        .filter(|line| line.trim().starts_with('['))
        .for_each(|line| {
            for (idx, cr8) in line.chars().skip(1).step_by(4).enumerate() {
                if cr8 != ' ' {
                    stacks[idx].push(cr8);
                }
            }
        });
    stacks
}

#[derive(Debug)]
struct Rule {
    n: usize,
    from: usize,
    to: usize,
}

impl Rule {
    fn new(raw: Vec<usize>) -> Self {
        Self {
            n: raw[0],
            from: raw[1],
            to: raw[2],
        }
    }
}

fn make_rules(input: &str) -> Vec<Rule> {
    input
        .lines()
        .map(|line| {
            line.split_whitespace()
                .skip(1)
                .step_by(2)
                .map(|num| num.parse::<usize>().unwrap())
                .collect()
        })
        .map(Rule::new)
        .collect()
}

fn make_ranges(input: String) -> Vec<(RangeInclusive<u64>, RangeInclusive<u64>)> {
    input
        .lines()
        .map(|line| {
            line.split(',')
                .map(|range| {
                    range
                        .split('-')
                        .map(|num| num.parse::<u64>().expect("bad num :/"))
                })
                .map(|mut nums| {
                    let lo = nums.next().expect("nolo :/");
                    let hi = nums.next().expect("nohi :/");
                    lo..=hi
                })
        })
        .map(|mut ranges| {
            let f = ranges.next().unwrap();
            let s = ranges.next().unwrap();
            (f, s)
        })
        .collect()
}

fn range_contains(r1: &RangeInclusive<u64>, r2: &RangeInclusive<u64>) -> bool {
    r1.start() <= r2.start() && r1.end() >= r2.end()
}

fn range_overlaps(r1: &RangeInclusive<u64>, r2: &RangeInclusive<u64>) -> bool {
    r1.contains(r2.start())
}

#[derive(Copy, Clone, PartialEq, Eq)]
enum RPS {
    Rock,
    Paper,
    Scissors,
}

impl RPS {
    fn from_str(s: &str) -> Self {
        match s {
            "A" | "X" => RPS::Rock,
            "B" | "Y" => RPS::Paper,
            "C" | "Z" => RPS::Scissors,
            _ => unreachable!("you did a bad thing"),
        }
    }

    fn win(self) -> RPS {
        match self {
            RPS::Rock => RPS::Scissors,
            RPS::Paper => RPS::Rock,
            RPS::Scissors => RPS::Paper,
        }
    }

    fn lose(self) -> RPS {
        match self {
            RPS::Rock => RPS::Paper,
            RPS::Paper => RPS::Scissors,
            RPS::Scissors => RPS::Rock,
        }
    }

    fn cmp(self, other: Self) -> Ordering {
        if self == other {
            Ordering::Equal
        } else if self.win() == other {
            Ordering::Greater
        } else {
            Ordering::Less
        }
    }

    fn score(you: Self, me: Self) -> u64 {
        let base = match me {
            RPS::Rock => 1,
            RPS::Paper => 2,
            RPS::Scissors => 3,
        };
        let win = match RPS::cmp(me, you) {
            Ordering::Less => 0,
            Ordering::Equal => 3,
            Ordering::Greater => 6,
        };
        base + win
    }
}

#[derive(Copy, Clone)]
enum Outcome {
    Win,
    Draw,
    Lose,
}

impl Outcome {
    fn from_str(s: &str) -> Self {
        match s {
            "X" => Outcome::Lose,
            "Y" => Outcome::Draw,
            "Z" => Outcome::Win,
            _ => unreachable!("yikes"),
        }
    }

    fn requires(self, you: RPS) -> RPS {
        match self {
            Outcome::Win => you.lose(),
            Outcome::Draw => you,
            Outcome::Lose => you.win(),
        }
    }
}

struct Rucksack {
    first: HashSet<char>,
    second: HashSet<char>,
}

impl Rucksack {
    fn new(mut input: String) -> Self {
        assert!(input.len() % 2 == 0);
        let second = input.split_off(input.len() / 2).chars().collect();
        Self {
            first: input.chars().collect(),
            second,
        }
    }

    fn overlap(&self) -> HashSet<&char> {
        self.first.intersection(&self.second).collect()
    }

    fn score(&self) -> u64 {
        self.overlap().into_iter().copied().map(score_char).sum()
    }
}

struct Rucksacks {
    first: HashSet<char>,
    second: HashSet<char>,
    third: HashSet<char>,
}

impl Rucksacks {
    fn new(f: String, s: String, t: String) -> Self {
        Rucksacks {
            first: f.chars().collect(),
            second: s.chars().collect(),
            third: t.chars().collect(),
        }
    }

    fn intersection(&self) -> HashSet<char> {
        let start: HashSet<_> = self.first.intersection(&self.second).copied().collect();
        start.intersection(&self.third).copied().collect()
    }

    fn score(&self) -> u64 {
        self.intersection().into_iter().map(score_char).sum()
    }
}

fn score_char(c: char) -> u64 {
    if c.is_lowercase() {
        c as u64 - 96
    } else {
        c as u64 - 38
    }
}