Решение на Bigint от Иван Иванов
Резултати
- 14 точки от тестове
- 0 бонус точки
- 14 точки общо
- 14 успешни тест(а)
- 1 неуспешни тест(а)
Код
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 {
return Bigint{sign:1, digits : vec![0]}
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
if sign != 1 && sign != -1{
panic!("Sign should be eighter 1 or -1")
}
if digits.is_empty() || (digits.len() ==1 && digits[0] == 0){
return Bigint::new();
}
let preprocessed_digits = remove_trailing_zerous(&digits);
return Bigint{sign: sign, digits : preprocessed_digits}
}
pub fn is_positive(&self) -> bool {
return self.sign == 1 && self.digits[0] != 0;
}
pub fn is_negative(&self) -> bool {
return 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 s.is_empty(){
return Ok(Bigint::new());
}
if !check_if_string_matches_pattern(s){
return Err(ParseError);
}
let mut sign : i8 = 1;
if s.chars().nth(0).unwrap() == '-' {
sign = -1;
}
let mut digits :Vec<u8> = Vec::new();
for c in s.chars() {
if c.is_digit(10) {
digits.push(c.to_digit(10).unwrap() as u8);
}
}
return Ok(Bigint::from_components(digits, sign));
}
}
fn check_if_string_matches_pattern(s: &str) -> bool {
for (i,c) in s.chars().enumerate() {
if i==0 && c != '+' && c!= '-' && !c.is_digit(10) {
return false;
}
if i >0 && !c.is_digit(10){
return false;
}
}
return true;
}
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 Ordering::Less;
}
else if self.sign > other.sign {
return Ordering::Greater;
}
if self.sign == 1{
return compare_positive_bigint_numbers(self,other);
}else{
return compare_negative_bigint_numbers(self,other);
}
}
}
fn compare_negative_bigint_numbers(first: &Bigint, second: &Bigint) -> Ordering {
if first.digits.len() > second.digits.len() {
return Ordering::Less;
}
else if first.digits.len() < second.digits.len(){
return Ordering::Greater;
}
for i in 0..first.digits.len(){
if first.digits[i] > second.digits[i] {
return Ordering::Less;
}
else if first.digits[i] < second.digits[i] {
return Ordering::Greater;
}
}
return Ordering::Equal;
}
fn compare_positive_bigint_numbers(first: &Bigint, second: &Bigint) -> Ordering {
if first.digits.len() < second.digits.len() {
return Ordering::Less;
}
else if first.digits.len() > second.digits.len(){
return Ordering::Greater;
}
for i in 0..first.digits.len(){
if first.digits[i] < second.digits[i] {
return Ordering::Less;
}
else if first.digits[i] > second.digits[i] {
return Ordering::Greater;
}
}
return Ordering::Equal;
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
let digits = add_digits(self.digits, other.digits);
return Bigint{ digits : digits, sign : self.sign};
}
let positive_self = Bigint{sign : 1, digits : self.digits};
let positive_other = Bigint{sign : 1, digits : other.digits};
if positive_self.cmp(&positive_other) == Ordering::Greater {
let digits = subtract_digits(positive_self.digits, positive_other.digits);
return Bigint{ sign : self.sign, digits : digits};
} else if positive_self.cmp(&positive_other) == Ordering::Less {
let digits = subtract_digits(positive_other.digits, positive_self.digits);
return Bigint{ sign : other.sign, digits : digits};
} else {
return Bigint::new();
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let negative_other = Bigint {sign: -1*other.sign, digits: other.digits};
let result = self.add(negative_other);
return result;
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let size_diff = (left.len() as i32 - right.len() as i32).abs() as usize;
let mut vector_of_zeroes = vec![0; size_diff];
if left.len() < right.len() {
vector_of_zeroes.append(&mut left);
return add_digits_equal_len(vector_of_zeroes, right);
} else if left.len() > right.len() {
vector_of_zeroes.append(&mut right);
return add_digits_equal_len(left, vector_of_zeroes);
}
return add_digits_equal_len(left, right);
}
fn add_digits_equal_len(first: Vec<u8>, second: Vec<u8>) -> Vec<u8> {
let mut result = Vec::new();
let mut carry = 0;
for i in (0..first.len()).rev() {
let mut digit = first[i] + second[i] + carry;
if digit > 9{
digit = digit - 10;
carry = 1;
}else{
carry = 0;
}
result.push(digit);
}
if carry != 0 {
result.push(1);
}
result.reverse();
return result;
}
fn substract_digits_equal_len(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut result = Vec::new();
let mut carry = 0;
for i in (0..larger.len()).rev() {
let digit = (larger[i] as i8 - smaller[i] as i8 - carry) as i8;
if digit < 0 {
result.push((digit + 10) as u8);
carry = 1;
} else {
result.push(digit as u8);
carry = 0;
}
}
result.reverse();
result = remove_trailing_zerous(&mut result);
return result;
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
let size_diff = (larger.len() as i32 - smaller.len() as i32).abs() as usize;
let mut vector_of_zeroes = vec![0; size_diff];
if larger.len() < smaller.len() {
vector_of_zeroes.append(&mut larger);
return substract_digits_equal_len(vector_of_zeroes, smaller);
} else if larger.len() > smaller.len() {
vector_of_zeroes.append(&mut smaller);
return substract_digits_equal_len(larger, vector_of_zeroes);
}
return substract_digits_equal_len(larger, smaller);
}
fn remove_trailing_zerous(digits: &Vec<u8>) -> Vec<u8> {
let mut preprocessed_digits = Vec::new();
let mut leading_zeroes_skipped = false;
for i in 0..digits.len(){
if digits[i] != 0{
leading_zeroes_skipped=true;
}
if leading_zeroes_skipped {
preprocessed_digits.push(digits[i]);
}
}
return preprocessed_digits;
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-18k6yhy/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.60s
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 ... FAILED
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_parsing_with_leading_zeroes stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [] }`,
right: `Bigint { sign: 1, digits: [0] }`', tests/solution_test.rs:71:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
failures:
solution_test::test_parsing_with_leading_zeroes
test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'