Решение на Bigint от Гергана Тончева

Обратно към всички решения

Към профила на Гергана Тончева

Код

#[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 {

if digits[0] == 0 && digits.len() > 1 {

let mut i = 0;

while digits[i] == 0 && i < digits.len() {

i += 1;

}

if sign != 1 && sign != -1 {

return Bigint {sign: 1, digits: digits[i..digits.len()].to_vec()};

}

return Bigint {sign: sign, digits: digits[i..digits.len()].to_vec()};

}

return Bigint {sign: sign, digits: digits}

}

/// Връща `true` ако числото е положително. Нулата не е положителна.

pub fn is_positive(&self) -> bool {

if self.sign == 1 && (self.digits[0] != 0) { // && self.digits.len() != 1

return true;

}

false

}

/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.

pub fn is_negative(&self) -> bool {

if self.sign == -1 && (self.digits[0] != 0) { //&& self.digits.len() != 1

return true;

}

false

}

}

use std::str::FromStr;

#[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 i = 0;

let mut sign = 1;

let mut vec = vec![];

let mut ch = s.chars().nth(i).unwrap();

if (ch < '0' || ch > '9') && ch != '-' && ch != '+' {

return Err(ParseError);

}

if ch == '-' {

sign = -1;

}

if ch >= '0' && ch <= '9' {

let num = (ch as u8) - 48;

vec.push(num);

}

i += 1;

while i < s.len() {

ch = s.chars().nth(i).unwrap();

if ch >= '0' && ch <= '9' {

let num = (ch as u8) - 48;

vec.push(num);

}

else {

return Err(ParseError);

}

i += 1;

}

let result = Bigint::from_components(vec, sign);

return Ok(result);

}

}

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 == 1 && other.sign == -1 {

return Ordering::Greater;

}

else if self.sign == -1 && other.sign == 1 {

return Ordering::Less;

}

else if self.digits.len() > other.digits.len() {

return Ordering::Greater;

}

else if self.digits.len() < other.digits.len() {

return Ordering::Less;

}

else if self.sign == 1 && other.sign == 1 {

return self.digits.cmp(&other.digits);

}

else {

return self.digits.cmp(&other.digits).reverse();

}

}

}

use std::ops::{Add, Sub};

impl Add for Bigint {

type Output = Bigint;

// / За да съберете две числа, първия въпрос е: какви са им знаците?

// /

// / - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен

// / знак.

// / - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим

// / отрицателен знак на крайния резултат.

// / - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите

// / на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна

// / стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е

// / положителна).

// /

// / При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е

// / по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да

// / запълните с нули, да внимавате с индексите, или нещо по средата.

// /

fn add(self, other: Self) -> Self {

let mut holder = 0;

let mut result = vec![];

let sign: i8;

if self.digits.len() == 0 {

return other;

}

if other.digits.len() == 0 {

return self;

}

if self.sign == other.sign {

let mut i_self = self.digits.len() - 1;

let mut i_other = other.digits.len() - 1;

let mut count: usize;

if i_self > i_other {

count = i_other + 1;

} else {

count = i_self + 1;

}

while count != 0 {

let k = (self.digits[i_self] + other.digits[i_other] + holder) % 10;

holder = (self.digits[i_self] + other.digits[i_other] + holder) / 10;

println!("YES");

result.push(k);

count -= 1;

if i_self != 0 {

i_self -= 1;

}

if i_other != 0 {

i_other -= 1;

}

}

if self.digits.len() < other.digits.len(){

// if i_other >= 0 && self.digits.len() < other.digits.len(){

while i_other > 0{

println!("{}", holder);

let k = (other.digits[i_other] + holder) % 10;

holder = (other.digits[i_other] + holder) / 10;

println!("{}", holder);

result.push(k);

if i_other != 0 {

i_other -= 1;

}

}

let k = (other.digits[i_other] + holder) % 10;

holder = (other.digits[i_other] + holder) / 10;

result.push(k);

}

if self.digits.len() > other.digits.len() {

// if i_self >= 0 && self.digits.len() > other.digits.len() {

println!("{}", holder);

while i_self > 0 {

let k = (self.digits[i_self] + holder) % 10;

holder = (self.digits[i_self] + holder) / 10;

result.push(k);

if i_self != 0 {

i_self -= 1;

}

}

let k = (self.digits[i_self] + holder) % 10;

holder = (self.digits[i_self] + holder) / 10;

result.push(k);

}

// if holder != 0 {

// result.push(holder);

// }

sign = self.sign;

}

else {

let mut i_self = self.digits.len() - 1;

let mut i_other = other.digits.len() - 1;

let self_vec = &self.digits;

let other_vec = &other.digits;

let first = Bigint{

sign: 1,

digits: self_vec.to_vec(),

};

let second = Bigint{

sign: 1,

digits: other_vec.to_vec(),

};

let mut count: usize;

let comp = first.cmp(&second);

if comp == Ordering::Greater {

count = other.digits.len();

while count != 0 {

let k: u8;

if (self.digits[i_self] - holder) < other.digits[i_other] {

k = self.digits[i_self] + 10 - other.digits[i_other] - holder;

holder = 1;

}

else {

k = self.digits[i_self] - other.digits[i_other] - holder;

holder = 0;

}

result.push(k);

count -= 1;

if i_self != 0 {

i_self -= 1;

}

if i_other != 0 {

i_other -= 1;

}

}

while i_self > 0 {

let k = self.digits[i_self] - holder;

holder = 0;

result.push(k);

if i_self != 0 {

i_self -= 1;

}

}

sign = self.sign;

}

else if comp == Ordering::Equal {

sign = 1;

result = vec![0];

}

else {

count = self.digits.len();

while count != 0 {

let k: u8;

if (other.digits[i_other] - holder) < self.digits[i_self] {

k = other.digits[i_other] + 10 - self.digits[i_self] - holder;

holder = 1;

}

else {

k = other.digits[i_other] - self.digits[i_self] - holder;

holder = 0;

}

result.push(k);

count -= 1;

if i_self != 0 {

i_self -= 1;

}

if i_other != 0 {

i_other -= 1;

}

}

while i_other > 0 {

let k = other.digits[i_other] - holder;

holder = 0;

result.push(k);

if i_other != 0 {

i_other -= 1;

}

}

sign = other.sign;

}

}

if holder != 0 {

result.push(holder);

}

result.reverse();

return Bigint::from_components(result, sign);

}

}

