from re import findall


def folding(axis: str, number: int) -> list:
    folded = list()
    for n in range(1, number + 1):
        for x, y in set(dots):
            if axis == "x" and x in (number - n, number + n):
                folded.append((number - n, y))
            elif axis == "y" and y in (number - n, number + n):
                folded.append((x, number - n))
    return folded


def visualing() -> None:
    max_x, max_y = [max(el) + 1 for el in [*zip(*dots)]]
    for y in range(max_y):
        for x in range(max_x):
            print("#" if (x, y) in dots else " ", end="")
        print("\n", end="")
    print()


dots = list()
actions = list()
instructions = False

for line in open("input.txt").read().splitlines():
    if not line:
        instructions = True
        continue
    if instructions:
        axis, number = findall(r"([xy])=(\d+)", line)[0]
        actions.append((axis, int(number)))
    else:
        dots.append(tuple(map(int, findall(r"\d+", line))))

for number, action in enumerate(actions):
    dots = folding(*action)
    if number == 1:
        print("Part One:", len(dots))

print("Part Two:")
visualing()

from collections import Counter

polymer, _, *rules = open("input.txt").read().splitlines()
rules = dict(rule.split(" -> ") for rule in rules)
pairs = Counter(polymer[i] + polymer[i + 1] for i in range(len(polymer) - 1))
chars = Counter(polymer)
steps = (10, 40)

for i in range(1, steps[-1] + 1):
    for (a, b), count in pairs.copy().items():
        if a + b in rules.keys():
            insert = rules[a + b]
            pairs[a + b] -= count
            pairs[a + insert] += count
            pairs[insert + b] += count
            chars[insert] += count
    if i in steps:
        print("Answer:", max(chars.values()) - min(chars.values()))

#[derive(Copy, Clone)]
pub enum Fold {
    X,
    Y,
}

#[derive(Clone)]
pub struct InvisiblePaper {
    dots: std::collections::HashSet<(i32, i32)>,
    folds: Vec<(Fold, i32)>,
}

impl InvisiblePaper {
    fn do_fold(&mut self, fold: (Fold, i32)) {
        self.dots = self.dots
                        .iter()
                        .map(|dot|
                            match fold.0 {
                                Fold::X => (fold.1 - (fold.1-dot.0).abs(), dot.1),
                                Fold::Y => (dot.0, fold.1 - (fold.1-dot.1).abs()),
                            })
                        .collect();
    }
}

pub fn parse_input(input: &str) -> InvisiblePaper {
    let lines = input.lines();
    let mut dots_done = false;
    let mut data = InvisiblePaper {
        dots: std::collections::HashSet::new(), 
        folds: Vec::new(),
    };
    for line in lines {
        if line.is_empty() {
            dots_done = true;
        } else {
            if !dots_done {
                let mut dot = line.split(',');
                data.dots.insert((dot.next().unwrap().parse().unwrap(),
                                dot.next().unwrap().parse().unwrap()));
            } else {
                let mut fold = line.split('=');
                let fold_type = if fold.next().unwrap().chars().nth(11)==Some('x') {
                    Fold::X
                } else {
                    Fold::Y
                };
                data.folds.push((fold_type,fold.next().unwrap().parse().unwrap()));
            }
        }
    }
    data
}

pub fn task1(data: &InvisiblePaper) -> usize {
    let mut data = data.clone();
    data.do_fold(data.folds[0]);
    data.dots.len()
}

pub fn task2(data: &InvisiblePaper) -> usize {
    let folds = &data.folds;
    let mut data = data.clone();
    for &fold in folds {
        data.do_fold(fold);
    }
    let max_x = data.dots.iter().map(|(x, _)|x).max().unwrap() + 1;
    let max_y = data.dots.iter().map(|(_, y)|y).max().unwrap() + 1;
    for y in 0..max_y {
        for x in 0..max_x {
            print!("{}", if data.dots.contains(&(x,y)) {"#"} else {"."});
        }
        println!("");
    }
    0
}

#[derive(Clone)]
pub struct PolymerData {
    polymer: Vec<char>,
    rules: std::collections::HashMap<(char, char), char>,
}

