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

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

Решение на Bigint от Иван Лучев

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

Към профила на Иван Лучев

Резултати

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

Код

use std::ops::{Add, Sub};
use std::cmp::{Eq, PartialEq, Ordering};
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 0,
digits: Vec::new(),
}
}
fn from_components(digits: Vec<u8>, mut sign: i8) -> Self {
let first_non_zero_index = digits.iter().position(|&r| r != 0).map_or(digits.len(), |x| x);
let digits = digits[first_non_zero_index..digits.len()].to_vec();
if digits.len() == 0 {
sign = 0;
}
Bigint {
sign,
digits
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1
}
pub fn is_negative(&self) -> bool {
self.sign == -1
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s.is_empty() {
return Ok(Bigint::new());
}
let (sign, digits) = match s.chars().next() {
Some('-') => (-1, &s[1..]),
Some('+') => (1, &s[1..]),
_ => (1, s),
};
let digits = digits.chars().map(|c| c.to_digit(10)).collect::<Option<Vec<u32>>>().ok_or(ParseError)?;
if digits.is_empty() {
Err(ParseError)
} else {
let digits = digits.into_iter().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 < other.sign {
Ordering::Less
} else if self.sign > other.sign {
Ordering::Greater
} else if self.sign == 1 {
compare_abs(&self.digits, &other.digits)
} else {
compare_abs(&self.digits, &other.digits).reverse()
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, mut other: Self) -> Self {
other.sign *= -1;
self.sub(other)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
if self.sign == -other.sign {
Bigint::from_components(simple_add(self.digits, other.digits), self.sign)
} else {
let (smaller, larger, sign) = {
if compare_abs(&self.digits, &other.digits) == Ordering::Greater {
(other.digits, self.digits, self.sign)
} else {
(self.digits, other.digits, -other.sign)
}
};
Bigint::from_components(simple_sub(larger, smaller), sign)
}
}
}
fn simple_add(a: Vec<u8>, b: Vec<u8>) -> Vec<u8> {
let mut reversed_result = Vec::new();
let mut carry: u8 = 0;
let mut a_it = a.iter().rev().peekable();
let mut b_it = b.iter().rev().peekable();
while a_it.peek().is_some() || b_it.peek().is_some() || carry > 0 {
let mut digit = carry;
carry = 0;
a_it.next().map(|x| digit += x);
b_it.next().map(|x| digit += x);
if digit >= 10 {
digit -= 10;
carry = 1;
}
reversed_result.push(digit);
}
reversed_result.reverse();
reversed_result
}
fn simple_sub(a: Vec<u8>, b: Vec<u8>) -> Vec<u8> {
let mut reversed_result = Vec::new();
let mut carry: u8 = 0;
let mut a = a.into_iter().rev();
let mut b = b.into_iter().rev();
while let Some(mut minuend) = a.next() {
let subtrahend = b.next().map_or(carry, |x| x + carry);
carry = 0;
if minuend < subtrahend {
minuend += 10;
carry = 1;
}
reversed_result.push(minuend - subtrahend);
}
reversed_result.reverse();
reversed_result
}
fn compare_abs(a: &Vec<u8>, b: &Vec<u8>) -> Ordering{
if a.len() < b.len() {
return Ordering::Less;
} else if a.len() > b.len() {
return Ordering::Greater;
}
for i in 0..a.len() {
if a[i] < b[i] {
return Ordering::Less;
} else if a[i] > b[i] {
return Ordering::Greater;
}
}
Ordering::Equal
}

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

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

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

Иван качи първо решение на 20.11.2020 19:13 (преди почти 5 години)

Иван качи решение на 20.11.2020 19:17 (преди почти 5 години)

use std::ops::{Add, Sub};
use std::cmp::{Eq, PartialEq, Ordering};
use std::str::FromStr;
-#[derive(Debug, PartialEq, Eq, Clone)]
+#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 0,
digits: Vec::new(),
}
}
fn from_components(digits: Vec<u8>, mut sign: i8) -> Self {
let first_non_zero_index = digits.iter().position(|&r| r != 0).map_or(digits.len(), |x| x);
let digits = digits[first_non_zero_index..digits.len()].to_vec();
if digits.len() == 0 {
sign = 0;
}
Bigint {
sign,
digits
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1
}
pub fn is_negative(&self) -> bool {
self.sign == -1
}
-
- pub fn abs(&self) -> Self {
- if self.sign == 0 {
- self.clone()
- } else {
- Bigint { 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> {
if s.is_empty() {
return Ok(Bigint::new());
}
let (sign, digits) = match s.chars().next() {
Some('-') => (-1, &s[1..]),
Some('+') => (1, &s[1..]),
_ => (1, s),
};
let digits = digits.chars().map(|c| c.to_digit(10)).collect::<Option<Vec<u32>>>().ok_or(ParseError)?;
if digits.is_empty() {
Err(ParseError)
} else {
let digits = digits.into_iter().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 < other.sign {
Ordering::Less
} else if self.sign > other.sign {
Ordering::Greater
} else if self.sign == 1 {
compare_abs(&self.digits, &other.digits)
} else {
compare_abs(&self.digits, &other.digits).reverse()
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, mut other: Self) -> Self {
other.sign *= -1;
self.sub(other)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
if self.sign == -other.sign {
Bigint::from_components(simple_add(self.digits, other.digits), self.sign)
} else {
let (smaller, larger, sign) = {
- if self.abs() <= other.abs() {
- (self.digits, other.digits, -other.sign)
- } else {
+ if compare_abs(&self.digits, &other.digits) == Ordering::Greater {
(other.digits, self.digits, self.sign)
+ } else {
+ (self.digits, other.digits, -other.sign)
}
};
Bigint::from_components(simple_sub(larger, smaller), sign)
}
}
}
fn simple_add(a: Vec<u8>, b: Vec<u8>) -> Vec<u8> {
let mut reversed_result = Vec::new();
let mut carry: u8 = 0;
let mut a_it = a.iter().rev().peekable();
let mut b_it = b.iter().rev().peekable();
while a_it.peek().is_some() || b_it.peek().is_some() || carry > 0 {
let mut digit = carry;
carry = 0;
a_it.next().map(|x| digit += x);
b_it.next().map(|x| digit += x);
if digit >= 10 {
digit -= 10;
carry = 1;
}
reversed_result.push(digit);
}
reversed_result.reverse();
reversed_result
}
fn simple_sub(a: Vec<u8>, b: Vec<u8>) -> Vec<u8> {
let mut reversed_result = Vec::new();
let mut carry: u8 = 0;
let mut a = a.into_iter().rev();
let mut b = b.into_iter().rev();
while let Some(mut minuend) = a.next() {
let subtrahend = b.next().map_or(carry, |x| x + carry);
carry = 0;
if minuend < subtrahend {
minuend += 10;
carry = 1;
}
reversed_result.push(minuend - subtrahend);
}
reversed_result.reverse();
reversed_result
}
fn compare_abs(a: &Vec<u8>, b: &Vec<u8>) -> Ordering{
if a.len() < b.len() {
return Ordering::Less;
} else if a.len() > b.len() {
return Ordering::Greater;
}
for i in 0..a.len() {
if a[i] < b[i] {
return Ordering::Less;
} else if a[i] > b[i] {
return Ordering::Greater;
}
}
Ordering::Equal
}