Решение на Bigint от Цветелина Стоянова
Към профила на Цветелина Стоянова
Резултати
- 14 точки от тестове
- 0 бонус точки
- 14 точки общо
- 14 успешни тест(а)
- 1 неуспешни тест(а)
Код
use std::cmp::Ordering;
use std::ops::Add;
use std::ops::Sub;
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
}
}
pub fn from_components(digits: Vec<u8>, sign: i8) -> Self {
if sign != -1 && sign != 1 {
panic!("Not a valid sign!");
}
let vec = remove_leading_zeros(digits);
return if vec.len() == 0 {
// cases [0,0,0], [0], []
Bigint {
sign: 1,
digits: vec![0],
}
} else {
Bigint {
sign: sign,
digits: vec,
}
};
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.digits[0] != 0
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.digits[0] != 0
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if !is_valid(s) {
return Err(ParseError);
}
let mut digits: Vec<u8> = Vec::new();
let mut sign: i8 = 1;
let mut d: u8;
for c in s.chars() {
if c == '-' {
sign = -1;
}
if c != '+' && c != '-' {
d = c.to_digit(10).unwrap() as u8;
digits.push(d);
}
}
return Ok(Bigint::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.sign < other.sign || self.digits.len() < other.digits.len() {
return Ordering::Less;
} else if self.sign > other.sign || self.digits.len() > other.digits.len() {
return Ordering::Greater;
}
let are_positive = self.sign == 1;
for i in 0..self.digits.len() {
let d1 = self.digits[i];
let d2 = other.digits[i];
if (d1 < d2 && are_positive) || (d1 > d2 && !are_positive) {
return Ordering::Less;
} else if (d1 > d2 && are_positive) || (d1 < d2 && !are_positive) {
return Ordering::Greater;
}
}
return Ordering::Equal;
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
Bigint {
digits: add_digits(self.digits, other.digits),
sign: self.sign,
}
} else {
add_vectors_different_signs(self, other)
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self.add(Bigint {
sign: -1 * other.sign,
digits: other.digits,
})
}
}
fn remove_leading_zeros(digits: Vec<u8>) -> Vec<u8> {
digits
.into_iter()
.skip_while(|&x| x == 0)
.collect::<Vec<u8>>()
}
fn is_valid(s: &str) -> bool {
for (i, c) in s.chars().enumerate() {
if i == 0 && c != '+' && c != '-' && !c.is_numeric() {
return false;
}
if i > 0 && !c.is_numeric() {
return false;
}
}
return true;
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
match left.len().cmp(&right.len()) {
Ordering::Less => {
let fulled_with_zeros_left = full_with_zeros_in_front(right.len() - left.len(), left);
add_vectors_fulled_with_zeros(fulled_with_zeros_left, right)
}
Ordering::Greater => {
let fulled_with_zeros_right = full_with_zeros_in_front(left.len() - right.len(), right);
add_vectors_fulled_with_zeros(left, fulled_with_zeros_right)
}
Ordering::Equal => add_vectors_fulled_with_zeros(left, right),
}
}
fn full_with_zeros_in_front(number_zeros: usize, vector: Vec<u8>) -> Vec<u8> {
let zero_vec = vec![0; number_zeros];
return [&zero_vec[..], &vector[..]].concat();
}
fn add_vectors_fulled_with_zeros(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
let mut edno_naym = 0;
let mut reversed_result: Vec<u8> = Vec::new();
for i in (0..left.len()).rev() {
let digit = left[i] + right[i] + edno_naym;
reversed_result.push(digit % 10);
edno_naym = digit / 10;
}
if edno_naym != 0 {
reversed_result.push(edno_naym);
}
let mut result = Vec::new();
result.extend(reversed_result.iter().rev());
return result;
}
fn substract_vectors_fulled_with_zeros(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut edno_naym = 0;
let mut reversed_result: Vec<u8> = Vec::new();
for i in (0..larger.len()).rev() {
let digit = larger[i] as isize - edno_naym as isize - smaller[i] as isize;
if digit >= 0 {
edno_naym = 0;
reversed_result.push(digit as u8);
} else {
edno_naym = 1;
reversed_result.push((digit + 10) as u8);
}
}
let mut result_with_leading_zeros = Vec::new();
result_with_leading_zeros.extend(reversed_result.iter().rev());
let result = remove_leading_zeros(result_with_leading_zeros);
return if result.len() == 0 { vec![0] } else { result };
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
if larger.len() > smaller.len() {
let fulled_with_zeros_right =
full_with_zeros_in_front(larger.len() - smaller.len(), smaller);
return substract_vectors_fulled_with_zeros(larger, fulled_with_zeros_right);
}
return substract_vectors_fulled_with_zeros(larger, smaller);
}
fn add_vectors_different_signs(first: Bigint, second: Bigint) -> Bigint {
let positive_first = Bigint {
sign: 1,
digits: first.digits,
};
let positive_second = Bigint {
sign: 1,
digits: second.digits,
};
let cmp = positive_first.cmp(&positive_second);
return match cmp {
Ordering::Greater => Bigint {
sign: first.sign,
digits: subtract_digits(positive_first.digits, positive_second.digits),
},
Ordering::Less => Bigint {
sign: second.sign,
digits: subtract_digits(positive_second.digits, positive_first.digits),
},
_ => Bigint::new(),
};
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-tf83q4/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.84s
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 ... ok
test solution_test::test_comparison ... FAILED
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_comparison stdout ----
thread 'main' panicked at 'assertion failed: bigint("-1") > bigint("-10")', tests/solution_test.rs:172:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
failures:
solution_test::test_comparison
test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'