pub fn parse_input(input: &str) -> PolymerData {
    let mut lines = input.lines();
    let mut polymer_data = PolymerData {
        polymer: lines.next().unwrap().chars().collect(),
        rules: std::collections::HashMap::new(),
    };
    lines.next();
    for line in lines {
        let mut parts = line.split(" -> ");
        let left = parts.next().unwrap();
        let right = parts.next().unwrap();
        polymer_data.rules.insert(
            (left.chars().nth(0).unwrap(), left.chars().nth(1).unwrap()),
            right.chars().nth(0).unwrap(),
        );
    }
    polymer_data
}

pub fn task1(data: &PolymerData) -> usize {
    let mut polymer = data.polymer.clone();
    for _ in 0..10 {
        let mut new_polymer = vec![polymer[0]];
        for pair in polymer.windows(2) {
            if let &[left, right] = pair {
                match data.rules.get(&(left, right)) {
                    Some(&v) => new_polymer.push(v),
                    _ => (),
                }
                new_polymer.push(right);
            }
        }
        polymer = new_polymer;
    }

    let mut counter = std::collections::HashMap::new();
    for element in polymer {
        *counter.entry(element).or_insert(0) += 1;
    }
    let min = counter.values().min().unwrap();
    let max = counter.values().max().unwrap();
    max - min
}

pub fn task2(data: &PolymerData) -> usize {
    let mut polymer = data.polymer.clone();
    for _ in 0..40 {
        let mut new_polymer = vec![polymer[0]];
        for pair in polymer.windows(2) {
            if let &[left, right] = pair {
                match data.rules.get(&(left, right)) {
                    Some(&v) => new_polymer.push(v),
                    _ => (),
                }
                new_polymer.push(right);
            }
        }
        polymer = new_polymer;
    }

    let mut counter = std::collections::HashMap::new();
    for element in polymer {
        *counter.entry(element).or_insert(0) += 1;
    }
    let min = counter.values().min().unwrap();
    let max = counter.values().max().unwrap();
    max - min
}

type Counter = std::collections::HashMap<char, usize>;

type Polymer = Vec<char>;
type PolymerRules = std::collections::HashMap<(char, char), char>;

#[derive(Clone)]
pub struct PolymerData {
    polymer: Polymer,
    rules: PolymerRules,
    counters: std::collections::HashMap<(char, char, usize), Counter>,
}

impl PolymerData {
    fn from_str(input: &str) -> PolymerData {
        let mut lines = input.lines();
        let mut polymer_data = PolymerData {
            polymer: lines.next().unwrap().chars().collect(),
            rules: std::collections::HashMap::new(),
            counters: std::collections::HashMap::new(),
        };
        lines.next();
        for line in lines {
            let mut parts = line.split(" -> ");
            let left = parts.next().unwrap();
            let right = parts.next().unwrap();
            polymer_data.rules.insert(
                (left.chars().nth(0).unwrap(), left.chars().nth(1).unwrap()),
                right.chars().nth(0).unwrap(),
            );
        }
        polymer_data
    }

    fn composition_recursive(&mut self, polymer: (char, char), steps: usize) -> Counter {
        let (left, right) = polymer;
        if !self.counters.contains_key(&(left, right, steps)) {
            let counters = if steps == 0 {
                [(right, 1)].into()
            } else {
                match self.rules.get(&(left, right)) {
                    Some(&v) => {
                        let mut left = self.composition_recursive((left, v), steps - 1);
                        for (element, count) in self.composition_recursive((v, right), steps - 1) {
                            *left.entry(element).or_insert(0) += count;
                        }
                        left
                    }
                    None => [(right, 1)].into(),
                }
            };
            self.counters.insert((left, right, steps), counters);
        }
        self.counters.get(&(left, right, steps)).unwrap().clone()
    }

    fn composition(&mut self, steps: usize) -> usize {
        let mut counter: Counter = [(self.polymer[0], 1)].into();
        for i in 0..self.polymer.len() - 1 {
            for (element, count) in
                self.composition_recursive((self.polymer[i], self.polymer[i + 1]), steps)
            {
                *counter.entry(element).or_insert(0) += count;
            }
        }

        let min = counter.values().min().unwrap();
        let max = counter.values().max().unwrap();
        max - min
    }
}

