Решение на Bigint от Георги Гергинов
Към профила на Георги Гергинов
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
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 {
Bigint {
sign: 1,
digits: vec![0],
}
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
if sign.abs() != 1 {
panic!("Sign variable has unknown value");
}
let mut new_bigint = Bigint {
sign,
digits,
};
Bigint::optimized_from(&mut new_bigint)
}
pub fn is_positive(&self) -> bool {
if self.digits == vec![0] {
return false
}
self.sign == 1
}
pub fn is_negative(&self) -> bool {
if self.digits == vec![0] {
return false
}
self.sign == -1
}
fn remove_nil_repetition(&mut self) {
if self.digits.len() < 2 || self.digits[0] != 0 {
return;
}
let mut count: usize = 0;
let mut without_nils = Vec::new();
while count < self.digits.len() && self.digits[count] == 0 {
count += 1;
}
while count < self.digits.len() {
without_nils.push(self.digits[count]);
count += 1;
}
if without_nils.is_empty() {
without_nils = vec![0];
}
self.digits = without_nils
}
fn make_nil_sign_positive(&mut self) {
if self.digits == vec![0] && self.sign != 1 {
self.sign = 1;
}
}
fn optimized_from(bigint: &mut Self) -> Self {
if bigint.digits.is_empty() {
bigint.digits = vec![0];
}
bigint.remove_nil_repetition();
bigint.make_nil_sign_positive();
Bigint {
sign: bigint.sign,
digits: bigint.digits.clone(),
}
}
fn stretch_with_nils(bigint: &Self, desire_length: usize) -> Self {
let mut new_bigint = Bigint{ digits: vec![], sign: bigint.sign, };
let mut count: usize = bigint.digits.len() - 1;
loop {
new_bigint.digits.push(bigint.digits[count]);
if count == 0 {
break;
}
count -= 1;
}
count = new_bigint.digits.len() - 1;
while count != desire_length - 1 {
new_bigint.digits.push(0);
count += 1;
}
new_bigint.digits.reverse();
new_bigint
}
fn addition_product_from(first: &Self, second: &Self) -> Self {
let mut digits = Vec::<u8>::new();
let mut count = first.digits.len() - 1;
let mut transferred: u8 = 0;
loop {
let curr_product: u8 = first.digits[count] + second.digits[count] + transferred;
if curr_product >= 10 {
digits.push(curr_product % 10);
transferred = 1;
} else {
digits.push(curr_product);
transferred = 0;
}
if count == 0 {
if transferred != 0 {
digits.push(transferred);
}
break;
}
count -= 1;
}
digits.reverse();
Bigint::from_components(digits, first.sign)
}
fn subtraction_product_from(bigger: &mut Self, smaller: &mut Self) -> Self {
let mut digits = Vec::<u8>::new();
let mut count = bigger.digits.len() - 1;
let mut transferred: u8 = 0;
let mut is_persistent_transfer: bool = false;
loop {
if transferred == 1 {
is_persistent_transfer = false;
if bigger.digits[count] == 0 {
bigger.digits[count] = 9;
is_persistent_transfer = true;
} else {
bigger.digits[count] -= 1;
transferred = 0;
}
}
if bigger.digits[count] < smaller.digits[count] {
transferred = 1;
} else {
transferred = 0;
}
digits.push(transferred*10 + bigger.digits[count] - smaller.digits[count]);
if is_persistent_transfer {
transferred = 1;
}
if count == 0 {
break;
}
count -= 1;
}
digits.reverse();
Bigint::from_components( digits, bigger.sign)
}
fn cmp_positive(&self, other: &Self) -> Ordering {
if self.digits.len() > other.digits.len() {
Ordering::Greater
} else if self.digits.len() < other.digits.len() {
Ordering::Less
} else {
self.cmp_same_length_positive(other)
}
}
fn cmp_same_length_positive(&self, other: &Self) -> Ordering {
let mut count: usize = 0;
while count < self.digits.len() {
if self.digits[count].cmp(&other.digits[count]) != Ordering::Equal {
return self.digits[count].cmp(&other.digits[count])
}
count += 1;
}
Ordering::Equal
}
fn add_diff_length(bigger: &Self, smaller: &Self) -> Self {
let mut bigger_clone = Bigint{ digits: bigger.digits.clone(), sign: bigger.sign, };
let mut new_smaller = Bigint::stretch_with_nils(&smaller, bigger.digits.len());
if new_smaller.sign != bigger_clone.sign {
Bigint::subtraction_product_from(&mut bigger_clone, &mut new_smaller)
} else {
Bigint::addition_product_from(&bigger_clone, &new_smaller)
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s.is_empty() {
return Ok(Bigint::new())
}
let vec_from_string: Vec<char> = s.chars().collect();
let mut digits: Vec<u8> = Vec::<u8>::new();
for ch in &vec_from_string {
let is_num: bool = { *ch >= '0' && *ch <= '9' };
let is_optional_beg_op: bool = { *ch == vec_from_string[0] && ( *ch == '+' || *ch == '-' ) };
if (!is_num && !is_optional_beg_op) ||
(is_optional_beg_op && vec_from_string.len() == 1) {
return Err(ParseError)
} else if is_num {
digits.push(ch.to_digit(10).unwrap() as u8);
}
}
Ok(Bigint::from_components(
digits,
match vec_from_string[0] {
'+' => 1,
'-' => -1,
_ => 1,
}, ))
}
}
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 let 1 = self.sign {
if let 1 = other.sign {
self.cmp_positive(other)
} else {
Ordering::Greater
}
} else {
if let 1 = other.sign {
Ordering::Less
} else {
self.cmp_positive(other).reverse()
}
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.digits.len() > other.digits.len() {
Bigint::add_diff_length(&self, &other)
} else if self.digits.len() < other.digits.len() {
Bigint::add_diff_length(&other, &self)
} else {
let mut self_clone = Bigint{ digits: self.digits.clone(), sign: self.sign, };
let mut other_clone = Bigint{ digits: other.digits.clone(), sign: other.sign, };
if self_clone.sign != other_clone.sign {
if self_clone.cmp_same_length_positive(&other_clone) == Ordering::Greater {
Bigint::subtraction_product_from(&mut self_clone, &mut other_clone)
} else if self_clone.cmp_same_length_positive(&other_clone) == Ordering::Less {
Bigint::subtraction_product_from(&mut other_clone, &mut self_clone)
} else {
Bigint::new()
}
} else {
Bigint::addition_product_from(&self_clone, &other_clone)
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + Bigint{ digits: other.digits.clone(), sign: -1*other.sign, }
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-1tr64ow/solution)
warning: value assigned to `transferred` is never read
--> src/lib.rs:165:21
|
165 | transferred = 0;
| ^^^^^^^^^^^
|
= note: `#[warn(unused_assignments)]` on by default
= help: maybe it is overwritten before being read?
warning: 1 warning emitted
Finished test [unoptimized + debuginfo] target(s) in 1.62s
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 ... 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
test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out