Решение на Bigint от Стефан Ангелов
Резултати
- 13 точки от тестове
- 0 бонус точки
- 13 точки общо
- 13 успешни тест(а)
- 2 неуспешни тест(а)
Код
use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Add, Sub};
use std::cmp::max;
#[derive(Debug)]
pub struct ParseError;
#[derive(Debug, Eq)]
pub struct Bigint {
pub sign: i8,
pub digits: Vec<u8>,
}
impl Bigint {
/// Конструира нов Bigint със стойност "0" и положителен знак.
/// Това може да означава празен вектор с цифри или масив с една цифра `0` -- ваш избор.
///
pub fn new() -> Self {
let mut vec = Vec::new();
vec.push(0);
Bigint {sign: 1, digits: vec}
}
/// Конструира нов Bigint с подадените цифри и знак.
///
/// Тук е добро място където можете да вкарате малко валидация и нормализиране на входа -- да
/// премахнете допълнителни нули или да се погрижите, че нулата винаги има консистентен знак.
/// Стига да се погрижите винаги да използвате функцията при конструириане на нови Bigint-ове.
///
/// Тази функция НЕ Е публична, така че НЕ Е задължителна -- ако не ви трябва, може смело да я
/// изтриете.
///
pub fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let vec = digits;
Bigint {sign: sign, digits: vec}
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
if self.sign == 1 && self.digits.len() > 0 && self.digits[0] != 0 {
true
}
else { false }
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
if self.sign == -1 && self.digits.len() > 0 && self.digits[0] != 0 {
true
}
else { false }
}
fn abs(&self) -> Self {
Bigint::from_components(self.digits.clone(), 1)
}
fn trim(mut self) -> Self {
let mut vec = Vec::new();
let mut is_found = false;
for elem in self.digits.iter() {
if *elem != 0 || is_found {
is_found = true;
vec.push(*elem);
}
}
if vec.len() == 0 {
vec.push(0);
}
self.digits = vec;
self
}
}
impl PartialEq for Bigint {
fn eq(&self, other: &Self) -> bool {
if self.digits[0] == 0 && other.digits[0] == 0 {
true
}
else if self.sign == other.sign && self.digits.len() == other.digits.len() {
let mut flag = true;
for i in 0..self.digits.len() {
if self.digits[i] != other.digits[i] {
flag = false;
break;
}
}
flag
}
else { false }
}
}
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 = Vec::new();
let mut split = String::from(s);
let first_char = String::from(s).chars().nth(0).unwrap();
if first_char == '+' || first_char == '-' {
split = String::from(s).split_off(1);
}
if first_char == '+' || (first_char >= '0' && first_char <= '9') || first_char == '-' {
let mut zeroes = 0;
for c in split.chars() {
if c != '0' || split.len() == 1 {
break;
}
zeroes += 1;
}
if first_char == '+' || first_char == '-' {
split = String::from(s).split_off(1 + zeroes);
}
else {
split = String::from(s).split_off(zeroes);
}
if split.is_empty() {
split = String::from("0");
}
for c in split.chars() {
if c >= '0' && c <= '9' {
let c = (c as u8) - 48;
vec.push(c);
}
else {return Err(ParseError);}
}
let mut sign = 0;
if first_char == '+' || (first_char >= '0' && first_char <= '9') {
sign = 1;
}
else if first_char == '-' {
sign = -1;
}
Ok(Bigint::from_components(vec, sign))
}
else {
Err(ParseError)
}
}
}
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.digits[0] == 0 && other.digits[0] == 0 {
Ordering::Equal
}
else if self.sign < other.sign {
Ordering::Less
}
else if self.sign > other.sign {
Ordering::Greater
}
else if self.sign == 1 {
if self.digits.len() < other.digits.len() {
Ordering::Less
}
else if self.digits.len() > other.digits.len() {
Ordering::Greater
}
else {
for index in 0..self.digits.len() {
if self.digits[index] < other.digits[index] {
return Ordering::Less;
}
else if self.digits[index] > other.digits[index] {
return Ordering::Greater;
}
}
Ordering::Equal
}
}
else {
if self.digits.len() > other.digits.len() {
Ordering::Less
}
else if self.digits.len() < other.digits.len() {
Ordering::Greater
}
else {
for index in 0..self.digits.len() {
if self.digits[index] > other.digits[index] {
return Ordering::Less;
}
else if self.digits[index] < other.digits[index] {
return Ordering::Greater;
}
}
Ordering::Equal
}
}
}
}
impl Add for Bigint {
type Output = Bigint;
/// За да съберете две числа, първия въпрос е: какви са им знаците?
///
/// - Ако и двете са положителни, събираме ги цифра по цифра и слагаме на резултата положителен
/// знак.
/// - Ако и двете са отрицателни, пак можем да ги съберем цифра по цифра и да сложим
/// отрицателен знак на крайния резултат.
/// - Ако имат различни знаци, намираме по-голямото *по абсолютна стойност*. Изваждаме цифрите
/// на по-малкото от по-голямото. Знака на резултата е знака на по-голямото по абсолютна
/// стойност. Ако са равни, резултата трябва да е нула (която винаги се очаква да е
/// положителна).
///
/// При събиране цифра по цифра, не забравяйте да пренасяте "едно наум" ако резултата е
/// по-голям от десетична цифра. При различна дължина на списъците от цифри, можете да
/// запълните с нули, да внимавате с индексите, или нещо по средата.
///
fn add(self, other: Self) -> Self {
let mut vec = Vec::new();
let mut carry = 0;
let mut bigger = Bigint::new();
let mut smaller = Bigint::new();
if Bigint::abs(&self) < Bigint::abs(&other) {
bigger = other;
smaller = self;
}
else {
bigger = self;
smaller = other;
}
let size_smaller = smaller.digits.len();
for index in size_smaller..bigger.digits.len() {
smaller.digits.insert(0, 0);
}
if bigger.sign == smaller.sign {
bigger.digits.reverse();
smaller.digits.reverse();
for index in 0..bigger.digits.len() {
let sum = bigger.digits[index] + smaller.digits[index] + carry;
vec.push(sum % 10);
if sum >= 10 {
carry = sum / 10;
}
}
}
else {
bigger.digits.reverse();
smaller.digits.reverse();
for index in 0..bigger.digits.len() {
println!("Big is {} and small is {}", bigger.digits[index], smaller.digits[index]);
if bigger.digits[index] < smaller.digits[index] {
let mut i = 1;
while bigger.digits[index + i] == 0 {
bigger.digits[index + i] = 9;
i += 1;
}
bigger.digits[index + i] -= 1;
bigger.digits[index] = 10 + bigger.digits[index];
}
let sub = bigger.digits[index] - smaller.digits[index];
println!("Sub is {}", sub);
vec.push(sub);
}
}
vec.reverse();
Bigint::trim(Bigint::from_components(vec, bigger.sign))
}
}
impl Sub for Bigint {
type Output = Bigint;
/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
/// събиране и по изваждане между `add` и `sub`.
///
/// При изваждане, също не забравяйте "едното наум", ако цифрата от която вадите е по-малката,
/// което ще се преведе до едно "-1" на следващата цифра. Погрижете се винаги да вадите от
/// по-голямото по абсолютна стойност число, и после сложете какъвто знак се налага.
///
/// Внимавайте с типовете -- изваждане на unsigned от unsigned число може да се счупи.
///
fn sub(self, other: Self) -> Self {
let mut other = other;
other.sign = -other.sign;
self + other
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-dtut7y/solution)
warning: unused import: `std::cmp::max`
--> src/lib.rs:4:5
|
4 | use std::cmp::max;
| ^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: value assigned to `bigger` is never read
--> src/lib.rs:253:13
|
253 | let mut bigger = Bigint::new();
| ^^^^^^^^^^
|
= note: `#[warn(unused_assignments)]` on by default
= help: maybe it is overwritten before being read?
warning: value assigned to `smaller` is never read
--> src/lib.rs:254:13
|
254 | let mut smaller = Bigint::new();
| ^^^^^^^^^^^
|
= help: maybe it is overwritten before being read?
warning: unused variable: `index`
--> src/lib.rs:264:13
|
264 | for index in size_smaller..bigger.digits.len() {
| ^^^^^ help: if this is intentional, prefix it with an underscore: `_index`
|
= note: `#[warn(unused_variables)]` on by default
warning: 4 warnings emitted
Finished test [unoptimized + debuginfo] target(s) in 1.76s
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 ... 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 ... FAILED
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:119:57
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: 1, digits: [0] }`,
right: `Bigint { sign: 1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:97:5
failures:
solution_test::test_bigint_construction
solution_test::test_sum_3_overflow
test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'