pub fn parse_input(input: &str) -> PolymerData {
    PolymerData::from_str(input)
}

fn task(data: &PolymerData, steps: usize) -> usize {
    let mut data = data.clone();
    data.composition(steps)
}

pub fn task1(data: &PolymerData) -> usize {
    task(data, 10)
}

pub fn task2(data: &PolymerData) -> usize {
    task(data, 40)
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_task1() {
        let input = "NNCB

CH -> B
HH -> N
CB -> H
NH -> C
HB -> C
HC -> B
HN -> C
NN -> C
BH -> H
NC -> B
NB -> B
BN -> B
BB -> N
BC -> B
CC -> N
CN -> C";

        assert_eq!(task1(&parse_input(input)), 1588);
    }
}

pub enum PacketContent {
    Literal(usize),
    Operator(Box<Vec<Packet>>),
}

pub struct Packet {
    version: u8,
    type_id: u8,
    content: PacketContent,
}

const LITERAL_ID: u8 = 4;
const BIT_LENGTH_SIZE: usize = 15;
const PACKETS_COUNT_SIZE: usize = 11;

#[derive(Debug)]
enum Error {
    UnexpectedEndOfStream,
}

fn get_number(input: &[u8]) -> usize {
    let mut number = 0_usize;
    for &bit in input {
        number = number << 1 | bit as usize;
    }
    number
}

fn parse_packet(input: &[u8]) -> Result<(Packet, &[u8]), Error> {
    if input.len() < 7 {
        return Err(Error::UnexpectedEndOfStream);
    }
    let version = get_number(&input[..3]) as u8;
    let type_id = get_number(&input[3..6]) as u8;
    if type_id == LITERAL_ID {
        let mut number = 0;
        let mut ptr = 6;
        loop {
            let next_part = get_number(&input[ptr..ptr + 5]);
            ptr += 5;
            number = (number << 4) | (next_part & 0xF);
            if next_part & 0x10 == 0 {
                break;
            }
        }
        Ok((
            Packet {
                version,
                type_id,
                content: PacketContent::Literal(number),
            },
            &input[ptr..],
        ))
    } else {
        let length_type_id = get_number(&input[6..7]);
        match length_type_id {
            0 => {
                let header_end = 7 + BIT_LENGTH_SIZE;
                let bit_length = get_number(&input[7..header_end]);
                let mut subpackets = Box::new(vec![]);
                let mut own_input = &input[header_end..header_end + bit_length];
                while own_input.len() > 0 {
                    let (packet, rest) = parse_packet(own_input)?;
                    subpackets.push(packet);
                    own_input = rest;
                }
                Ok((
                    Packet {
                        version,
                        type_id,
                        content: PacketContent::Operator(subpackets),
                    },
                    &input[header_end + bit_length..],
                ))
            }
            1 => {
                let header_end = 7 + PACKETS_COUNT_SIZE;
                let packet_count = get_number(&input[7..header_end]);
                let mut subpackets = Box::new(Vec::with_capacity(packet_count));
                let mut own_input = &input[header_end..];
                for _ in 0..packet_count {
                    let (packet, rest) = parse_packet(own_input)?;
                    subpackets.push(packet);
                    own_input = rest;
                }
                Ok((
                    Packet {
                        version,
                        type_id,
                        content: PacketContent::Operator(subpackets),
                    },
                    own_input,
                ))
            }
            _ => panic!("Wrong length type id: {}", length_type_id),
        }
    }
}

pub fn parse_input(input: &str) -> Packet {
    let bit_stream: Vec<u8> = input
        .chars()
        .flat_map(|hex_digit| {
            (0..4).rev().map(move |i| {
                ((hex_digit.to_digit(16).unwrap() >> i) & 1) as u8
            })
        })
        .collect();
    parse_packet(&bit_stream).unwrap().0
}

