Решение на Bigint от Бетина Христова
Към профила на Бетина Христова
Резултати
- 13 точки от тестове
- 0 бонус точки
- 13 точки общо
- 13 успешни тест(а)
- 2 неуспешни тест(а)
Код
use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Add, Sub};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
let new_digit = vec![0];
Bigint::from_components(new_digit, 1)
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut new_digits:Vec::<u8>;
let mut last_zero_pos: usize = 0;
let mut is_zero: bool = true;
let mut actual_sign: i8 = sign;
for (pos, digit) in digits.iter().enumerate() {
if digit > &0_u8 {
last_zero_pos = pos;
is_zero = false;
break;
}
}
if is_zero {
new_digits = vec![0];
actual_sign = 1;
}
else {
new_digits = digits[last_zero_pos..digits.len()].to_vec();
}
new_digits.reverse();
Bigint {
sign: actual_sign,
digits: new_digits
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
fn is_zero(&self) -> bool {
let mut is_zero: bool = true;
for digit in self.digits.iter() {
if digit > &0_u8 {
is_zero = false;
break;
}
}
is_zero
}
fn add_digits(&self, left: &Vec<u8>, right: &Vec<u8>) -> Vec<u8> {
let mut result:Vec::<u8> = Vec::<u8>::new();
let mut carry = 0_u8;
let length = left.len();
for i in 0..length {
if i >= right.len()
{
result.push(left[i] + carry);
carry = 0;
}
else
{
let mut current_result = left[i] + right[i];
if current_result > 9
{
current_result = current_result % 10;
result.push(current_result + carry);
carry = 1;
} else {
result.push(current_result + carry);
carry = 0;
}
}
}
result.reverse();
result
}
fn subtract_digits(&self, larger: &Vec<u8>, smaller: &Vec<u8>) -> Vec<u8> {
let mut result:Vec::<u8> = Vec::<u8>::new();
let mut carry = 0_u8;
let length = larger.len();
for i in 0..length {
if i >= smaller.len()
{
result.push(larger[i] - carry);
carry = 0;
}
else
{
let current_result: u8;
if (larger[i] - carry) >= smaller[i] {
current_result = larger[i] - smaller[i];
result.push(current_result - carry);
carry = 0;
} else {
current_result = (larger[i] + 10 ) - smaller[i];
result.push(current_result - carry);
carry = 1;
}
}
}
result.reverse();
result
}
}
#[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 digits;
let mut s2:&str = s;
if s.chars().take(1).next() == Some('-'){
sign = -1;
s2 = &s[1..s.len()];
}
if s.chars().take(1).next() == Some('+'){
s2 = &s[1..s.len()];
}
if s2.chars().any(|c| !c.is_numeric()) {
return Err(ParseError)
} else {
digits = s2.chars().map(|c| c as u8 - '0' as u8).collect::<Vec<u8>>();
}
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 {
return self.sign.cmp(&other.sign)
}
else if self.sign == -1 && self.digits.len() != other.digits.len()
{
return other.digits.len().cmp(&self.digits.len())
}
else if self.sign == 1 && self.digits.len() != other.digits.len()
{
return self.digits.len().cmp(&other.digits.len())
}
for i in 0..self.digits.len()
{
if self.digits[i] > other.digits[i]
{
if self.sign == 1
{
return self.digits[i].cmp(&other.digits[i])
} else {
return other.digits[i].cmp(&self.digits[i])
}
}
else if self.digits[i] < other.digits[i]
{
if self.sign == 1
{
return self.digits[i].cmp(&other.digits[i])
} else {
return other.digits[i].cmp(&self.digits[i])
}
}
}
return other.digits.len().cmp(&self.digits.len())
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
if self.digits.len() > other.digits.len() {
return Bigint::from_components(self.add_digits(&self.digits, &other.digits), self.sign);
} else {
return Bigint::from_components(self.add_digits(&other.digits, &self.digits), self.sign);
}
} else {
let self_copy_sign = self.sign;
let other_copy_sign = other.sign;
let mut self_copy = self;
let mut other_copy = other;
self_copy.sign = 1;
other_copy.sign = 1;
match self_copy.cmp(&other_copy) {
Ordering::Equal => Bigint::new(),
Ordering::Less => return Bigint::from_components(self_copy.subtract_digits(&other_copy.digits, &self_copy.digits), other_copy_sign),
Ordering::Greater => return Bigint::from_components(self_copy.subtract_digits(&self_copy.digits, &other_copy.digits), self_copy_sign),
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
if self.sign == other.sign {
if self.digits.len() > other.digits.len() {
return Bigint::from_components(self.subtract_digits(&self.digits, &other.digits), self.sign);
} else if self.digits.len() < other.digits.len() {
return Bigint::from_components(self.subtract_digits(&other.digits, &self.digits), self.sign);
} else {
match self.sign {
-1 => match self.cmp(&other) {
Ordering::Less => return Bigint::from_components(self.subtract_digits(&self.digits, &other.digits), -1),
Ordering::Greater => return Bigint::from_components(self.subtract_digits(&other.digits, &self.digits), 1),
Ordering::Equal => return Bigint::new()
},
1 => match self.cmp(&other) {
Ordering::Less => return Bigint::from_components(self.subtract_digits(&other.digits, &self.digits), -1),
Ordering::Greater => return Bigint::from_components(self.subtract_digits(&self.digits, &other.digits), 1),
Ordering::Equal => return Bigint::new()
},
_ => return Bigint::new()
}
}
} else {
let actual_sign: i8;
let self_sign = self.sign;
let other_sign = other.sign;
let mut self_copy = self;
let mut other_copy = other;
self_copy.sign = 1;
other_copy.sign = 1;
match self_copy.cmp(&other_copy) {
Ordering::Equal => actual_sign = self_sign,
Ordering::Less => actual_sign = other_sign,
Ordering::Greater => actual_sign = self_sign,
}
if self_sign != other_sign {
return Bigint::from_components(self_copy.add_digits(&self_copy.digits, &other_copy.digits), actual_sign);
} else {
return Bigint::from_components(self_copy.add_digits(&other_copy.digits, &self_copy.digits), actual_sign);
}
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-jm4qku/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.71s
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 ... 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 ... FAILED
test solution_test::test_sum_1_basic ... ok
test solution_test::test_sum_2_different_lengths ... ok
test solution_test::test_sum_3_overflow ... FAILED
test solution_test::test_sum_4_negative ... ok
failures:
---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:104:29
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [0, 10, 9] }`,
right: `Bigint { sign: 1, digits: [0, 0, 0, 1] }`', tests/solution_test.rs:97:5
failures:
solution_test::test_sub_3_carry
solution_test::test_sum_3_overflow
test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'