Решение на Bigint от Лъчезар Младенов
Към профила на Лъчезар Младенов
Резултати
- 14 точки от тестове
- 0 бонус точки
- 14 точки общо
- 14 успешни тест(а)
- 1 неуспешни тест(а)
Код
#[cfg(test)]
mod tests {
#[test]
fn it_works() {
assert_eq!(2 + 2, 4);
}
}
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
/// Конструира нов Bigint със стойност "0" и положителен знак.
/// Това може да означава празен вектор с цифри или масив с една цифра `0` -- ваш избор.
///
pub fn new() -> Self {
Self { sign: 1, digits: vec![0] }
}
/// Конструира нов Bigint с подадените цифри и знак.
///
/// Тук е добро място където можете да вкарате малко валидация и нормализиране на входа -- да
/// премахнете допълнителни нули или да се погрижите, че нулата винаги има консистентен знак.
/// Стига да се погрижите винаги да използвате функцията при конструириане на нови Bigint-ове.
///
/// Тази функция НЕ Е публична, така че НЕ Е задължителна -- ако не ви трябва, може смело да я
/// изтриете.
///
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut m_digits: Vec<u8> = digits;
while m_digits[0] == 0 && m_digits.len() > 1 {
m_digits.remove(0);
}
if m_digits[0] == 0 {
return Self { sign: 1, digits: m_digits }
}
Self { sign: sign, digits: m_digits }
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
if self.digits.len() == 1 && self.digits[0] == 0 {
return false;
}
self.sign == 1
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
if self.digits.len() == 1 && self.digits[0] == 0 {
return false
}
self.sign == -1
}
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
/// Очакваме низа да е във формат десетично цяло число с опционален знак, тоест всички тези
/// неща би трябвало да върнат `Ok` резултат с конструиран Bigint:
/// use std::str::FromStr;
/// 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 sign: i8 = 1;
let mut digits: Vec<u8> = Vec::new();
for (i, c) in s.chars().enumerate() {
if i == 0 {
if c == '-' {
sign = -1;
} else if c >= '0' && c <= '9' {
digits.push(c as u8 - 48);
sign = 1;
} else if c == '+' {
sign = 1;
} else {
return Err(ParseError)
}
} else {
if c >= '0' && c <= '9' {
digits.push(c as u8 - 48);
} else {
return Err(ParseError)
}
}
}
if digits.len() == 0 {
digits.push(0);
}
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 {
/// Ако едното от числата е положително, а другото -- отрицателно, положителното е по-голямо.
///
/// Ако и двете числа са положителни, това с повече цифри е по-голямо. Ако имат еднакъв брой
/// цифри, лексикографско сравнение на цифрите от по-значима към по-малко значима цифра ще ви
/// върне по-голямото число. (Внимавайте с нулата -- тя има 1 цифра)
///
/// Ако и двете числа са отрицателни, горната логика е същата, просто сравнението е обърнато
/// (-1 е по-голямо от -2 и от -10).
///
fn cmp(&self, other: &Bigint) -> Ordering {
if self.sign > other.sign {
return Ordering::Greater
} else if self.sign < other.sign {
return Ordering::Less
}
let self_size = self.digits.len();
let other_size = other.digits.len();
if self.sign == 1 {
if self_size > other_size {
return Ordering::Greater
} else if self_size < other_size {
return Ordering::Less
}
} else {
if self_size > other_size {
return Ordering::Less
} else if self_size < other_size {
return Ordering::Greater
}
}
for i in 0..self_size {
if self.digits[i] > other.digits[i] {
return Ordering::Greater
} else if self.digits[i] < other.digits[i] {
return Ordering::Less
}
}
Ordering::Equal
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
/// За да съберете две числа, първия въпрос е: какви са им знаците?
///
/// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
/// знак.
/// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
/// отрицателен знак на крайния резултат.
/// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
/// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
/// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
/// положителна).
///
/// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
/// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
/// запълните с нули, да внимавате с индексите, или нещо по средата.
///
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
return Self { sign: self.sign, digits: add_digits(self.digits, other.digits) }
}
if larger(&self.digits, &other.digits) {
let mut bigint = Self { sign: self.sign, digits: subtract_digits(self.digits, other.digits) };
if bigint.digits.len() == 1 && bigint.digits[0] == 0 {
bigint.sign = 1;
}
return bigint
}
Self { sign: other.sign, digits: subtract_digits(other.digits, self.digits) }
}
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
let mut left_it = left.iter().rev();
let mut right_it = right.iter().rev();
let mut result: Vec<u8> = vec![];
let mut temp = 0;
loop {
match (left_it.next(), right_it.next()) {
(Some(x), Some(y)) => {
result.push((x + y + temp) % 10);
temp = (x + y + temp) / 10
},
(None, Some(y)) => {
result.push((y + temp) % 10);
temp = (y + temp) / 10
},
(Some(x), None) => {
result.push((x + temp) % 10);
temp = (x + temp) / 10
},
(None, None) => break,
}
}
if temp > 0 {
result.push(temp);
}
result.reverse();
result
}
impl Sub for Bigint {
type Output = Bigint;
/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
/// събиране и по изваждане между `add` и `sub`.
///
/// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
/// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
/// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
///
/// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
///
fn sub(self, other: Self) -> Self {
if self.sign == other.sign * -1 {
return Self { sign: self.sign, digits: add_digits(self.digits, other.digits) }
}
if larger(&self.digits, &other.digits) {
let mut bigint = Self { sign: self.sign, digits: subtract_digits(self.digits, other.digits) };
if bigint.digits.len() == 1 && bigint.digits[0] == 0 {
bigint.sign = 1;
}
return bigint
}
Self { sign: other.sign * -1, digits: subtract_digits(other.digits, self.digits) }
}
}
fn larger(left: &Vec<u8>, right: &Vec<u8>) -> bool {
if left.len() > right.len() {
return true
}
if left.len() < right.len() {
return false
}
for i in 0..left.len() {
if left[i] > right[i] {
return true
}
if left[i] < right[i] {
return false
}
}
true
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut l_it = larger.iter().rev();
let mut r_it = smaller.iter().rev();
let mut result: Vec<u8> = vec![];
let mut carry: i8 = 0;
loop {
match (l_it.next(), r_it.next()) {
(Some(x), Some(y)) => {
let mut val: i8 = *x as i8;
let y1: i8 = *y as i8;
if carry == 1 {
if val == 0 {
val = 9;
carry = 1;
} else {
val = val - 1;
carry = 0;
}
}
if val < y1 {
result.push((10 + val - y1) as u8);
carry = 1
} else {
result.push((val - y1) as u8);
}
},
(Some(x), None) => {
let mut val: i8 = *x as i8;
if carry == 1 {
if val > 0 {
val -= 1;
carry = 0;
} else {
val = 9;
carry = 1;
}
}
result.push(val as u8)
},
_ => break,
}
}
let mut l = result.len() - 1;
while l > 0 {
if result[l] != 0 {
break;
}
l -= 1;
}
result = result.into_iter().rev().skip_while(|&x| x == 0).collect();
if result.len() == 0 {
result.push(0);
}
result
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-1yc0fi5/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.79s
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 ... 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_comparison stdout ----
thread 'main' panicked at 'assertion failed: bigint("-1") > bigint("-2")', tests/solution_test.rs:171:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
failures:
solution_test::test_comparison
test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'