impl Packet {
    fn version_sum(&self) -> usize {
        self.version as usize
            + match &self.content {
                PacketContent::Literal(_) => 0,
                PacketContent::Operator(subpackets) => {
                    subpackets.iter().map(|p| p.version_sum()).sum()
                }
            }
    }
    fn calculate(&self) -> usize {
        match (&self.content, self.type_id) {
            (PacketContent::Operator(subpackets), 0) => {
                subpackets.iter().map(|p| p.calculate()).sum()
            }
            (PacketContent::Operator(subpackets), 1) => {
                subpackets.iter().map(|p| p.calculate()).product()
            }
            (PacketContent::Operator(subpackets), 2) => {
                subpackets.iter().map(|p| p.calculate()).min().unwrap()
            }
            (PacketContent::Operator(subpackets), 3) => {
                subpackets.iter().map(|p| p.calculate()).max().unwrap()
            }
            (&PacketContent::Literal(value), 4) => value,
            (PacketContent::Operator(subpackets), 5) => {
                if subpackets[0].calculate() > subpackets[1].calculate() {
                    1
                } else {
                    0
                }
            }
            (PacketContent::Operator(subpackets), 6) => {
                if subpackets[0].calculate() < subpackets[1].calculate() {
                    1
                } else {
                    0
                }
            }
            (PacketContent::Operator(subpackets), 7) => {
                if subpackets[0].calculate() == subpackets[1].calculate() {
                    1
                } else {
                    0
                }
            }
            _ => panic!("Wrong type_id: {}", self.type_id),
        }
    }
}

pub fn task1(input: &Packet) -> usize {
    input.version_sum()
}

pub fn task2(input: &Packet) -> usize {
    input.calculate()
}

use std::boxed::Box;
use std::str::Chars;

#[derive(Clone)]
pub enum SnailfishNumber {
    Regular(u32),
    Pair(Box<(SnailfishNumber, SnailfishNumber)>),
}

impl std::fmt::Debug for SnailfishNumber {
    fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            SnailfishNumber::Regular(value) => value.fmt(fmt),
            SnailfishNumber::Pair(pair) => {
                write!(fmt, "[{:?},{:?}]", &pair.0, &pair.1)
            }
        }
    }
}

impl SnailfishNumber {
    fn pair(left: SnailfishNumber, right: SnailfishNumber) -> SnailfishNumber {
        SnailfishNumber::Pair(Box::new((left, right)))
    }
    fn regular(value: u32) -> SnailfishNumber {
        SnailfishNumber::Regular(value)
    }
    fn regpair(left: u32, right: u32) -> SnailfishNumber {
        SnailfishNumber::pair(
            SnailfishNumber::regular(left),
            SnailfishNumber::regular(right),
        )
    }
}

fn read_snailfish_number<'a>(input: &mut Chars<'a>) -> SnailfishNumber {
    let first = input.next().unwrap();
    if first == '[' {
        let left = read_snailfish_number(input.by_ref());
        assert_eq!(input.next().unwrap(), ',');
        let right = read_snailfish_number(input.by_ref());
        assert_eq!(input.next().unwrap(), ']');
        SnailfishNumber::pair(left, right)
    } else {
        SnailfishNumber::regular(first.to_digit(10).unwrap())
    }
}

enum Explosion {
    Not,
    Both(u32, u32),
    FromLeft(u32),
    FromRight(u32),
    Did,
}

impl Explosion {
    fn to_bool(&self) -> bool {
        match self {
            Explosion::Not => false,
            _ => true,
        }
    }
}

impl SnailfishNumber {
    fn reduce(&mut self) {
        loop {
            //println!("Calling explode for {:?}", self);
            if !self.explode(1).to_bool() {
                //println!("Calling split for {:?}", self);
                if !self.split() {
                    //println!("Done: {:?}", self);
                    break;
                }
            }
        }
    }

    fn explode(&mut self, level: u32) -> Explosion {
        //println!("Exploding level={}: {:?}", level, self);
        match self {
            SnailfishNumber::Regular(_) => Explosion::Not,
            SnailfishNumber::Pair(pair) => {
                if let (
                    SnailfishNumber::Regular(left),
                    SnailfishNumber::Regular(right),
                ) = **pair
                {
                    if level > 4 {
                        Explosion::Both(left, right)
                    } else {
                        Explosion::Not
                    }
                } else {
                    match pair.0.explode(level + 1) {
                        Explosion::Both(left_left, left_right) => {
                            pair.0 = SnailfishNumber::regular(0);
                            pair.1.insert_from_left(left_right);
                            Explosion::FromLeft(left_left)
                        }
                        Explosion::FromRight(left_right) => {
                            pair.1.insert_from_left(left_right);
                            Explosion::Did
                        }
                        Explosion::Not => match pair.1.explode(level + 1) {
                            Explosion::Both(right_left, right_right) => {
                                pair.0.insert_from_right(right_left);
                                pair.1 = SnailfishNumber::regular(0);
                                Explosion::FromRight(right_right)
                            }
                            Explosion::FromLeft(right_left) => {
                                pair.0.insert_from_right(right_left);
                                Explosion::Did
                            }
                            other => other, //Did, Not, Right
                        },
                        other => other, //Did, Not, LEft
                    }
                }
            }
        }
    }

