Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Bigint от Тервел Вълков

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

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

Резултати

  • 15 точки от тестове
  • 0 бонус точки
  • 15 точки общо
  • 15 успешни тест(а)
  • 0 неуспешни тест(а)

Код

use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::Neg;
use std::ops::Add;
use std::ops::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 digits.is_empty() {
panic!("Cannot construct number without digits!");
}
// remove leading zeroes
let mut i = 0;
while i < digits.len() && digits[i] == 0 { // find index of last leading zero
i += 1;
}
let mut digits = digits;
digits.drain(0..i);
// if the digits were all zeroes, then we would have removed all of them, leaving an empty vector, but we need at least one zero
if digits.is_empty() {
digits.push(0);
}
// if digits == vec![0] && sign == -1 {
// panic!("Negative zero not allowed!");
// }
let mut sign = sign;
if digits == vec![0] && sign == -1 {
sign = 1;
}
Bigint {
sign: sign,
digits: digits,
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.is_zero() == false
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.is_zero() == false
}
pub fn is_zero(&self) -> bool {
self.digits == vec![0]
}
pub fn abs(&self) -> Self {
Bigint {
sign: 1,
digits: self.digits.clone(),
}
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint {
sign: self.sign * (-1),
digits: self.digits.clone(),
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut s = String::from(s);
let sign: i8;
if s.starts_with("+") {
sign = 1;
s.remove(0);
} else if s.starts_with("-") {
sign = -1;
s.remove(0);
} else { // if there is no sign, we assume positive
sign = 1;
}
if s.is_empty() {
s = String::from("0");
} // if s is just "+" or "-", we'll treat it as a zero
if s.chars().all(|x| x.is_ascii_digit()) == false { // there are any non-digit characters
return Err(ParseError);
}
let digits = s.chars().map(|ch| ch.to_digit(10).unwrap()).map(|x| x as u8).collect();
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 == 1 && other.sign == -1 {
return Ordering::Greater;
} else if self.sign == -1 && other.sign == 1 {
return Ordering::Less;
}
let sign = self.sign;
if self.digits.len() > other.digits.len() {
if sign == 1 {
return Ordering::Greater;
} else if sign == -1 {
return Ordering::Less;
}
} else if self.digits.len() < other.digits.len() {
if sign == 1 {
return Ordering::Less;
} else if sign == -1 {
return Ordering::Greater;
}
}
// ??? more elegant way to do this?
for i in 0..self.digits.len() {
if sign == 1 {
if self.digits[i] > other.digits[i] {
return Ordering::Greater;
} else if self.digits[i] < other.digits[i] {
return Ordering::Less
}
} else if sign == -1 {
if self.digits[i] > other.digits[i] {
return Ordering::Less;
} else if self.digits[i] < other.digits[i] {
return Ordering::Greater
}
}
}
// ??? something with zip? map?
// for (x, y) in self.digits.iter().zip(other.digits.iter()) {
// ...
// }
Ordering::Equal
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
fn add_digits(left: &Vec<u8>, right: &Vec<u8>) -> Vec<u8> {
let length_max = std::cmp::max(left.len(), right.len());
let left_padded = zero_pad(left, length_max);
let right_padded = zero_pad(right, length_max);
let mut result = Vec::new();
let mut carry: u8 = 0;
for i in (0..length_max).rev() {
let digit = left_padded[i] + right_padded[i] + carry;
if digit >= 10 {
result.push(digit % 10);
carry = 1;
} else {
result.push(digit);
carry = 0;
}
}
if carry == 1 {
result.push(1);
}
result.reverse();
result
}
fn subtract_digits(larger: &Vec<u8>, smaller: &Vec<u8>) -> Vec<u8> {
let smaller_padded = zero_pad(smaller, larger.len());
// we don't need to pad the larger number, since it's larger by absolute value, and so has at least as many digits as the smaller one
let mut result = Vec::new();
let mut carry: u8 = 0;
for i in (0..larger.len()).rev() {
if larger[i] < smaller_padded[i] + carry {
result.push(larger[i] + 10 - smaller_padded[i] - carry); // borrowing
carry = 1;
} else {
result.push(larger[i] - smaller_padded[i] - carry);
carry = 0;
}
}
if carry != 0 { // as we're subtracting from the larger number, there shouldn't be a carried one at the end
panic!("Subtraction error!");
}
// I don't know why I decided to do a mathematical proof in the middle of my code, but here it is:
// assuming valid input (larger > smaller), this should hold for the numbers - there is an index k (0 <= k < larger.len()), such that:
// larger[i] == smaller_padded[i], i < k
// larger[k] > smaller_padded[k],
// in this case, (larger[k+1] - smaller_padded[k+1] - carry) may:
// I. not produce a carried one, in which case larger[k] > smaller_padded[k] + 0, so there will be no carry
// II. produce a carried one, but larger[k] >= smaller_padded[k] + 1, so there will be no carry
// (III. those digits might also not exist if k is the last index, but then there is no carry anyway)
// because larger[i] == smaller_padded[i], i < k, and there is no carry when we subtract larger[k] and smaller_padded[k],
// there will be no further carries from this point on, so if there ends up being one at the end, the input must have been invalid
result.reverse();
result
}
fn zero_pad(digits: &Vec<u8>, length: usize) -> Vec<u8> {
let mut result = digits.clone();
if length > digits.len() {
result.splice(..0, [0].repeat(length - digits.len())); // add to beginning of vector
}
result
}
if self.sign == other.sign {
return Bigint::from_components(add_digits(&self.digits, &other.digits), self.sign);
} else {
match Ord::cmp(&self.abs(), &other.abs()) {
Ordering::Greater => Bigint::from_components(subtract_digits(&self.digits, &other.digits), self.sign),
Ordering::Less => Bigint::from_components(subtract_digits(&other.digits, &self.digits), other.sign),
Ordering::Equal => Bigint::new(),
}
// if self.abs() > other.abs() {
// return Bigint::from_components(subtract_digits(&self.digits, &other.digits), self.sign);
// } else if self.abs() < other.abs() {
// return Bigint::from_components(subtract_digits(&other.digits, &self.digits), other.sign);
// } else { // different signs, but equality by absolute value, means we should get zero
// return Bigint::new();
// }
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_zero_signed() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint("+0"));
assert_eq!(regular_zero, bigint("-0"));
}
#[test]
fn test_zero_leading() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint("000"));
assert_eq!(regular_zero, bigint("000000000"));
}
#[test]
fn test_zero_empty() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint(""));
assert_eq!(regular_zero, bigint("+"));
assert_eq!(regular_zero, bigint("-"));
}
#[test]
fn test_positive() {
assert!(bigint("1234").is_positive());
assert!(bigint("+1234").is_positive());
assert!(bigint("0001234").is_positive());
assert!(bigint("+0001234").is_positive());
}
#[test]
fn test_negative() {
assert!(bigint("-1234").is_negative());
assert!(bigint("-0001234").is_negative());
}
#[test]
fn test_number_leading_zeros() {
let regular_number = bigint("123");
assert_eq!(regular_number, bigint("0123"));
assert_eq!(regular_number, bigint("000123"));
assert_eq!(regular_number, bigint("00000123"));
}
#[test]
fn test_number_sign() {
let regular_number = bigint("123");
assert_eq!(regular_number, bigint("+123"));
assert_eq!(regular_number, bigint("+000123"));
assert_eq!(regular_number, bigint("+00000123"));
}
#[test]
fn test_number_negative_sign() {
let regular_number = bigint("-123");
assert_eq!(regular_number, bigint("-123"));
assert_eq!(regular_number, bigint("-000123"));
assert_eq!(regular_number, bigint("-00000123"));
}
#[test]
fn test_invalid_two_signs() {
assert!(Bigint::from_str("++123").is_err());
}
#[test]
fn test_invalid_letter_o() {
assert!(Bigint::from_str("12O3").is_err());
}
#[test]
fn test_invalid_word() {
assert!(Bigint::from_str("word").is_err());
}
#[test]
fn test_add() {
assert_eq!(bigint("234") + bigint("666"), bigint("900"));
assert_eq!(bigint("234") + bigint("766"), bigint("1000"));
assert_eq!(bigint("111") + bigint("999"), bigint("1110"));
assert_eq!(bigint("127000") + bigint("23"), bigint("127023"));
assert_eq!(bigint("111111111111111111") + bigint("222222222222222222"), bigint("333333333333333333"));
}
#[test]
fn test_add_negative() {
assert_eq!(bigint("-234") + bigint("-666"), bigint("-900"));
assert_eq!(bigint("-234") + bigint("-766"), bigint("-1000"));
assert_eq!(bigint("-127000") + bigint("-23"), bigint("-127023"));
assert_eq!(bigint("-111111111111111111") + bigint("-222222222222222222"), bigint("-333333333333333333"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("628") - bigint("142"), bigint("486"));
assert_eq!(bigint("628") + bigint("-142"), bigint("486"));
assert_eq!(bigint("142") - bigint("628"), bigint("-486"));
assert_eq!(bigint("142") + bigint("-628"), bigint("-486"));
assert_eq!(bigint("-628") + bigint("142"), bigint("-486"));
assert_eq!(bigint("211") - bigint("238"), bigint("-27"));
assert_eq!(bigint("1000") - bigint("101"), bigint("899"));
assert_eq!(bigint("451020") - bigint("319005"), bigint("132015"));
}
#[test]
fn test_sub_negative() {
assert_eq!(bigint("-628") - bigint("-28"), bigint("-600"));
assert_eq!(bigint("-234") - bigint("-123"), bigint("-111"));
assert_eq!(bigint("-100") - bigint("-208"), bigint("108"));
}
#[test]
fn test_comparison() {
assert!(bigint("24") == bigint("24"));
assert!(bigint("24") <= bigint("24"));
assert!(bigint("1233") < bigint("1234"));
assert!(bigint("428") < bigint("620"));
assert!(bigint("000428") < bigint("000000000620"));
}
#[test]
fn test_comparison_negative() {
assert!(bigint("-24") == bigint("-24"));
assert!(bigint("-24") <= bigint("-24"));
assert!(bigint("-1233") > bigint("-1234"));
assert!(bigint("-428") > bigint("-620"));
assert!(bigint("-000428") > bigint("-000000000620"));
}
#[test]
fn test_comparison_different_signs() {
assert!(bigint("123") > bigint("-25"));
assert!(bigint("-40") < bigint("34"));
}
#[test]
fn test_comparison_different_length() {
assert!(bigint("1234") > bigint("123"));
assert!(bigint("-1234") < bigint("-123"));
assert!(bigint("790") > bigint("23"));
assert!(bigint("-790") < bigint("-23"));
assert!(bigint("1000000000000") > bigint("999999999999"));
assert!(bigint("-1000000000000") < bigint("-999999999999"));
}
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-1pa7d2o/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.80s
     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

История (3 версии и 0 коментара)

Тервел качи първо решение на 19.11.2020 22:42 (преди почти 5 години)

Тервел качи решение на 20.11.2020 13:29 (преди почти 5 години)

use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::Neg;
use std::ops::Add;
use std::ops::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 digits.is_empty() {
panic!("Cannot construct number without digits!");
}
- // remove leading zeros
+ // remove leading zeroes
let mut i = 0;
while i < digits.len() && digits[i] == 0 { // find index of last leading zero
i += 1;
}
let mut digits = digits;
digits.drain(0..i);
// if the digits were all zeroes, then we would have removed all of them, leaving an empty vector, but we need at least one zero
if digits.is_empty() {
digits.push(0);
}
// if digits == vec![0] && sign == -1 {
// panic!("Negative zero not allowed!");
// }
let mut sign = sign;
if digits == vec![0] && sign == -1 {
sign = 1;
}
Bigint {
sign: sign,
digits: digits,
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.is_zero() == false
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.is_zero() == false
}
pub fn is_zero(&self) -> bool {
self.digits == vec![0]
}
pub fn abs(&self) -> Self {
Bigint {
sign: 1,
digits: self.digits.clone(),
}
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint {
sign: self.sign * (-1),
digits: self.digits.clone(),
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut s = String::from(s);
let sign: i8;
if s.starts_with("+") {
sign = 1;
s.remove(0);
} else if s.starts_with("-") {
sign = -1;
s.remove(0);
} else { // if there is no sign, we assume positive
sign = 1;
}
if s.is_empty() {
s = String::from("0");
} // if s is just "+" or "-", we'll treat it as a zero
if s.chars().all(|x| x.is_ascii_digit()) == false { // there are any non-digit characters
return Err(ParseError);
}
- let v = s.chars().map(|ch| ch.to_digit(10).unwrap()).map(|x| x as u8).collect();
+ let digits = s.chars().map(|ch| ch.to_digit(10).unwrap()).map(|x| x as u8).collect();
- Ok(Bigint::from_components(v, sign))
+ 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 == 1 && other.sign == -1 {
return Ordering::Greater;
} else if self.sign == -1 && other.sign == 1 {
return Ordering::Less;
}
let sign = self.sign;
if self.digits.len() > other.digits.len() {
if sign == 1 {
return Ordering::Greater;
} else if sign == -1 {
return Ordering::Less;
}
} else if self.digits.len() < other.digits.len() {
if sign == 1 {
return Ordering::Less;
} else if sign == -1 {
return Ordering::Greater;
}
}
// ??? more elegant way to do this?
for i in 0..self.digits.len() {
if sign == 1 {
if self.digits[i] > other.digits[i] {
return Ordering::Greater;
} else if self.digits[i] < other.digits[i] {
return Ordering::Less
}
} else if sign == -1 {
if self.digits[i] > other.digits[i] {
return Ordering::Less;
} else if self.digits[i] < other.digits[i] {
return Ordering::Greater
}
}
}
// ??? something with zip? map?
// for (x, y) in self.digits.iter().zip(other.digits.iter()) {
// ...
// }
Ordering::Equal
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
fn add_digits(left: &Vec<u8>, right: &Vec<u8>) -> Vec<u8> {
let length_max = std::cmp::max(left.len(), right.len());
+
let left_padded = zero_pad(left, length_max);
let right_padded = zero_pad(right, length_max);
let mut result = Vec::new();
let mut carry: u8 = 0;
for i in (0..length_max).rev() {
let digit = left_padded[i] + right_padded[i] + carry;
if digit >= 10 {
result.push(digit % 10);
carry = 1;
} else {
result.push(digit);
carry = 0;
}
}
if carry == 1 {
result.push(1);
}
result.reverse();
result
}
fn subtract_digits(larger: &Vec<u8>, smaller: &Vec<u8>) -> Vec<u8> {
let smaller_padded = zero_pad(smaller, larger.len());
- // we don't need to pad the larger number, since it's larger by absolute value, and so has at least as many digits as smaller
+ // we don't need to pad the larger number, since it's larger by absolute value, and so has at least as many digits as the smaller one
let mut result = Vec::new();
let mut carry: u8 = 0;
for i in (0..larger.len()).rev() {
if larger[i] < smaller_padded[i] + carry {
- result.push(larger[i] + 10 - smaller_padded[i] - carry);
+ result.push(larger[i] + 10 - smaller_padded[i] - carry); // borrowing
carry = 1;
} else {
result.push(larger[i] - smaller_padded[i] - carry);
carry = 0;
}
}
-
+
+ if carry != 0 { // as we're subtracting from the larger number, there shouldn't be a carried one at the end
+ panic!("Subtraction error!");
+ }
+ // I don't know why I decided to do a mathematical proof in the middle of my code, but here it is:
+ // assuming valid input (larger > smaller), this should hold for the numbers - there is an index k (0 <= k < larger.len()), such that:
+ // larger[i] == smaller_padded[i], i < k
+ // larger[k] > smaller_padded[k],
+ // in this case, (larger[k+1] - smaller_padded[k+1] - carry) may:
+ // I. not produce a carried one, in which case larger[k] > smaller_padded[k] + 0, so there will be no carry
+ // II. produce a carried one, but larger[k] >= smaller_padded[k] + 1, so there will be no carry
+ // (III. those digits might also not exist if k is the last index, but then there is no carry anyway)
+ // because larger[i] == smaller_padded[i], i < k, and there is no carry when we subtract larger[k] and smaller_padded[k],
+ // there will be no further carries from this point on, so if there ends up being one at the end, the input must have been invalid
+
result.reverse();
result
}
fn zero_pad(digits: &Vec<u8>, length: usize) -> Vec<u8> {
let mut result = digits.clone();
if length > digits.len() {
- result.splice(..0, [0].repeat(length - digits.len()));
+ result.splice(..0, [0].repeat(length - digits.len())); // add to beginning of vector
}
result
}
if self.sign == other.sign {
return Bigint::from_components(add_digits(&self.digits, &other.digits), self.sign);
} else {
if self.abs() > other.abs() {
return Bigint::from_components(subtract_digits(&self.digits, &other.digits), self.sign);
- } else {
+ } else if self.abs() < other.abs() {
return Bigint::from_components(subtract_digits(&other.digits, &self.digits), other.sign);
+ } else { // different signs, but equality by absolute value, means we should get zero
+ return Bigint::new();
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_zero_signed() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint("+0"));
assert_eq!(regular_zero, bigint("-0"));
}
#[test]
fn test_zero_leading() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint("000"));
assert_eq!(regular_zero, bigint("000000000"));
}
#[test]
fn test_zero_empty() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint(""));
assert_eq!(regular_zero, bigint("+"));
assert_eq!(regular_zero, bigint("-"));
}
#[test]
fn test_positive() {
assert!(bigint("1234").is_positive());
assert!(bigint("+1234").is_positive());
assert!(bigint("0001234").is_positive());
assert!(bigint("+0001234").is_positive());
}
#[test]
fn test_negative() {
assert!(bigint("-1234").is_negative());
assert!(bigint("-0001234").is_negative());
}
#[test]
fn test_number_leading_zeros() {
let regular_number = bigint("123");
assert_eq!(regular_number, bigint("0123"));
assert_eq!(regular_number, bigint("000123"));
assert_eq!(regular_number, bigint("00000123"));
}
#[test]
fn test_number_sign() {
let regular_number = bigint("123");
assert_eq!(regular_number, bigint("+123"));
assert_eq!(regular_number, bigint("+000123"));
assert_eq!(regular_number, bigint("+00000123"));
}
#[test]
fn test_number_negative_sign() {
let regular_number = bigint("-123");
assert_eq!(regular_number, bigint("-123"));
assert_eq!(regular_number, bigint("-000123"));
assert_eq!(regular_number, bigint("-00000123"));
}
#[test]
fn test_invalid_two_signs() {
assert!(Bigint::from_str("++123").is_err());
}
#[test]
fn test_invalid_letter_o() {
assert!(Bigint::from_str("12O3").is_err());
}
#[test]
fn test_invalid_word() {
assert!(Bigint::from_str("word").is_err());
}
#[test]
fn test_add() {
assert_eq!(bigint("234") + bigint("666"), bigint("900"));
assert_eq!(bigint("234") + bigint("766"), bigint("1000"));
assert_eq!(bigint("111") + bigint("999"), bigint("1110"));
assert_eq!(bigint("127000") + bigint("23"), bigint("127023"));
assert_eq!(bigint("111111111111111111") + bigint("222222222222222222"), bigint("333333333333333333"));
}
#[test]
fn test_add_negative() {
assert_eq!(bigint("-234") + bigint("-666"), bigint("-900"));
assert_eq!(bigint("-234") + bigint("-766"), bigint("-1000"));
assert_eq!(bigint("-127000") + bigint("-23"), bigint("-127023"));
assert_eq!(bigint("-111111111111111111") + bigint("-222222222222222222"), bigint("-333333333333333333"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("628") - bigint("142"), bigint("486"));
assert_eq!(bigint("628") + bigint("-142"), bigint("486"));
assert_eq!(bigint("142") - bigint("628"), bigint("-486"));
assert_eq!(bigint("142") + bigint("-628"), bigint("-486"));
assert_eq!(bigint("-628") + bigint("142"), bigint("-486"));
assert_eq!(bigint("211") - bigint("238"), bigint("-27"));
+
+ assert_eq!(bigint("1000") - bigint("101"), bigint("899"));
+ assert_eq!(bigint("451020") - bigint("319005"), bigint("132015"));
}
#[test]
fn test_sub_negative() {
assert_eq!(bigint("-628") - bigint("-28"), bigint("-600"));
assert_eq!(bigint("-234") - bigint("-123"), bigint("-111"));
assert_eq!(bigint("-100") - bigint("-208"), bigint("108"));
}
#[test]
fn test_comparison() {
assert!(bigint("24") == bigint("24"));
assert!(bigint("24") <= bigint("24"));
assert!(bigint("1233") < bigint("1234"));
assert!(bigint("428") < bigint("620"));
assert!(bigint("000428") < bigint("000000000620"));
}
#[test]
fn test_comparison_negative() {
assert!(bigint("-24") == bigint("-24"));
assert!(bigint("-24") <= bigint("-24"));
assert!(bigint("-1233") > bigint("-1234"));
assert!(bigint("-428") > bigint("-620"));
assert!(bigint("-000428") > bigint("-000000000620"));
}
#[test]
fn test_comparison_different_signs() {
assert!(bigint("123") > bigint("-25"));
assert!(bigint("-40") < bigint("34"));
}
#[test]
fn test_comparison_different_length() {
assert!(bigint("1234") > bigint("123"));
assert!(bigint("-1234") < bigint("-123"));
assert!(bigint("790") > bigint("23"));
assert!(bigint("-790") < bigint("-23"));
assert!(bigint("1000000000000") > bigint("999999999999"));
assert!(bigint("-1000000000000") < bigint("-999999999999"));
}
-}
+}

