Решение на Bigint от Йоана Николова
Резултати
- 12 точки от тестове
- 0 бонус точки
- 12 точки общо
- 12 успешни тест(а)
- 3 неуспешни тест(а)
Код
use std::str::FromStr;
use std::iter::FromIterator;
use std::fmt::Debug;
use std::cmp::Ordering;
use std::ops::{Add, Sub};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
#[derive(Debug)]
pub struct ParseError;
impl Bigint {
pub fn new() -> Self {
Bigint{sign: 1, digits: vec![0] }
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
if digits.is_empty() {
return Bigint::new()
}
let last_zero_index = has_zeros_till_index(digits.clone());
if last_zero_index == digits.len(){
return Bigint::new()
}
else {
if last_zero_index > 0{
return Bigint{sign, digits: Vec::from_iter(digits[last_zero_index ..digits.len()].iter().cloned())}
}
}
Bigint{sign, digits}
}
pub fn is_positive(&self) -> bool {
if self.digits.is_empty(){
return false
}
let last_zero_index = has_zeros_till_index(self.digits.clone());
if last_zero_index == self.digits.len() {
return false
} else {
return self.sign == 1
}
}
pub fn is_negative(&self) -> bool {
if self.digits.is_empty(){
return false
}
let last_zero_index = has_zeros_till_index(self.digits.clone());
if last_zero_index == self.digits.len(){
return false
}
if self.digits[0] == 0 {
return false
} else {
return self.sign == -1
}
}
}
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 digits: Vec<u8> ;
let mut char_vec: Vec<char> = s.chars().collect();
let mut temp: Vec<u8> = Vec::new();
let sign;
if char_vec[0] == '+' || char_vec[0] == '-' {
if char_vec[0] == '+'{
sign = 1;
}
else {
sign = -1;
}
char_vec.remove(0);
}
else {
sign = 1;
}
for ch in char_vec {
match ch {
'0'..='9' => {
let ch = ch as u8 - '0' as u8;
temp.push(ch);
},
_ => {
return Err(ParseError);
},
};
}
digits = temp.clone();
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 {
let copy_self = Bigint::from_components(self.digits.clone(), self.sign);
let copy_other = Bigint::from_components(other.digits.clone(), other.sign);
if copy_self.sign > copy_other.sign {
// + > -
return Ordering::Greater;
}
else {
if copy_self.sign < copy_other.sign {
// - < +
return Ordering::Less;
}
else {
let x = compare_digits(©_self, ©_other);
if copy_self.sign == 1{
return x;
}
else {
return x.reverse();
}
}
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let copy_self = Bigint::from_components(self.digits.clone(), self.sign);
let copy_other = Bigint::from_components(other.digits.clone(), other.sign);
if copy_self.sign == copy_other.sign{
return Bigint::from_components(add_digits(copy_self.digits, copy_other.digits), copy_self.sign);
}
else {
match compare_digits(©_self, ©_other){
Ordering::Greater => Bigint::from_components(subtract_digits(copy_self.digits, copy_other.digits), copy_self.sign),
Ordering::Less => Bigint::from_components(subtract_digits(copy_other.digits, copy_self.digits), copy_other.sign),
Ordering::Equal => Bigint::new(),
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
return match other.sign {
1 => self.add(Bigint::from_components(other.digits, -1)),
_ => self.add(Bigint::from_components(other.digits, 1)),
}
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut temp:Vec<u8> = Vec::new();
let mut counter = 0;
let left_is_bigger_vec = if left.len() >= right.len(){ true } else { false };
let bigger_length = if left_is_bigger_vec { left.len() } else { right.len() };
let smaller_length = if left_is_bigger_vec { right.len() } else { left.len() };
let mut add_1 = false;
left.reverse();
right.reverse();
while counter < bigger_length {
if counter >= smaller_length {
let digit;
if left_is_bigger_vec{
digit = if add_1 { left[counter] + 1} else { left[counter] };
}
else {
digit = if add_1 { right[counter] + 1} else { right[counter] };
}
add_1 = false;
temp.push(digit);
}
else {
let sum = if add_1 { left[counter] + right[counter] + 1} else { left[counter] + right[counter] };
if sum >= 9{
add_1 = true;
temp.push(sum%10);
}
else {
add_1 = false;
temp.push(sum);
}
}
counter += 1;
}
if add_1 {
temp.push(1);
}
temp.reverse();
return temp.clone();
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
let mut temp:Vec<u8> = Vec::new();
let mut counter = 0;
let bigger_length = larger.len();
let smaller_length = smaller.len();
let mut sub_1 = false;
larger.reverse();
smaller.reverse();
while counter < bigger_length {
if counter >= smaller_length {
let digit;
if sub_1{
if larger[counter] < 1 {
digit = 9;
sub_1 = true;
}
else {
digit = larger[counter] - 1;
sub_1 = false;
}
}
else {
digit = larger[counter];
sub_1 = false;
}
temp.push(digit);
}
else {
let sub_digit;
if sub_1 {
if larger[counter] < smaller[counter] + 1 {
sub_digit = 10 + larger[counter] - smaller[counter] - 1;
sub_1 = true;
}
else {
sub_digit = larger[counter] - smaller[counter] - 1;
sub_1 = false;
}
}
else {
if larger[counter] < smaller[counter] {
sub_digit = 10 + larger[counter] - smaller[counter];
sub_1 = true;
}
else {
sub_digit = larger[counter] - smaller[counter];
sub_1 = false;
}
}
temp.push(sub_digit);
}
counter += 1;
}
temp.reverse();
return temp.clone();
}
fn has_zeros_till_index(vector: Vec<u8>) -> usize{
let mut index = 0;
for digit in vector{
if digit == 0{
index += 1;
}
else {
break;
}
}
index
}
fn compare_digits(first_number: &Bigint, second_number: &Bigint) -> Ordering{
let first_len = first_number.digits.len();
let second_len = second_number.digits.len();
if first_len == second_len {
let mut counter = 0;
while counter < first_len {
if first_number.digits[counter] == second_number.digits[counter] {
counter += 1;
} else {
if first_number.digits[counter] > second_number.digits[counter] {
return Ordering::Greater;
} else {
return Ordering::Less;
}
}
}
return Ordering::Equal;
}
else {
if first_len > second_len {
return Ordering::Greater;
} else {
return Ordering::Less;
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-s1911r/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.78s
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 ... FAILED
test solution_test::test_sum_3_overflow ... FAILED
test solution_test::test_sum_4_negative ... FAILED
failures:
---- solution_test::test_sum_2_different_lengths stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [5, 8, 9] }`,
right: `Bigint { sign: 1, digits: [5, 7, 9] }`', tests/solution_test.rs:92:5
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: [9, 10, 0] }`,
right: `Bigint { sign: 1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:97:5
---- solution_test::test_sum_4_negative stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: -1, digits: [5, 8, 9] }`,
right: `Bigint { sign: -1, digits: [5, 7, 9] }`', tests/solution_test.rs:112:5
failures:
solution_test::test_sum_2_different_lengths
solution_test::test_sum_3_overflow
solution_test::test_sum_4_negative
test result: FAILED. 12 passed; 3 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'