use std::cmp::max;
use std::fmt;
use std::ops::{Add, Mul, Sub};

pub struct Number {
    radix: usize,
    digits: Vec<u8>,
}

impl Number {
    pub fn parse(snum: &str, radix: usize) -> Result<Number, &str> {
        let snum = snum.as_bytes();
        let mut digits = Vec::new();
        for i in (0..snum.len()).rev() {
            match Number::parse_digit(snum[i]) {
                Some(digit) => {
                    if digit as usize >= radix {
                        return Err("Аргумент не является числом");
                    } else {
                        digits.push(digit);
                    }
                }
                None => {
                    return Err("Аргумент не является числом");
                }
            }
        }
        return Ok(Number { radix, digits });
    }

    pub fn len(&self) -> usize {
        self.digits.len()
    }

    fn parse_digit(c: u8) -> Option<u8> {
        if c >= 'a' as u8 {
            Some(c - 'a' as u8 + 10_u8)
        } else if c >= '0' as u8 {
            Some(c - '0' as u8)
        } else {
            None
        }
    }

    fn fix_leading_zeros(mut self) -> Self {
        let mut leading = 0;
        for i in (1..self.digits.len()).rev() {
            if self.digits[i] == 0 {
                leading += 1;
            } else {
                break;
            }
        }
        for _ in 0..leading {
            self.digits.pop();
        }
        return self;
    }
}

impl fmt::Display for Number {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for i in (0..self.digits.len()).rev() {
            let digit = if self.digits[i] > 9 {
                ('a' as u8 - 10 + self.digits[i]) as char
            } else {
                ('0' as u8 + self.digits[i]) as char
            };
            write!(f, "{}", digit)?;
        }

        if self.radix != 10 {
            write!(f, "_{}", self.radix)?;
        }
        return Ok(());
    }
}

impl Add for Number {
    type Output = Self;

    fn add(self, other: Self) -> Self::Output {
        let mut k = 0;
        let len = max(self.len(), other.len());
        let mut digits = Vec::new();
        for i in 0..len {
            let mut digit = 0;
            if i < self.len() {
                digit += self.digits[i] as usize;
            }
            if i < other.len() {
                digit += other.digits[i] as usize;
            }
            digit += k;
            let (div, rem) = (digit / self.radix, digit % self.radix);
            digit = rem;
            k = div;
            digits.push(digit as u8);
        }
        if k != 0 {
            digits.push(k as u8);
        }

        return Number {
            radix: self.radix,
            digits,
        };
    }
}

impl Sub for Number {
    type Output = Self;

    fn sub(self, other: Self) -> Self::Output {
        let len = max(self.len(), other.len());
        let mut digits = Vec::new();
        let mut k = 0;
        for i in 0..len {
            let q1 = if i < self.len() {
                self.digits[i] as i64
            } else {
                0_i64
            };
            let q2 = if i < other.len() {
                other.digits[i] as i64
            } else {
                0_i64
            };
            let b = self.radix as i64;
            let res = q1 - q2 + k;
            let digit = (res + b) % b;
            k = if res < 0 { -1 } else { 0 };
            digits.push(digit as u8);
        }
        if k != 0 {
            digits.push(k as u8);
        }

        return Number {
            radix: self.radix,
            digits,
        }
        .fix_leading_zeros();
    }
}

impl Mul for Number {
    type Output = Self;

    fn mul(self, other: Self) -> Self::Output {
        let n = self.len();
        let m = other.len();
        let mut digits = vec![0; n + m];

        for j in 0..m {
            let vj = other.digits[j] as usize;
            if vj == 0 {
                digits[n + j] = 0;
            } else {
                let mut k = 0;
                for i in 0..n {
                    let ui = self.digits[i] as usize;
                    let t = ui * vj + digits[i + j] as usize + k;
                    digits[i + j] = (t % self.radix) as u8;
                    k = t / self.radix;
                }
                digits[n + j] = k as u8;
            }
        }
        return Number {
            radix: self.radix,
            digits,
        }
        .fix_leading_zeros();
    }
}