pub struct Number {
    // (depth, value)
    v: Vec<(u8, u8)>,
}

impl Number {
    pub fn parse(s: &str) -> Self {
        let mut depth = 0;
        let mut v = vec![];
        for c in s.chars() {
            match c {
                '[' => depth += 1,
                ']' => depth -= 1,
                ',' => {},
                _ => {
                    let i = c.to_digit(10).unwrap() as u8;
                    v.push((i, depth));
                },
            }
        }
        return Number {v};
    }

    fn explode(&mut self) -> bool {
        match self.v.iter().position(|(_, depth)| *depth > 4) {
            Some(i) => {
                let (a, depth_a) = self.v.remove(i);
                let (b, depth_b) = self.v.remove(i);
                assert_eq!(depth_a, depth_b);
                self.v.insert(i, (0, depth_a - 1));
                if i > 0 {
                    self.v[i - 1].0 += a;
                }
                if i + 1 < self.v.len() {
                    self.v[i + 1].0 += b;
                }
                true
            },
            None => false,
        }
    }

    fn split(&mut self) -> bool {
        match self.v.iter().position(|(value, _)| *value >= 10) {
            Some(i) => {
                let (value, depth) = self.v.remove(i);
                self.v.insert(i, (value - value / 2, depth + 1));
                self.v.insert(i, (value / 2, depth + 1));
                true
            },
            None => false,
        }
    }

    fn magnitute_insert(&self, mut path: &mut Vec<Option<u64>>, value: u64) {
        match path.pop() {
            Some(None) => {
                path.push(Some(value));
            },
            Some(Some(left)) => {
                self.magnitute_insert(&mut path, 3 * left + 2 * value);
            },
            None => path.push(Some(value)),
        }
    }

    pub fn magnitute(&self) -> u64 {
        let mut path: Vec<Option<u64>> = vec![];

        for (value, depth) in self.v.iter() {
            while path.len() < usize::from(*depth) {
                path.push(None);
            }
            self.magnitute_insert(&mut path, u64::from(*value));
        }
        match path[..] {
            [Some(v)] => v,
            _ => unreachable!(),
        }
    }
}

impl std::ops::Add for &Number {
    type Output = Number;

    fn add(self, other: Self) -> Number {
        let mut result = Number {
            v: vec![],
        };
        if self.v.len() == 0 {
            for (i, depth) in other.v.iter() {
                result.v.push((*i, *depth));
            }
        } else {
            for (i, depth) in self.v.iter() {
                result.v.push((*i, *depth + 1));
            }
            for (i, depth) in other.v.iter() {
                result.v.push((*i, *depth + 1));
            }
        }
        while result.explode() || result.split() {}
        return result;
    }
}

impl std::iter::Sum for Number {
    fn sum<I: Iterator<Item=Self>>(iter: I) -> Self {
        return iter.fold(Number {v: vec![]}, |a, b| &a + &b);
    }
}

impl std::fmt::Display for Number {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut path = vec![];

        for (value, depth) in self.v.iter() {
            while path.len() < usize::from(*depth) {
                write!(f, "[")?;
                path.push(false);
            }

            write!(f, "{}", value)?;

            loop {
                match path.pop() {
                    Some(true) => write!(f, "]")?,
                    Some(false) => {
                        write!(f, ",")?;
                        path.push(true);
                        break;
                    },
                    None => break,
                }
            }
        }

        return Ok(());
    }
}