Решение на Bigint от Симеон Николов
Резултати
- 5 точки от тестове
- 0 бонус точки
- 5 точки общо
- 5 успешни тест(а)
- 10 неуспешни тест(а)
Код
use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::{Add, Sub};
#[cfg(test)]
mod tests {
#[test]
fn it_works() {
assert_eq!(2 + 2, 4);
}
}
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: char,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self{
sign:'+',
digits:vec![0],
}
}
/// Връща `true` ако числото е положително. Нулата не е положителна.
pub fn is_positive(&self) -> bool {
self.sign == '+'
}
/// Връща `true` ако числото е отрицателно. Нулата не е отрицателна.
pub fn is_negative(&self) -> bool {
!self.is_positive()
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
//Работя с ACCII.Всичките тези числа по-долу са съответните байтове в Ascii таблицата.
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut buffer:Vec<u8> = s.to_string().into_bytes();
let mut sgn:char;
let mut flag:bool = true;
//Проверява дали някой от символите е невалиден
for i in 0..buffer.len(){
//57 = '9' , 48 = '0', 43 = '+' , 45 = '-'
//todo! оправи логиката защото това допуска изрази от вида 123+45
if buffer[i] > 57 || buffer[i] < 48 && buffer[i]!=43 && buffer[i]!= 45{
flag = false;
}
}
//Логика за знаците
if buffer[0]== 43 && buffer.len()>1{
sgn = '+';
buffer.remove(0);
}
else if buffer[0]== 45 && buffer.len()>1{
sgn = '-';
buffer.remove(0);
}
else {
sgn = '+';
}
//Премахва нулите в началото на конвертирания във вектор низ
while buffer[0] == 48 && buffer.len()>1{
buffer.remove(0);
}
//И най-накрая конвертирам в цифри, за да може да се улесни живота на всички. :)
for i in 0..buffer.len(){
buffer[i] = buffer[i] - 48;
}
// -0 == +0
if sgn == '-' && buffer[0] == 0{
sgn = '+'
}
if flag{
Ok(Bigint{sign:sgn,digits:buffer})
}
else{
Err(ParseError)
}
}
}
impl PartialOrd for Bigint {
/// Две цели числа винаги могат да се сравнят, така че "частичното" равенство е същото като
/// пълното.
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Bigint {
fn cmp(&self, other: &Bigint) -> Ordering {
if self.digits[0] == 0 && other.digits[0] == 0 {
Ordering::Equal
}
else if self.sign == '+' && other.sign == '-'{
Ordering::Greater
}
else if self.sign == '-' && other.sign == '+'{
Ordering::Less
}
else if self.sign == '+' && other.sign == '+'{
if self.digits.len() >other.digits.len(){
Ordering::Greater
}
else if self.digits.len() < other.digits.len(){
Ordering::Less
}
else{
self.digits.cmp(&other.digits)
}
}
else {
if self.digits.len() >other.digits.len(){
Ordering::Less
}
else if self.digits.len() < other.digits.len(){
Ordering::Greater
}
else{
self.digits.cmp(&other.digits).reverse()
}
}
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut i = 0;
left.reverse();
right.reverse();
if left.len() >right.len(){
while i <right.len(){
left[i] = right[i] + left[i];
if left[i] >=10 {
left[i] = left[i] - 10;
left[i + 1] = left[i + 1] + 10;
}
i = i + 1;
}
left.reverse();
left
}
else{
while i < right.len(){
left[i] = right[i] + left[i];
if left[i] >=10 && i+1<= left.len(){
left[i] = left[i] - 10;
left[i + 1] = left[i + 1] + 10;
}
else if left[i] >=10 && i+1 > left.len(){
left[i] = left[i] - 10;
left.push(1);
}
i = i + 1;
}
left.reverse();
left
}
}
fn subtract_digits(mut larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut i = larger.len() - smaller.len();
while i<smaller.len(){
if larger[i]>smaller[i]{
larger[i] = larger[i] - smaller[i];
}
else{
larger[i - 1] = larger[i - 1] - 1;
larger[i] = 10 - smaller[i] ;
}
i = i + 1;
}
larger
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == '+' && other.sign == '+'{
Self{
sign:'+',
digits:add_digits(self.digits,other.digits)
}
}
else if self.sign == '-' && other.sign == '+' && self.digits.len() > other.digits.len(){
Self{
sign:'-',
digits:subtract_digits(self.digits, other.digits)
}
}
else if self.sign == '-' && other.sign == '+' && self.digits.len() <= other.digits.len()
{
Self{
sign:'+',
digits:subtract_digits(other.digits, self.digits)
}
}
else{
Self{
sign:'-',
digits:add_digits(self.digits,other.digits)
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
/// Изваждането често се имплементира като събиране с отрицателен знак. Тоест, `A - B` е
/// еквивалентно на `A + (-B)`. Можете да имплементирате изваждането като форма на събиране, и
/// в него да пакетирате логиката. Или можете да проверите знаците и да разделите логиката по
/// събиране и по изваждане между `add` и `sub`.
///
fn sub(self, other: Self) -> Self {
if self.sign == '+' && other.sign == '-' && self.digits.len()>other.digits.len(){
Self{
sign:'+',
digits:subtract_digits(self.digits, other.digits)
}
}
else if self.sign == '+' && other.sign == '-' && self.digits.len()<=other.digits.len()
{
Self{
sign:'-',
digits:subtract_digits(other.digits, self.digits)
}
}
else if self.sign == '-' && other.sign == '-' {
Self{
sign:'-',
digits:add_digits(self.digits,other.digits)
}
}
else{
Self{
sign:'+',
digits:subtract_digits(self.digits,other.digits)
}
}
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-3s6p02/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.61s
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 ... FAILED
test solution_test::test_comparison ... ok
test solution_test::test_invalid_string ... FAILED
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 ... 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 ... FAILED
test solution_test::test_sum_3_overflow ... FAILED
test solution_test::test_sum_4_negative ... FAILED
failures:
---- solution_test::test_bigint_construction stdout ----
thread 'main' panicked at 'index out of bounds: the len is 0 but the index is 0', src/lib.rs:61:12
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
---- solution_test::test_bigint_zero_sign stdout ----
thread 'main' panicked at 'assertion failed: !zero.is_positive()', tests/solution_test.rs:21:5
---- solution_test::test_invalid_string stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:80:25
---- solution_test::test_neutralization stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:189:38
---- solution_test::test_sub_1_basic stdout ----
thread 'main' panicked at 'attempt to subtract with overflow', src/lib.rs:189:38
---- solution_test::test_sub_2_diferent_lengths stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: '+', digits: [1, 0, 10, 0] }`,
right: `Bigint { sign: '+', digits: [1, 0, 0, 0] }`', tests/solution_test.rs:151:5
---- solution_test::test_sub_3_carry stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: '+', digits: [1, 0, 0, 0] }`,
right: `Bigint { sign: '+', digits: [9, 9, 9] }`', tests/solution_test.rs:157:5
---- solution_test::test_sum_2_different_lengths stdout ----
thread 'main' panicked at 'index out of bounds: the len is 2 but the index is 2', src/lib.rs:163:32
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: '+', digits: [9, 19, 0] }`,
right: `Bigint { sign: '+', digits: [1, 0, 0, 0] }`', tests/solution_test.rs:97:5
---- solution_test::test_sum_4_negative stdout ----
thread 'main' panicked at 'index out of bounds: the len is 2 but the index is 2', src/lib.rs:163:32
failures:
solution_test::test_bigint_construction
solution_test::test_bigint_zero_sign
solution_test::test_invalid_string
solution_test::test_neutralization
solution_test::test_sub_1_basic
solution_test::test_sub_2_diferent_lengths
solution_test::test_sub_3_carry
solution_test::test_sum_2_different_lengths
solution_test::test_sum_3_overflow
solution_test::test_sum_4_negative
test result: FAILED. 5 passed; 10 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'