Решение на Bigint от Борис Ангелов
Резултати
- 11 точки от тестове
- 0 бонус точки
- 11 точки общо
- 11 успешни тест(а)
- 4 неуспешни тест(а)
Код
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
/// Конструира нов Bigint със стойност "0" и положителен знак.
/// Това може да означава празен вектор с цифри или масив с една цифра `0` -- ваш избор.
///
pub fn new() -> Self {
return Bigint {
sign: 0_i8,
digits: Vec::new()
};
}
/// Конструира нов Bigint с подадените цифри и знак.
///
/// Тук е добро място където можете да вкарате малко валидация и нормализиране на входа -- да
/// премахнете допълнителни нули или да се погрижите, че нулата винаги има консистентен знак.
/// Стига да се погрижите винаги да използвате функцията при конструириане на нови Bigint-ове.
///
/// Тази функция НЕ Е публична, така че НЕ Е задължителна -- ако не ви трябва, може смело да я
/// изтриете.
///
pub fn from_components(mut digits: Vec<u8>, mut sign: i8) -> Self {
while digits.len() > 0 && digits[0] == 0 {
digits.remove(0);
}
//println!("{} len {} sign", digits.len(), sign);
if digits.len() == 0 {
sign = 0_i8;
} else if sign == 0_i8 {
sign = 1_i8;
}
//println!("{:?}", digits);
return Bigint {
sign: sign,
digits: digits
}
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
return self.sign > 0;
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
return self.sign < 0;
}
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut digits: Vec<u8> = Vec::new();
let mut sign = 0_i8;
for (i, c) in s.chars().enumerate() {
match i {
0 => {
match c {
'-' => sign = -1_i8,
'+' => sign = 1_i8,
'0' => sign = 0_i8,
'1'..='9' => {
digits.push((c as u8) - ('0' as u8));
sign = 1_i8;
},
_ => return Err(ParseError)
}
},
_ => {
if !c.is_digit(10) {
return Err(ParseError);
} else {
digits.push((c as u8) - ('0' as u8));
}
}
}
}
return Ok(Bigint::from_components(digits, sign));
}
}
use std::cmp::Ordering;
impl PartialOrd for Bigint {
/// Две цели числа винаги могат да се сравнят, така че "частичното" равенство е същото като
/// пълното.
///
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
/// Ако едното от числата е положително, а другото -- отрицателно, положителното е по-голямо.
///
/// Ако едното от числата има по-голям брой цифри, то ще бъде по-голямото. (Стига да не са нули
/// -- вероятно е добра идея да се погрижите да няма започващи нули при конструкция.)
///
/// Ако двете числа имат еднакъв брой цифри, лексикографско сравнение на числата ще ви даде
/// правилен резултат -- от по-значимите цифри към по-малко значимите. Внимавайте в какъв ред
/// си държите цифритe и дали не трябва да ги обърнете.
///
/// Ако двете числа са отрицателни, сравнението по абсолютна стойност ще е обърнато (-1 е
/// по-голямо от -2) -- погледнете документацията на `Ordering` за това как лесно можете да
/// обърнете резултата.
///
fn cmp(&self, other: &Bigint) -> Ordering {
//println!("{:?}", self.digits);
//println!("{:?}", other.digits);
if self.sign > other.sign {
return Ordering::Greater;
} else if self.sign < other.sign {
return Ordering::Less;
} else {
let isPositive = self.sign > 0;
if self.digits.len() > other.digits.len() {
return if isPositive {Ordering::Greater} else {Ordering::Less};
} else if self.digits.len() < other.digits.len() {
return if isPositive {Ordering::Less} else {Ordering::Greater};
} else {
for (i, x) in self.digits.iter().enumerate() {
if x > &other.digits[i] {
return if isPositive {Ordering::Greater} else {Ordering::Less};
} else if x < &other.digits[i] {
return if isPositive {Ordering::Less} else {Ordering::Greater};
}
}
}
}
return Ordering::Equal;
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
/// За да съберете две числа, първия въпрос е: какви са им знаците?
///
/// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
/// знак.
/// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
/// отрицателен знак на крайния резултат.
/// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
/// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
/// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
/// положителна).
///
/// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
/// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
/// запълните с нули, да внимавате с индексите, или нещо по средата.
///
fn add(self, other: Self) -> Self {
let mut carry = 0_i8;
let mut digits: Vec<u8> = Vec::new();
let mut sign = self.sign;
let mut id: i32 = (self.digits.len() as i32) - 1;
let mut id1: i32 = (other.digits.len() as i32) - 1;
let mut i = if id > 0 {self.digits.len() - 1} else {0};
let mut other_i = if id1 > 0 {other.digits.len() - 1} else {0};
while id >= 0 {
if id1 < 0 {
sign = self.sign;
break;
}
let temp = self.sign * (self.digits[i] as i8) + other.sign * (other.digits[other_i] as i8) + carry;
let mut val : i8 = 0;
if temp < 0 {
if i == 0 {
if other_i == 0 {
sign = if temp < 0 {-1} else {1};
} else if other_i > 0 {
sign = other.sign;
}
} else if other_i > 0 {
val = val + (1 - (other.sign + self.sign) / 2) * 10;
}
val = val + (temp % 10);
carry = if val < 0 {temp / 10} else {-1};
val = val.abs();
} else {
val = temp % 10;
carry = temp / 10;
}
id = id - 1;
id1 = id1 - 1;
if id >= 0 {
i = i - 1;
}
if id1 >= 0 {
other_i = other_i - 1;
}
digits.push(val as u8);
}
while id >= 0 {
let n = self.sign * (self.digits[i] as i8);
sign = self.sign;
let temp = n + carry;
let val = temp % 10;
carry = temp / 10;
digits.push(val.abs() as u8);
id = id - 1;
if id >= 0 {
i = i - 1;
}
}
while id1 >= 0 {
let n = other.sign * (other.digits[other_i] as i8);
sign = other.sign;
let temp = (n as i8) + carry;
let val = temp % 10;
carry = temp / 10;
digits.push(val.abs() as u8);
id1 = id1 - 1;
if id1 >= 0 {
other_i = other_i - 1;
}
}
if carry != 0 {
digits.push(carry.abs() as u8);
}
digits.reverse();
return Bigint::from_components(digits, sign);
}
}
impl Sub for Bigint {
type Output = Bigint;
/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
/// събиране и по изваждане между `add` и `sub`.
///
/// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
/// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
/// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
///
/// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
///
fn sub(self, other: Self) -> Self {
let new_other = Bigint {
sign: -1 * other.sign,
digits: other.digits,
};
return self + new_other;
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-9mg75e/solution)
warning: variable `isPositive` should have a snake case name
--> src/lib.rs:129:17
|
129 | let isPositive = self.sign > 0;
| ^^^^^^^^^^ help: convert the identifier to snake case: `is_positive`
|
= note: `#[warn(non_snake_case)]` on by default
warning: 1 warning emitted
Finished test [unoptimized + debuginfo] target(s) in 1.61s
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: [5, 5, 6] }`,
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, 0, 0, 1] }`,
right: `Bigint { sign: 1, digits: [9, 9, 9] }`', tests/solution_test.rs:157:5
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: -1, digits: [1, 1, 19, 20] }`,
right: `Bigint { sign: -1, digits: [1, 1, 1, 0] }`', tests/solution_test.rs:101:5
---- solution_test::test_sum_4_negative stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: -1, digits: [6, 12, 11] }`,
right: `Bigint { sign: -1, digits: [5, 7, 9] }`', tests/solution_test.rs:112: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'