Решение на Bigint от Тихомир Каменов

Обратно към всички решения

Към профила на Тихомир Каменов

Код

#[derive(Debug, PartialEq, Eq)]

pub struct Bigint {

sign: i8,

digits: Vec<u8>,

}

impl Bigint {

pub fn new() -> Self {

Self { sign: 1, digits: Vec::<u8>::new() }

}

fn from_components(digits: Vec<u8>, sign: i8) -> Self {

if digits.is_empty() {

return Bigint::new();

}

let mut digits_iter = digits.iter();

let mut dig_vec = Vec::<u8>::new();

// used to signal that there are 0s in the beginning of the vector

let mut zero_flag = true;

loop {

let temp = digits_iter.next();

match temp {

Some(&0) => if zero_flag { continue } else { dig_vec.push(0) },

Some(&i) => {

zero_flag = false;

dig_vec.push(i);

},

None => if zero_flag { return Bigint::new() } else { break; }

}

}

Self {sign, digits: dig_vec}

}

pub fn is_positive(&self) -> bool {

if self.digits.is_empty() {

return false;

}

self.sign == 1

}

pub fn is_negative(&self) -> bool {

if self.digits.is_empty() {

return false;

}

self.sign == -1

}

// used in the add function

fn abs(&self) -> Self {

Bigint::from_components(self.digits.clone(), 1)

}

}

#[derive(Debug)]

pub struct ParseError;

use std::str::FromStr;

impl FromStr for Bigint {

type Err = ParseError;

fn from_str(s: &str) -> Result<Self, Self::Err> {

let mut iter = (*s).chars();

let mut digits = Vec::<u8>::new();

let mut sign: i8 = 1;

// used to allow + and - in the beginning

let mut symbol_flag = true;

loop {

match iter.next() {

None => break,

Some(i) => {

if i >= '0' && i <= '9' {

symbol_flag = false;

digits.push(i as u8 - '0' as u8);

} else if symbol_flag && i == '-' {

sign = -1;

} else if symbol_flag && i == '+' {

continue;

} else {

return Err(ParseError);

}

}

}

}

Ok(Bigint::from_components(digits, sign))

}

}

use std::cmp::Ordering;

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);

}

if self.digits.len() != other.digits.len() {

if self.is_positive() {

// 187 > 25

return self.digits.len().cmp(&other.digits.len());

} else {

// -187 < -25

return other.digits.len().cmp(&self.digits.len());

}

}

for i in 0..self.digits.len() {

if self.digits[i] != other.digits[i] {

if self.is_positive() {

return self.digits[i].cmp(&other.digits[i]);

} else {

return other.digits[i].cmp(&self.digits[i]);

}

}

}

Ordering::Equal

}

}

use std::ops::{Add, Sub};

impl Add for Bigint {

type Output = Bigint;

fn add(self, other: Self) -> Self {

if self.digits.is_empty() {

return other;

}

if other.digits.is_empty() {

return self;

}

let res;

let sign;

if self.sign == other.sign {

res = add_digits(self.digits, other.digits);

sign = self.sign;

} else {

if self.abs() > other.abs() {

res = subtract_digits(self.digits, other.digits);

sign = self.sign;

} else {

res = subtract_digits(other.digits, self.digits);

sign = other.sign;

}

}

Bigint::from_components(res, sign)

}

}

impl Sub for Bigint {

type Output = Bigint;

fn sub(self, other: Self) -> Self {

if other.is_positive() {

// A - B => A + (-B)

return self + Bigint::from_components(other.digits, -1);

}

// A - (-B) => A + B

self + Bigint::from_components(other.digits, 1)

}

}

fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {

let mut res = Vec::<u8>::new();

let mut smaller = left;

let mut bigger = right;

let carryover = 1;

if smaller.len() > bigger.len() {

let temp = bigger;

bigger = smaller;

smaller = temp;

}

smaller.reverse();

bigger.reverse();

for i in 0..smaller.len() {

res.push((bigger[i] + smaller[i]) % 10);

if bigger[i] + smaller[i] >= 10 {

if i < bigger.len() - 1 {

bigger[i+1] += carryover;

} else {

res.push(carryover);

}

}

}

// adding the remaining digits

for i in smaller.len()..bigger.len() {

res.push(bigger[i]);

}

res.reverse();

res

}

fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {

if larger.is_empty() {

return smaller;

}

if smaller.is_empty() {

return larger;

}

let mut res = Vec::<u8>::new();

let borrow = 1;

larger.reverse();

smaller.reverse();

for i in 0..smaller.len() {

// ex.: 25 - 7; 5 - 7 => 15 - 7 = 8 and the previous digit is decreased by 1

if larger[i] < smaller[i] {

res.push(larger[i] + 10 - smaller[i]);

larger[i + 1] -= borrow;

} else {

res.push(larger[i] - smaller[i]);

}

}

for i in smaller.len()..larger.len() {

res.push(larger[i]);

}

res.reverse();

res

}

#[cfg(test)]

mod tests {

use super::Bigint;

use std::str::FromStr;

#[test]

fn test_from_str_when_input_is_a_positive_number() {

let number = "00113";

let expected_digits = vec![1,1,3];

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = Bigint::from_str(number).unwrap();

assert_eq!(expected, result);

}

#[test]

fn test_from_str_when_input_is_a_positive_number_with_a_symbol() {

let number = "+00113";

let expected_digits = vec![1,1,3];

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = Bigint::from_str(number).unwrap();

assert_eq!(expected, result);

}

#[test]

fn test_from_str_when_input_is_a_negative_number() {

let number = "-00113";

let expected_digits = vec![1,1,3];

let expected_sign = -1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = Bigint::from_str(number).unwrap();

assert_eq!(expected, result);

}

#[test]

#[should_panic]

fn test_from_str_when_input_is_invalid() {

let number = "-00?13";

Bigint::from_str(number).unwrap();

}

#[test]

fn test_from_str_when_input_is_empty_string() {

let number = "";

let expected_digits = Vec::<u8>::new();

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = Bigint::from_str(number).unwrap();

assert_eq!(expected, result);

}

#[test]

fn test_bigint_new() {

let expected_digits = Vec::<u8>::new();

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = Bigint::new();

assert_eq!(expected, result);

}

#[test]

fn test_is_positive_with_positive_number() {

let number = "42";

let bigint = Bigint::from_str(number).unwrap();

assert!(bigint.is_positive());

}

#[test]

#[should_panic]

fn test_is_positive_with_negative_number() {

let number = "-42";

let bigint = Bigint::from_str(number).unwrap();

assert!(bigint.is_positive());

}

#[test]

fn test_is_negative_with_negative_number() {

let number = "-42";

let bigint = Bigint::from_str(number).unwrap();

assert!(bigint.is_negative());

}

#[test]

#[should_panic]

fn test_is_negative_with_positive_number() {

let number = "42";

let bigint = Bigint::from_str(number).unwrap();

assert!(bigint.is_negative());

}

use std::cmp::Ordering;

#[test]

fn test_cmp_with_equal_numbers() {

let number = "42";

let bigint1 = Bigint::from_str(number).unwrap();

let bigint2 = Bigint::from_str(number).unwrap();

let expected = Ordering::Equal;

let result = bigint1.cmp(&bigint2);

assert_eq!(expected, result);

}

#[test]

fn test_cmp_with_a_bigger_and_a_smaller_number() {

let number1 = "12345";

let number2 = "424";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected = Ordering::Greater;

let result = bigint1.cmp(&bigint2);

assert_eq!(expected, result);

}

#[test]

fn test_cmp_with_a_bigger_and_a_smaller_number_of_same_len() {

let number1 = "94";

let number2 = "23";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected = Ordering::Greater;

let result = bigint1.cmp(&bigint2);

assert_eq!(expected, result);

}

#[test]

fn test_cmp_with_a_positive_and_a_negative_number() {

let number1 = "123";

let number2 = "-123";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected = Ordering::Greater;

let result = bigint1.cmp(&bigint2);

assert_eq!(expected, result);

}

#[test]

fn test_cmp_with_a_negative_and_a_positive_number() {

let number1 = "-123";

let number2 = "123";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected = Ordering::Less;

let result = bigint1.cmp(&bigint2);

assert_eq!(expected, result);

}

#[test]

fn test_cmp_with_a_smaller_negative_and_a_bigger_negative_number() {

let number1 = "-123";

let number2 = "-87";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected = Ordering::Less;

let result = bigint1.cmp(&bigint2);

assert_eq!(expected, result);

}

#[test]

fn test_cmp_with_a_smaller_negative_and_a_bigger_negative_number_of_same_len() {

let number1 = "-93";

let number2 = "-87";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected = Ordering::Less;

let result = bigint1.cmp(&bigint2);

assert_eq!(expected, result);

}

#[test]

fn test_add_with_positive_numbers() {

let number1 = "1234";

let number2 = "12345";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![1,3,5,7,9];

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 + bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_positive_numbers_with_carryover() {

let number = "546";

let bigint1 = Bigint::from_str(number).unwrap();

let bigint2 = Bigint::from_str(number).unwrap();

let expected_digits = vec![1,0,9,2];

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 + bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_a_positive_and_a_negative_number() {

let number1 = "546";

let number2 = "-488";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![5,8];

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 + bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_a_negative_and_a_positive_number() {

let number1 = "-488";

let number2 = "546";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![5,8];

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 + bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_a_positive_number_with_smaller_abs_value_and_a_negative_number_with_bigger_abs_value() {

let number1 = "488";

let number2 = "-546";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![5,8];

let expected_sign = -1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 + bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_negative_numbers() {

let number1 = "-1234";

let number2 = "-12345";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![1,3,5,7,9];

let expected_sign = -1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 + bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_a_positive_number_and_zero() {

let number = "123";

let bigint1 = Bigint::from_str(number).unwrap();

let bigint2 = Bigint::new();

let expected = Bigint::from_str(number).unwrap();

let result = bigint1 + bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_zero_and_a_positive_number() {

let number = "123";

let bigint1 = Bigint::from_str(number).unwrap();

let bigint2 = Bigint::new();

let expected = Bigint::from_str(number).unwrap();

let result = bigint2 + bigint1;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_a_negative_number_and_zero() {

let number = "-123";

let bigint1 = Bigint::from_str(number).unwrap();

let bigint2 = Bigint::new();

let expected = Bigint::from_str(number).unwrap();

let result = bigint1 + bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_add_with_zero_and_a_negative_number() {

let number = "-123";

let bigint1 = Bigint::from_str(number).unwrap();

let bigint2 = Bigint::new();

let expected = Bigint::from_str(number).unwrap();

let result = bigint2 + bigint1;

assert_eq!(expected, result);

}

#[test]

fn test_sub_with_positive_numbers() {

let number1 = "13";

let number2 = "77";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![6, 4];

let expected_sign = -1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 - bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_sub_with_negative_numbers() {

let number1 = "-400";

let number2 = "-550";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![1,5,0];

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 - bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_sub_with_a_positive_and_a_negative_number() {

let number1 = "847";

let number2 = "-235";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![1,0,8,2];

let expected_sign = 1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 - bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_sub_with_a_negative_and_a_positive_number() {

let number1 = "-235";

let number2 = "847";

let bigint1 = Bigint::from_str(number1).unwrap();

let bigint2 = Bigint::from_str(number2).unwrap();

let expected_digits = vec![1,0,8,2];

let expected_sign = -1;

let expected = Bigint::from_components(expected_digits, expected_sign);

let result = bigint1 - bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_sub_with_a_positive_number_and_zero() {

let number = "123";

let bigint1 = Bigint::from_str(number).unwrap();

let bigint2 = Bigint::new();

let expected = Bigint::from_str(number).unwrap();

let result = bigint1 - bigint2;

assert_eq!(expected, result);

}

#[test]

fn test_sub_with_zero_and_a_positive_number() {

let number = "123";

let neg_number = "-123";

let bigint1 = Bigint::from_str(number).unwrap();

let bigint2 = Bigint::new();

let expected = Bigint::from_str(neg_number).unwrap();

let result = bigint2 - bigint1;

assert_eq!(expected, result);

}

}

Лог от изпълнението

Compiling solution v0.1.0 (/tmp/d20201127-2274206-32r1sy/solution)
    Finished test [unoptimized + debuginfo] target(s) in 2.56s
     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:236:13
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


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'

История (2 версии и 1 коментар)