Решение на Bigint от Лили Стефанова
Резултати
- 11 точки от тестове
- 0 бонус точки
- 11 точки общо
- 11 успешни тест(а)
- 4 неуспешни тест(а)
Код
use std::fmt::{self, Display, Formatter};
use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Add, Sub};
#[derive(Debug)]
pub struct ParseError
{
details : String,
}
impl ParseError {
fn new(msg: &str) -> ParseError {
ParseError{details: msg.to_string()}
}
}
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
pub sign: i8,
pub digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
}
}
fn from_components(mut digits: Vec<u8>, mut sign: i8) -> Self {
let index = digits.iter().position(|&x| x > 0);
match index
{
Some(i) => Self::remove_zeros(&mut digits, i),
None => {
digits = vec![0];
sign = 1
},
}
Bigint
{
sign : sign,
digits : digits,
}
}
fn remove_zeros(digits: &mut Vec<u8>, index: usize) -> ()
{
let mut i :usize = 0;
while i < index
{
digits.remove(0);
i+=1;
}
}
pub fn is_positive(&self) -> bool {
if !self.is_zero() && self.sign == 1 {true} else {false}
}
pub fn is_negative(&self) -> bool {
if !self.is_zero() && self.sign == -1 {true} else {false}
}
}
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let sign :i8;
let mut digits : Vec<u8>;
digits = Vec::new();
if s.is_empty()
{
sign = 1;
digits.push(0);
}
else
{
let mut elements = s.chars().enumerate();
let first = elements.next();
match first
{
Some((_,'+')) => sign = 1,
Some((_,'-')) => sign = -1,
Some((_,n)) if n.is_digit(10) => {
sign = 1;
if let Some(i) = n.to_digit(10) {digits.push(i as u8)
}},
_ => return Err(ParseError::new("Not a number!"))
}
for e in elements
{
match e
{
(_, n) if n.is_digit(10) => {
if let Some(i) = n.to_digit(10) {digits.push(i as u8)}
},
_ => return Err(ParseError::new("Not a number!"))
}
}
}
let new = Bigint::from_components(digits, sign);
Ok(new)
}
}
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 result : Ordering;
//if self.sign > other.sign {result = Ordering::Greater} else {result = Ordering::Less}
match (self.sign, other.sign)
{
(1, -1) => result = Ordering::Greater,
(-1, 1) => result = Ordering::Less,
(1, 1) => result = compare_vectors(&self.digits, &other.digits),
(-1, -1) => result = compare_vectors(&other.digits, &self.digits),
_ => unreachable!(),
}
return result;
}
}
fn compare_vectors(v1 : &Vec<u8>, v2 : &Vec<u8>) -> Ordering
{
let len1 = v1.len();
let len2 = v2.len();
if len1 > len2 {return Ordering::Greater;}
if len1 < len2 {return Ordering::Less;}
for (x, y) in v1.iter().zip(v2.iter()) {
if x > y {
return Ordering::Greater;
}
else if x < y {
return Ordering::Less;
}
}
return Ordering::Equal;
}
impl Add for Bigint {
type Output = Bigint;
fn add(mut self, mut other: Self) -> Self {
let result : Vec<u8>;
let sign : i8;
let sign_self = self.sign;
let sign_other = other.sign;
let greater : Bigint;
let less : Bigint;
self.sign = 1;
other.sign = 1;
if self.cmp(&other) == Ordering::Greater {greater = self; less = other}
else {greater = other; less = self};
let mut greater_digits = greater.digits;
greater_digits.reverse();
let mut less_digits = less.digits;
less_digits.reverse();
match (sign_self, sign_other)
{
(1, 1) => {
sign = 1;
result = add_digits(greater_digits, less_digits);
},
(-1, -1) => {
sign = -1;
println!("{:?} {:?}", &greater_digits, &less_digits);
result = add_digits(greater_digits, less_digits);
},
(1, -1) => {
sign = 1;
result = subtract_digits(greater_digits, less_digits);
},
(-1, 1) => {
sign = -1;
result = subtract_digits(greater_digits, less_digits);
},
_ => unreachable!()
}
let output = Bigint::from_components(result, sign);
output
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, mut other: Self) -> Self {
other.sign *=-1;
let output = self.add(other);
output
}
}
fn add_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut carry : u8 = 0;
let mut result : Vec<u8> = Vec::new();
let mut iter = larger.iter();
for (ldigit, sdigit) in larger.iter().zip(smaller.iter())
{
result.push((ldigit+sdigit)%10 + carry);
carry = (ldigit + sdigit)/10;
iter.next();
}
for ldigit in iter
{
result.push(ldigit%10 + carry);
carry = ldigit / 10;
}
if carry > 0 {result.push(carry);}
result.reverse();
result
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut carry :u8 = 0;
let mut result : Vec<u8> = Vec::new();
let mut iter = larger.iter();
for (ldigit, sdigit) in larger.iter().zip(smaller.iter())
{
if ldigit < sdigit || (ldigit == sdigit && carry == 1)
{
result.push(10 + ldigit - sdigit - carry);
carry = 1;
}
else
{
result.push(ldigit - sdigit - carry);
carry = 0;
}
iter.next();
}
for ldigit in iter
{
if ldigit >= &carry
{
result.push(ldigit - carry);
carry = 0;
}
else
{
result.push(10 + ldigit - carry);
carry = 1;
}
}
result.reverse();
result
}
impl Display for Bigint {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
match self.sign
{
1 => write!(f, "{:?}", self.digits),
-1 => write!(f, "-{:?}", self.digits),
_ => unreachable!()
}
}
}
trait IsZero {
fn is_zero(&self) ->bool;
}
impl IsZero for Bigint{
fn is_zero(&self) -> bool
{
let index = self.digits.iter().position(|&x| x > 0);
if index == None {true} else {false}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-mxey7a/solution)
Finished test [unoptimized + debuginfo] target(s) in 2.19s
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 ... FAILED
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 ... FAILED
test solution_test::test_sum_4_negative ... FAILED
failures:
---- solution_test::test_sub_1_basic stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [4, 4, 4] }`,
right: `Bigint { sign: -1, digits: [4, 4, 4] }`', tests/solution_test.rs:140:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [1, 4, 4, 4] }`,
right: `Bigint { sign: -1, digits: [1, 4, 4, 4] }`', tests/solution_test.rs:159:5
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [9, 10, 0] }`,
right: `Bigint { sign: 1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:97:5
---- solution_test::test_sum_4_negative stdout ----
[6, 5, 4] [3, 2, 1]
[0, 0, 0, 2, 1] [2, 1]
[3, 2, 1] [1]
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [4, 4, 4] }`,
right: `Bigint { sign: -1, digits: [4, 4, 4] }`', tests/solution_test.rs:116:5
failures:
solution_test::test_sub_1_basic
solution_test::test_sub_3_carry
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'