    fn insert_from_left(&mut self, value: u32) {
        //println!("Insert left {:?} into {:?}", value, self);
        match self {
            SnailfishNumber::Regular(self_value) => {
                *self_value += value;
            }
            SnailfishNumber::Pair(pair) => {
                pair.0.insert_from_left(value);
            }
        }
    }

    fn insert_from_right(&mut self, value: u32) {
        //println!("Insert right {:?} into {:?}", value, self);
        match self {
            SnailfishNumber::Regular(self_value) => {
                *self_value += value;
            }
            SnailfishNumber::Pair(pair) => {
                pair.1.insert_from_right(value);
            }
        }
    }

    fn split(&mut self) -> bool {
        match self {
            SnailfishNumber::Regular(value) => {
                if *value >= 10 {
                    *self =
                        SnailfishNumber::regpair(*value / 2, (*value + 1) / 2);
                    true
                } else {
                    false
                }
            }
            SnailfishNumber::Pair(pair) => pair.0.split() || pair.1.split(),
        }
    }

    fn magnitude(&self) -> u32 {
        //println!("Finding magnitude of {:?}", self);
        match self {
            SnailfishNumber::Regular(v) => *v,
            SnailfishNumber::Pair(pair) => {
                3 * pair.0.magnitude() + 2 * pair.1.magnitude()
            }
        }
    }
}

fn add(left: SnailfishNumber, right: SnailfishNumber) -> SnailfishNumber {
    let mut result = SnailfishNumber::pair(left, right);
    result.reduce();
    result
}

fn sum_vec(numbers: &Vec<SnailfishNumber>) -> SnailfishNumber {
    numbers
        .iter()
        .skip(1)
        .fold(numbers[0].clone(), |acc, num| add(acc, num.clone()))
}

pub fn parse_input(input: &str) -> Vec<SnailfishNumber> {
    input
        .lines()
        .map(|line| read_snailfish_number(&mut line.chars()))
        .collect()
}

pub fn task1(input: &Vec<SnailfishNumber>) -> u32 {
    sum_vec(input).magnitude()
}

