Решение на Bigint от Костадин Пеков
Резултати
- 8 точки от тестове
- 0 бонус точки
- 8 точки общо
- 8 успешни тест(а)
- 7 неуспешни тест(а)
Код
use std::num;
#[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 {
// len()
//}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
if self.digits.len() == 1 && self.digits[0] == 0
{
return false;
}
return self.sign==1;
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
if self.digits.len() == 1 && self.digits[0] == 0
{
return false;
}
return self.sign==-1;
}
pub fn print(&self)
{
print!("{}", self.sign);
for i in &self.digits
{
print!("{}", i);
}
}
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
//impl From<num::ParseIntError> for ParseError {
// fn from(error: num::ParseIntError) -> Self {
// ParseError{error}
// }
//}
impl FromStr for Bigint {
type Err = ParseError;
/// Очакваме низа да е във формат десетично цяло число с опционален знак, тоест всички тези
/// неща би трябвало да върнат `Ok` резултат с конструиран Bigint:
///
/// Това включва нулата, като имате предвид че, както казахме, +0 и -0 трябва да са
/// еквивалентни.
///
/// Ако подадения низ е празен, това връща същото като да сме подали "0". Ако подадения низ е
/// само "+" или "-", ваше решение е дали да е нула или да е грешка, няма да го тестваме.
///
/// Ако подадения низ започва с нули, това няма значение -- игнорират се. Тоест, конструиране с
/// "00123" ще е същото като конструиране с "123".
///
/// Ако сме подали низ, който включва каквито и да е други символи освен цифрите 0-9 (и
/// опционален начален знак), очакваме да върнете `ParseError`.
///
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut sign_fn = 1i8;
let mut start = 0usize;
let mut possible_digits: Vec<char> = s.chars()
.collect();
if possible_digits.len() == 0
{
return Ok(Bigint{sign: 1, digits: vec![0]});
}
if possible_digits[0] == '-'
{
sign_fn = -1;
start = 1;
}
if possible_digits[0] == '+'
{
sign_fn = 1;
start = 1;
}
let mut digits_with_zeros = Vec::new();
let mut found_first_non_zero = false;
//possible_digits.remove(0);
//possible_digits.remove(possible_digits.len() - 1);
for i in start..s.len() as usize
{
if (possible_digits[i] as u8) < ('0' as u8) || (possible_digits[i] as u8) > ('9' as u8)
{
println!("errored {}, {}",i,possible_digits[i]);
return Err(ParseError);
}
if(possible_digits[i] as u8) >= ('1' as u8) && (possible_digits[i] as u8) <= ('9' as u8){
found_first_non_zero = true;
}
if(found_first_non_zero == true)
{
digits_with_zeros.push(possible_digits[i] as u8 - '0' as u8);
}
//digits_with_zeros.push(possible_digits[i].parse::<i32>()? as u8);
}
if(digits_with_zeros.len() == 0)
{
return Ok(Bigint{sign: 1, digits: vec![0]});
}
Ok(Bigint{sign: sign_fn, digits: digits_with_zeros})
}
}
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 {
if self.sign == 1 && other.sign == -1
{
return Ordering::Greater;
}
else if self.sign == -1 && other.sign == 1
{
return Ordering::Less;
}
if(self.digits.len() > other.digits.len())
{
if(self.sign == 1)
{
return Ordering::Greater;
}
else
{
return Ordering::Greater.reverse();
}
}
else if(self.digits.len() < other.digits.len()) {
if(self.sign == 1)
{
return Ordering::Less;
}
else
{
return Ordering::Less.reverse();
}
}
for i in 0..self.digits.len()
{
if(self.digits[i] > other.digits[i])
{
if(self.sign == 1)
{
return Ordering::Greater;
}
else
{
return Ordering::Greater.reverse();
}
}
if(self.digits[i] < other.digits[i])
{
if(self.sign == 1)
{
return Ordering::Less;
}
else
{
return Ordering::Less.reverse();
}
}
}
Ordering::Equal
}
}
use std::ops::{Add, Sub};
pub fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
let mut result_digits = Vec::new();
let mut carry = 0u8;
larger.reverse();
smaller.reverse();
for i in 0..smaller.len()
{
let mut subtr = larger[i]as i32 - smaller[i] as i32 - carry as i32;
if subtr < 0
{
subtr = subtr + 10;
carry = 1;
}
else
{
carry = 0;
}
result_digits.push(subtr as u8);
}
for i in smaller.len()..larger.len()
{
let mut subtr = larger[i]as i32 - carry as i32;
if subtr < 0
{
subtr = subtr + 10;
carry = 1;
}
else
{
carry = 0;
}
result_digits.push(subtr as u8);
}
result_digits.reverse();
return result_digits;
}
impl Add for Bigint {
type Output = Bigint;
/// За да съберете две числа, първия въпрос е: какви са им знаците?
///
/// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
/// знак.
/// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
/// отрицателен знак на крайния резултат.
/// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
/// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
/// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
/// положителна).
///
/// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
/// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
/// запълните с нули, да внимавате с индексите, или нещо по средата.
///
fn add(mut self, mut other: Self) -> Self {
let mut result_digits = Vec::new();
if(self.sign == other.sign)
{
self.digits.reverse();
other.digits.reverse();
let mut len = 0usize;
if(self.digits.len() >= other.digits.len())
{
len = other.digits.len();
}
else
{
len = self.digits.len()
}
let mut carry = 0u8;
for i in 0..len
{
let mut sum = 0u8;
sum = self.digits[i] + other.digits[i] + carry;
result_digits.push(sum%10);
carry = sum/10;
}
if(self.digits.len() >= len)
{
for i in len..self.digits.len()
{
let mut sum = 0u8;
sum = self.digits[i] + carry;
result_digits.push(sum%10);
carry = sum/10;
}
}
else
{
for i in len..other.digits.len()
{
let mut sum = 0u8;
sum = self.digits[i] + carry;
result_digits.push(sum%10);
carry = sum/10;
}
}
result_digits.push(carry);
return Bigint{sign : self.sign, digits : result_digits};
}
else {
if(self.digits.len() > other.digits.len())
{
return Bigint{sign : self.sign, digits : subtract_digits(self.digits,other.digits)};
}
else
{
return Bigint{sign : other.sign, digits : subtract_digits(other.digits,self.digits)};
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
/// събиране и по изваждане между `add` и `sub`.
///
/// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
/// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
/// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
///
/// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
///
fn sub(self, other: Self) -> Self {
if(self.digits.len() > other.digits.len())
{
return Bigint{sign : self.sign, digits : subtract_digits(self.digits,other.digits)};
}
else
{
return Bigint{sign : other.sign, digits : subtract_digits(other.digits,self.digits)};
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-18gq1zu/solution)
warning: unused import: `std::num`
--> src/lib.rs:1:5
|
1 | use std::num;
| ^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:117:12
|
117 | if(found_first_non_zero == true)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
|
= note: `#[warn(unused_parens)]` on by default
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:123:11
|
123 | if(digits_with_zeros.len() == 0)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:164:11
|
164 | if(self.digits.len() > other.digits.len())
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:166:15
|
166 | if(self.sign == 1)
| ^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:175:16
|
175 | else if(self.digits.len() < other.digits.len()) {
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:176:15
|
176 | if(self.sign == 1)
| ^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:187:15
|
187 | if(self.digits[i] > other.digits[i])
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:189:19
|
189 | if(self.sign == 1)
| ^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:198:15
|
198 | if(self.digits[i] < other.digits[i])
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:200:19
|
200 | if(self.sign == 1)
| ^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:273:11
|
273 | if(self.sign == other.sign)
| ^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:278:15
|
278 | if(self.digits.len() >= other.digits.len())
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:294:15
|
294 | if(self.digits.len() >= len)
| ^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:319:15
|
319 | if(self.digits.len() > other.digits.len())
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: unnecessary parentheses around `if` condition
--> src/lib.rs:346:11
|
346 | if(self.digits.len() > other.digits.len())
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove these parentheses
warning: value assigned to `len` is never read
--> src/lib.rs:277:17
|
277 | let mut len = 0usize;
| ^^^^^^^
|
= note: `#[warn(unused_assignments)]` on by default
= help: maybe it is overwritten before being read?
warning: value assigned to `sum` is never read
--> src/lib.rs:289:21
|
289 | let mut sum = 0u8;
| ^^^^^^^
|
= help: maybe it is overwritten before being read?
warning: value assigned to `sum` is never read
--> src/lib.rs:298:25
|
298 | let mut sum = 0u8;
| ^^^^^^^
|
= help: maybe it is overwritten before being read?
warning: value assigned to `sum` is never read
--> src/lib.rs:308:25
|
308 | let mut sum = 0u8;
| ^^^^^^^
|
= help: maybe it is overwritten before being read?
warning: variable does not need to be mutable
--> src/lib.rs:86:13
|
86 | let mut possible_digits: Vec<char> = s.chars()
| ----^^^^^^^^^^^^^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: 21 warnings emitted
Finished test [unoptimized + debuginfo] target(s) in 1.95s
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 ... 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 ... 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 ... FAILED
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_neutralization stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [0, 0, 0] }`,
right: `Bigint { sign: 1, digits: [0] }`', tests/solution_test.rs:126:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
---- 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:139:5
---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [0, 9, 9, 9] }`,
right: `Bigint { sign: 1, digits: [9, 9, 9] }`', tests/solution_test.rs:157:5
---- solution_test::test_sum_1_basic stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [3, 0] }`,
right: `Bigint { sign: 1, digits: [3] }`', tests/solution_test.rs:76:5
---- solution_test::test_sum_2_different_lengths stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [2, 1, 0] }`,
right: `Bigint { sign: 1, digits: [1, 2, 0, 1, 2] }`', tests/solution_test.rs:88:5
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [0, 0, 0, 1] }`,
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 'assertion failed: `(left == right)`
left: `Bigint { sign: -1, digits: [9, 7, 5, 0] }`,
right: `Bigint { sign: -1, digits: [5, 7, 9] }`', tests/solution_test.rs:112:5
failures:
solution_test::test_neutralization
solution_test::test_sub_1_basic
solution_test::test_sub_3_carry
solution_test::test_sum_1_basic
solution_test::test_sum_2_different_lengths
solution_test::test_sum_3_overflow
solution_test::test_sum_4_negative
test result: FAILED. 8 passed; 7 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'