impl Sub for Bigint {

type Output = Bigint;

/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е

/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и

/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по

/// събиране и по изваждане между `add` и `sub`.

///

/// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,

/// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от

/// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.

///

/// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.

///

fn sub(self, other: Self) -> Self {

let other_vec = &other.digits;

let sign = &other.sign * (-1);

let second = Bigint{

sign: sign,

digits: other_vec.to_vec(),

};

let result = Bigint::add(self, second);

return result;

}

}

// fn main() {

// println!("Hello, world!");

// let k = Bigint{

// sign: -1,

// digits: vec![2, 0],

// };

// let l = Bigint{

// sign: 1,

// digits: vec![2, 0, 0],

// };

//

// let m = Bigint::from_str("1").unwrap();

//

// println!("{:?}", m);

// println!("{:?}", Bigint::sub(k, l));

//

// }

Лог от изпълнението

Compiling solution v0.1.0 (/tmp/d20201127-2274206-130ueu5/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.74s
     Running target/debug/deps/solution_test-589a43f0f4b10ca3

running 15 tests
test solution_test::test_bigint_construction ... FAILED
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 ... FAILED
test solution_test::test_sub_1_basic ... ok
test solution_test::test_sub_2_diferent_lengths ... FAILED
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 ... ok
test solution_test::test_sum_4_negative ... ok

failures:

---- solution_test::test_bigint_construction stdout ----
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/lib.rs:94:39
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- solution_test::test_comparison stdout ----
thread 'main' panicked at 'assertion failed: bigint("-1") > bigint("-10")', tests/solution_test.rs:172:5

---- solution_test::test_parsing_with_leading_zeroes stdout ----
thread 'main' panicked at 'index out of bounds: the len is 4 but the index is 4', src/lib.rs:29:19

---- solution_test::test_sub_2_diferent_lengths stdout ----
thread 'main' panicked at 'index out of bounds: the len is 3 but the index is 3', src/lib.rs:29:19

---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:326:30


failures:
    solution_test::test_bigint_construction
    solution_test::test_comparison
    solution_test::test_parsing_with_leading_zeroes
    solution_test::test_sub_2_diferent_lengths
    solution_test::test_sub_3_carry

test result: FAILED. 10 passed; 5 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '--test solution_test'

История (1 версия и 0 коментара)