pub fn task2(input: &Vec<SnailfishNumber>) -> u32 {
    let mut best = 0;
    for i in 0..input.len() {
        for j in 0..input.len() {
            if i != j {
                best = std::cmp::max(
                    best,
                    add(input[i].clone(), input[j].clone()).magnitude(),
                );
            }
        }
    }
    best
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_reduce() {
        let data = "[[[[[9,8],1],2],3],4]
[[6,[5,[4,[3,2]]]],1]
[[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]]
[[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]]";
        let expected = "[[[[0,9],2],3],4]
[[6,[5,[7,0]]],3]
[[3,[2,[8,0]]],[9,[5,[7,0]]]]
[[[[0,7],4],[[7,8],[6,0]]],[8,1]]";
        let mut nums = parse_input(&data);
        for (input, expected) in nums.iter_mut().zip(expected.lines()) {
            input.reduce();
            assert_eq!(format!("{:?}", input), expected);
        }
    }

    #[test]
    fn test_magnitude() {
        for (input, expected) in parse_input(
            "[[1,2],[[3,4],5]]
[[[[0,7],4],[[7,8],[6,0]]],[8,1]]
[[[[1,1],[2,2]],[3,3]],[4,4]]
[[[[3,0],[5,3]],[4,4]],[5,5]]
[[[[5,0],[7,4]],[5,5]],[6,6]]
[[[[8,7],[7,7]],[[8,6],[7,7]]],[[[0,7],[6,6]],[8,7]]]",
        )
        .iter()
        .zip([143, 1384, 445, 791, 1137, 3488].into_iter())
        {
            assert_eq!(input.magnitude(), expected);
        }
    }

    #[test]
    fn test_add1() {
        let nums = &parse_input(
            "[1,1]
[2,2]",
        );
        let sum = add(nums[0].clone(), nums[1].clone());
        assert_eq!(format!("{:?}", sum), "[[1,1],[2,2]]");
    }

    #[test]
    fn test_add3() {
        let nums = &parse_input(
            "[[[[4,3],4],4],[7,[[8,4],9]]]
[1,1]",
        );
        let sum = add(nums[0].clone(), nums[1].clone());
        assert_eq!(format!("{:?}", sum), "[[[[0,7],4],[[7,8],[6,0]]],[8,1]]");
    }

    #[test]
    fn test_add2() {
        let nums = &parse_input(
            "[[[0,[4,5]],[0,0]],[[[4,5],[2,6]],[9,5]]]
[7,[[[3,7],[4,3]],[[6,3],[8,8]]]]",
        );
        let sum = add(nums[0].clone(), nums[1].clone());
        assert_eq!(
            format!("{:?}", sum),
            "[[[[4,0],[5,4]],[[7,7],[6,0]]],[[8,[7,7]],[[7,9],[5,0]]]]"
        );
    }

    #[test]
    fn test_sum1() {
        let data = "[1,1]
[2,2]
[3,3]
[4,4]";
        let num = parse_input(&data);
        let result = sum_vec(&num);
        assert_eq!(format!("{:?}", &result), "[[[[1,1],[2,2]],[3,3]],[4,4]]");
    }

    #[test]
    fn test_sum2() {
        let data = "[1,1]
[2,2]
[3,3]
[4,4]
[5,5]";
        let num = parse_input(&data);
        let result = sum_vec(&num);
        assert_eq!(format!("{:?}", &result), "[[[[3,0],[5,3]],[4,4]],[5,5]]");
    }

    #[test]
    fn test_sum3() {
        let data = "[1,1]
[2,2]
[3,3]
[4,4]
[5,5]
[6,6]";
        let num = parse_input(&data);
        let result = sum_vec(&num);
        assert_eq!(format!("{:?}", &result), "[[[[5,0],[7,4]],[5,5]],[6,6]]");
    }

    #[test]
    fn test_task1() {
        let data = "[[[0,[5,8]],[[1,7],[9,6]]],[[4,[1,2]],[[1,4],2]]]
[[[5,[2,8]],4],[5,[[9,9],0]]]
[6,[[[6,2],[5,6]],[[7,6],[4,7]]]]
[[[6,[0,7]],[0,9]],[4,[9,[9,0]]]]
[[[7,[6,4]],[3,[1,3]]],[[[5,5],1],9]]
[[6,[[7,3],[3,2]]],[[[3,8],[5,7]],4]]
[[[[5,4],[7,7]],8],[[8,3],8]]
[[9,3],[[9,9],[6,[4,9]]]]
[[2,[[7,7],7]],[[5,8],[[9,3],[0,2]]]]
[[[[5,2],5],[8,[3,7]]],[[5,[7,5]],[4,4]]]";

        assert_eq!(task1(&parse_input(&data)), 4140);
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub struct Player {
    position: usize,
    score: usize,
}

impl Player {
    fn new(position: usize) -> Player {
        Player { position, score: 0 }
    }
}

#[derive(Clone)]
pub struct Game {
    players: Vec<Player>,
    turn: usize,
    dice_value: usize,
    dice_rolled: usize,
}

pub fn parse_input(input: &str) -> Vec<usize> {
    input
        .lines()
        .map(|line| line.split(": ").skip(1).next().unwrap().parse().unwrap())
        .collect()
}

impl Game {
    const WIN_SCORE: usize = 1000;
    const BOARD_SIZE: usize = 10;
    const DICE_SIZE: usize = 100;

    fn new(player_pos: &Vec<usize>) -> Game {
        Game {
            players: player_pos.iter().map(|&pos| Player::new(pos)).collect(),
            turn: 0,
            dice_value: 1,
            dice_rolled: 0,
        }
    }
    fn step(&mut self) {
        let whos_turn = self.turn % self.players.len();
        self.players[whos_turn].position = (self.players[whos_turn].position
            + self.roll()
            + self.roll()
            + self.roll()
            - 1)
            % Game::BOARD_SIZE
            + 1;
        self.players[whos_turn].score += self.players[whos_turn].position;
        self.turn += 1;
    }
    fn roll(&mut self) -> usize {
        let roll = self.dice_value;
        self.dice_rolled += 1;
        self.dice_value = self.dice_value % Game::DICE_SIZE + 1;
        roll
    }
    fn ended(&self) -> bool {
        self.players
            .iter()
            .any(|player| player.score >= Game::WIN_SCORE)
    }
    fn less_score(&self) -> usize {
        self.players
            .iter()
            .map(|player| player.score)
            .min()
            .unwrap()
    }
}

pub fn task1(input: &Vec<usize>) -> usize {
    let mut game = Game::new(input);
    while !game.ended() {
        game.step();
    }
    game.less_score() * game.dice_rolled
}

#[derive(Clone, Debug)]
pub struct DiracGame {
    //universes: Vec<(Vec<Player>, u128)>,
    universes: std::collections::HashMap<Vec<Player>, u128>,
    wins: Vec<u128>,
    turn: usize,
}

impl DiracGame {
    //roll, number of universes
    const DIRAC_CUBE: [(usize, u128); 7] =
        [(3, 1), (4, 3), (5, 6), (6, 7), (7, 6), (8, 3), (9, 1)];
    const WIN_SCORE: usize = 21;
    const BOARD_SIZE: usize = 10;

    fn new(pos: &Vec<usize>) -> DiracGame {
        DiracGame {
            universes: [(
                pos.iter().map(|&position| Player::new(position)).collect(),
                1,
            )]
            .into(),

            wins: vec![0; pos.len()],
            turn: 0,
        }
    }
    fn ended(&self) -> bool {
        self.universes.is_empty()
    }

    fn step(&mut self) {
        let whos_turn = self.turn % self.wins.len();
        let mut universes = std::collections::HashMap::new();
        for (players, old_universes) in &self.universes {
            for (roll, roll_universes) in DiracGame::DIRAC_CUBE {
                let new_position = (players[whos_turn].position + roll - 1)
                    % DiracGame::BOARD_SIZE
                    + 1;
                let new_score = players[whos_turn].score + new_position;
                if new_score >= DiracGame::WIN_SCORE {
                    self.wins[whos_turn] += old_universes * roll_universes;
                } else {
                    let mut new_players = players.clone();
                    new_players[whos_turn].position = new_position;
                    new_players[whos_turn].score = new_score;
                    *universes.entry(new_players).or_insert(0) +=
                        old_universes * roll_universes;
                }
            }
        }
        self.universes = universes;
        self.turn += 1;
    }
}

pub fn task2(input: &Vec<usize>) -> u128 {
    let mut game = DiracGame::new(input);
    while !game.ended() {
        game.step();
    }
    *game.wins.iter().max().unwrap()
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_task1() {
        let data = parse_input(
            &"Player 1 starting position: 4
Player 2 starting position: 8",
        );
        assert_eq!(task1(&data), 739785);
    }

    #[test]
    fn test_task2() {
        let data = parse_input(
            &"Player 1 starting position: 4
Player 2 starting position: 8",
        );
        assert_eq!(task2(&data), 444356092776315);
    }
}

type Rect = ((i32, i32), (i32, i32));

pub fn parse_input(input: &str) -> Rect {
    let mut parts = input["target area: ".len()..].split(", ");
    let mut xs = parts.next().unwrap()["x=".len()..]
        .split("..")
        .map(|x| x.parse().unwrap());
    let mut ys = parts.next().unwrap()["x=".len()..]
        .split("..")
        .map(|x| x.parse().unwrap());
    (
        (xs.next().unwrap(), ys.next().unwrap()),
        (xs.next().unwrap(), ys.next().unwrap()),
    )
}

pub fn task1(input: &Rect) -> i32 {
    let &((x1, y1), (x2, _y2)) = input;
    //x1<=vx*(vx+1)/2<=x2
    //2*x1<=vx**2 + vx<=2*x2
    let vx = (((1 + 8 * x2) as f64).sqrt() as i32 - 1) / 2;
    assert!(vx * (vx + 1) / 2 >= x1, "Probe don't stop, vx={}", vx);
    let vy = (y1 + 1).abs();
    vy * (vy + 1) / 2
}

fn get_all_velocities(input: &Rect) -> std::collections::HashSet<(i32, i32)> {
    let &((x1, y1), (x2, y2)) = input;
    let max_t = 2 * y1.abs();

    let mut result = std::collections::HashSet::new();

    for t in 1..=max_t {
        let mut vx_min = (x1 + t * (t - 1) / 2 + t - 1) / t;
        if vx_min < t {
            vx_min = ((((1 + 8 * x1) as f64).sqrt() - 1.0) / 2.0).ceil() as i32;
        }
        let mut vx_max = (x2 + t * (t - 1) / 2) / t;
        if vx_max < t {
            vx_max = ((((1 + 8 * x2) as f64).sqrt() - 1.0) / 2.0) as i32;
        }
        let vy_min = ((y1 + t * (t - 1) / 2) as f64 / t as f64).ceil() as i32;
        let vy_max = ((y2 + t * (t - 1) / 2) as f64 / t as f64).floor() as i32;
        /*let r = std::cmp::max(0, vx_max - vx_min + 1) as usize
            * std::cmp::max(0, vy_max - vy_min + 1) as usize;
        println!(
            "t={}, vx={}..{}, vy={}..{}, total={}",
            t, vx_min, vx_max, vy_min, vy_max, r
        );*/
        for vx in vx_min..=vx_max {
            for vy in vy_min..=vy_max {
                result.insert((vx, vy));
            }
        }
    }
    result
}

pub fn task2(input: &Rect) -> usize {
    get_all_velocities(input).len()
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_task1() {
        assert_eq!(task1(&((20, -10), (30, -5))), 45);
    }

    #[test]
    fn test_task2() {
        assert_eq!(task2(&((20, -10), (30, -5))), 112);
    }

    use itertools::Itertools;

    #[test]
    fn test_get_all_velocities() {
        let expected_str = "23,-10  25,-9   27,-5   29,-6   22,-6   21,-7   9,0     27,-7   24,-5
25,-7   26,-6   25,-5   6,8     11,-2   20,-5   29,-10  6,3     28,-7
8,0     30,-6   29,-8   20,-10  6,7     6,4     6,1     14,-4   21,-6
26,-10  7,-1    7,7     8,-1    21,-9   6,2     20,-7   30,-10  14,-3
20,-8   13,-2   7,3     28,-8   29,-9   15,-3   22,-5   26,-8   25,-8
25,-6   15,-4   9,-2    15,-2   12,-2   28,-9   12,-3   24,-6   23,-7
25,-10  7,8     11,-3   26,-7   7,1     23,-9   6,0     22,-10  27,-6
8,1     22,-8   13,-4   7,6     28,-6   11,-4   12,-4   26,-9   7,4
24,-10  23,-8   30,-8   7,0     9,-1    10,-1   26,-5   22,-9   6,5
7,5     23,-6   28,-10  10,-2   11,-1   20,-9   14,-2   29,-7   13,-3
23,-5   24,-8   27,-9   30,-7   28,-5   21,-10  7,9     6,6     21,-5
27,-10  7,2     30,-9   21,-8   22,-7   24,-9   20,-6   6,9     29,-5
8,-2    27,-8   30,-5   24,-7";
        let expected = expected_str
            .split_whitespace()
            .map(|pair| {
                pair.split(',')
                    .map(|n| n.parse().unwrap())
                    .collect_tuple()
                    .unwrap()
            })
            .collect();
        let result = get_all_velocities(&((20, -10), (30, -5)));
        if result != expected {
            let extra: Vec<_> = result.difference(&expected).collect();
            if !extra.is_empty() {
                println!("Extra values: {:?}", extra);
            }
            let lost: Vec<_> = expected.difference(&result).collect();
            if !lost.is_empty() {
                println!("Lost values: {:?}", lost);
            }
            assert!(false);
        }
    }
}