Решение на Bigint от Християна Панайотова
Към профила на Християна Панайотова
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
use std::cmp::Ordering;
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
/// Конструира нов Bigint със стойност "0" и положителен знак.
/// Това може да означава празен вектор с цифри или масив с една цифра `0` -- ваш избор.
///
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
}
}
/// Конструира нов Bigint с подадените цифри и знак.
///
/// Тук е добро място където можете да вкарате малко валидация и нормализиране на входа -- да
/// премахнете допълнителни нули или да се погрижите, че нулата винаги има консистентен знак.
/// Стига да се погрижите винаги да използвате функцията при конструириане на нови Bigint-ове.
///
/// Тази функция НЕ Е публична, така че НЕ Е задължителна -- ако не ви трябва, може смело да я
/// изтриете.
///
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut start_zero = 0;
for num in &digits {
if *num == 0 {
start_zero = start_zero + 1;
} else {
break;
}
}
let mut vec = digits.clone();
let mut new_sign = sign;
vec.drain(0..start_zero);
if vec.len() == 0 {
vec = vec![0];
new_sign = 1;
}
for name in vec.iter() {
println!("{}", name);
}
Bigint {
sign: new_sign,
digits: vec,
}
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
return self.sign == 1 && (self.digits.len() > 1 || self.digits[0] != 0);
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
return self.sign == -1 && (self.digits.len() > 1 || self.digits[0] != 0);
}
/// Връща `true` ако числото е нула.
pub fn is_zero(&self) -> bool {
return !self.is_negative() && !self.is_positive();
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
/// Очакваме низа да е във формат десетично цяло число с опционален знак, тоест всички тези
/// неща би трябвало да върнат `Ok` резултат с конструиран Bigint:
///
/// Bigint::from_str("123") // => положителен знак по подразбиране
/// Bigint::from_str("+123")
/// Bigint::from_str("-123")
///
/// Това включва нулата, като имате предвид че, както казахме, +0 и -0 трябва да са
/// еквивалентни.
///
/// Ако подадения низ е празен, това връща същото като да сме подали "0".
///
/// Ако подадения низ започва с нули, това няма значение -- игнорират се. Тоест, конструиране с
/// "00123" ще е същото като конструиране с "123".
///
/// Ако сме подали низ, който включва каквито и да е други символи освен цифрите 0-9 (и
/// опционален начален знак), очакваме да върнете `ParseError`.
///
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut vec: std::vec::Vec<u8> = vec![];
let mut sign = 1;
for (i, c) in s.chars().enumerate() {
if i == 0 && c == '-' {
sign = -1
} else if i == 0 && c == '+' {
continue;
} else {
let number = match c.to_digit(10) {
Some(v) => v,
None => return Err(ParseError {}),
};
vec.push(number as u8);
}
}
for name in vec.iter() {
println!("{}", name);
}
Ok(Bigint::from_components(vec, sign))
}
}
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 {
if self.is_negative() && (other.is_positive() || other.is_zero()) {
std::cmp::Ordering::Less
} else if self.is_positive() && (other.is_negative() || other.is_zero()) {
std::cmp::Ordering::Greater
} else if other.is_zero() && self.is_zero() {
std::cmp::Ordering::Equal
} else if self.digits.len() > other.digits.len() && self.is_positive() {
std::cmp::Ordering::Greater
} else if self.digits.len() > other.digits.len() && self.is_negative() {
std::cmp::Ordering::Less
} else if self.digits.len() == other.digits.len() && !self.is_zero() {
let is_positive = self.is_positive();
let mut result = std::cmp::Ordering::Greater;
for (pos, element) in self.digits.iter().enumerate() {
if *element > other.digits[pos] && is_positive {
result = std::cmp::Ordering::Greater;
break;
} else if *element < other.digits[pos] && is_positive {
result = std::cmp::Ordering::Less;
break;
} else if *element < other.digits[pos] && !is_positive {
result = std::cmp::Ordering::Greater;
break;
} else if *element > other.digits[pos] && !is_positive {
result = std::cmp::Ordering::Less;
break;
} else if pos == (self.digits.len() - 1) {
result = std::cmp::Ordering::Equal;
break;
}
}
result
} else {
other.cmp(self).reverse()
}
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
left.reverse();
right.reverse();
let len = if left.len() > right.len() {
left.len()
} else {
right.len()
};
let mut vec: Vec<u8> = vec![];
let mut to_add = 0;
for i in 0..len {
let left_value = if left.len() > i { left[i] } else { 0 };
let right_value = if right.len() > i { right[i] } else { 0 };
let mut value = left_value + right_value + to_add;
to_add = if value >= 10 { 1 } else { 0 };
value = value % 10;
vec.push(value);
}
if to_add > 0 {
vec.push(to_add)
}
vec.reverse();
vec
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
larger.reverse();
smaller.reverse();
let len = larger.len();
let mut vec: Vec<u8> = vec![];
for i in 0..len {
let larger_value = if larger.len() > i { larger[i] } else { 0 };
let smaller_value = if smaller.len() > i { smaller[i] } else { 0 };
let mut value = 0;
if larger_value < smaller_value {
for j in (i + 1)..len {
if larger[j] > 0 {
larger[j] = larger[j] - 1;
value = (larger_value + 10) - smaller_value;
break;
} else {
larger[j] = 9;
}
}
} else {
value = larger_value - smaller_value;
}
vec.push(value);
}
vec.reverse();
vec
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
/// За да съберете две числа, първия въпрос е: какви са им знаците?
///
/// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
/// знак.
/// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
/// отрицателен знак на крайния резултат.
/// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
/// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
/// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
/// положителна).
///
/// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
/// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
/// запълните с нули, да внимавате с индексите, или нещо по средата.
///
fn add(self, other: Self) -> Self {
if self.is_zero() {
other
} else if other.is_zero() {
self
} else if other.is_positive() && self.is_positive() {
let digits = add_digits(other.digits, self.digits);
Bigint::from_components(digits, 1)
} else if other.is_negative() && self.is_negative() {
let digits = add_digits(other.digits, self.digits);
Bigint::from_components(digits, -1)
} else {
if self.is_negative() {
other - Bigint::from_components(self.digits, 1)
} else {
self - Bigint::from_components(other.digits, 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.is_zero() {
self
} else if self.is_zero() {
let sign = if other.is_positive() { -1 } else { 1 };
Bigint::from_components(other.digits, sign)
} else if other.is_positive() && self.is_positive() {
if other > self {
let digits = subtract_digits(other.digits, self.digits);
Bigint::from_components(digits, -1)
} else {
let digits = subtract_digits(self.digits, other.digits);
Bigint::from_components(digits, 1)
}
} else if other.is_negative() && self.is_negative() {
if other > self {
let digits = subtract_digits(self.digits, other.digits);
Bigint::from_components(digits, -1)
} else {
let digits = subtract_digits(other.digits, self.digits);
Bigint::from_components(digits, 1)
}
} else {
let sign = if other.is_positive() { -1 } else { 1 };
self + Bigint::from_components(other.digits, sign)
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-18xpeqp/solution)
Finished test [unoptimized + debuginfo] target(s) in 2.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 ... 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
test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out