Решение на Bigint от Юмит Яйя
Резултати
- 9 точки от тестове
- 0 бонус точки
- 9 точки общо
- 9 успешни тест(а)
- 6 неуспешни тест(а)
Код
use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Sub, Add};
// fn main() {
// let test = Bigint::new();
// println!("{}",test.is_positive());
// println!("{}",test.is_negative());
//
// let test2 = Bigint::from_components(vec![2,4],-1);
// println!("{}",test2.is_positive());
// println!("{}",test2.is_negative());
//
// println!("");
// let test3 = Bigint::from_str("-0").unwrap();
// println!("{}",test3.is_positive());
// println!("{}",test3.is_negative());
// }
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0]
}
}
/// Конструира нов Bigint с подадените цифри и знак.
///
/// Тук е добро място където можете да вкарате малко валидация и нормализиране на входа -- да
/// премахнете допълнителни нули или да се погрижите, че нулата винаги има консистентен знак.
/// Стига да се погрижите винаги да използвате функцията при конструириане на нови Bigint-ове.
///
/// Тази функция НЕ Е публична, така че НЕ Е задължителна -- ако не ви трябва, може смело да я
/// изтриете.
///
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
Bigint {
sign,
digits
}
}
pub fn is_positive(&self) -> bool {
if (self.sign == 1)
&& (self.digits.len() > 1
|| self.digits[0] != 0) {
return true;
}
return false;
}
pub fn is_negative(&self) -> bool {
if self.sign == -1 {
return true;
}
return false;
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
//check for empty
if s.len() == 0 {
return Ok(Bigint::new());
}
//If input is only sign
if s.len() == 1
&& (((s.chars().nth(0).unwrap() as u32) < 48)
|| ((s.chars().nth(0).unwrap() as u32) > 58)) {
return Err(ParseError{});
}
//check if all chars but first are not valid
for ch in s.chars().skip(1) {
if ((ch as u32) < 48) || ((ch as u32) > 58) {
return Err(ParseError{});
}
}
let sign:i8;
let digits:Vec<u8>;
if s.chars().nth(0) == Some('-') {
sign = -1;
digits = vec_form_str(
s.chars()
.skip(1)
.take(s.len() - 1)
.collect::<String>()
);
} else {
sign = 1;
if s.chars().nth(0) == Some('+') {
digits = vec_form_str(
s.chars()
.skip(1)
.take(s.len() - 1)
.collect()
);
} else if ((s.chars().nth(0).unwrap() as u32) >= 48) && ((s.chars().nth(0).unwrap() as u32) <= 58){
digits = vec_form_str(String::from(s));
} else {
//first char is invalid
return Err(ParseError{});
}
}
//if input is 0
if digits.len() == 0 {
return Ok(Bigint::new());
}
return Ok(
Bigint {
sign,
digits
}
);
}
}
fn vec_form_str(s: String) -> Vec<u8>{
let mut vec:Vec<u8> = Vec::new();
let mut no_leading_zeros = false;
for ch in s.chars() {
if ch == '0' && !no_leading_zeros {
continue;
} else if !no_leading_zeros {
no_leading_zeros = true;
}
vec.push((ch as u32 - 48) as u8);
}
return vec;
}
impl PartialOrd for Bigint {
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
/// Ако едното от числата има по-голям брой цифри, то ще бъде по-голямото. (Стига да не са нули
/// -- вероятно е добра идея да се погрижите да няма започващи нули при конструкция.)
///
/// Ако двете числа имат еднакъв брой цифри, лексикографско сравнение на числата ще ви даде
/// правилен резултат -- от по-значимите цифри към по-малко значимите. Внимавайте в какъв ред
/// си държите цифритe и дали не трябва да ги обърнете.
///
fn cmp(&self, other: &Bigint) -> Ordering {
//if signs are different
if self.sign != other.sign {
if self.sign > 0 {
return Ordering::Greater;
} else {
return Ordering::Less;
}
}
if self.digits.len() > other.digits.len() {
if self.sign < 0 {
return Ordering::Less;
} else {
return Ordering::Greater;
}
} else if self.digits.len() < other.digits.len() {
if self.sign < 0 {
return Ordering::Greater;
} else {
return Ordering::Less;
}
// return Ordering::Less;
} else {
let mut i = 0;
let mut k = 0;
loop {
if self.digits[i] > other.digits[k] {
if self.sign < 0 {
return Ordering::Less;
} else {
return Ordering::Greater;
}
// return Ordering::Greater;
} else if self.digits[i] < other.digits[k] {
if self.sign < 0 {
return Ordering::Greater;
} else {
return Ordering::Less;
}
// return Ordering::Less;
}
if i == self.digits.len()
|| k == other.digits.len() {
return Ordering::Equal;
}
i += 1;
k += 1;
}
}
return Ordering::Equal;
}
}
impl Add for Bigint {
type Output = Bigint;
/// За да съберете две числа, първия въпрос е: какви са им знаците?
///
/// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
/// знак.
/// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
/// отрицателен знак на крайния резултат.
/// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
/// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
/// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
/// положителна).
///
/// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
/// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
/// запълните с нули, да внимавате с индексите, или нещо по средата.
///
fn add(self, other: Self) -> Self {
let mut new_digits: Vec<u8> = Vec::new();
let mut new_sign: i8 = 1;
let mut new_digit:u8 = 0;
let mut carry = 0;
if self.sign == other.sign {
new_sign = self.sign;
let mut i = self.digits.len() - 1;
let mut k = other.digits.len() - 1;
loop{
new_digit = self.digits[i] + other.digits[k];
new_digits.insert(0, ((new_digit) % 10) + carry);
carry = new_digit / 10;
// if i >= 0 && k >=0 {
// new_digit = self.digits[i] + other.digits[k];
// new_digits.insert(0, ((new_digit) % 10) + carry);
// carry = new_digit / 10;
// } else if i >= 0{
// new_digits.insert(0, self.digits[i]);
// } else {
// new_digits.insert(0, self.digits[k]);
// }
if i == 0 || k == 0 {
break;
}
i -= 1;
k -= 1;
}
if i > 0 {
i -= 1;
loop{
new_digits.insert(0, self.digits[i]);
if i == 0 {
break;
}
i -= 1;
}
}
if k > 0 {
k -= 1;
loop{
new_digits.insert(0, self.digits[k]);
if k == 0 {
break;
}
k -= 1;
}
}
} else {
// if self.cmp(&other) == Ordering::Greater {
// new_sign = self.sign;
// } else {
// println!("Less");
// new_sign = other.sign;
// }
if lexically_bigger(&self.digits, &other.digits) == Ordering::Greater {
new_sign = self.sign;
} else {
// println!("Less");
new_sign = other.sign;
}
let mut i = self.digits.len() - 1;
let mut k = other.digits.len() - 1;
loop{
if lexically_bigger(&self.digits, &other.digits) == Ordering::Greater {
new_digit = 0;
if (self.digits[i] - carry) < other.digits[k] {
new_digit += 10;
new_digit = new_digit + self.digits[i] - carry - other.digits[k];
carry = 1
} else {
new_digit = new_digit + self.digits[i] - carry - other.digits[k];
carry = 0;
}
} else {
new_digit = 0;
if (other.digits[k] - carry) < self.digits[i] {
new_digit += 10;
new_digit = new_digit + other.digits[k] - carry - self.digits[i];
carry = 1
} else {
new_digit = new_digit + other.digits[k] - carry - self.digits[i];
carry = 0;
}
}
new_digits.insert(0, new_digit);
// if i >= 0 && k >=0 {
//
// } else if i >= 0{
// new_digits.insert(0, self.digits[i] - carry);
// carry = 0;
// } else {
// new_digits.insert(0, self.digits[k] - carry);
// carry = 0;
// }
if i == 0 || k == 0 {
break;
}
i -= 1;
k -= 1;
}
if i > 0 {
i -= 1;
loop{
new_digits.insert(0, self.digits[i] - carry);
carry = 0;
if i == 0 {
break;
}
i -= 1;
}
}
if k > 0 {
k -= 1;
loop{
new_digits.insert(0, other.digits[k] - carry);
carry = 0;
if k == 0 {
break;
}
k -= 1;
}
}
let mut new_digits_2: Vec<u8> = vec![];
let mut starting_null = true;
for num in new_digits {
if num == 0 && starting_null {
continue
} else if starting_null {
starting_null = false;
}
new_digits_2.push(num);
}
new_digits = new_digits_2;
}
if new_digits.len() == 0 {
new_digits.push(0);
}
return Bigint {
sign: new_sign,
digits: new_digits
};
}
}
fn lexically_bigger(a: &Vec<u8>, b: &Vec<u8>) -> Ordering {
if a.len() > b.len() {
return Ordering::Greater;
}
if a.len() < b.len() {
return Ordering::Less;
}
let mut i = 0;
let mut k = 0;
loop {
if i == a.len()
&& k == b.len() {
return Ordering::Equal;
}
if i == a.len() {
return Ordering::Less;
}
if k == b.len() {
return Ordering::Greater;
}
if a[i] > b[k] {
return Ordering::Greater;
} else if a[i] < b[k] {
return Ordering::Less;
}
i += 1;
k += 1;
}
}
impl Sub for Bigint {
type Output = Bigint;
/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
/// събиране и по изваждане между `add` и `sub`.
///
/// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
/// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
/// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
///
/// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
///
fn sub(self, other: Self) -> Self {
if other.digits.len() == 1 && other.digits[0] == 0 {
return self.add(Bigint{
sign: other.sign,
digits: other.digits
});
} else {
return self.add(Bigint{
sign: other.sign * -1,
digits: other.digits
});
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-1aoizoo/solution)
warning: unreachable statement
--> src/lib.rs:218:13
|
176 | return Ordering::Less;
| --------------------- any code following this expression is unreachable
...
218 | return Ordering::Equal;
| ^^^^^^^^^^^^^^^^^^^^^^^ unreachable statement
|
= note: `#[warn(unreachable_code)]` on by default
warning: value assigned to `new_sign` is never read
--> src/lib.rs:242:17
|
242 | let mut new_sign: i8 = 1;
| ^^^^^^^^^^^^
|
= note: `#[warn(unused_assignments)]` on by default
= help: maybe it is overwritten before being read?
warning: value assigned to `new_digit` is never read
--> src/lib.rs:243:17
|
243 | let mut new_digit:u8 = 0;
| ^^^^^^^^^^^^^
|
= help: maybe it is overwritten before being read?
warning: associated function is never used: `from_components`
--> src/lib.rs:44:12
|
44 | fn from_components(digits: Vec<u8>, sign: i8) -> Self {
| ^^^^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: 4 warnings emitted
Finished test [unoptimized + debuginfo] target(s) in 1.78s
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 ... FAILED
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 ... FAILED
test solution_test::test_sum_1_basic ... ok
test solution_test::test_sum_2_different_lengths ... FAILED
test solution_test::test_sum_3_overflow ... FAILED
test solution_test::test_sum_4_negative ... FAILED
failures:
---- solution_test::test_comparison stdout ----
thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 3', src/lib.rs:192:24
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] }`,
right: `Bigint { sign: 1, digits: [0] }`', tests/solution_test.rs:127:5
---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:355:46
---- solution_test::test_sum_2_different_lengths stdout ----
thread 'main' panicked at 'index out of bounds: the len is 2 but the index is 2', src/lib.rs:283:46
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [9, 9, 0] }`,
right: `Bigint { sign: 1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:97:5
---- 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:283:46
failures:
solution_test::test_comparison
solution_test::test_neutralization
solution_test::test_sub_3_carry
solution_test::test_sum_2_different_lengths
solution_test::test_sum_3_overflow
solution_test::test_sum_4_negative
test result: FAILED. 9 passed; 6 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'