Тервел качи решение на 20.11.2020 13:35 (преди почти 5 години)

use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::Neg;
use std::ops::Add;
use std::ops::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 digits.is_empty() {
panic!("Cannot construct number without digits!");
}
// remove leading zeroes
let mut i = 0;
while i < digits.len() && digits[i] == 0 { // find index of last leading zero
i += 1;
}
let mut digits = digits;
digits.drain(0..i);
// if the digits were all zeroes, then we would have removed all of them, leaving an empty vector, but we need at least one zero
if digits.is_empty() {
digits.push(0);
}
// if digits == vec![0] && sign == -1 {
// panic!("Negative zero not allowed!");
// }
let mut sign = sign;
if digits == vec![0] && sign == -1 {
sign = 1;
}
Bigint {
sign: sign,
digits: digits,
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.is_zero() == false
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.is_zero() == false
}
pub fn is_zero(&self) -> bool {
self.digits == vec![0]
}
pub fn abs(&self) -> Self {
Bigint {
sign: 1,
digits: self.digits.clone(),
}
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint {
sign: self.sign * (-1),
digits: self.digits.clone(),
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut s = String::from(s);
let sign: i8;
if s.starts_with("+") {
sign = 1;
s.remove(0);
} else if s.starts_with("-") {
sign = -1;
s.remove(0);
} else { // if there is no sign, we assume positive
sign = 1;
}
if s.is_empty() {
s = String::from("0");
} // if s is just "+" or "-", we'll treat it as a zero
if s.chars().all(|x| x.is_ascii_digit()) == false { // there are any non-digit characters
return Err(ParseError);
}
let digits = s.chars().map(|ch| ch.to_digit(10).unwrap()).map(|x| x as u8).collect();
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 == 1 && other.sign == -1 {
return Ordering::Greater;
} else if self.sign == -1 && other.sign == 1 {
return Ordering::Less;
}
let sign = self.sign;
if self.digits.len() > other.digits.len() {
if sign == 1 {
return Ordering::Greater;
} else if sign == -1 {
return Ordering::Less;
}
} else if self.digits.len() < other.digits.len() {
if sign == 1 {
return Ordering::Less;
} else if sign == -1 {
return Ordering::Greater;
}
}
// ??? more elegant way to do this?
for i in 0..self.digits.len() {
if sign == 1 {
if self.digits[i] > other.digits[i] {
return Ordering::Greater;
} else if self.digits[i] < other.digits[i] {
return Ordering::Less
}
} else if sign == -1 {
if self.digits[i] > other.digits[i] {
return Ordering::Less;
} else if self.digits[i] < other.digits[i] {
return Ordering::Greater
}
}
}
// ??? something with zip? map?
// for (x, y) in self.digits.iter().zip(other.digits.iter()) {
// ...
// }
Ordering::Equal
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
fn add_digits(left: &Vec<u8>, right: &Vec<u8>) -> Vec<u8> {
let length_max = std::cmp::max(left.len(), right.len());
let left_padded = zero_pad(left, length_max);
let right_padded = zero_pad(right, length_max);
let mut result = Vec::new();
let mut carry: u8 = 0;
for i in (0..length_max).rev() {
let digit = left_padded[i] + right_padded[i] + carry;
if digit >= 10 {
result.push(digit % 10);
carry = 1;
} else {
result.push(digit);
carry = 0;
}
}
if carry == 1 {
result.push(1);
}
result.reverse();
result
}
fn subtract_digits(larger: &Vec<u8>, smaller: &Vec<u8>) -> Vec<u8> {
let smaller_padded = zero_pad(smaller, larger.len());
// we don't need to pad the larger number, since it's larger by absolute value, and so has at least as many digits as the smaller one
let mut result = Vec::new();
let mut carry: u8 = 0;
for i in (0..larger.len()).rev() {
if larger[i] < smaller_padded[i] + carry {
result.push(larger[i] + 10 - smaller_padded[i] - carry); // borrowing
carry = 1;
} else {
result.push(larger[i] - smaller_padded[i] - carry);
carry = 0;
}
}
if carry != 0 { // as we're subtracting from the larger number, there shouldn't be a carried one at the end
panic!("Subtraction error!");
}
// I don't know why I decided to do a mathematical proof in the middle of my code, but here it is:
// assuming valid input (larger > smaller), this should hold for the numbers - there is an index k (0 <= k < larger.len()), such that:
// larger[i] == smaller_padded[i], i < k
// larger[k] > smaller_padded[k],
// in this case, (larger[k+1] - smaller_padded[k+1] - carry) may:
// I. not produce a carried one, in which case larger[k] > smaller_padded[k] + 0, so there will be no carry
// II. produce a carried one, but larger[k] >= smaller_padded[k] + 1, so there will be no carry
// (III. those digits might also not exist if k is the last index, but then there is no carry anyway)
// because larger[i] == smaller_padded[i], i < k, and there is no carry when we subtract larger[k] and smaller_padded[k],
// there will be no further carries from this point on, so if there ends up being one at the end, the input must have been invalid
result.reverse();
result
}
fn zero_pad(digits: &Vec<u8>, length: usize) -> Vec<u8> {
let mut result = digits.clone();
if length > digits.len() {
result.splice(..0, [0].repeat(length - digits.len())); // add to beginning of vector
}
result
}
if self.sign == other.sign {
return Bigint::from_components(add_digits(&self.digits, &other.digits), self.sign);
} else {
- if self.abs() > other.abs() {
- return Bigint::from_components(subtract_digits(&self.digits, &other.digits), self.sign);
- } else if self.abs() < other.abs() {
- return Bigint::from_components(subtract_digits(&other.digits, &self.digits), other.sign);
- } else { // different signs, but equality by absolute value, means we should get zero
- return Bigint::new();
+ match Ord::cmp(&self.abs(), &other.abs()) {
+ Ordering::Greater => Bigint::from_components(subtract_digits(&self.digits, &other.digits), self.sign),
+ Ordering::Less => Bigint::from_components(subtract_digits(&other.digits, &self.digits), other.sign),
+ Ordering::Equal => Bigint::new(),
}
+ // if self.abs() > other.abs() {
+ // return Bigint::from_components(subtract_digits(&self.digits, &other.digits), self.sign);
+ // } else if self.abs() < other.abs() {
+ // return Bigint::from_components(subtract_digits(&other.digits, &self.digits), other.sign);
+ // } else { // different signs, but equality by absolute value, means we should get zero
+ // return Bigint::new();
+ // }
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_zero_signed() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint("+0"));
assert_eq!(regular_zero, bigint("-0"));
}
#[test]
fn test_zero_leading() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint("000"));
assert_eq!(regular_zero, bigint("000000000"));
}
#[test]
fn test_zero_empty() {
let regular_zero = Bigint::new();
assert_eq!(regular_zero, bigint(""));
assert_eq!(regular_zero, bigint("+"));
assert_eq!(regular_zero, bigint("-"));
}
#[test]
fn test_positive() {
assert!(bigint("1234").is_positive());
assert!(bigint("+1234").is_positive());
assert!(bigint("0001234").is_positive());
assert!(bigint("+0001234").is_positive());
}
#[test]
fn test_negative() {
assert!(bigint("-1234").is_negative());
assert!(bigint("-0001234").is_negative());
}
#[test]
fn test_number_leading_zeros() {
let regular_number = bigint("123");
assert_eq!(regular_number, bigint("0123"));
assert_eq!(regular_number, bigint("000123"));
assert_eq!(regular_number, bigint("00000123"));
}
#[test]
fn test_number_sign() {
let regular_number = bigint("123");
assert_eq!(regular_number, bigint("+123"));
assert_eq!(regular_number, bigint("+000123"));
assert_eq!(regular_number, bigint("+00000123"));
}
#[test]
fn test_number_negative_sign() {
let regular_number = bigint("-123");
assert_eq!(regular_number, bigint("-123"));
assert_eq!(regular_number, bigint("-000123"));
assert_eq!(regular_number, bigint("-00000123"));
}
#[test]
fn test_invalid_two_signs() {
assert!(Bigint::from_str("++123").is_err());
}
#[test]
fn test_invalid_letter_o() {
assert!(Bigint::from_str("12O3").is_err());
}
#[test]
fn test_invalid_word() {
assert!(Bigint::from_str("word").is_err());
}
#[test]
fn test_add() {
assert_eq!(bigint("234") + bigint("666"), bigint("900"));
assert_eq!(bigint("234") + bigint("766"), bigint("1000"));
assert_eq!(bigint("111") + bigint("999"), bigint("1110"));
assert_eq!(bigint("127000") + bigint("23"), bigint("127023"));
assert_eq!(bigint("111111111111111111") + bigint("222222222222222222"), bigint("333333333333333333"));
}
#[test]
fn test_add_negative() {
assert_eq!(bigint("-234") + bigint("-666"), bigint("-900"));
assert_eq!(bigint("-234") + bigint("-766"), bigint("-1000"));
assert_eq!(bigint("-127000") + bigint("-23"), bigint("-127023"));
assert_eq!(bigint("-111111111111111111") + bigint("-222222222222222222"), bigint("-333333333333333333"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("628") - bigint("142"), bigint("486"));
assert_eq!(bigint("628") + bigint("-142"), bigint("486"));
assert_eq!(bigint("142") - bigint("628"), bigint("-486"));
assert_eq!(bigint("142") + bigint("-628"), bigint("-486"));
assert_eq!(bigint("-628") + bigint("142"), bigint("-486"));
assert_eq!(bigint("211") - bigint("238"), bigint("-27"));
assert_eq!(bigint("1000") - bigint("101"), bigint("899"));
assert_eq!(bigint("451020") - bigint("319005"), bigint("132015"));
}
#[test]
fn test_sub_negative() {
assert_eq!(bigint("-628") - bigint("-28"), bigint("-600"));
assert_eq!(bigint("-234") - bigint("-123"), bigint("-111"));
assert_eq!(bigint("-100") - bigint("-208"), bigint("108"));
}
#[test]
fn test_comparison() {
assert!(bigint("24") == bigint("24"));
assert!(bigint("24") <= bigint("24"));
assert!(bigint("1233") < bigint("1234"));
assert!(bigint("428") < bigint("620"));
assert!(bigint("000428") < bigint("000000000620"));
}
#[test]
fn test_comparison_negative() {
assert!(bigint("-24") == bigint("-24"));
assert!(bigint("-24") <= bigint("-24"));
assert!(bigint("-1233") > bigint("-1234"));
assert!(bigint("-428") > bigint("-620"));
assert!(bigint("-000428") > bigint("-000000000620"));
}
#[test]
fn test_comparison_different_signs() {
assert!(bigint("123") > bigint("-25"));
assert!(bigint("-40") < bigint("34"));
}
#[test]
fn test_comparison_different_length() {
assert!(bigint("1234") > bigint("123"));
assert!(bigint("-1234") < bigint("-123"));
assert!(bigint("790") > bigint("23"));
assert!(bigint("-790") < bigint("-23"));
assert!(bigint("1000000000000") > bigint("999999999999"));
assert!(bigint("-1000000000000") < bigint("-999999999999"));
}
}