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

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

Решение на Bigint от Теодор Тошков

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

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

Резултати

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

Код

use std::cmp::Ordering;
use std::ops::{Add, Neg, Sub};
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
}
// private
impl Bigint {
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let digits = {
let mut digits: Vec<u8> = digits
.into_iter()
.rev()
.skip_while(|&digit| digit == 0)
.collect();
digits.reverse();
if digits.is_empty() {
digits.push(0);
};
digits
};
Self {
sign: if digits.last().unwrap() == &0 {
1
} else {
sign
},
digits,
}
}
fn is_zero(&self) -> bool {
self.digits.last().unwrap() == &0
}
fn abs_cmp(&self, other: &Bigint) -> Ordering {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Equal => self.digits.iter().rev().cmp(other.digits.iter().rev()),
other => other,
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let (sign, to_skip) = match s.chars().next() {
Some('-') => (-1, 1),
Some('+') => (1, 1),
_ => (1, 0),
};
let parsed_digits: Option<Vec<u8>> = s
.chars()
.skip(to_skip)
.map(|c| c.to_digit(10).map(|digit| digit as u8))
.collect();
match parsed_digits {
Some(digits) => Ok(Bigint::from_components(
digits.into_iter().rev().collect(),
sign,
)),
None => Err(Self::Err {}),
}
}
}
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 {
match self.sign.cmp(&other.sign) {
Ordering::Equal => {
let ord = self.abs_cmp(&other);
if self.sign == 1 {
ord
} else {
ord.reverse()
}
}
other => other,
}
}
}
fn operate_on_digits<F>(left: &[u8], right: &[u8], len: usize, func: F) -> Vec<u8>
where
F: FnMut((&u8, &u8)) -> u8,
{
let padding = [0].repeat(len + 1);
left.iter()
.chain(padding.iter())
.zip(right.iter().chain(padding.iter()))
.map(func)
.collect()
}
fn add_digits(left: &[u8], right: &[u8], len: usize) -> Vec<u8> {
let mut remainder = 0;
let adder = |addends: (&u8, &u8)| {
let sum = addends.0 + addends.1 + remainder;
remainder = sum / 10;
sum % 10
};
operate_on_digits(&left, &right, len, adder)
}
fn subtract_digits(larger: &[u8], smaller: &[u8], len: usize) -> Vec<u8> {
let mut remainder = 0;
let subber = |arguments: (&u8, &u8)| {
let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
remainder = if lhs >= rhs { 0 } else { 1 };
distance(remainder * 10, distance(lhs, rhs))
};
operate_on_digits(&larger, &smaller, len, subber)
}
fn distance<U: Sub<Output = U> + Ord>(a: U, b: U) -> U {
if a >= b {
a - b
} else {
b - a
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let len = distance(self.digits.len(), other.digits.len());
if self.sign == other.sign {
Bigint::from_components(add_digits(&self.digits, &other.digits, len), self.sign)
} else {
let (bigger, smaller) = if self.abs_cmp(&other) == Ordering::Less {
(&other, &self)
} else {
(&self, &other)
};
Bigint::from_components(
subtract_digits(&bigger.digits, &smaller.digits, len),
bigger.sign,
)
}
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint::from_components(self.digits, -self.sign)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
#[cfg(test)]
mod test {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_is_positive() {
assert_eq!(bigint("1").is_positive(), true);
assert_eq!(bigint("+1").is_positive(), true);
assert_eq!(bigint("+0").is_positive(), false);
assert_eq!(Bigint::new().is_positive(), false);
}
#[test]
fn test_is_negative() {
assert_eq!(bigint("-1").is_negative(), true);
assert_eq!(bigint("-0").is_negative(), false);
assert_eq!(Bigint::new().is_negative(), false);
}
#[test]
fn test_parse_0() {
assert_eq!(bigint("0"), bigint("-0"));
assert_eq!(bigint("0"), bigint("+0"));
assert_eq!(bigint("0"), bigint(""));
assert_eq!(bigint("0"), bigint("+"));
assert_eq!(bigint("0"), bigint("-"));
}
#[test]
fn test_parse_default_sign() {
assert_eq!(bigint("123"), bigint("+123"));
}
#[test]
fn test_parse_leading_zeroes() {
assert_eq!(bigint("123"), bigint("0123"));
assert_eq!(bigint("123"), bigint("00000123"));
assert_eq!(bigint("123"), bigint("+0123"));
assert_eq!(bigint("123"), bigint("+000000123"));
assert_eq!(bigint("-123"), bigint("-0123"));
assert_eq!(bigint("-123"), bigint("-000000123"));
assert_ne!(bigint("123"), bigint("1230"));
assert_ne!(bigint("123"), bigint("1203"));
}
#[test]
fn test_parse_error() {
assert!(Bigint::from_str("NaN").is_err());
assert!(Bigint::from_str("++1").is_err());
assert!(Bigint::from_str("--1").is_err());
assert!(Bigint::from_str(" +1").is_err());
assert!(Bigint::from_str(" 1").is_err());
assert!(Bigint::from_str(" -1").is_err());
assert!(Bigint::from_str(" 01").is_err());
assert!(Bigint::from_str("1+1").is_err());
assert!(Bigint::from_str("1-1").is_err());
assert!(Bigint::from_str("1+").is_err());
assert!(Bigint::from_str("1-").is_err());
assert!(Bigint::from_str("1 ").is_err());
assert!(Bigint::from_str("+1 ").is_err());
assert!(Bigint::from_str("-1 ").is_err());
assert!(Bigint::from_str(" ").is_err());
assert!(Bigint::from_str("1 1").is_err());
assert!(Bigint::from_str("+ 1").is_err());
assert!(Bigint::from_str("- 1").is_err());
assert!(Bigint::from_str("български").is_err());
assert!(Bigint::from_str("1о").is_err());
}
#[test]
fn test_ord_same_sign() {
assert!(bigint("123") < bigint("124"));
assert!(bigint("125") > bigint("123"));
assert!(bigint("2") < bigint("10"));
assert!(bigint("20") > bigint("10"));
assert!(bigint("-123") > bigint("-124"));
assert!(bigint("-324") < bigint("-200"));
assert!(bigint("-12") < bigint("-2"));
assert!(bigint("-3") > bigint("-11"));
}
#[test]
fn test_ord_different_signs() {
assert!(bigint("0") < bigint("124"));
assert!(bigint("243") > bigint("0"));
assert!(bigint("-123") < bigint("0"));
assert!(bigint("0") > bigint("-124"));
assert!(bigint("-111") < bigint("222"));
assert!(bigint("-444") < bigint("333"));
assert!(bigint("-2") < bigint("10"));
assert!(bigint("-20") < bigint("3"));
}
#[test]
fn test_same_sign_sum() {
assert_eq!(bigint("123") + bigint("321"), bigint("444"));
assert_eq!(bigint("-234") + bigint("-432"), bigint("-666"));
assert_eq!(bigint("10") + bigint("312"), bigint("322"));
assert_eq!(bigint("-20") + bigint("-400"), bigint("-420"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("0") + bigint("69"), bigint("69"));
}
#[test]
fn test_same_sign_sum_overflow() {
assert_eq!(bigint("1") + bigint("9"), bigint("10"));
assert_eq!(bigint("123") + bigint("118"), bigint("241"));
assert_eq!(bigint("234") + bigint("195"), bigint("429"));
}
#[test]
fn test_different_sign_sum() {
assert_eq!(bigint("-20") + bigint("0"), bigint("-20"));
assert_eq!(bigint("0") + bigint("-30"), bigint("-30"));
assert_eq!(bigint("45") + bigint("-32"), bigint("13"));
assert_eq!(bigint("-20") + bigint("36"), bigint("16"));
assert_eq!(bigint("-69") + bigint("27"), bigint("-42"));
assert_eq!(bigint("34") + bigint("-58"), bigint("-24"));
}
#[test]
fn test_different_sign_sum_underflow() {
assert_eq!(bigint("-10") + bigint("1"), bigint("-9"));
assert_eq!(bigint("2") + bigint("-8"), bigint("-6"));
assert_eq!(bigint("-111") + bigint("22"), bigint("-89"));
assert_eq!(bigint("44") + bigint("-333"), bigint("-289"));
assert_eq!(bigint("32") + bigint("-9"), bigint("23"));
assert_eq!(bigint("-8") + bigint("27"), bigint("19"));
assert_eq!(bigint("222") + bigint("-33"), bigint("189"));
assert_eq!(bigint("-66") + bigint("555"), bigint("489"));
}
#[test]
fn test_negate() {
assert_eq!(-bigint("0"), bigint("0"));
assert_eq!(-bigint("123"), bigint("-123"));
assert_eq!(-bigint("-321"), bigint("321"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("23") - bigint("0"), bigint("23"));
assert_eq!(bigint("0") - bigint("-23"), bigint("23"));
assert_eq!(bigint("0") - bigint("23"), bigint("-23"));
assert_eq!(bigint("17") - bigint("9"), bigint("8"));
assert_eq!(bigint("17") - bigint("1"), bigint("16"));
assert_eq!(bigint("17") - bigint("13"), bigint("4"));
assert_eq!(bigint("-34") - bigint("6"), bigint("-40"));
assert_eq!(bigint("-34") - bigint("25"), bigint("-59"));
assert_eq!(bigint("-34") - bigint("3"), bigint("-37"));
assert_eq!(bigint("-45") - bigint("-6"), bigint("-39"));
assert_eq!(bigint("-45") - bigint("-21"), bigint("-24"));
assert_eq!(bigint("-45") - bigint("-37"), bigint("-8"));
assert_eq!(bigint("56") - bigint("-7"), bigint("63"));
assert_eq!(bigint("56") - bigint("-23"), bigint("79"));
assert_eq!(bigint("56") - bigint("-45"), bigint("101"));
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
}

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

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

История (8 версии и 4 коментара)

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

Теодор качи решение на 19.11.2020 02:27 (преди почти 5 години)

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
}
// private
impl Bigint {
// TODO: clean up
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let digits = {
let mut digits: Vec<u8> = digits
.into_iter()
.rev()
.skip_while(|&digit| digit == 0)
.collect();
digits.reverse();
if digits.is_empty() {
digits.push(0);
};
digits
};
Self {
sign: if digits.last().unwrap() == &0 {
1
} else {
sign
},
digits,
}
}
fn is_zero(&self) -> bool {
self.digits.last().unwrap() == &0
}
- fn padded(&self, padded_len: usize) -> Vec<u8> {
- let mut digits = self.digits.clone();
- digits.resize(padded_len, 0);
- digits
- }
-
- fn reverse_padded(&self, padded_len: usize) -> Vec<u8> {
- let mut digits = self.padded(padded_len);
- digits.reverse();
- digits
- }
-
fn abs_cmp(&self, other: &Bigint) -> Ordering {
- let len = std::cmp::max(self.digits.len(), other.digits.len());
- self.reverse_padded(len).cmp(&other.reverse_padded(len))
+ match self.digits.len().cmp(&other.digits.len()) {
+ Ordering::Equal => self.digits.iter().rev().cmp(other.digits.iter().rev()),
+ other => other,
+ }
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut digits = s.chars();
let sign = match s.chars().nth(0) {
Some('-') => {
digits.next();
-1
}
Some('+') => {
digits.next();
1
}
_ => 1,
};
let parsed_digits: Option<Vec<u8>> = digits
.map(|c| c.to_digit(10).map(|digit| digit as u8))
.collect();
match parsed_digits {
Some(digits) => {
let mut digits = digits;
digits.reverse();
Ok(Bigint::from_components(digits, sign))
}
None => Err(Self::Err {}),
}
}
}
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 {
match self.sign.cmp(&other.sign) {
Ordering::Equal => {
let ord = self.abs_cmp(&other);
if self.sign == 1 {
ord
} else {
ord.reverse()
}
}
other => other,
}
}
}
use std::ops::Add;
-fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
+fn add_digits(left: &Vec<u8>, right: &Vec<u8>, len: usize) -> Vec<u8> {
+ let padding = [0].repeat(len);
let mut remainder = 0;
let adder = |addends: (&u8, &u8)| {
let sum = addends.0 + addends.1 + remainder;
remainder = sum / 10;
sum % 10
};
- let mut result: Vec<u8> = left.iter().zip(right.iter()).map(adder).collect();
+ let mut result: Vec<u8> = left
+ .iter()
+ .chain(padding.iter())
+ .zip(right.iter().chain(padding.iter()))
+ .map(adder)
+ .collect();
result.push(remainder);
result
}
-fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
+fn subtract_digits(larger: &Vec<u8>, smaller: &Vec<u8>, len: usize) -> Vec<u8> {
+ let padding = [0].repeat(len);
let mut remainder = 0;
+
let subber = |arguments: (&u8, &u8)| {
let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
if lhs >= rhs {
remainder = 0;
lhs - rhs
} else {
remainder = 1;
10 - (rhs - lhs)
}
};
- let mut result: Vec<u8> = larger.iter().zip(smaller.iter()).map(subber).collect();
+ let mut result: Vec<u8> = larger
+ .iter()
+ .chain(padding.iter())
+ .zip(smaller.iter().chain(padding.iter()))
+ .map(subber)
+ .collect();
result.push(remainder);
result
}
+fn distance(a: usize, b: usize) -> usize {
+ if a >= b {
+ a - b
+ } else {
+ b - a
+ }
+}
+
impl Add for Bigint {
type Output = Bigint;
- // TODO: too many copies
fn add(self, other: Self) -> Self {
- let len = std::cmp::max(self.digits.len(), other.digits.len());
+ let len = distance(self.digits.len(), other.digits.len());
if self.sign == other.sign {
- Bigint::from_components(add_digits(self.padded(len), other.padded(len)), self.sign)
+ Bigint::from_components(add_digits(&self.digits, &other.digits, len), self.sign)
} else {
let (bigger, smaller) = if self.abs_cmp(&other) == Ordering::Less {
(&other, &self)
} else {
(&self, &other)
};
Bigint::from_components(
- subtract_digits(bigger.padded(len), smaller.padded(len)),
+ subtract_digits(&bigger.digits, &smaller.digits, len),
bigger.sign,
)
}
}
}
use std::ops::Neg;
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint::from_components(self.digits, self.sign * -1)
}
}
use std::ops::Sub;
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
use std::str::FromStr;
#[cfg(test)]
mod test {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_is_positive() {
assert_eq!(bigint("1").is_positive(), true);
assert_eq!(bigint("+1").is_positive(), true);
assert_eq!(bigint("+0").is_positive(), false);
assert_eq!(Bigint::new().is_positive(), false);
}
#[test]
fn test_is_negative() {
assert_eq!(bigint("-1").is_negative(), true);
assert_eq!(bigint("-0").is_negative(), false);
assert_eq!(Bigint::new().is_negative(), false);
}
#[test]
fn test_parse_0() {
assert_eq!(bigint("0"), bigint("-0"));
assert_eq!(bigint("0"), bigint("+0"));
assert_eq!(bigint("0"), bigint(""));
}
#[test]
fn test_parse_default_sign() {
assert_eq!(bigint("123"), bigint("+123"));
}
#[test]
fn test_parse_leading_zeroes() {
assert_eq!(bigint("123"), bigint("0123"));
assert_eq!(bigint("123"), bigint("00000123"));
assert_eq!(bigint("123"), bigint("+0123"));
assert_eq!(bigint("123"), bigint("+000000123"));
assert_eq!(bigint("-123"), bigint("-0123"));
assert_eq!(bigint("-123"), bigint("-000000123"));
assert_ne!(bigint("123"), bigint("1230"));
assert_ne!(bigint("123"), bigint("1203"));
}
#[test]
fn test_parse_error() {
assert!(Bigint::from_str("NaN").is_err());
assert!(Bigint::from_str("++1").is_err());
assert!(Bigint::from_str("--1").is_err());
assert!(Bigint::from_str(" +1").is_err());
assert!(Bigint::from_str(" 1").is_err());
assert!(Bigint::from_str(" -1").is_err());
assert!(Bigint::from_str(" 01").is_err());
assert!(Bigint::from_str("1+1").is_err());
assert!(Bigint::from_str("1-1").is_err());
assert!(Bigint::from_str("1+").is_err());
assert!(Bigint::from_str("1-").is_err());
assert!(Bigint::from_str("1 ").is_err());
assert!(Bigint::from_str("+1 ").is_err());
assert!(Bigint::from_str("-1 ").is_err());
assert!(Bigint::from_str(" ").is_err());
assert!(Bigint::from_str("1 1").is_err());
assert!(Bigint::from_str("+ 1").is_err());
assert!(Bigint::from_str("- 1").is_err());
}
#[test]
fn test_ord_same_sign() {
assert!(bigint("123") < bigint("124"));
assert!(bigint("125") > bigint("123"));
assert!(bigint("2") < bigint("10"));
assert!(bigint("20") > bigint("10"));
assert!(bigint("-123") > bigint("-124"));
assert!(bigint("-324") < bigint("-200"));
assert!(bigint("-12") < bigint("-2"));
assert!(bigint("-3") > bigint("-11"));
}
#[test]
fn test_ord_different_signs() {
assert!(bigint("0") < bigint("124"));
assert!(bigint("243") > bigint("0"));
assert!(bigint("-123") < bigint("0"));
assert!(bigint("0") > bigint("-124"));
assert!(bigint("-111") < bigint("222"));
assert!(bigint("-444") < bigint("333"));
assert!(bigint("-2") < bigint("10"));
assert!(bigint("-20") < bigint("3"));
}
#[test]
fn test_same_sign_sum() {
assert_eq!(bigint("123") + bigint("321"), bigint("444"));
assert_eq!(bigint("-234") + bigint("-432"), bigint("-666"));
assert_eq!(bigint("10") + bigint("312"), bigint("322"));
assert_eq!(bigint("-20") + bigint("-400"), bigint("-420"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("0") + bigint("69"), bigint("69"));
}
#[test]
fn test_same_sign_sum_overflow() {
assert_eq!(bigint("1") + bigint("9"), bigint("10"));
assert_eq!(bigint("123") + bigint("118"), bigint("241"));
assert_eq!(bigint("234") + bigint("195"), bigint("429"));
}
#[test]
fn test_different_sign_sum() {
assert_eq!(bigint("-20") + bigint("0"), bigint("-20"));
assert_eq!(bigint("0") + bigint("-30"), bigint("-30"));
assert_eq!(bigint("45") + bigint("-32"), bigint("13"));
assert_eq!(bigint("-20") + bigint("36"), bigint("16"));
assert_eq!(bigint("-69") + bigint("27"), bigint("-42"));
assert_eq!(bigint("34") + bigint("-58"), bigint("-24"));
}
#[test]
fn test_different_sign_sum_underflow() {
assert_eq!(bigint("-10") + bigint("1"), bigint("-9"));
assert_eq!(bigint("2") + bigint("-8"), bigint("-6"));
assert_eq!(bigint("-111") + bigint("22"), bigint("-89"));
assert_eq!(bigint("44") + bigint("-333"), bigint("-289"));
assert_eq!(bigint("32") + bigint("-9"), bigint("23"));
assert_eq!(bigint("-8") + bigint("27"), bigint("19"));
assert_eq!(bigint("222") + bigint("-33"), bigint("189"));
assert_eq!(bigint("-66") + bigint("555"), bigint("489"));
}
#[test]
fn test_negate() {
assert_eq!(-bigint("0"), bigint("0"));
assert_eq!(-bigint("123"), bigint("-123"));
assert_eq!(-bigint("-321"), bigint("321"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("23") - bigint("0"), bigint("23"));
assert_eq!(bigint("0") - bigint("-23"), bigint("23"));
assert_eq!(bigint("0") - bigint("23"), bigint("-23"));
assert_eq!(bigint("17") - bigint("9"), bigint("8"));
assert_eq!(bigint("17") - bigint("1"), bigint("16"));
assert_eq!(bigint("17") - bigint("13"), bigint("4"));
assert_eq!(bigint("-34") - bigint("6"), bigint("-40"));
assert_eq!(bigint("-34") - bigint("25"), bigint("-59"));
assert_eq!(bigint("-34") - bigint("3"), bigint("-37"));
assert_eq!(bigint("-45") - bigint("-6"), bigint("-39"));
assert_eq!(bigint("-45") - bigint("-21"), bigint("-24"));
assert_eq!(bigint("-45") - bigint("-37"), bigint("-8"));
assert_eq!(bigint("56") - bigint("-7"), bigint("63"));
assert_eq!(bigint("56") - bigint("-23"), bigint("79"));
assert_eq!(bigint("56") - bigint("-45"), bigint("101"));
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
}

Теодор качи решение на 19.11.2020 08:19 (преди почти 5 години)

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
}
// private
impl Bigint {
// TODO: clean up
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let digits = {
let mut digits: Vec<u8> = digits
.into_iter()
.rev()
.skip_while(|&digit| digit == 0)
.collect();
digits.reverse();
if digits.is_empty() {
digits.push(0);
};
digits
};
Self {
sign: if digits.last().unwrap() == &0 {
1
} else {
sign
},
digits,
}
}
fn is_zero(&self) -> bool {
self.digits.last().unwrap() == &0
}
fn abs_cmp(&self, other: &Bigint) -> Ordering {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Equal => self.digits.iter().rev().cmp(other.digits.iter().rev()),
other => other,
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut digits = s.chars();
let sign = match s.chars().nth(0) {
Some('-') => {
digits.next();
-1
}
Some('+') => {
digits.next();
1
}
_ => 1,
};
let parsed_digits: Option<Vec<u8>> = digits
.map(|c| c.to_digit(10).map(|digit| digit as u8))
.collect();
match parsed_digits {
Some(digits) => {
let mut digits = digits;
digits.reverse();
Ok(Bigint::from_components(digits, sign))
}
None => Err(Self::Err {}),
}
}
}
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 {
match self.sign.cmp(&other.sign) {
Ordering::Equal => {
let ord = self.abs_cmp(&other);
if self.sign == 1 {
ord
} else {
ord.reverse()
}
}
other => other,
}
}
}
use std::ops::Add;
fn add_digits(left: &Vec<u8>, right: &Vec<u8>, len: usize) -> Vec<u8> {
- let padding = [0].repeat(len);
+ let padding = [0].repeat(len + 1);
let mut remainder = 0;
let adder = |addends: (&u8, &u8)| {
let sum = addends.0 + addends.1 + remainder;
remainder = sum / 10;
sum % 10
};
- let mut result: Vec<u8> = left
- .iter()
+ left.iter()
.chain(padding.iter())
.zip(right.iter().chain(padding.iter()))
.map(adder)
- .collect();
-
- result.push(remainder);
- result
+ .collect()
}
fn subtract_digits(larger: &Vec<u8>, smaller: &Vec<u8>, len: usize) -> Vec<u8> {
- let padding = [0].repeat(len);
+ let padding = [0].repeat(len + 1);
let mut remainder = 0;
let subber = |arguments: (&u8, &u8)| {
let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
if lhs >= rhs {
remainder = 0;
lhs - rhs
} else {
remainder = 1;
10 - (rhs - lhs)
}
};
- let mut result: Vec<u8> = larger
+ larger
.iter()
.chain(padding.iter())
.zip(smaller.iter().chain(padding.iter()))
.map(subber)
- .collect();
-
- result.push(remainder);
- result
+ .collect()
}
fn distance(a: usize, b: usize) -> usize {
if a >= b {
a - b
} else {
b - a
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let len = distance(self.digits.len(), other.digits.len());
if self.sign == other.sign {
Bigint::from_components(add_digits(&self.digits, &other.digits, len), self.sign)
} else {
let (bigger, smaller) = if self.abs_cmp(&other) == Ordering::Less {
(&other, &self)
} else {
(&self, &other)
};
Bigint::from_components(
subtract_digits(&bigger.digits, &smaller.digits, len),
bigger.sign,
)
}
}
}
use std::ops::Neg;
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint::from_components(self.digits, self.sign * -1)
}
}
use std::ops::Sub;
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
use std::str::FromStr;
#[cfg(test)]
mod test {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_is_positive() {
assert_eq!(bigint("1").is_positive(), true);
assert_eq!(bigint("+1").is_positive(), true);
assert_eq!(bigint("+0").is_positive(), false);
assert_eq!(Bigint::new().is_positive(), false);
}
#[test]
fn test_is_negative() {
assert_eq!(bigint("-1").is_negative(), true);
assert_eq!(bigint("-0").is_negative(), false);
assert_eq!(Bigint::new().is_negative(), false);
}
#[test]
fn test_parse_0() {
assert_eq!(bigint("0"), bigint("-0"));
assert_eq!(bigint("0"), bigint("+0"));
assert_eq!(bigint("0"), bigint(""));
}
#[test]
fn test_parse_default_sign() {
assert_eq!(bigint("123"), bigint("+123"));
}
#[test]
fn test_parse_leading_zeroes() {
assert_eq!(bigint("123"), bigint("0123"));
assert_eq!(bigint("123"), bigint("00000123"));
assert_eq!(bigint("123"), bigint("+0123"));
assert_eq!(bigint("123"), bigint("+000000123"));
assert_eq!(bigint("-123"), bigint("-0123"));
assert_eq!(bigint("-123"), bigint("-000000123"));
assert_ne!(bigint("123"), bigint("1230"));
assert_ne!(bigint("123"), bigint("1203"));
}
#[test]
fn test_parse_error() {
assert!(Bigint::from_str("NaN").is_err());
assert!(Bigint::from_str("++1").is_err());
assert!(Bigint::from_str("--1").is_err());
assert!(Bigint::from_str(" +1").is_err());
assert!(Bigint::from_str(" 1").is_err());
assert!(Bigint::from_str(" -1").is_err());
assert!(Bigint::from_str(" 01").is_err());
assert!(Bigint::from_str("1+1").is_err());
assert!(Bigint::from_str("1-1").is_err());
assert!(Bigint::from_str("1+").is_err());
assert!(Bigint::from_str("1-").is_err());
assert!(Bigint::from_str("1 ").is_err());
assert!(Bigint::from_str("+1 ").is_err());
assert!(Bigint::from_str("-1 ").is_err());
assert!(Bigint::from_str(" ").is_err());
assert!(Bigint::from_str("1 1").is_err());
assert!(Bigint::from_str("+ 1").is_err());
assert!(Bigint::from_str("- 1").is_err());
}
#[test]
fn test_ord_same_sign() {
assert!(bigint("123") < bigint("124"));
assert!(bigint("125") > bigint("123"));
assert!(bigint("2") < bigint("10"));
assert!(bigint("20") > bigint("10"));
assert!(bigint("-123") > bigint("-124"));
assert!(bigint("-324") < bigint("-200"));
assert!(bigint("-12") < bigint("-2"));
assert!(bigint("-3") > bigint("-11"));
}
#[test]
fn test_ord_different_signs() {
assert!(bigint("0") < bigint("124"));
assert!(bigint("243") > bigint("0"));
assert!(bigint("-123") < bigint("0"));
assert!(bigint("0") > bigint("-124"));
assert!(bigint("-111") < bigint("222"));
assert!(bigint("-444") < bigint("333"));
assert!(bigint("-2") < bigint("10"));
assert!(bigint("-20") < bigint("3"));
}
#[test]
fn test_same_sign_sum() {
assert_eq!(bigint("123") + bigint("321"), bigint("444"));
assert_eq!(bigint("-234") + bigint("-432"), bigint("-666"));
assert_eq!(bigint("10") + bigint("312"), bigint("322"));
assert_eq!(bigint("-20") + bigint("-400"), bigint("-420"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("0") + bigint("69"), bigint("69"));
}
#[test]
fn test_same_sign_sum_overflow() {
assert_eq!(bigint("1") + bigint("9"), bigint("10"));
assert_eq!(bigint("123") + bigint("118"), bigint("241"));
assert_eq!(bigint("234") + bigint("195"), bigint("429"));
}
#[test]
fn test_different_sign_sum() {
assert_eq!(bigint("-20") + bigint("0"), bigint("-20"));
assert_eq!(bigint("0") + bigint("-30"), bigint("-30"));
assert_eq!(bigint("45") + bigint("-32"), bigint("13"));
assert_eq!(bigint("-20") + bigint("36"), bigint("16"));
assert_eq!(bigint("-69") + bigint("27"), bigint("-42"));
assert_eq!(bigint("34") + bigint("-58"), bigint("-24"));
}
#[test]
fn test_different_sign_sum_underflow() {
assert_eq!(bigint("-10") + bigint("1"), bigint("-9"));
assert_eq!(bigint("2") + bigint("-8"), bigint("-6"));
assert_eq!(bigint("-111") + bigint("22"), bigint("-89"));
assert_eq!(bigint("44") + bigint("-333"), bigint("-289"));
assert_eq!(bigint("32") + bigint("-9"), bigint("23"));
assert_eq!(bigint("-8") + bigint("27"), bigint("19"));
assert_eq!(bigint("222") + bigint("-33"), bigint("189"));
assert_eq!(bigint("-66") + bigint("555"), bigint("489"));
}
#[test]
fn test_negate() {
assert_eq!(-bigint("0"), bigint("0"));
assert_eq!(-bigint("123"), bigint("-123"));
assert_eq!(-bigint("-321"), bigint("321"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("23") - bigint("0"), bigint("23"));
assert_eq!(bigint("0") - bigint("-23"), bigint("23"));
assert_eq!(bigint("0") - bigint("23"), bigint("-23"));
assert_eq!(bigint("17") - bigint("9"), bigint("8"));
assert_eq!(bigint("17") - bigint("1"), bigint("16"));
assert_eq!(bigint("17") - bigint("13"), bigint("4"));
assert_eq!(bigint("-34") - bigint("6"), bigint("-40"));
assert_eq!(bigint("-34") - bigint("25"), bigint("-59"));
assert_eq!(bigint("-34") - bigint("3"), bigint("-37"));
assert_eq!(bigint("-45") - bigint("-6"), bigint("-39"));
assert_eq!(bigint("-45") - bigint("-21"), bigint("-24"));
assert_eq!(bigint("-45") - bigint("-37"), bigint("-8"));
assert_eq!(bigint("56") - bigint("-7"), bigint("63"));
assert_eq!(bigint("56") - bigint("-23"), bigint("79"));
assert_eq!(bigint("56") - bigint("-45"), bigint("101"));
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
}

Проблем:

Промених distance функцията на

fn distance<U: num::Unsigned + PartialOrd>(a: U, b: U) -> U

За да си променя closure-а за събирането с различни знаци на

let subber = |arguments: (&u8, &u8)| {
    let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
    remainder = if lhs >= rhs { 0 } else { 1 };
    distance(remainder * 10, distance(lhs, rhs))
};

Това са единствените промени.

Локално ми се компилира и тестовете минават, като се опитам да upload-на промените тук ми дава "имате синтактична грешка" :(

EDIT:

Стана с fn distance<U: Sub<Output = U> + Ord>(a: U, b: U) -> U

Нямам идея дали проблема е в PartialOrd, който трябваше да е Ord или num::Unsigned (пробвах и num::traits::Unsigned без успех), но по някаква причина се компилираше само при мен (stable 1.48)

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

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
}
// private
impl Bigint {
// TODO: clean up
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let digits = {
let mut digits: Vec<u8> = digits
.into_iter()
.rev()
.skip_while(|&digit| digit == 0)
.collect();
digits.reverse();
if digits.is_empty() {
digits.push(0);
};
digits
};
Self {
sign: if digits.last().unwrap() == &0 {
1
} else {
sign
},
digits,
}
}
fn is_zero(&self) -> bool {
self.digits.last().unwrap() == &0
}
fn abs_cmp(&self, other: &Bigint) -> Ordering {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Equal => self.digits.iter().rev().cmp(other.digits.iter().rev()),
other => other,
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut digits = s.chars();
let sign = match s.chars().nth(0) {
Some('-') => {
digits.next();
-1
}
Some('+') => {
digits.next();
1
}
_ => 1,
};
let parsed_digits: Option<Vec<u8>> = digits
.map(|c| c.to_digit(10).map(|digit| digit as u8))
.collect();
match parsed_digits {
Some(digits) => {
let mut digits = digits;
digits.reverse();
Ok(Bigint::from_components(digits, sign))
}
None => Err(Self::Err {}),
}
}
}
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 {
match self.sign.cmp(&other.sign) {
Ordering::Equal => {
let ord = self.abs_cmp(&other);
if self.sign == 1 {
ord
} else {
ord.reverse()
}
}
other => other,
}
}
}
use std::ops::Add;
fn add_digits(left: &Vec<u8>, right: &Vec<u8>, len: usize) -> Vec<u8> {
let padding = [0].repeat(len + 1);
let mut remainder = 0;
let adder = |addends: (&u8, &u8)| {
let sum = addends.0 + addends.1 + remainder;
remainder = sum / 10;
sum % 10
};
left.iter()
.chain(padding.iter())
.zip(right.iter().chain(padding.iter()))
.map(adder)
.collect()
}
fn subtract_digits(larger: &Vec<u8>, smaller: &Vec<u8>, len: usize) -> Vec<u8> {
let padding = [0].repeat(len + 1);
let mut remainder = 0;
let subber = |arguments: (&u8, &u8)| {
let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
- if lhs >= rhs {
- remainder = 0;
- lhs - rhs
- } else {
- remainder = 1;
- 10 - (rhs - lhs)
- }
+ remainder = if lhs >= rhs { 0 } else { 1 };
+
+ distance(remainder * 10, distance(lhs, rhs))
};
larger
.iter()
.chain(padding.iter())
.zip(smaller.iter().chain(padding.iter()))
.map(subber)
.collect()
}
-fn distance(a: usize, b: usize) -> usize {
+fn distance<U: Sub<Output = U> + Ord>(a: U, b: U) -> U {
if a >= b {
a - b
} else {
b - a
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let len = distance(self.digits.len(), other.digits.len());
if self.sign == other.sign {
Bigint::from_components(add_digits(&self.digits, &other.digits, len), self.sign)
} else {
let (bigger, smaller) = if self.abs_cmp(&other) == Ordering::Less {
(&other, &self)
} else {
(&self, &other)
};
Bigint::from_components(
subtract_digits(&bigger.digits, &smaller.digits, len),
bigger.sign,
)
}
}
}
use std::ops::Neg;
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint::from_components(self.digits, self.sign * -1)
}
}
use std::ops::Sub;
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
use std::str::FromStr;
#[cfg(test)]
mod test {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_is_positive() {
assert_eq!(bigint("1").is_positive(), true);
assert_eq!(bigint("+1").is_positive(), true);
assert_eq!(bigint("+0").is_positive(), false);
assert_eq!(Bigint::new().is_positive(), false);
}
#[test]
fn test_is_negative() {
assert_eq!(bigint("-1").is_negative(), true);
assert_eq!(bigint("-0").is_negative(), false);
assert_eq!(Bigint::new().is_negative(), false);
}
#[test]
fn test_parse_0() {
assert_eq!(bigint("0"), bigint("-0"));
assert_eq!(bigint("0"), bigint("+0"));
assert_eq!(bigint("0"), bigint(""));
}
#[test]
fn test_parse_default_sign() {
assert_eq!(bigint("123"), bigint("+123"));
}
#[test]
fn test_parse_leading_zeroes() {
assert_eq!(bigint("123"), bigint("0123"));
assert_eq!(bigint("123"), bigint("00000123"));
assert_eq!(bigint("123"), bigint("+0123"));
assert_eq!(bigint("123"), bigint("+000000123"));
assert_eq!(bigint("-123"), bigint("-0123"));
assert_eq!(bigint("-123"), bigint("-000000123"));
assert_ne!(bigint("123"), bigint("1230"));
assert_ne!(bigint("123"), bigint("1203"));
}
#[test]
fn test_parse_error() {
assert!(Bigint::from_str("NaN").is_err());
assert!(Bigint::from_str("++1").is_err());
assert!(Bigint::from_str("--1").is_err());
assert!(Bigint::from_str(" +1").is_err());
assert!(Bigint::from_str(" 1").is_err());
assert!(Bigint::from_str(" -1").is_err());
assert!(Bigint::from_str(" 01").is_err());
assert!(Bigint::from_str("1+1").is_err());
assert!(Bigint::from_str("1-1").is_err());
assert!(Bigint::from_str("1+").is_err());
assert!(Bigint::from_str("1-").is_err());
assert!(Bigint::from_str("1 ").is_err());
assert!(Bigint::from_str("+1 ").is_err());
assert!(Bigint::from_str("-1 ").is_err());
assert!(Bigint::from_str(" ").is_err());
assert!(Bigint::from_str("1 1").is_err());
assert!(Bigint::from_str("+ 1").is_err());
assert!(Bigint::from_str("- 1").is_err());
}
#[test]
fn test_ord_same_sign() {
assert!(bigint("123") < bigint("124"));
assert!(bigint("125") > bigint("123"));
assert!(bigint("2") < bigint("10"));
assert!(bigint("20") > bigint("10"));
assert!(bigint("-123") > bigint("-124"));
assert!(bigint("-324") < bigint("-200"));
assert!(bigint("-12") < bigint("-2"));
assert!(bigint("-3") > bigint("-11"));
}
#[test]
fn test_ord_different_signs() {
assert!(bigint("0") < bigint("124"));
assert!(bigint("243") > bigint("0"));
assert!(bigint("-123") < bigint("0"));
assert!(bigint("0") > bigint("-124"));
assert!(bigint("-111") < bigint("222"));
assert!(bigint("-444") < bigint("333"));
assert!(bigint("-2") < bigint("10"));
assert!(bigint("-20") < bigint("3"));
}
#[test]
fn test_same_sign_sum() {
assert_eq!(bigint("123") + bigint("321"), bigint("444"));
assert_eq!(bigint("-234") + bigint("-432"), bigint("-666"));
assert_eq!(bigint("10") + bigint("312"), bigint("322"));
assert_eq!(bigint("-20") + bigint("-400"), bigint("-420"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("0") + bigint("69"), bigint("69"));
}
#[test]
fn test_same_sign_sum_overflow() {
assert_eq!(bigint("1") + bigint("9"), bigint("10"));
assert_eq!(bigint("123") + bigint("118"), bigint("241"));
assert_eq!(bigint("234") + bigint("195"), bigint("429"));
}
#[test]
fn test_different_sign_sum() {
assert_eq!(bigint("-20") + bigint("0"), bigint("-20"));
assert_eq!(bigint("0") + bigint("-30"), bigint("-30"));
assert_eq!(bigint("45") + bigint("-32"), bigint("13"));
assert_eq!(bigint("-20") + bigint("36"), bigint("16"));
assert_eq!(bigint("-69") + bigint("27"), bigint("-42"));
assert_eq!(bigint("34") + bigint("-58"), bigint("-24"));
}
#[test]
fn test_different_sign_sum_underflow() {
assert_eq!(bigint("-10") + bigint("1"), bigint("-9"));
assert_eq!(bigint("2") + bigint("-8"), bigint("-6"));
assert_eq!(bigint("-111") + bigint("22"), bigint("-89"));
assert_eq!(bigint("44") + bigint("-333"), bigint("-289"));
assert_eq!(bigint("32") + bigint("-9"), bigint("23"));
assert_eq!(bigint("-8") + bigint("27"), bigint("19"));
assert_eq!(bigint("222") + bigint("-33"), bigint("189"));
assert_eq!(bigint("-66") + bigint("555"), bigint("489"));
}
#[test]
fn test_negate() {
assert_eq!(-bigint("0"), bigint("0"));
assert_eq!(-bigint("123"), bigint("-123"));
assert_eq!(-bigint("-321"), bigint("321"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("23") - bigint("0"), bigint("23"));
assert_eq!(bigint("0") - bigint("-23"), bigint("23"));
assert_eq!(bigint("0") - bigint("23"), bigint("-23"));
assert_eq!(bigint("17") - bigint("9"), bigint("8"));
assert_eq!(bigint("17") - bigint("1"), bigint("16"));
assert_eq!(bigint("17") - bigint("13"), bigint("4"));
assert_eq!(bigint("-34") - bigint("6"), bigint("-40"));
assert_eq!(bigint("-34") - bigint("25"), bigint("-59"));
assert_eq!(bigint("-34") - bigint("3"), bigint("-37"));
assert_eq!(bigint("-45") - bigint("-6"), bigint("-39"));
assert_eq!(bigint("-45") - bigint("-21"), bigint("-24"));
assert_eq!(bigint("-45") - bigint("-37"), bigint("-8"));
assert_eq!(bigint("56") - bigint("-7"), bigint("63"));
assert_eq!(bigint("56") - bigint("-23"), bigint("79"));
assert_eq!(bigint("56") - bigint("-45"), bigint("101"));
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
}

Последната стабилна версия на Rust би трябвало да е 1.47 -- това ми дава rustup, това се вижда и на официалния сайт: https://www.rust-lang.org/. Сигурен ли си, че не си на nightly, или някакъв бета канал?

Иначе вероятно е num::Unsigned -- не мога да намеря такъв trait в стандартната библиотека. Къде го виждаш ти в документацията?

Опа, 1.48 беше типо, 1.47 е.

Май е станало омазване, защото сутринта преди работа правих промени по кода на онлайн компилатор и той явно си добавя някакви crate-ове сам без да каже (и като търсих подходящ trait за това 1я резултат явно не е бил от std).

Ще го мина в нормалната ми среда пак, за да не се окаже, че е омазан повече :D

Теодор качи решение на 19.11.2020 17:57 (преди почти 5 години)

#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
}
// private
impl Bigint {
- // TODO: clean up
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let digits = {
let mut digits: Vec<u8> = digits
.into_iter()
.rev()
.skip_while(|&digit| digit == 0)
.collect();
+
digits.reverse();
if digits.is_empty() {
digits.push(0);
};
digits
};
Self {
sign: if digits.last().unwrap() == &0 {
1
} else {
sign
},
digits,
}
}
+
fn is_zero(&self) -> bool {
self.digits.last().unwrap() == &0
}
fn abs_cmp(&self, other: &Bigint) -> Ordering {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Equal => self.digits.iter().rev().cmp(other.digits.iter().rev()),
other => other,
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
- let mut digits = s.chars();
-
- let sign = match s.chars().nth(0) {
- Some('-') => {
- digits.next();
- -1
- }
- Some('+') => {
- digits.next();
- 1
- }
- _ => 1,
+ let (sign, to_skip) = match s.chars().next() {
+ Some('-') => (-1, 1),
+ Some('+') => (1, 1),
+ _ => (1, 0),
};
- let parsed_digits: Option<Vec<u8>> = digits
+ let parsed_digits: Option<Vec<u8>> = s
+ .chars()
+ .skip(to_skip)
.map(|c| c.to_digit(10).map(|digit| digit as u8))
.collect();
match parsed_digits {
- Some(digits) => {
- let mut digits = digits;
- digits.reverse();
- Ok(Bigint::from_components(digits, sign))
- }
+ Some(digits) => Ok(Bigint::from_components(
+ digits.into_iter().rev().collect(),
+ sign,
+ )),
None => Err(Self::Err {}),
}
}
}
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 {
match self.sign.cmp(&other.sign) {
Ordering::Equal => {
let ord = self.abs_cmp(&other);
if self.sign == 1 {
ord
} else {
ord.reverse()
}
}
other => other,
}
}
}
use std::ops::Add;
-fn add_digits(left: &Vec<u8>, right: &Vec<u8>, len: usize) -> Vec<u8> {
+fn add_digits(left: &[u8], right: &[u8], len: usize) -> Vec<u8> {
let padding = [0].repeat(len + 1);
let mut remainder = 0;
let adder = |addends: (&u8, &u8)| {
let sum = addends.0 + addends.1 + remainder;
remainder = sum / 10;
sum % 10
};
left.iter()
.chain(padding.iter())
.zip(right.iter().chain(padding.iter()))
.map(adder)
.collect()
}
-fn subtract_digits(larger: &Vec<u8>, smaller: &Vec<u8>, len: usize) -> Vec<u8> {
+fn subtract_digits(larger: &[u8], smaller: &[u8], len: usize) -> Vec<u8> {
let padding = [0].repeat(len + 1);
let mut remainder = 0;
let subber = |arguments: (&u8, &u8)| {
let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
remainder = if lhs >= rhs { 0 } else { 1 };
distance(remainder * 10, distance(lhs, rhs))
};
larger
.iter()
.chain(padding.iter())
.zip(smaller.iter().chain(padding.iter()))
.map(subber)
.collect()
}
fn distance<U: Sub<Output = U> + Ord>(a: U, b: U) -> U {
if a >= b {
a - b
} else {
b - a
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let len = distance(self.digits.len(), other.digits.len());
if self.sign == other.sign {
Bigint::from_components(add_digits(&self.digits, &other.digits, len), self.sign)
} else {
let (bigger, smaller) = if self.abs_cmp(&other) == Ordering::Less {
(&other, &self)
} else {
(&self, &other)
};
Bigint::from_components(
subtract_digits(&bigger.digits, &smaller.digits, len),
bigger.sign,
)
}
}
}
use std::ops::Neg;
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
- Bigint::from_components(self.digits, self.sign * -1)
+ Bigint::from_components(self.digits, -self.sign)
}
}
use std::ops::Sub;
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
use std::str::FromStr;
#[cfg(test)]
mod test {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_is_positive() {
assert_eq!(bigint("1").is_positive(), true);
assert_eq!(bigint("+1").is_positive(), true);
assert_eq!(bigint("+0").is_positive(), false);
assert_eq!(Bigint::new().is_positive(), false);
}
#[test]
fn test_is_negative() {
assert_eq!(bigint("-1").is_negative(), true);
assert_eq!(bigint("-0").is_negative(), false);
assert_eq!(Bigint::new().is_negative(), false);
}
#[test]
fn test_parse_0() {
assert_eq!(bigint("0"), bigint("-0"));
assert_eq!(bigint("0"), bigint("+0"));
assert_eq!(bigint("0"), bigint(""));
}
#[test]
fn test_parse_default_sign() {
assert_eq!(bigint("123"), bigint("+123"));
}
#[test]
fn test_parse_leading_zeroes() {
assert_eq!(bigint("123"), bigint("0123"));
assert_eq!(bigint("123"), bigint("00000123"));
assert_eq!(bigint("123"), bigint("+0123"));
assert_eq!(bigint("123"), bigint("+000000123"));
assert_eq!(bigint("-123"), bigint("-0123"));
assert_eq!(bigint("-123"), bigint("-000000123"));
assert_ne!(bigint("123"), bigint("1230"));
assert_ne!(bigint("123"), bigint("1203"));
}
#[test]
fn test_parse_error() {
assert!(Bigint::from_str("NaN").is_err());
assert!(Bigint::from_str("++1").is_err());
assert!(Bigint::from_str("--1").is_err());
assert!(Bigint::from_str(" +1").is_err());
assert!(Bigint::from_str(" 1").is_err());
assert!(Bigint::from_str(" -1").is_err());
assert!(Bigint::from_str(" 01").is_err());
assert!(Bigint::from_str("1+1").is_err());
assert!(Bigint::from_str("1-1").is_err());
assert!(Bigint::from_str("1+").is_err());
assert!(Bigint::from_str("1-").is_err());
assert!(Bigint::from_str("1 ").is_err());
assert!(Bigint::from_str("+1 ").is_err());
assert!(Bigint::from_str("-1 ").is_err());
assert!(Bigint::from_str(" ").is_err());
assert!(Bigint::from_str("1 1").is_err());
assert!(Bigint::from_str("+ 1").is_err());
assert!(Bigint::from_str("- 1").is_err());
}
#[test]
fn test_ord_same_sign() {
assert!(bigint("123") < bigint("124"));
assert!(bigint("125") > bigint("123"));
assert!(bigint("2") < bigint("10"));
assert!(bigint("20") > bigint("10"));
assert!(bigint("-123") > bigint("-124"));
assert!(bigint("-324") < bigint("-200"));
assert!(bigint("-12") < bigint("-2"));
assert!(bigint("-3") > bigint("-11"));
}
#[test]
fn test_ord_different_signs() {
assert!(bigint("0") < bigint("124"));
assert!(bigint("243") > bigint("0"));
assert!(bigint("-123") < bigint("0"));
assert!(bigint("0") > bigint("-124"));
assert!(bigint("-111") < bigint("222"));
assert!(bigint("-444") < bigint("333"));
assert!(bigint("-2") < bigint("10"));
assert!(bigint("-20") < bigint("3"));
}
#[test]
fn test_same_sign_sum() {
assert_eq!(bigint("123") + bigint("321"), bigint("444"));
assert_eq!(bigint("-234") + bigint("-432"), bigint("-666"));
assert_eq!(bigint("10") + bigint("312"), bigint("322"));
assert_eq!(bigint("-20") + bigint("-400"), bigint("-420"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("0") + bigint("69"), bigint("69"));
}
#[test]
fn test_same_sign_sum_overflow() {
assert_eq!(bigint("1") + bigint("9"), bigint("10"));
assert_eq!(bigint("123") + bigint("118"), bigint("241"));
assert_eq!(bigint("234") + bigint("195"), bigint("429"));
}
#[test]
fn test_different_sign_sum() {
assert_eq!(bigint("-20") + bigint("0"), bigint("-20"));
assert_eq!(bigint("0") + bigint("-30"), bigint("-30"));
assert_eq!(bigint("45") + bigint("-32"), bigint("13"));
assert_eq!(bigint("-20") + bigint("36"), bigint("16"));
assert_eq!(bigint("-69") + bigint("27"), bigint("-42"));
assert_eq!(bigint("34") + bigint("-58"), bigint("-24"));
}
#[test]
fn test_different_sign_sum_underflow() {
assert_eq!(bigint("-10") + bigint("1"), bigint("-9"));
assert_eq!(bigint("2") + bigint("-8"), bigint("-6"));
assert_eq!(bigint("-111") + bigint("22"), bigint("-89"));
assert_eq!(bigint("44") + bigint("-333"), bigint("-289"));
assert_eq!(bigint("32") + bigint("-9"), bigint("23"));
assert_eq!(bigint("-8") + bigint("27"), bigint("19"));
assert_eq!(bigint("222") + bigint("-33"), bigint("189"));
assert_eq!(bigint("-66") + bigint("555"), bigint("489"));
}
#[test]
fn test_negate() {
assert_eq!(-bigint("0"), bigint("0"));
assert_eq!(-bigint("123"), bigint("-123"));
assert_eq!(-bigint("-321"), bigint("321"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("23") - bigint("0"), bigint("23"));
assert_eq!(bigint("0") - bigint("-23"), bigint("23"));
assert_eq!(bigint("0") - bigint("23"), bigint("-23"));
assert_eq!(bigint("17") - bigint("9"), bigint("8"));
assert_eq!(bigint("17") - bigint("1"), bigint("16"));
assert_eq!(bigint("17") - bigint("13"), bigint("4"));
assert_eq!(bigint("-34") - bigint("6"), bigint("-40"));
assert_eq!(bigint("-34") - bigint("25"), bigint("-59"));
assert_eq!(bigint("-34") - bigint("3"), bigint("-37"));
assert_eq!(bigint("-45") - bigint("-6"), bigint("-39"));
assert_eq!(bigint("-45") - bigint("-21"), bigint("-24"));
assert_eq!(bigint("-45") - bigint("-37"), bigint("-8"));
assert_eq!(bigint("56") - bigint("-7"), bigint("63"));
assert_eq!(bigint("56") - bigint("-23"), bigint("79"));
assert_eq!(bigint("56") - bigint("-45"), bigint("101"));
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
}

Теодор качи решение на 19.11.2020 18:05 (преди почти 5 години)

+use std::cmp::Ordering;
+use std::ops::{Add, Neg, Sub};
+use std::str::FromStr;
+
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
}
// private
impl Bigint {
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let digits = {
let mut digits: Vec<u8> = digits
.into_iter()
.rev()
.skip_while(|&digit| digit == 0)
.collect();
digits.reverse();
if digits.is_empty() {
digits.push(0);
};
digits
};
Self {
sign: if digits.last().unwrap() == &0 {
1
} else {
sign
},
digits,
}
}
fn is_zero(&self) -> bool {
self.digits.last().unwrap() == &0
}
fn abs_cmp(&self, other: &Bigint) -> Ordering {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Equal => self.digits.iter().rev().cmp(other.digits.iter().rev()),
other => other,
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let (sign, to_skip) = match s.chars().next() {
Some('-') => (-1, 1),
Some('+') => (1, 1),
_ => (1, 0),
};
let parsed_digits: Option<Vec<u8>> = s
.chars()
.skip(to_skip)
.map(|c| c.to_digit(10).map(|digit| digit as u8))
.collect();
match parsed_digits {
Some(digits) => Ok(Bigint::from_components(
digits.into_iter().rev().collect(),
sign,
)),
None => Err(Self::Err {}),
}
}
}
-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 {
match self.sign.cmp(&other.sign) {
Ordering::Equal => {
let ord = self.abs_cmp(&other);
if self.sign == 1 {
ord
} else {
ord.reverse()
}
}
other => other,
}
}
}
-use std::ops::Add;
-
fn add_digits(left: &[u8], right: &[u8], len: usize) -> Vec<u8> {
let padding = [0].repeat(len + 1);
let mut remainder = 0;
let adder = |addends: (&u8, &u8)| {
let sum = addends.0 + addends.1 + remainder;
remainder = sum / 10;
sum % 10
};
left.iter()
.chain(padding.iter())
.zip(right.iter().chain(padding.iter()))
.map(adder)
.collect()
}
fn subtract_digits(larger: &[u8], smaller: &[u8], len: usize) -> Vec<u8> {
let padding = [0].repeat(len + 1);
let mut remainder = 0;
let subber = |arguments: (&u8, &u8)| {
let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
remainder = if lhs >= rhs { 0 } else { 1 };
distance(remainder * 10, distance(lhs, rhs))
};
larger
.iter()
.chain(padding.iter())
.zip(smaller.iter().chain(padding.iter()))
.map(subber)
.collect()
}
fn distance<U: Sub<Output = U> + Ord>(a: U, b: U) -> U {
if a >= b {
a - b
} else {
b - a
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let len = distance(self.digits.len(), other.digits.len());
if self.sign == other.sign {
Bigint::from_components(add_digits(&self.digits, &other.digits, len), self.sign)
} else {
let (bigger, smaller) = if self.abs_cmp(&other) == Ordering::Less {
(&other, &self)
} else {
(&self, &other)
};
Bigint::from_components(
subtract_digits(&bigger.digits, &smaller.digits, len),
bigger.sign,
)
}
}
}
-use std::ops::Neg;
-
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint::from_components(self.digits, -self.sign)
}
}
-use std::ops::Sub;
-
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
-
-use std::str::FromStr;
#[cfg(test)]
mod test {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_is_positive() {
assert_eq!(bigint("1").is_positive(), true);
assert_eq!(bigint("+1").is_positive(), true);
assert_eq!(bigint("+0").is_positive(), false);
assert_eq!(Bigint::new().is_positive(), false);
}
#[test]
fn test_is_negative() {
assert_eq!(bigint("-1").is_negative(), true);
assert_eq!(bigint("-0").is_negative(), false);
assert_eq!(Bigint::new().is_negative(), false);
}
#[test]
fn test_parse_0() {
assert_eq!(bigint("0"), bigint("-0"));
assert_eq!(bigint("0"), bigint("+0"));
assert_eq!(bigint("0"), bigint(""));
}
#[test]
fn test_parse_default_sign() {
assert_eq!(bigint("123"), bigint("+123"));
}
#[test]
fn test_parse_leading_zeroes() {
assert_eq!(bigint("123"), bigint("0123"));
assert_eq!(bigint("123"), bigint("00000123"));
assert_eq!(bigint("123"), bigint("+0123"));
assert_eq!(bigint("123"), bigint("+000000123"));
assert_eq!(bigint("-123"), bigint("-0123"));
assert_eq!(bigint("-123"), bigint("-000000123"));
assert_ne!(bigint("123"), bigint("1230"));
assert_ne!(bigint("123"), bigint("1203"));
}
#[test]
fn test_parse_error() {
assert!(Bigint::from_str("NaN").is_err());
assert!(Bigint::from_str("++1").is_err());
assert!(Bigint::from_str("--1").is_err());
assert!(Bigint::from_str(" +1").is_err());
assert!(Bigint::from_str(" 1").is_err());
assert!(Bigint::from_str(" -1").is_err());
assert!(Bigint::from_str(" 01").is_err());
assert!(Bigint::from_str("1+1").is_err());
assert!(Bigint::from_str("1-1").is_err());
assert!(Bigint::from_str("1+").is_err());
assert!(Bigint::from_str("1-").is_err());
assert!(Bigint::from_str("1 ").is_err());
assert!(Bigint::from_str("+1 ").is_err());
assert!(Bigint::from_str("-1 ").is_err());
assert!(Bigint::from_str(" ").is_err());
assert!(Bigint::from_str("1 1").is_err());
assert!(Bigint::from_str("+ 1").is_err());
assert!(Bigint::from_str("- 1").is_err());
}
#[test]
fn test_ord_same_sign() {
assert!(bigint("123") < bigint("124"));
assert!(bigint("125") > bigint("123"));
assert!(bigint("2") < bigint("10"));
assert!(bigint("20") > bigint("10"));
assert!(bigint("-123") > bigint("-124"));
assert!(bigint("-324") < bigint("-200"));
assert!(bigint("-12") < bigint("-2"));
assert!(bigint("-3") > bigint("-11"));
}
#[test]
fn test_ord_different_signs() {
assert!(bigint("0") < bigint("124"));
assert!(bigint("243") > bigint("0"));
assert!(bigint("-123") < bigint("0"));
assert!(bigint("0") > bigint("-124"));
assert!(bigint("-111") < bigint("222"));
assert!(bigint("-444") < bigint("333"));
assert!(bigint("-2") < bigint("10"));
assert!(bigint("-20") < bigint("3"));
}
#[test]
fn test_same_sign_sum() {
assert_eq!(bigint("123") + bigint("321"), bigint("444"));
assert_eq!(bigint("-234") + bigint("-432"), bigint("-666"));
assert_eq!(bigint("10") + bigint("312"), bigint("322"));
assert_eq!(bigint("-20") + bigint("-400"), bigint("-420"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("0") + bigint("69"), bigint("69"));
}
#[test]
fn test_same_sign_sum_overflow() {
assert_eq!(bigint("1") + bigint("9"), bigint("10"));
assert_eq!(bigint("123") + bigint("118"), bigint("241"));
assert_eq!(bigint("234") + bigint("195"), bigint("429"));
}
#[test]
fn test_different_sign_sum() {
assert_eq!(bigint("-20") + bigint("0"), bigint("-20"));
assert_eq!(bigint("0") + bigint("-30"), bigint("-30"));
assert_eq!(bigint("45") + bigint("-32"), bigint("13"));
assert_eq!(bigint("-20") + bigint("36"), bigint("16"));
assert_eq!(bigint("-69") + bigint("27"), bigint("-42"));
assert_eq!(bigint("34") + bigint("-58"), bigint("-24"));
}
#[test]
fn test_different_sign_sum_underflow() {
assert_eq!(bigint("-10") + bigint("1"), bigint("-9"));
assert_eq!(bigint("2") + bigint("-8"), bigint("-6"));
assert_eq!(bigint("-111") + bigint("22"), bigint("-89"));
assert_eq!(bigint("44") + bigint("-333"), bigint("-289"));
assert_eq!(bigint("32") + bigint("-9"), bigint("23"));
assert_eq!(bigint("-8") + bigint("27"), bigint("19"));
assert_eq!(bigint("222") + bigint("-33"), bigint("189"));
assert_eq!(bigint("-66") + bigint("555"), bigint("489"));
}
#[test]
fn test_negate() {
assert_eq!(-bigint("0"), bigint("0"));
assert_eq!(-bigint("123"), bigint("-123"));
assert_eq!(-bigint("-321"), bigint("321"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("23") - bigint("0"), bigint("23"));
assert_eq!(bigint("0") - bigint("-23"), bigint("23"));
assert_eq!(bigint("0") - bigint("23"), bigint("-23"));
assert_eq!(bigint("17") - bigint("9"), bigint("8"));
assert_eq!(bigint("17") - bigint("1"), bigint("16"));
assert_eq!(bigint("17") - bigint("13"), bigint("4"));
assert_eq!(bigint("-34") - bigint("6"), bigint("-40"));
assert_eq!(bigint("-34") - bigint("25"), bigint("-59"));
assert_eq!(bigint("-34") - bigint("3"), bigint("-37"));
assert_eq!(bigint("-45") - bigint("-6"), bigint("-39"));
assert_eq!(bigint("-45") - bigint("-21"), bigint("-24"));
assert_eq!(bigint("-45") - bigint("-37"), bigint("-8"));
assert_eq!(bigint("56") - bigint("-7"), bigint("63"));
assert_eq!(bigint("56") - bigint("-23"), bigint("79"));
assert_eq!(bigint("56") - bigint("-45"), bigint("101"));
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
}

Теодор качи решение на 19.11.2020 20:39 (преди почти 5 години)

use std::cmp::Ordering;
use std::ops::{Add, Neg, Sub};
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
}
// private
impl Bigint {
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let digits = {
let mut digits: Vec<u8> = digits
.into_iter()
.rev()
.skip_while(|&digit| digit == 0)
.collect();
digits.reverse();
if digits.is_empty() {
digits.push(0);
};
digits
};
Self {
sign: if digits.last().unwrap() == &0 {
1
} else {
sign
},
digits,
}
}
fn is_zero(&self) -> bool {
self.digits.last().unwrap() == &0
}
fn abs_cmp(&self, other: &Bigint) -> Ordering {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Equal => self.digits.iter().rev().cmp(other.digits.iter().rev()),
other => other,
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let (sign, to_skip) = match s.chars().next() {
Some('-') => (-1, 1),
Some('+') => (1, 1),
_ => (1, 0),
};
let parsed_digits: Option<Vec<u8>> = s
.chars()
.skip(to_skip)
.map(|c| c.to_digit(10).map(|digit| digit as u8))
.collect();
match parsed_digits {
Some(digits) => Ok(Bigint::from_components(
digits.into_iter().rev().collect(),
sign,
)),
None => Err(Self::Err {}),
}
}
}
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 {
match self.sign.cmp(&other.sign) {
Ordering::Equal => {
let ord = self.abs_cmp(&other);
if self.sign == 1 {
ord
} else {
ord.reverse()
}
}
other => other,
}
}
}
fn add_digits(left: &[u8], right: &[u8], len: usize) -> Vec<u8> {
let padding = [0].repeat(len + 1);
let mut remainder = 0;
let adder = |addends: (&u8, &u8)| {
let sum = addends.0 + addends.1 + remainder;
remainder = sum / 10;
sum % 10
};
left.iter()
.chain(padding.iter())
.zip(right.iter().chain(padding.iter()))
.map(adder)
.collect()
}
fn subtract_digits(larger: &[u8], smaller: &[u8], len: usize) -> Vec<u8> {
let padding = [0].repeat(len + 1);
let mut remainder = 0;
let subber = |arguments: (&u8, &u8)| {
let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
remainder = if lhs >= rhs { 0 } else { 1 };
distance(remainder * 10, distance(lhs, rhs))
};
larger
.iter()
.chain(padding.iter())
.zip(smaller.iter().chain(padding.iter()))
.map(subber)
.collect()
}
fn distance<U: Sub<Output = U> + Ord>(a: U, b: U) -> U {
if a >= b {
a - b
} else {
b - a
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let len = distance(self.digits.len(), other.digits.len());
if self.sign == other.sign {
Bigint::from_components(add_digits(&self.digits, &other.digits, len), self.sign)
} else {
let (bigger, smaller) = if self.abs_cmp(&other) == Ordering::Less {
(&other, &self)
} else {
(&self, &other)
};
Bigint::from_components(
subtract_digits(&bigger.digits, &smaller.digits, len),
bigger.sign,
)
}
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint::from_components(self.digits, -self.sign)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
#[cfg(test)]
mod test {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_is_positive() {
assert_eq!(bigint("1").is_positive(), true);
assert_eq!(bigint("+1").is_positive(), true);
assert_eq!(bigint("+0").is_positive(), false);
assert_eq!(Bigint::new().is_positive(), false);
}
#[test]
fn test_is_negative() {
assert_eq!(bigint("-1").is_negative(), true);
assert_eq!(bigint("-0").is_negative(), false);
assert_eq!(Bigint::new().is_negative(), false);
}
#[test]
fn test_parse_0() {
assert_eq!(bigint("0"), bigint("-0"));
assert_eq!(bigint("0"), bigint("+0"));
assert_eq!(bigint("0"), bigint(""));
+ assert_eq!(bigint("0"), bigint("+"));
+ assert_eq!(bigint("0"), bigint("-"));
}
#[test]
fn test_parse_default_sign() {
assert_eq!(bigint("123"), bigint("+123"));
}
#[test]
fn test_parse_leading_zeroes() {
assert_eq!(bigint("123"), bigint("0123"));
assert_eq!(bigint("123"), bigint("00000123"));
assert_eq!(bigint("123"), bigint("+0123"));
assert_eq!(bigint("123"), bigint("+000000123"));
assert_eq!(bigint("-123"), bigint("-0123"));
assert_eq!(bigint("-123"), bigint("-000000123"));
assert_ne!(bigint("123"), bigint("1230"));
assert_ne!(bigint("123"), bigint("1203"));
}
#[test]
fn test_parse_error() {
assert!(Bigint::from_str("NaN").is_err());
assert!(Bigint::from_str("++1").is_err());
assert!(Bigint::from_str("--1").is_err());
assert!(Bigint::from_str(" +1").is_err());
assert!(Bigint::from_str(" 1").is_err());
assert!(Bigint::from_str(" -1").is_err());
assert!(Bigint::from_str(" 01").is_err());
assert!(Bigint::from_str("1+1").is_err());
assert!(Bigint::from_str("1-1").is_err());
assert!(Bigint::from_str("1+").is_err());
assert!(Bigint::from_str("1-").is_err());
assert!(Bigint::from_str("1 ").is_err());
assert!(Bigint::from_str("+1 ").is_err());
assert!(Bigint::from_str("-1 ").is_err());
assert!(Bigint::from_str(" ").is_err());
assert!(Bigint::from_str("1 1").is_err());
assert!(Bigint::from_str("+ 1").is_err());
assert!(Bigint::from_str("- 1").is_err());
+ assert!(Bigint::from_str("български").is_err());
+ assert!(Bigint::from_str("1о").is_err());
}
#[test]
fn test_ord_same_sign() {
assert!(bigint("123") < bigint("124"));
assert!(bigint("125") > bigint("123"));
assert!(bigint("2") < bigint("10"));
assert!(bigint("20") > bigint("10"));
assert!(bigint("-123") > bigint("-124"));
assert!(bigint("-324") < bigint("-200"));
assert!(bigint("-12") < bigint("-2"));
assert!(bigint("-3") > bigint("-11"));
}
#[test]
fn test_ord_different_signs() {
assert!(bigint("0") < bigint("124"));
assert!(bigint("243") > bigint("0"));
assert!(bigint("-123") < bigint("0"));
assert!(bigint("0") > bigint("-124"));
assert!(bigint("-111") < bigint("222"));
assert!(bigint("-444") < bigint("333"));
assert!(bigint("-2") < bigint("10"));
assert!(bigint("-20") < bigint("3"));
}
#[test]
fn test_same_sign_sum() {
assert_eq!(bigint("123") + bigint("321"), bigint("444"));
assert_eq!(bigint("-234") + bigint("-432"), bigint("-666"));
assert_eq!(bigint("10") + bigint("312"), bigint("322"));
assert_eq!(bigint("-20") + bigint("-400"), bigint("-420"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("0") + bigint("69"), bigint("69"));
}
#[test]
fn test_same_sign_sum_overflow() {
assert_eq!(bigint("1") + bigint("9"), bigint("10"));
assert_eq!(bigint("123") + bigint("118"), bigint("241"));
assert_eq!(bigint("234") + bigint("195"), bigint("429"));
}
#[test]
fn test_different_sign_sum() {
assert_eq!(bigint("-20") + bigint("0"), bigint("-20"));
assert_eq!(bigint("0") + bigint("-30"), bigint("-30"));
assert_eq!(bigint("45") + bigint("-32"), bigint("13"));
assert_eq!(bigint("-20") + bigint("36"), bigint("16"));
assert_eq!(bigint("-69") + bigint("27"), bigint("-42"));
assert_eq!(bigint("34") + bigint("-58"), bigint("-24"));
}
#[test]
fn test_different_sign_sum_underflow() {
assert_eq!(bigint("-10") + bigint("1"), bigint("-9"));
assert_eq!(bigint("2") + bigint("-8"), bigint("-6"));
assert_eq!(bigint("-111") + bigint("22"), bigint("-89"));
assert_eq!(bigint("44") + bigint("-333"), bigint("-289"));
assert_eq!(bigint("32") + bigint("-9"), bigint("23"));
assert_eq!(bigint("-8") + bigint("27"), bigint("19"));
assert_eq!(bigint("222") + bigint("-33"), bigint("189"));
assert_eq!(bigint("-66") + bigint("555"), bigint("489"));
}
#[test]
fn test_negate() {
assert_eq!(-bigint("0"), bigint("0"));
assert_eq!(-bigint("123"), bigint("-123"));
assert_eq!(-bigint("-321"), bigint("321"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("23") - bigint("0"), bigint("23"));
assert_eq!(bigint("0") - bigint("-23"), bigint("23"));
assert_eq!(bigint("0") - bigint("23"), bigint("-23"));
assert_eq!(bigint("17") - bigint("9"), bigint("8"));
assert_eq!(bigint("17") - bigint("1"), bigint("16"));
assert_eq!(bigint("17") - bigint("13"), bigint("4"));
assert_eq!(bigint("-34") - bigint("6"), bigint("-40"));
assert_eq!(bigint("-34") - bigint("25"), bigint("-59"));
assert_eq!(bigint("-34") - bigint("3"), bigint("-37"));
assert_eq!(bigint("-45") - bigint("-6"), bigint("-39"));
assert_eq!(bigint("-45") - bigint("-21"), bigint("-24"));
assert_eq!(bigint("-45") - bigint("-37"), bigint("-8"));
assert_eq!(bigint("56") - bigint("-7"), bigint("63"));
assert_eq!(bigint("56") - bigint("-23"), bigint("79"));
assert_eq!(bigint("56") - bigint("-45"), bigint("101"));
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
-}
+}

Теодор качи решение на 19.11.2020 21:10 (преди почти 5 години)

use std::cmp::Ordering;
use std::ops::{Add, Neg, Sub};
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign: 1,
digits: vec![0],
}
}
pub fn is_positive(&self) -> bool {
!self.is_zero() && self.sign == 1
}
pub fn is_negative(&self) -> bool {
!self.is_zero() && self.sign == -1
}
}
// private
impl Bigint {
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let digits = {
let mut digits: Vec<u8> = digits
.into_iter()
.rev()
.skip_while(|&digit| digit == 0)
.collect();
digits.reverse();
if digits.is_empty() {
digits.push(0);
};
digits
};
Self {
sign: if digits.last().unwrap() == &0 {
1
} else {
sign
},
digits,
}
}
fn is_zero(&self) -> bool {
self.digits.last().unwrap() == &0
}
fn abs_cmp(&self, other: &Bigint) -> Ordering {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Equal => self.digits.iter().rev().cmp(other.digits.iter().rev()),
other => other,
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let (sign, to_skip) = match s.chars().next() {
Some('-') => (-1, 1),
Some('+') => (1, 1),
_ => (1, 0),
};
let parsed_digits: Option<Vec<u8>> = s
.chars()
.skip(to_skip)
.map(|c| c.to_digit(10).map(|digit| digit as u8))
.collect();
match parsed_digits {
Some(digits) => Ok(Bigint::from_components(
digits.into_iter().rev().collect(),
sign,
)),
None => Err(Self::Err {}),
}
}
}
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 {
match self.sign.cmp(&other.sign) {
Ordering::Equal => {
let ord = self.abs_cmp(&other);
if self.sign == 1 {
ord
} else {
ord.reverse()
}
}
other => other,
}
}
}
-fn add_digits(left: &[u8], right: &[u8], len: usize) -> Vec<u8> {
+fn operate_on_digits<F>(left: &[u8], right: &[u8], len: usize, func: F) -> Vec<u8>
+where
+ F: FnMut((&u8, &u8)) -> u8,
+{
let padding = [0].repeat(len + 1);
+ left.iter()
+ .chain(padding.iter())
+ .zip(right.iter().chain(padding.iter()))
+ .map(func)
+ .collect()
+}
+
+fn add_digits(left: &[u8], right: &[u8], len: usize) -> Vec<u8> {
let mut remainder = 0;
let adder = |addends: (&u8, &u8)| {
let sum = addends.0 + addends.1 + remainder;
remainder = sum / 10;
sum % 10
};
- left.iter()
- .chain(padding.iter())
- .zip(right.iter().chain(padding.iter()))
- .map(adder)
- .collect()
+ operate_on_digits(&left, &right, len, adder)
}
fn subtract_digits(larger: &[u8], smaller: &[u8], len: usize) -> Vec<u8> {
- let padding = [0].repeat(len + 1);
let mut remainder = 0;
-
let subber = |arguments: (&u8, &u8)| {
let (lhs, rhs) = (*arguments.0, arguments.1 + remainder);
remainder = if lhs >= rhs { 0 } else { 1 };
-
distance(remainder * 10, distance(lhs, rhs))
};
- larger
- .iter()
- .chain(padding.iter())
- .zip(smaller.iter().chain(padding.iter()))
- .map(subber)
- .collect()
+ operate_on_digits(&larger, &smaller, len, subber)
}
fn distance<U: Sub<Output = U> + Ord>(a: U, b: U) -> U {
if a >= b {
a - b
} else {
b - a
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let len = distance(self.digits.len(), other.digits.len());
if self.sign == other.sign {
Bigint::from_components(add_digits(&self.digits, &other.digits, len), self.sign)
} else {
let (bigger, smaller) = if self.abs_cmp(&other) == Ordering::Less {
(&other, &self)
} else {
(&self, &other)
};
Bigint::from_components(
subtract_digits(&bigger.digits, &smaller.digits, len),
bigger.sign,
)
}
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self::Output {
Bigint::from_components(self.digits, -self.sign)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
#[cfg(test)]
mod test {
use super::*;
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
#[test]
fn test_is_positive() {
assert_eq!(bigint("1").is_positive(), true);
assert_eq!(bigint("+1").is_positive(), true);
assert_eq!(bigint("+0").is_positive(), false);
assert_eq!(Bigint::new().is_positive(), false);
}
#[test]
fn test_is_negative() {
assert_eq!(bigint("-1").is_negative(), true);
assert_eq!(bigint("-0").is_negative(), false);
assert_eq!(Bigint::new().is_negative(), false);
}
#[test]
fn test_parse_0() {
assert_eq!(bigint("0"), bigint("-0"));
assert_eq!(bigint("0"), bigint("+0"));
assert_eq!(bigint("0"), bigint(""));
assert_eq!(bigint("0"), bigint("+"));
assert_eq!(bigint("0"), bigint("-"));
}
#[test]
fn test_parse_default_sign() {
assert_eq!(bigint("123"), bigint("+123"));
}
#[test]
fn test_parse_leading_zeroes() {
assert_eq!(bigint("123"), bigint("0123"));
assert_eq!(bigint("123"), bigint("00000123"));
assert_eq!(bigint("123"), bigint("+0123"));
assert_eq!(bigint("123"), bigint("+000000123"));
assert_eq!(bigint("-123"), bigint("-0123"));
assert_eq!(bigint("-123"), bigint("-000000123"));
assert_ne!(bigint("123"), bigint("1230"));
assert_ne!(bigint("123"), bigint("1203"));
}
#[test]
fn test_parse_error() {
assert!(Bigint::from_str("NaN").is_err());
assert!(Bigint::from_str("++1").is_err());
assert!(Bigint::from_str("--1").is_err());
assert!(Bigint::from_str(" +1").is_err());
assert!(Bigint::from_str(" 1").is_err());
assert!(Bigint::from_str(" -1").is_err());
assert!(Bigint::from_str(" 01").is_err());
assert!(Bigint::from_str("1+1").is_err());
assert!(Bigint::from_str("1-1").is_err());
assert!(Bigint::from_str("1+").is_err());
assert!(Bigint::from_str("1-").is_err());
assert!(Bigint::from_str("1 ").is_err());
assert!(Bigint::from_str("+1 ").is_err());
assert!(Bigint::from_str("-1 ").is_err());
assert!(Bigint::from_str(" ").is_err());
assert!(Bigint::from_str("1 1").is_err());
assert!(Bigint::from_str("+ 1").is_err());
assert!(Bigint::from_str("- 1").is_err());
assert!(Bigint::from_str("български").is_err());
assert!(Bigint::from_str("1о").is_err());
}
#[test]
fn test_ord_same_sign() {
assert!(bigint("123") < bigint("124"));
assert!(bigint("125") > bigint("123"));
assert!(bigint("2") < bigint("10"));
assert!(bigint("20") > bigint("10"));
assert!(bigint("-123") > bigint("-124"));
assert!(bigint("-324") < bigint("-200"));
assert!(bigint("-12") < bigint("-2"));
assert!(bigint("-3") > bigint("-11"));
}
#[test]
fn test_ord_different_signs() {
assert!(bigint("0") < bigint("124"));
assert!(bigint("243") > bigint("0"));
assert!(bigint("-123") < bigint("0"));
assert!(bigint("0") > bigint("-124"));
assert!(bigint("-111") < bigint("222"));
assert!(bigint("-444") < bigint("333"));
assert!(bigint("-2") < bigint("10"));
assert!(bigint("-20") < bigint("3"));
}
#[test]
fn test_same_sign_sum() {
assert_eq!(bigint("123") + bigint("321"), bigint("444"));
assert_eq!(bigint("-234") + bigint("-432"), bigint("-666"));
assert_eq!(bigint("10") + bigint("312"), bigint("322"));
assert_eq!(bigint("-20") + bigint("-400"), bigint("-420"));
assert_eq!(bigint("0") + bigint("0"), bigint("0"));
assert_eq!(bigint("0") + bigint("69"), bigint("69"));
}
#[test]
fn test_same_sign_sum_overflow() {
assert_eq!(bigint("1") + bigint("9"), bigint("10"));
assert_eq!(bigint("123") + bigint("118"), bigint("241"));
assert_eq!(bigint("234") + bigint("195"), bigint("429"));
}
#[test]
fn test_different_sign_sum() {
assert_eq!(bigint("-20") + bigint("0"), bigint("-20"));
assert_eq!(bigint("0") + bigint("-30"), bigint("-30"));
assert_eq!(bigint("45") + bigint("-32"), bigint("13"));
assert_eq!(bigint("-20") + bigint("36"), bigint("16"));
assert_eq!(bigint("-69") + bigint("27"), bigint("-42"));
assert_eq!(bigint("34") + bigint("-58"), bigint("-24"));
}
#[test]
fn test_different_sign_sum_underflow() {
assert_eq!(bigint("-10") + bigint("1"), bigint("-9"));
assert_eq!(bigint("2") + bigint("-8"), bigint("-6"));
assert_eq!(bigint("-111") + bigint("22"), bigint("-89"));
assert_eq!(bigint("44") + bigint("-333"), bigint("-289"));
assert_eq!(bigint("32") + bigint("-9"), bigint("23"));
assert_eq!(bigint("-8") + bigint("27"), bigint("19"));
assert_eq!(bigint("222") + bigint("-33"), bigint("189"));
assert_eq!(bigint("-66") + bigint("555"), bigint("489"));
}
#[test]
fn test_negate() {
assert_eq!(-bigint("0"), bigint("0"));
assert_eq!(-bigint("123"), bigint("-123"));
assert_eq!(-bigint("-321"), bigint("321"));
}
#[test]
fn test_sub() {
assert_eq!(bigint("23") - bigint("0"), bigint("23"));
assert_eq!(bigint("0") - bigint("-23"), bigint("23"));
assert_eq!(bigint("0") - bigint("23"), bigint("-23"));
assert_eq!(bigint("17") - bigint("9"), bigint("8"));
assert_eq!(bigint("17") - bigint("1"), bigint("16"));
assert_eq!(bigint("17") - bigint("13"), bigint("4"));
assert_eq!(bigint("-34") - bigint("6"), bigint("-40"));
assert_eq!(bigint("-34") - bigint("25"), bigint("-59"));
assert_eq!(bigint("-34") - bigint("3"), bigint("-37"));
assert_eq!(bigint("-45") - bigint("-6"), bigint("-39"));
assert_eq!(bigint("-45") - bigint("-21"), bigint("-24"));
assert_eq!(bigint("-45") - bigint("-37"), bigint("-8"));
assert_eq!(bigint("56") - bigint("-7"), bigint("63"));
assert_eq!(bigint("56") - bigint("-23"), bigint("79"));
assert_eq!(bigint("56") - bigint("-45"), bigint("101"));
}
#[test]
fn test_basic() {
assert_eq!(Bigint::new(), bigint("0"));
assert!(Bigint::from_str("foobar").is_err());
assert!(bigint("1").is_positive());
assert!(bigint("-1").is_negative());
assert_eq!(bigint("123") + bigint("456"), bigint("579"));
assert_eq!(bigint("579") - bigint("456"), bigint("123"));
assert!(bigint("123") > bigint("122"));
}
-}
+}