Решение на Bigint от Георги Катевски
Към профила на Георги Катевски
Резултати
- 14 точки от тестове
- 0 бонус точки
- 14 точки общо
- 14 успешни тест(а)
- 1 неуспешни тест(а)
Код
use std::str::FromStr;
//use std::num::ParseIntError;
use std::cmp::Ordering;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
/// Конструира нов Bigint със стойност "0" и положителен знак.
/// Това може да означава празен вектор с цифри или масив с една цифра `0` -- ваш избор.
///
pub fn new() -> Self {
let mut vec= Vec::with_capacity(1);
vec.push(0);
return Bigint{ sign:1, digits:vec};
}
/// Конструира нов Bigint с подадените цифри и знак.
///
/// Тук е добро място където можете да вкарате малко валидация и нормализиране на входа -- да
/// премахнете допълнителни нули или да се погрижите, че нулата винаги има консистентен знак.
/// Стига да се погрижите винаги да използвате функцията при конструириане на нови Bigint-ове.
///
/// Тази функция НЕ Е публична, така че НЕ Е задължителна -- ако не ви трябва, може смело да я
/// изтриете.
///
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
return Self{sign,digits};
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
if self.sign==-1
{
return false;
}else
{
return true;
}
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
if self.sign==-1
{
return true;
}else
{
return false;
}
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let num_string=s.to_string();
let mut vec= Vec::new();
let mut _sign=0;
let mut flag=false;
if num_string.len()==0
{
vec.push(0);
_sign=1;
}
if num_string.len() != 0 &&num_string.as_bytes()[0]as char =='-'
{
_sign=-1;
}
else{
_sign=1;
}
let mut count=true;
for c in num_string.chars() {
if c=='-' && count==true
{
count=false;
if flag==false{
continue;
}else
{
return Err(ParseError);
}
}
if c=='+' && count== true
{
count=false;
if flag==false{
continue;
}else
{
return Err(ParseError);
}
}
if flag==false && c== '0'
{
continue;
}
if c!='0' && !(c).is_digit(10) && flag==true
{
return Err(ParseError);
}
flag=true;
if c!='0' && !(c).is_digit(10) && flag==true
{
return Err(ParseError);
}
println!("{:?}:--",c as u8 - '0' as u8);
vec.push(c as u8 - '0' as u8);
}
if vec.len()==0
{
vec.push(0);
_sign=1;
}
Ok(Bigint{digits:vec,sign:_sign})
}
}
impl PartialOrd for Bigint {
/// Две цели числа винаги могат да се сравнят, така че "частичното" равенство е същото като
/// пълното.
///
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
#[allow(non_snake_case)]
impl Ord for Bigint {
/// Ако едното от числата има по-голям брой цифри, то ще бъде по-голямото. (Стига да не са нули
/// -- вероятно е добра идея да се погрижите да няма започващи нули при конструкция.)
///
/// Ако двете числа имат еднакъв брой цифри, лексикографско сравнение на числата ще ви даде
/// правилен резултат -- от по-значимите цифри към по-малко значимите. Внимавайте в какъв ред
/// си държите цифритe и дали не трябва да ги обърнете.
///
fn cmp(&self, other: &Bigint) -> Ordering {
let a=self.digits.len() ;
let _resultG = Ordering::Greater.then(Ordering::Greater);
let _resultL = Ordering::Less.then(Ordering::Less);
let _resultE = Ordering::Equal.then(Ordering::Equal);
if self.is_negative() && other.is_positive()
{
return _resultL;
} else if self.is_positive() && other.is_negative()
{
return _resultG;
} else {
if self.digits.len() > other.digits.len() && (self.is_positive() && other.is_positive())
{
return _resultG;
}
else if self.digits.len() < other.digits.len() && (self.is_positive() && other.is_positive())
{
return _resultL;
}
else if self.digits.len() < other.digits.len() && (self.is_negative() && other.is_negative())
{
return _resultG;
}
else if self.digits.len() > other.digits.len() && (self.is_negative() && other.is_negative())
{
return _resultL;
}
else
{
for i in 0..a {
if self.digits[i as usize] > other.digits[i as usize] && (self.is_positive() && other.is_positive())
{
return _resultG;
}
else if self.digits[i as usize] < other.digits[i as usize] && (self.is_positive() && other.is_positive())
{
return _resultL;
}
if self.digits[i as usize] > other.digits[i as usize] && (self.is_negative() && other.is_negative())
{
return _resultL;
}
else if self.digits[i as usize] < other.digits[i as usize] && (self.is_negative() && other.is_negative())
{
return _resultG;
}
}
return _resultE;
}
}
}
}
use::std::char;
use std::ops::Add;
impl Add for Bigint {
type Output = Bigint;
/// За да съберете две числа, първия въпрос е: какви са им знаците?
///
/// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
/// знак.
/// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
/// отрицателен знак на крайния резултат.
/// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
/// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
/// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
/// положителна).
///
/// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
/// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
/// запълните с нули, да внимавате с индексите, или нещо по средата.
///
fn add(self, other: Self) -> Self {
if self.is_positive() && other.is_negative()
{
if check(&self.digits,&other.digits)==Ordering::Greater.then(Ordering::Greater)
{
return Self{digits:subtract_digits(self.digits,other.digits),sign:1};
}else if check(&self.digits,&other.digits)==Ordering::Less.then(Ordering::Less)
{
return Self{digits:subtract_digits(other.digits,self.digits),sign:-1};
}
else
{
let mut vec=Vec::new();
vec.push(0);
return Self{digits:vec,sign:1};
}
}
else if self.is_negative() && other.is_positive()
{
if check(&self.digits,&other.digits)==Ordering::Greater.then(Ordering::Greater)
{
return Self{digits:subtract_digits(self.digits,other.digits),sign:-1};
}
else if check(&self.digits,&other.digits)==Ordering::Less.then(Ordering::Less)
{
return Self{digits:subtract_digits(other.digits,self.digits),sign:1};
}
else
{
let mut vec=Vec::new();
vec.push(0);
return Self{digits:vec,sign:1};
}
}
else if self.is_negative() && other.is_negative()
{
return Self{digits:add_digits(self.digits,other.digits),sign:-1};
}
else
{
return Self{digits:add_digits(self.digits,other.digits),sign:1};
}
}
}
use std::ops::Sub;
impl Sub for Bigint {
type Output = Bigint;
/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
/// събиране и по изваждане между `add` и `sub`.
///
/// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
/// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
/// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
///
/// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
///
fn sub(self, other: Self) -> Self {
if self.is_negative() && other.is_negative()
{
if check(&self.digits,&other.digits)==Ordering::Greater.then(Ordering::Greater)
{
return Self{digits:subtract_digits(self.digits, other.digits),sign:-1};
}
else if check(&self.digits,&other.digits)==Ordering::Less.then(Ordering::Less)
{
return Self{digits:subtract_digits(other.digits, self.digits),sign:1};
}
else
{
let mut vec=Vec::new();
vec.push(0);
return Self{digits:vec,sign:1};
}
}
else if self.is_positive() && other.is_positive()
{
if check(&self.digits,&other.digits)==Ordering::Greater.then(Ordering::Greater)
{
return Self{digits:subtract_digits(self.digits, other.digits),sign:1};
}
else if check(&self.digits,&other.digits)==Ordering::Less.then(Ordering::Less)
{
return Self{digits:subtract_digits(other.digits,self.digits),sign:-1};
}
else
{
let mut vec=Vec::new();
vec.push(0);
return Self{digits:vec,sign:1};
}
}
else if self.is_negative() && other.is_positive()
{
return Self{digits:add_digits(self.digits, other.digits),sign:-1};
}
else
{
return Self{digits:add_digits(self.digits, other.digits),sign:1};
}
}
}
/// Незадължително
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
//let mut flag=true;
let mut vec=Vec::new();
left.reverse();
right.reverse();
let mut count=0;
let mut k=-1;
let size;
if left.len()>=right.len()
{
size=right.len();
}
else
{
size=left.len();
}
while size!=count
{
let mut m=left[count as usize]+right[count as usize];
if k==1
{
m+=1;
}
if m<=9
{
vec.push(m);
k= -1;
}
else
{
vec.push(m-10);
k=1;
}
count+=1;
}
if right.len()>left.len()
{
while right.len()!=count
{
let mut m=right[count as usize];
if k==1
{
m+=1;
if m<=9
{
vec.push(m);
k=-1;
}
else
{
vec.push(m-10);
k=1;
}
}
else
{
vec.push(m);
}
count+=1;
}
}
if left.len()>right.len()
{
while(left.len())!=count
{
let mut m=left[count as usize];
if k==1
{
m+=1;
if m<=9
{
vec.push(m);
k=-1;
}
else
{
vec.push(m-10);
k=1;
}
}
else
{
vec.push(m);
}
count+=1;
}
}
if k==1
{
vec.push(1);
}
vec.reverse();
return vec;
}
/// Незадължително
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
larger.reverse();
smaller.reverse();
let mut vec=Vec::new();
let mut count=0;
let mut k=-1;
while smaller.len()!=count
{
let mut m:i8 ;
if k==1
{
m= larger[count as usize] as i8 -smaller[count as usize] as i8;
m-=1;
k=-1;
}
else
{
m= larger[count as usize] as i8 -smaller[count as usize] as i8;
}
if m >= 0
{
vec.push(m as u8);
}
else{
m+=10;
k=1;
vec.push(m as u8);
}
count+=1;
}
while larger.len()!=count
{
let mut m:i8;
m=larger[count as usize] as i8;
if k==1 && m==0
{
m=9;
vec.push(m as u8);
}
else if k==1 && m!=0
{
m-=1;
vec.push(m as u8);
k=-1;
}
else
{
vec.push(m as u8);
}
count+=1;
}
let mut i =vec.len()-1;
//remove zeros
while vec[i]==0 && i !=0
{
vec.remove(i);
i-=1;
}
vec.reverse();
return vec;
}
#[allow(non_snake_case)]
fn check( larger: &Vec<u8>, smaller: &Vec<u8>) -> Ordering
{
let _resultG = Ordering::Greater.then(Ordering::Greater);
let _resultL = Ordering::Less.then(Ordering::Less);
let _resultE = Ordering::Equal.then(Ordering::Equal);
if larger.len() > smaller.len()
{
return _resultG ;
}
else if larger.len() <smaller.len()
{
return _resultL;
}
else
{
for i in 0..larger.len() {
if larger[i as usize] > smaller[i as usize]
{
return _resultG;
}
else if larger[i as usize] < smaller[i as usize]
{
return _resultL;
}
}
return _resultE;
}
}
fn bigint(s: &str) -> Bigint {
Bigint::from_str(s).unwrap()
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-d67s8h/solution)
warning: associated function is never used: `from_components`
--> src/lib.rs:32:8
|
32 | fn from_components(digits: Vec<u8>, sign: i8) -> Self {
| ^^^^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: function is never used: `bigint`
--> src/lib.rs:598:4
|
598 | fn bigint(s: &str) -> Bigint {
| ^^^^^^
warning: 2 warnings emitted
Finished test [unoptimized + debuginfo] target(s) in 1.70s
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 ... FAILED
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
failures:
---- solution_test::test_bigint_zero_sign stdout ----
thread 'main' panicked at 'assertion failed: !zero.is_positive()', tests/solution_test.rs:21:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
failures:
solution_test::test_bigint_zero_sign
test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'