Решение на Bigint от Петър Милев
Резултати
- 14 точки от тестове
- 0 бонус точки
- 14 точки общо
- 14 успешни тест(а)
- 1 неуспешни тест(а)
Код
use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Add, Sub, Neg};
#[derive(Debug, PartialEq, Eq, Clone)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
/// Конструира нов Bigint със стойност "0" и положителен знак.
/// Това може да означава празен вектор с цифри или масив с една цифра `0` -- ваш избор.
///
pub fn new() -> Self {
Bigint { sign: 1, digits: vec![0] }
}
fn from_components(mut digits: Vec<u8>, sign: i8) -> Self {
while digits.len() != 0 && digits[0] == 0 {
digits.iter()
.position(|&e| e == 0)
.map(|p| digits.remove(p));
}
if digits.len() == 0 {
return Self::new();
}
Bigint { sign: sign, digits: digits.to_vec() }
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
self.sign > 0
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
self.sign < 0
}
fn cmp_abs(&self, other: &Bigint) -> Ordering {
if self.digits.len() > other.digits.len() {
return Ordering::Greater;
} else if self.digits.len() < other.digits.len() {
return Ordering::Less;
}
for i in 0..self.digits.len() {
match self.digits[i].cmp(&other.digits[i]) {
Ordering::Greater => return Ordering::Greater,
Ordering::Less => return Ordering::Less,
_ => ()
}
}
Ordering::Equal
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut sign: i8 = 1;
let mut digits = vec![];
for (i, c) in s.chars().enumerate() {
if i == 0 {
match c {
'-' => {
sign = -1;
continue;
},
'+' => continue,
_ => ()
}
}
match c.to_digit(10) {
Some(d) => digits.push(d as u8),
None => return Err(Self::Err{})
}
}
Ok(Self::from_components(digits, sign))
}
}
impl PartialOrd for Bigint {
/// Две цели числа винаги могат да се сравнят, така че "частичното" равенство е същото като
/// пълното.
///
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
fn cmp(&self, other: &Bigint) -> Ordering {
if self.is_positive() != other.is_positive() {
if self.is_positive() {
return Ordering::Greater;
} else {
return Ordering::Less;
}
}
let res = self.cmp_abs(other);
if self.is_negative() {
return res.reverse();
}
res
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Self::from_components(self.digits, -self.sign)
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut res: Vec<u8> = vec![];
let (greater, less) = match self.cmp_abs(&other) {
Ordering::Greater => (&self, &other),
_ => (&other, &self)
};
let g_iter = greater.digits.iter().rev();
let mut l_iter = less.digits.iter().rev();
let sign: i8 = greater.sign * less.sign;
let mut one_in_mind: i8 = 0;
for i in g_iter {
let g_digit = *i as i8;
let l_digit = match l_iter.next() {
Some(d) => *d as i8,
None => 0
};
let new_digit = g_digit + sign * l_digit + one_in_mind;
// println!("1: {} {} = {} | {}", g_digit, l_digit, new_digit, one_in_mind);
res.push(((new_digit + 10) % 10) as u8);
one_in_mind = if (0..10).contains(&new_digit) { 0 } else { sign }; // sign can be new_digit.signum()
}
res.push(one_in_mind as u8);
res.reverse();
Bigint::from_components(res, greater.sign)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
// for printing Bigint
impl std::fmt::Display for Bigint {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(f, "{}{}", if self.sign == -1 { "-" } else { "" }, self.digits.iter().map(|el| el.to_string()).collect::<String>())
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-1o7jwza/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.77s
Running target/debug/deps/solution_test-589a43f0f4b10ca3
running 15 tests
test solution_test::test_bigint_construction ... ok
test solution_test::test_bigint_nonzero_sign ... ok
test solution_test::test_bigint_zero_sign ... FAILED
test solution_test::test_comparison ... ok
test solution_test::test_invalid_string ... ok
test solution_test::test_neutralization ... ok
test solution_test::test_parsing_with_and_without_sign ... ok
test solution_test::test_parsing_with_leading_zeroes ... ok
test solution_test::test_sub_1_basic ... ok
test solution_test::test_sub_2_diferent_lengths ... ok
test solution_test::test_sub_3_carry ... ok
test solution_test::test_sum_1_basic ... ok
test solution_test::test_sum_2_different_lengths ... ok
test solution_test::test_sum_3_overflow ... ok
test solution_test::test_sum_4_negative ... ok
failures:
---- solution_test::test_bigint_zero_sign stdout ----
thread 'main' panicked at 'assertion failed: !zero.is_positive()', tests/solution_test.rs:21:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
failures:
solution_test::test_bigint_zero_sign
test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'