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

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

Решение на Bigint от Александра Йовкова

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

Към профила на Александра Йовкова

Резултати

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

Код

use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Add, 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 is_zero(&self) -> bool {
self.digits == vec![0]
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
self.sign == 1 && !self.is_zero()
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
self.sign == -1 && !self.is_zero()
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut num_str = s;
let sign: i8;
// Set sign
match s.chars().nth(0).unwrap() {
'0'..='9' => sign=1,
'+' => {num_str = &num_str[1..]; sign=1 },
'-' => {num_str = &num_str[1..]; sign=-1 },
_ => return Err(ParseError)
}
// Remove leading zeroes
let mut first_non_zero_index = 0;
for char_index in num_str.char_indices() {
if char_index.1 != '0' {
first_non_zero_index = char_index.0;
break;
}
}
if first_non_zero_index != 0 {
num_str = &num_str[first_non_zero_index..];
}
if num_str.is_empty() || num_str == String::from('0') || num_str.chars().all(|x| x == '0'){
return Ok(Bigint::new());
}
let mut v = Vec::<u8>::with_capacity(num_str.len());
for b in num_str.chars() {
match b {
'0'..='9' => v.push(b.to_digit(10).unwrap() as u8),
_ => return Err(ParseError)
}
}
let res = Bigint{digits: v, sign: sign};
Ok(res)
}
}
impl PartialOrd for Bigint {
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
fn cmp(&self, other: &Bigint) -> Ordering {
let mut result = Ordering::Less;
if self.sign == other.sign {
let self_num_digits = self.digits.len();
let other_num_digits = other.digits.len();
if self_num_digits == other_num_digits {
let self_as_str: String = self.digits.iter().map(|i| i.to_string()).collect::<String>();
let other_as_str: String = other.digits.iter().map(|i| i.to_string()).collect::<String>();
if self_as_str == other_as_str {
result = Ordering::Equal;
}
if self_as_str > other_as_str {
result = Ordering::Greater;
}
} else if self_num_digits > other_num_digits {
result = Ordering::Greater;
}
} else if self.sign > other.sign {
result = Ordering::Greater;
}
if self.sign == -1 && other.sign == -1 {
result = result.reverse();
}
result
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut result: Vec<u8> = Vec::new();
let mut n1;
let mut n2;
if self.sign * other.sign == 1 {
// Numbers have same sign
if self > other {
n1 = self.digits;
n2 = other.digits;
} else {
n1 = other.digits;
n2 = self.digits;
}
n1.reverse();
n2.reverse();
let mut carry = 0;
for i in 0..n2.len() {
let sum = n1[i] + n2[i] + carry;
result.push(sum % 10);
carry = sum / 10;
}
for i in n2.len() .. n1.len() {
let sum = n1[i] + carry;
result.push(sum % 10);
carry = sum / 10;
}
if carry != 0 {
result.push(carry);
}
result.reverse();
return Bigint {digits: result, sign: self.sign}
} else {
let cmp_num_1 = Bigint{digits: self.digits, sign: 1};
let cmp_num_2 = Bigint{digits: other.digits, sign: 1};
if self.sign == other.sign && cmp_num_1 == cmp_num_2 {
return Bigint::new();
}
let sign: i8;
if cmp_num_1 < cmp_num_2 {
sign = other.sign;
n1 = cmp_num_2.digits;
n2 = cmp_num_1.digits;
} else {
sign = self.sign;
n1 = cmp_num_1.digits;
n2 = cmp_num_2.digits;
}
n1.reverse();
n2.reverse();
let mut carry: i8 = 0;
for i in 0..n2.len() {
let sub: i8 = n1[i] as i8 - n2[i] as i8 - carry;
if sub < 0 {
result.push((sub+10) as u8);
carry = 1;
} else {
result.push(sub as u8);
carry = 0;
}
}
for i in n2.len() .. n1.len() {
let sub: i8 = n1[i] as i8 - carry;
if sub < 0 {
result.push((sub+10) as u8);
carry = 1;
} else {
result.push(sub as u8);
carry = 0;
}
}
result.reverse();
// Remove possible leading zeroes
let mut first_non_zero_index = 0;
for (index, el) in result.iter().enumerate() {
if *el != 0 {
first_non_zero_index = index;
break;
}
}
if first_non_zero_index != 0 {
result = (&result[first_non_zero_index..]).to_vec();
}
return Bigint {digits: result, sign: sign}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let negated_other = Bigint{digits: other.digits, sign: other.sign * -1};
self + negated_other
}
}
fn main() {}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-1y08g1d/solution)
warning: function is never used: `main`
   --> src/lib.rs:234:4
    |
234 | fn main() {}
    |    ^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 1 warning emitted

    Finished test [unoptimized + debuginfo] target(s) in 1.83s
     Running target/debug/deps/solution_test-589a43f0f4b10ca3

running 15 tests
test solution_test::test_bigint_construction ... FAILED
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 ... FAILED
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 ... FAILED
test solution_test::test_sum_4_negative ... FAILED

failures:

