Решение на Bigint от Георги Анастасов
Към профила на Георги Анастасов
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
use std::cmp;
use std::cmp::Ordering;
// use std::mem;
use std::ops::{Add, Sub};
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
let mut empty_bigint: Vec<u8> = Vec::new();
empty_bigint.push(0);
Bigint {
sign: 1,
digits: empty_bigint,
}
}
pub fn from_components(mut digits: Vec<u8>, sign: i8) -> Self {
while digits[0] == 0 && digits.len() > 1 {
digits.remove(0);
}
if digits[0] == 0 {
Bigint { sign: 1, digits }
} else {
Bigint { sign, digits }
}
}
pub fn is_positive(&self) -> bool {
if self.digits[0] == 0 {
return false;
}
self.sign == 1
}
pub fn is_negative(&self) -> bool {
if self.digits[0] == 0 {
return false;
}
self.sign == -1
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut digits: Vec<u8> = Vec::new();
let mut sign = 0;
if s == "" {
digits.push(0);
sign = 1;
}
for char_c in s.chars() {
if char_c == '-' && sign == 0 {
sign = -1;
} else if char_c == '+' && sign == 0 {
sign = 1;
} else {
match char_c.to_digit(10) {
Some(t) => digits.push(t as u8),
None => return Err(ParseError),
}
}
}
if sign == 0 {
sign = 1;
}
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 {
Ordering::Greater
} else if self.sign < other.sign {
Ordering::Less
} else {
if self.sign == 1 {
if self.digits.len() > other.digits.len() {
Ordering::Greater
} else if self.digits.len() < other.digits.len() {
Ordering::Less
} else {
self.digits.cmp(&other.digits)
}
} else {
if self.digits.len() < other.digits.len() {
Ordering::Greater
} else if self.digits.len() > other.digits.len() {
Ordering::Less
} else {
self.digits.cmp(&other.digits).reverse()
}
}
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut sum_vec: Vec<u8> = Vec::new();
let mut self_reversed: Vec<u8> = Vec::new();
let mut other_reversed: Vec<u8> = Vec::new();
let new_sign: i8;
let max_len = cmp::max(self.digits.len(), other.digits.len());
if vect_func::abs_vector(&self.digits, &other.digits) {
for elem in self.digits.iter().rev() {
self_reversed.push(*elem);
}
for elem in other.digits.iter().rev() {
other_reversed.push(*elem);
}
new_sign = self.sign;
} else {
for elem in self.digits.iter().rev() {
other_reversed.push(*elem);
}
for elem in other.digits.iter().rev() {
self_reversed.push(*elem);
}
new_sign = other.sign;
}
vect_func::add_zeros(&mut self_reversed, max_len);
vect_func::add_zeros(&mut other_reversed, max_len);
let mut one_on_mind = 0;
if self.sign == other.sign {
for elem in 0..max_len {
let sum: u8 = self_reversed[elem] + other_reversed[elem];
if sum >= 10 || sum + one_on_mind == 10 {
sum_vec.push(sum + one_on_mind - 10);
one_on_mind = 1;
} else {
sum_vec.push(sum + one_on_mind);
one_on_mind = 0;
}
}
if one_on_mind == 1 {
sum_vec.push(one_on_mind);
}
} else {
for elem in 0..max_len {
let sum: u8;
if self_reversed[elem] >= other_reversed[elem] {
sum = self_reversed[elem] - other_reversed[elem];
if sum == 0 && one_on_mind == 1 {
sum_vec.push(9);
} else {
sum_vec.push(sum - one_on_mind);
one_on_mind = 0;
}
} else {
sum = self_reversed[elem] + 10 - other_reversed[elem];
sum_vec.push(sum - one_on_mind);
one_on_mind = 1;
}
}
if one_on_mind == 1 {
sum_vec.remove(sum_vec.len() - 1);
}
}
sum_vec.reverse();
Bigint::from_components(sum_vec, new_sign)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + Bigint {
sign: other.sign * (-1),
digits: other.digits,
}
}
}
mod vect_func {
use std::cmp::Ordering;
pub fn abs_vector(this: &Vec<u8>, that: &Vec<u8>) -> bool {
if this.len() == that.len() {
match this.cmp(&that) {
Ordering::Less => return false,
Ordering::Greater => return true,
Ordering::Equal => return true,
};
}
this.len() > that.len()
}
pub fn add_zeros(raw_vector: &mut Vec<u8>, size: usize) {
while raw_vector.len() < size {
raw_vector.push(0);
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-1kz6zhj/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.70s
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