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

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

Решение на Bigint от Йордан Миронски

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

Към профила на Йордан Миронски

Резултати

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

Код

use std::{cmp::Ordering, ops::Add, str::FromStr, ops::Sub};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self
{
let mut v = Vec::new();
v.push(0);
Self { digits: v, sign: 1 }
}
pub fn is_positive(&self) -> bool
{
if self.digits[0] == 0 { false }
else { self.sign == 1 }
}
pub fn is_negative(&self) -> bool
{
if self.digits[0] == 0 { false }
else { self.sign == -1 }
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err>
{
let mut sgn = 1;
let mut digs = Vec::new();
digs.push(0);
if s.is_empty()
{
return Ok(Bigint::new());
}
let s1 = &s[1..];
if s.chars().nth(0).unwrap() == '+' || s.chars().nth(0).unwrap() == '-'
{
if s1.is_empty()
{
return Ok(Bigint::new());
}
}
if !s1.chars().all(char::is_numeric)
{
return Err(ParseError{});
}
if s.chars().nth(0).unwrap() == '+' || s.chars().nth(0).unwrap() == '-'
{
if s1.chars().all(|x| x == '0')
{
return Ok(Bigint::new());
}
} else if s.chars().all(|x| x == '0')
{
return Ok(Bigint::new());
}
if s.chars().nth(0).unwrap() == '+'
{
sgn = 1;
}
else if s.chars().nth(0).unwrap() == '-'
{
sgn = -1;
}
else if s.chars().nth(0).unwrap().is_digit(10)
{
sgn = 1;
}
else {
return Err(ParseError{});
}
let mut i = 0;
if !s.chars().nth(0).unwrap().is_digit(10)
{
i = 1;
}
while s.chars().nth(i).unwrap() == '0'
{
i += 1;
}
digs.pop();
for mut j in i..s.len()
{
digs.push(s.chars().nth(j).unwrap().to_digit(10).unwrap() as u8);
j += 1;
}
return Ok(Bigint{digits:digs, sign:sgn});
}
}
impl PartialOrd for Bigint {
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint
{
fn cmp(&self, other: &Bigint) -> Ordering
{
if self.sign == 1 && other.sign == -1 { return Ordering::Greater; }
else if self.sign == -1 && other.sign == 1 { return Ordering::Less; }
else {
let mut check = 1;
if self.sign == -1 && other.sign == -1 { check = -1; }
if self.digits.len() < other.digits.len()
{
if check == 1
{
return Ordering::Less;
}
else { return Ordering::Greater; }
}else if self.digits.len() > other.digits.len() {
if check == 1
{
return Ordering::Greater;
}
else {return Ordering::Less;}
}
else
{
if check == 1
{
return self.digits.cmp(&other.digits);
}
else
{
if self.digits.cmp(&other.digits) == Ordering::Less
{
return Ordering::Greater;
}else if self.digits.cmp(&other.digits) == Ordering::Greater
{
return Ordering::Less;
}else {
return Ordering::Equal;
}
}
}
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self
{
let mut v1 = self.digits.clone();
let mut v2 = other.digits.clone();
v1.reverse();
v2.reverse();
if (self.sign == 1 && other.sign == 1) || (self.sign == -1 && other.sign == -1)
{
let mut s = 1;
if self.sign == 1 && other.sign == 1 { s = 1 }
if self.sign == -1 && other.sign == -1 { s = -1 }
if v1.len() < v2.len()
{
let mut v = Vec::new();
let mut carry = 0;
for i in 0..v1.len()
{
let curr = v1[i] + v2[i] + carry;
v.push(curr % 10);
carry = curr / 10;
}
for i in v1.len()..v2.len()
{
let curr = v2[i] + carry;
v.push(curr % 10);
carry = curr / 10;
}
while carry > 0
{
v.push(carry % 10);
carry /= 10;
}
v.reverse();
return Self{digits:v,sign:s};
}
else
{
let mut v = Vec::new();
let mut carry = 0;
for i in 0..v2.len()
{
let curr = v1[i] + v2[i] + carry;
v.push(curr % 10);
carry = curr / 10;
}
for i in v2.len()..v1.len()
{
let curr = v1[i] + carry;
v.push(curr % 10);
carry = curr / 10;
}
while carry > 0
{
v.push(carry % 10);
carry /= 10;
}
v.reverse();
return Self{digits:v, sign:s};
}
}
else
{
v1.reverse();
v2.reverse();
let b1 = Bigint{digits:v1.clone(), sign:1};
let b2 = Bigint{digits:v2.clone(), sign:1};
let mut s = 1;
if b1 < b2
{
s = other.sign;
}
if b2 < b1
{
s = self.sign;
}
if b1 < b2
{
v1.reverse();
v2.reverse();
let mut v:Vec<u8> = Vec::new();
let mut carry = 0;
for i in 0..v1.len()
{
let mut curr = v2[i] as i8 - v1[i] as i8 - carry;
let mut us_curr:u8 = curr as u8;
if curr < 0
{
curr = curr + 10;
us_curr = curr as u8;
carry = 1;
}
else
{
carry = 0;
}
v.push(us_curr);
}
for i in v1.len()..v2.len()
{
let mut curr:u8 = v2[i] as u8 - carry as u8;
if curr < 0
{
curr = curr + 10;
carry = 1;
}
else
{
carry = 0;
}
v.push(curr);
}
v.reverse();
let mut k = 0;
while v[k] == 0
{
k = k + 1;
}
let mut res:Vec<u8> = Vec::new();
while k < v.len()
{
res.push(v[k]);
k = k + 1;
}
return Self{digits:res, sign:s};
}
if b2 < b1
{
v1.reverse();
v2.reverse();
let mut v:Vec<u8> = Vec::new();
let mut carry = 0;
for i in 0..v2.len()
{
let mut curr= v1[i] as i8 - v2[i] as i8 - carry;
let mut us_curr:u8 = curr as u8;
if curr < 0
{
curr = curr + 10;
us_curr = curr as u8;
carry = 1;
}
else
{
carry = 0;
}
v.push(us_curr);
}
for i in v2.len()..v1.len()
{
let mut curr:u8 = v1[i] as u8 - carry as u8;
if curr < 0
{
curr = curr + 10;
carry = 1;
}
else
{
carry = 0;
}
v.push(curr);
}
v.reverse();
let mut k = 0;
while v[k] == 0
{
k = k + 1;
}
let mut res:Vec<u8> = Vec::new();
while k < v.len()
{
res.push(v[k]);
k = k + 1;
}
return Self{digits:res, sign:s};
}
if b1 == b2
{
let temp = Bigint::new();
return Self{digits:temp.digits, sign:1};
}
return Self{digits:v1.clone(), sign:1};
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let i1 = Bigint{digits:self.digits.clone(), sign:self.sign};
let mut i2 = Bigint{digits:other.digits.clone(), sign:other.sign};
if i1.sign == 1 && i2.sign == 1
{
i2.sign = -1;
let i3 = i1+i2;
return Self{digits:i3.digits, sign:i3.sign};
}
if i1.sign == 1 && i2.sign == -1
{
i2.sign = 1;
let i3 = i1+i2;
return Self{digits:i3.digits, sign:i3.sign};
}
if i1.sign == -1 && i2.sign == -1
{
i2.sign = 1;
let i3 = i1+i2;
return Self{digits:i3.digits, sign:i3.sign};
}
if i1.sign == -1 && i2.sign == 1
{
i2.sign = -1;
let i3 = i1+i2;
return Self{digits:i3.digits, sign:i3.sign};
}
else {
let e = Vec::new();
return Self{digits:e , sign:1};
}
}
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-scl5ok/solution)
warning: value assigned to `sgn` is never read
  --> src/lib.rs:39:13
   |
39 |         let mut sgn = 1;
   |             ^^^^^^^
   |
   = note: `#[warn(unused_assignments)]` on by default
   = help: maybe it is overwritten before being read?

warning: value assigned to `j` is never read
  --> src/lib.rs:96:13
   |
96 |             j += 1;
   |             ^
   |
   = help: maybe it is overwritten before being read?

warning: comparison is useless due to type limits
   --> src/lib.rs:268:24
    |
268 |                     if curr < 0 
    |                        ^^^^^^^^
    |
    = note: `#[warn(unused_comparisons)]` on by default

warning: comparison is useless due to type limits
   --> src/lib.rs:324:24
    |
324 |                     if curr < 0 
    |                        ^^^^^^^^

warning: 4 warnings emitted

    Finished test [unoptimized + debuginfo] target(s) in 2.05s
     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 ... FAILED
test solution_test::test_neutralization ... ok
test solution_test::test_parsing_with_and_without_sign ... ok
test solution_test::test_parsing_with_leading_zeroes ... ok
test solution_test::test_sub_1_basic ... ok
test solution_test::test_sub_2_diferent_lengths ... ok
test solution_test::test_sub_3_carry ... FAILED
test solution_test::test_sum_1_basic ... ok
test solution_test::test_sum_2_different_lengths ... ok
test solution_test::test_sum_3_overflow ... ok
test solution_test::test_sum_4_negative ... ok

failures:

---- solution_test::test_invalid_string stdout ----
thread 'main' panicked at 'byte index 1 is not a char boundary; it is inside 'к' (bytes 0..2) of `кирилица`', src/lib.rs:46:19
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:323:39


failures:
    solution_test::test_invalid_string
    solution_test::test_sub_3_carry

test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out

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

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

Йордан качи първо решение на 23.11.2020 23:49 (преди почти 5 години)

Йордан качи решение на 24.11.2020 00:23 (преди почти 5 години)

use std::{cmp::Ordering, ops::Add, str::FromStr, ops::Sub};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self
{
let mut v = Vec::new();
v.push(0);
Self { digits: v, sign: 1 }
}
pub fn is_positive(&self) -> bool
{
if self.digits[0] == 0 { false }
else { self.sign == 1 }
}
pub fn is_negative(&self) -> bool
{
if self.digits[0] == 0 { false }
else { self.sign == -1 }
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err>
{
let mut sgn = 1;
let mut digs = Vec::new();
digs.push(0);
if s.is_empty()
{
return Ok(Bigint::new());
}
let s1 = &s[1..];
if s.chars().nth(0).unwrap() == '+' || s.chars().nth(0).unwrap() == '-'
{
if s1.is_empty()
{
return Ok(Bigint::new());
}
}
if !s1.chars().all(char::is_numeric)
{
return Err(ParseError{});
}
if s.chars().nth(0).unwrap() == '+' || s.chars().nth(0).unwrap() == '-'
{
if s1.chars().all(|x| x == '0')
{
return Ok(Bigint::new());
}
} else if s.chars().all(|x| x == '0')
{
return Ok(Bigint::new());
}
if s.chars().nth(0).unwrap() == '+'
{
sgn = 1;
}
else if s.chars().nth(0).unwrap() == '-'
{
sgn = -1;
}
else if s.chars().nth(0).unwrap().is_digit(10)
{
sgn = 1;
}
else {
return Err(ParseError{});
}
let mut i = 0;
if !s.chars().nth(0).unwrap().is_digit(10)
{
i = 1;
}
while s.chars().nth(i).unwrap() == '0'
{
i += 1;
}
digs.pop();
for mut j in i..s.len()
{
digs.push(s.chars().nth(j).unwrap().to_digit(10).unwrap() as u8);
j += 1;
}
return Ok(Bigint{digits:digs, sign:sgn});
}
}
impl PartialOrd for Bigint {
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint
{
fn cmp(&self, other: &Bigint) -> Ordering
{
if self.sign == 1 && other.sign == -1 { return Ordering::Greater; }
else if self.sign == -1 && other.sign == 1 { return Ordering::Less; }
else {
let mut check = 1;
if self.sign == -1 && other.sign == -1 { check = -1; }
if self.digits.len() < other.digits.len()
{
if check == 1
{
return Ordering::Less;
}
else { return Ordering::Greater; }
}else if self.digits.len() > other.digits.len() {
if check == 1
{
return Ordering::Greater;
}
else {return Ordering::Less;}
}
else
{
if check == 1
{
return self.digits.cmp(&other.digits);
}
else
{
if self.digits.cmp(&other.digits) == Ordering::Less
{
return Ordering::Greater;
}else if self.digits.cmp(&other.digits) == Ordering::Greater
{
return Ordering::Less;
}else {
return Ordering::Equal;
}
}
}
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self
{
let mut v1 = self.digits.clone();
let mut v2 = other.digits.clone();
v1.reverse();
v2.reverse();
if (self.sign == 1 && other.sign == 1) || (self.sign == -1 && other.sign == -1)
{
let mut s = 1;
if self.sign == 1 && other.sign == 1 { s = 1 }
if self.sign == -1 && other.sign == -1 { s = -1 }
if v1.len() < v2.len()
{
let mut v = Vec::new();
let mut carry = 0;
for i in 0..v1.len()
{
let curr = v1[i] + v2[i] + carry;
v.push(curr % 10);
carry = curr / 10;
}
for i in v1.len()..v2.len()
{
let curr = v2[i] + carry;
v.push(curr % 10);
carry = curr / 10;
}
while carry > 0
{
v.push(carry % 10);
carry /= 10;
}
v.reverse();
return Self{digits:v,sign:s};
}
else
{
let mut v = Vec::new();
let mut carry = 0;
for i in 0..v2.len()
{
let curr = v1[i] + v2[i] + carry;
v.push(curr % 10);
carry = curr / 10;
}
for i in v2.len()..v1.len()
{
let curr = v1[i] + carry;
v.push(curr % 10);
carry = curr / 10;
}
while carry > 0
{
v.push(carry % 10);
carry /= 10;
}
v.reverse();
return Self{digits:v, sign:s};
}
}
else
{
v1.reverse();
v2.reverse();
let b1 = Bigint{digits:v1.clone(), sign:1};
let b2 = Bigint{digits:v2.clone(), sign:1};
let mut s = 1;
if b1 < b2
{
s = other.sign;
}
if b2 < b1
{
s = self.sign;
}
if b1 < b2
{
v1.reverse();
v2.reverse();
let mut v:Vec<u8> = Vec::new();
let mut carry = 0;
for i in 0..v1.len()
{
let mut curr = v2[i] as i8 - v1[i] as i8 - carry;
let mut us_curr:u8 = curr as u8;
if curr < 0
{
curr = curr + 10;
us_curr = curr as u8;
carry = 1;
}
else
{
carry = 0;
}
v.push(us_curr);
}
for i in v1.len()..v2.len()
{
let mut curr:u8 = v2[i] as u8 - carry as u8;
if curr < 0
{
curr = curr + 10;
carry = 1;
}
else
{
carry = 0;
}
v.push(curr);
}
- v.reverse();
- return Self{digits:v, sign:s};
+ v.reverse();
+ let mut k = 0;
+
+ while v[k] == 0
+ {
+ k = k + 1;
+ }
+ let mut res:Vec<u8> = Vec::new();
+ while k < v.len()
+ {
+ res.push(v[k]);
+ k = k + 1;
+ }
+ return Self{digits:res, sign:s};
}
if b2 < b1
{
v1.reverse();
v2.reverse();
let mut v:Vec<u8> = Vec::new();
let mut carry = 0;
for i in 0..v2.len()
{
let mut curr= v1[i] as i8 - v2[i] as i8 - carry;
let mut us_curr:u8 = curr as u8;
if curr < 0
{
curr = curr + 10;
us_curr = curr as u8;
carry = 1;
}
else
{
carry = 0;
}
v.push(us_curr);
}
for i in v2.len()..v1.len()
{
let mut curr:u8 = v1[i] as u8 - carry as u8;
if curr < 0
{
curr = curr + 10;
carry = 1;
}
else
{
carry = 0;
}
v.push(curr);
}
v.reverse();
- return Self{digits:v,sign:s};
+ let mut k = 0;
+
+ while v[k] == 0
+ {
+ k = k + 1;
+ }
+ let mut res:Vec<u8> = Vec::new();
+ while k < v.len()
+ {
+ res.push(v[k]);
+ k = k + 1;
+ }
+ return Self{digits:res, sign:s};
}
if b1 == b2
{
let temp = Bigint::new();
return Self{digits:temp.digits, sign:1};
}
return Self{digits:v1.clone(), sign:1};
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let i1 = Bigint{digits:self.digits.clone(), sign:self.sign};
let mut i2 = Bigint{digits:other.digits.clone(), sign:other.sign};
if i1.sign == 1 && i2.sign == 1
{
i2.sign = -1;
let i3 = i1+i2;
return Self{digits:i3.digits, sign:i3.sign};
}
if i1.sign == 1 && i2.sign == -1
{
i2.sign = 1;
let i3 = i1+i2;
return Self{digits:i3.digits, sign:i3.sign};
}
if i1.sign == -1 && i2.sign == -1
{
i2.sign = 1;
let i3 = i1+i2;
return Self{digits:i3.digits, sign:i3.sign};
}
if i1.sign == -1 && i2.sign == 1
{
i2.sign = -1;
let i3 = i1+i2;
return Self{digits:i3.digits, sign:i3.sign};
}
else {
let e = Vec::new();
return Self{digits:e , sign:1};
}
}
}