---- solution_test::test_bigint_construction stdout ----
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/lib.rs:46:32
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- solution_test::test_neutralization stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Bigint { sign: -1, digits: [0, 0, 0] }`,
 right: `Bigint { sign: 1, digits: [0] }`', tests/solution_test.rs:126:5

---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'index out of bounds: the len is 1 but the index is 1', src/lib.rs:146:27

---- solution_test::test_sum_4_negative stdout ----
thread 'main' panicked at 'index out of bounds: the len is 2 but the index is 2', src/lib.rs:146:27


failures:
    solution_test::test_bigint_construction
    solution_test::test_neutralization
    solution_test::test_sum_3_overflow
    solution_test::test_sum_4_negative

test result: FAILED. 11 passed; 4 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '--test solution_test'

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

Александра качи първо решение на 27.11.2020 03:27 (преди почти 5 години)

Александра качи решение на 27.11.2020 03:32 (преди почти 5 години)

-
use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Add, 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 is_zero(&self) -> bool {
self.digits == vec![0]
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
self.sign == 1 && !self.is_zero()
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
self.sign == -1 && !self.is_zero()
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut num_str = s;
let sign: i8;
// Set sign
match s.chars().nth(0).unwrap() {
'0'..='9' => sign=1,
'+' => {num_str = &num_str[1..]; sign=1 },
'-' => {num_str = &num_str[1..]; sign=-1 },
_ => return Err(ParseError)
}
// Remove leading zeroes
let mut first_non_zero_index = 0;
for char_index in num_str.char_indices() {
if char_index.1 != '0' {
first_non_zero_index = char_index.0;
break;
}
}
if first_non_zero_index != 0 {
num_str = &num_str[first_non_zero_index..];
}
if num_str.is_empty() || num_str == String::from('0') || num_str.chars().all(|x| x == '0'){
return Ok(Bigint::new());
}
let mut v = Vec::<u8>::with_capacity(num_str.len());
for b in num_str.chars() {
match b {
'0'..='9' => v.push(b.to_digit(10).unwrap() as u8),
_ => return Err(ParseError)
}
}
let res = Bigint{digits: v, sign: sign};
Ok(res)
}
}
impl PartialOrd for Bigint {
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
fn cmp(&self, other: &Bigint) -> Ordering {
let mut result = Ordering::Less;
if self.sign == other.sign {
let self_num_digits = self.digits.len();
let other_num_digits = other.digits.len();
if self_num_digits == other_num_digits {
let self_as_str: String = self.digits.iter().map(|i| i.to_string()).collect::<String>();
let other_as_str: String = other.digits.iter().map(|i| i.to_string()).collect::<String>();
if self_as_str == other_as_str {
result = Ordering::Equal;
}
if self_as_str > other_as_str {
result = Ordering::Greater;
}
} else if self_num_digits > other_num_digits {
result = Ordering::Greater;
}
} else if self.sign > other.sign {
result = Ordering::Greater;
}
if self.sign == -1 && other.sign == -1 {
result = result.reverse();
}
result
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut result: Vec<u8> = Vec::new();
let mut n1;
let mut n2;
if self.sign * other.sign == 1 {
// Numbers have same sign
if self > other {
n1 = self.digits;
n2 = other.digits;
} else {
n1 = other.digits;
n2 = self.digits;
}
n1.reverse();
n2.reverse();
let mut carry = 0;
for i in 0..n2.len() {
let sum = n1[i] + n2[i] + carry;
result.push(sum % 10);
carry = sum / 10;
}
for i in n2.len() .. n1.len() {
let sum = n1[i] + carry;
result.push(sum % 10);
carry = sum / 10;
}
if carry != 0 {
result.push(carry);
}
result.reverse();
return Bigint {digits: result, sign: self.sign}
} else {
let cmp_num_1 = Bigint{digits: self.digits, sign: 1};
let cmp_num_2 = Bigint{digits: other.digits, sign: 1};
if self.sign == other.sign && cmp_num_1 == cmp_num_2 {
return Bigint::new();
}
let sign: i8;
if cmp_num_1 < cmp_num_2 {
sign = other.sign;
n1 = cmp_num_2.digits;
n2 = cmp_num_1.digits;
} else {
sign = self.sign;
n1 = cmp_num_1.digits;
n2 = cmp_num_2.digits;
}
n1.reverse();
n2.reverse();
let mut carry: i8 = 0;
for i in 0..n2.len() {
let sub: i8 = n1[i] as i8 - n2[i] as i8 - carry;
if sub < 0 {
result.push((sub+10) as u8);
carry = 1;
} else {
result.push(sub as u8);
carry = 0;
}
}
for i in n2.len() .. n1.len() {
let sub: i8 = n1[i] as i8 - carry;
if sub < 0 {
result.push((sub+10) as u8);
carry = 1;
} else {
result.push(sub as u8);
carry = 0;
}
}
result.reverse();
// Remove possible leading zeroes
let mut first_non_zero_index = 0;
for (index, el) in result.iter().enumerate() {
if *el != 0 {
first_non_zero_index = index;
break;
}
}
if first_non_zero_index != 0 {
result = (&result[first_non_zero_index..]).to_vec();
}
return Bigint {digits: result, sign: sign}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let negated_other = Bigint{digits: other.digits, sign: other.sign * -1};
self + negated_other
}
-}
-
-fn bigint(s: &str) -> Bigint {
- Bigint::from_str(s).unwrap()
}
fn main() {}