Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Bigint от Тодор Димов

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

Към профила на Тодор Димов

Резултати

  • 13 точки от тестове
  • 0 бонус точки
  • 13 точки общо
  • 13 успешни тест(а)
  • 2 неуспешни тест(а)

Код

#![allow(clippy::suspicious_else_formatting)]
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint
{
is_negative: bool,
parts: Vec<u32>,
}
// use regex::Regex;
impl Bigint
{
const RADIX: u32 = 1_000_000_000;
const RADIX_LENGTH: usize = 9;
// fn string_to_parts(s: &str) -> Vec<u32>
// {
// let mut result = Vec::<u32>::new();
// let mut str_len = s.len();
// let mut subs = ( s, "" );
// while str_len > Bigint::RADIX_LENGTH
// {
// subs = subs.0.split_at( str_len - Bigint::RADIX_LENGTH );
// result.push( subs.1.parse::<u32>().unwrap() );
// str_len -= Bigint::RADIX_LENGTH;
// }
// result.push( subs.0.parse::<u32>().unwrap_or( 0 ) );
// result
// }
// fn from_matches(sign: &Option<regex::Match>, digits: &Option<regex::Match>) -> Self
// {
// let parts = Self::string_to_parts( digits.map_or( "0", |m| m.as_str() ) );
// let is_negative = sign.map_or( "", |m| m.as_str() ) == "-" && !Self::parts_are_zero( &parts );
// Self { is_negative, parts }
// }
fn digits_to_parts(digits: Vec<u32>) -> Vec<u32>
{
let mut result = Vec::<u32>::new();
let mut counter = 0;
for digit in digits.iter().rev()
{
if counter == 0
{
result.push( *digit );
}
else
{
*result.last_mut().unwrap() += digit * 10_u32.pow( counter );
}
if counter == Bigint::RADIX_LENGTH as u32 - 1
{
counter = 0;
}
else
{
counter += 1;
}
}
while result.len() > 1 && *result.last().unwrap() == 0
{
result.pop();
}
result
}
pub fn new() -> Self
{
Self { is_negative: false, parts: vec![ 0 ] }
}
fn parts_are_zero(parts: &[u32]) -> bool
{
parts.len() == 1 && parts[ 0 ] == 0
}
pub fn is_positive(&self) -> bool
{
!self.is_negative && !Self::parts_are_zero( &self.parts )
}
pub fn is_negative(&self) -> bool
{
self.is_negative
}
pub fn is_zero(&self) -> bool
{
!self.is_negative && Self::parts_are_zero( &self.parts )
}
fn has_more_parts_than(&self, other: &Self) -> bool
{
self.parts.len() > other.parts.len()
}
fn compare_abs(&self, other: &Self) -> Ordering
{
self.parts.len().cmp( &other.parts.len() )
.then( self.parts.iter().rev().cmp( other.parts.iter().rev() ) )
}
fn carry(&mut self, to: usize, carry: u32)
{
if to < self.parts.len()
{
self.parts[ to ] += carry;
}
else if carry > 0
{
self.parts.push( carry );
}
}
fn borrow(&mut self, to: usize)
{
if to + 2 == self.parts.len() && self.parts[ to + 1 ] == 1
{
self.parts.pop();
}
else
{
self.parts[ to + 1 ] -= 1;
}
self.parts[ to ] += Bigint::RADIX;
}
fn add_diff_sign(self, other: Self) -> Self
{
match self.compare_abs( &other )
{
Ordering::Less =>
{
other.sub_parts( self )
}
Ordering::Greater =>
{
self.sub_parts( other )
}
Ordering::Equal =>
{
Self::new()
}
}
}
fn add_same_sign(mut self, mut other: Self) -> Self
{
let self_len = self.parts.len();
other.parts.resize( self_len, 0 );
for i in 0 .. self_len
{
self.parts[ i ] += other.parts[ i ];
self.carry( i + 1, self.parts[ i ] / Bigint::RADIX );
self.parts[ i ] %= Bigint::RADIX;
}
self
}
fn sub_diff_sign(self, mut other: Self) -> Self
{
other.is_negative = !other.is_negative;
if self.has_more_parts_than( &other )
{
self.add_same_sign( other )
}
else
{
other.add_same_sign( self )
}
}
fn sub_same_sign(self, mut other: Self) -> Self
{
other.is_negative = !other.is_negative;
self.add_diff_sign( other )
}
fn sub_parts(mut self, mut other: Self) -> Self
{
other.parts.resize( self.parts.len(), 0 );
let mut i = 0;
while i < self.parts.len()
{
if self.parts[ i ] < other.parts[ i ]
{
self.borrow( i );
}
self.parts[ i ] -= other.parts[ i ];
i += 1;
}
self
}
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint
{
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err>
{
// 2.5 times longer because the supid language doesn't have built-in regex library
// and we can't use crates because fuck you, that's why
let mut chars_iter = s.chars();
match chars_iter.next()
{
Some( first ) =>
{
let mut is_negative = first == '-';
if first == '+' || is_negative
{
if chars_iter.all( |c| c.is_digit( 10 ) )
{
let mut chars_iter2 = s.chars();
chars_iter2.next();
let parts = Bigint::digits_to_parts( chars_iter2.map( |c| c.to_digit( 10 ).unwrap() ).collect() );
if Bigint::parts_are_zero( &parts )
{
is_negative = false;
}
Ok( Bigint { is_negative, parts } )
}
else
{
Err( Self::Err{} )
}
}
else if s.chars().all( |c| c.is_digit( 10 ) )
{
let parts = Bigint::digits_to_parts( s.chars().map( |c| c.to_digit( 10 ).unwrap() ).collect() );
Ok( Bigint { is_negative, parts } )
}
else
{
Err( Self::Err{} )
}
}
None =>
{
Ok( Self::new() )
}
}
// match Regex::new( r"^(([+-])?0*(\d+))?$" ).unwrap().captures( s )
// {
// Some( captures ) => Ok( Bigint::from_matches( &captures.get( 2 ), &captures.get( 3 ) ) ),
// None => Err( Self::Err{} ),
// }
}
}
use core::cmp::Ordering;
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.is_negative && !other.is_negative
{
Ordering::Less
}
else if !self.is_negative && other.is_negative
{
Ordering::Greater
}
else if self.is_negative && other.is_negative
{
other.compare_abs( &self )
}
else
{
self.compare_abs( &other )
}
}
}
use core::ops::Add;
impl Add for Bigint
{
type Output = Bigint;
fn add(self, other: Self) -> Self
{
if self.is_zero()
{
other
}
else if other.is_zero()
{
self
}
else if self.is_negative != other.is_negative
{
self.add_diff_sign( other )
}
else if self.has_more_parts_than( &other )
{
self.add_same_sign( other )
}
else
{
other.add_same_sign( self )
}
}
}
use core::ops::Sub;
impl Sub for Bigint
{
type Output = Bigint;
fn sub(self, mut other: Self) -> Self
{
if self.is_zero()
{
other.is_negative = !other.is_negative;
other
}
else if other.is_zero()
{
self
}
else if self.is_negative != other.is_negative
{
self.sub_diff_sign( other )
}
else
{
self.sub_same_sign( other )
}
}
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-y5m28k/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.78s
     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 ... ok
test solution_test::test_sub_2_diferent_lengths ... ok
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_neutralization stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Bigint { is_negative: true, parts: [0] }`,
 right: `Bigint { is_negative: false, parts: [0] }`', tests/solution_test.rs:133:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

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


failures:
    solution_test::test_neutralization
    solution_test::test_sub_3_carry

test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out

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

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

Тодор качи първо решение на 22.11.2020 16:06 (преди почти 5 години)

Тодор качи решение на 22.11.2020 19:33 (преди почти 5 години)

#![allow(clippy::suspicious_else_formatting)]
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint
{
- is_negative: bool,
- parts: Vec<u32>,
+ is_negative: bool,
+ parts: Vec<u32>,
}
-//use regex::Regex;
+// use regex::Regex;
impl Bigint
{
- const RADIX: u32 = 1_000_000_000;
- const RADIX_LENGTH: usize = 9;
+ const RADIX: u32 = 1_000_000_000;
+ const RADIX_LENGTH: usize = 9;
- fn string_to_parts(s: &str) -> Vec<u32>
- {
- let mut result = Vec::<u32>::new();
-
- let mut str_len = s.len();
- let mut subs = ( s, "" );
-
- while str_len > Bigint::RADIX_LENGTH
- {
- subs = subs.0.split_at( str_len - Bigint::RADIX_LENGTH );
- result.push( subs.1.parse::<u32>().unwrap() );
- str_len -= Bigint::RADIX_LENGTH;
- }
- result.push( subs.0.parse::<u32>().unwrap_or( 0 ) );
-
- result
- }
+ // fn string_to_parts(s: &str) -> Vec<u32>
+ // {
+ // let mut result = Vec::<u32>::new();
+
+ // let mut str_len = s.len();
+ // let mut subs = ( s, "" );
+
+ // while str_len > Bigint::RADIX_LENGTH
+ // {
+ // subs = subs.0.split_at( str_len - Bigint::RADIX_LENGTH );
+ // result.push( subs.1.parse::<u32>().unwrap() );
+ // str_len -= Bigint::RADIX_LENGTH;
+ // }
+ // result.push( subs.0.parse::<u32>().unwrap_or( 0 ) );
+
+ // result
+ // }
- //fn from_matches(sign: &Option<regex::Match>, digits: &Option<regex::Match>) -> Self
- //{
- // let parts = Self::string_to_parts( digits.map_or( "0", |m| m.as_str() ) );
- // let is_negative = sign.map_or( "", |m| m.as_str() ) == "-" && !Self::parts_are_zero( &parts );
+ // fn from_matches(sign: &Option<regex::Match>, digits: &Option<regex::Match>) -> Self
+ // {
+ // let parts = Self::string_to_parts( digits.map_or( "0", |m| m.as_str() ) );
+ // let is_negative = sign.map_or( "", |m| m.as_str() ) == "-" && !Self::parts_are_zero( &parts );
- // Self { is_negative, parts }
- //}
+ // Self { is_negative, parts }
+ // }
- fn digits_to_parts(digits: Vec<u32>) -> Vec<u32>
- {
- let mut result = Vec::<u32>::new();
- let mut counter = 0;
- for digit in digits.iter().rev()
- {
- if counter == 0
- {
- result.push( *digit );
- }
- else
- {
- *result.last_mut().unwrap() += digit * 10_u32.pow( counter );
- }
-
- if counter == Bigint::RADIX_LENGTH as u32 - 1
- {
- counter = 0;
- }
- else
- {
- counter += 1;
- }
- }
-
- while result.len() > 1 && *result.last().unwrap() == 0
- {
- result.pop();
- }
-
- result
- }
+ fn digits_to_parts(digits: Vec<u32>) -> Vec<u32>
+ {
+ let mut result = Vec::<u32>::new();
+ let mut counter = 0;
+ for digit in digits.iter().rev()
+ {
+ if counter == 0
+ {
+ result.push( *digit );
+ }
+ else
+ {
+ *result.last_mut().unwrap() += digit * 10_u32.pow( counter );
+ }
+
+ if counter == Bigint::RADIX_LENGTH as u32 - 1
+ {
+ counter = 0;
+ }
+ else
+ {
+ counter += 1;
+ }
+ }
+
+ while result.len() > 1 && *result.last().unwrap() == 0
+ {
+ result.pop();
+ }
+
+ result
+ }
- pub fn new() -> Self
- {
- Self { is_negative: false, parts: vec![ 0 ] }
- }
+ pub fn new() -> Self
+ {
+ Self { is_negative: false, parts: vec![ 0 ] }
+ }
- fn parts_are_zero(parts: &[u32]) -> bool
- {
- parts.len() == 1 && parts[ 0 ] == 0
- }
+ fn parts_are_zero(parts: &[u32]) -> bool
+ {
+ parts.len() == 1 && parts[ 0 ] == 0
+ }
- pub fn is_positive(&self) -> bool
- {
- !self.is_negative && !Self::parts_are_zero( &self.parts )
- }
+ pub fn is_positive(&self) -> bool
+ {
+ !self.is_negative && !Self::parts_are_zero( &self.parts )
+ }
- pub fn is_negative(&self) -> bool
- {
- self.is_negative
- }
-
- pub fn is_zero(&self) -> bool
- {
- !self.is_negative && Self::parts_are_zero( &self.parts )
- }
-
- fn has_more_parts_than(&self, other: &Self) -> bool
- {
- self.parts.len() > other.parts.len()
- }
-
- fn compare_abs(&self, other: &Self) -> Ordering
- {
- self.parts.len().cmp( &other.parts.len() )
- .then( self.parts.iter().rev().cmp( other.parts.iter().rev() ) )
- }
-
- fn carry(&mut self, to: usize, carry: u32)
- {
- if to < self.parts.len()
- {
- self.parts[ to ] += carry;
- }
- else if carry > 0
- {
- self.parts.push( carry );
- }
- }
-
- fn borrow(&mut self, to: usize)
- {
- if to + 2 == self.parts.len() && self.parts[ to + 1 ] == 1
- {
- self.parts.pop();
- }
- else
- {
- self.parts[ to + 1 ] -= 1;
- }
-
- self.parts[ to ] += Bigint::RADIX;
- }
-
- fn add_diff_sign(self, other: Self) -> Self
- {
- match self.compare_abs( &other )
- {
- Ordering::Less =>
- {
- other.sub_parts( self )
- }
- Ordering::Greater =>
- {
- self.sub_parts( other )
- }
- Ordering::Equal =>
- {
- Self::new()
- }
- }
- }
-
- fn add_same_sign(mut self, mut other: Self) -> Self
- {
- let self_len = self.parts.len();
-
- other.parts.resize( self_len, 0 );
-
- for i in 0 .. self_len
- {
- self.parts[ i ] += other.parts[ i ];
- self.carry( i + 1, self.parts[ i ] / Bigint::RADIX );
- self.parts[ i ] %= Bigint::RADIX;
- }
-
- self
- }
-
- fn sub_diff_sign(self, mut other: Self) -> Self
- {
- other.is_negative = !other.is_negative;
-
- if self.has_more_parts_than( &other )
- {
- self.add_same_sign( other )
- }
- else
- {
- other.add_same_sign( self )
- }
- }
-
- fn sub_same_sign(self, mut other: Self) -> Self
- {
- other.is_negative = !other.is_negative;
- self.add_diff_sign( other )
- }
-
- fn sub_parts(mut self, mut other: Self) -> Self
- {
- other.parts.resize( self.parts.len(), 0 );
-
- let mut i = 0;
- while i < self.parts.len()
- {
- if self.parts[ i ] < other.parts[ i ]
- {
- self.borrow( i );
- }
- self.parts[ i ] -= other.parts[ i ];
-
- i += 1;
- }
-
- self
- }
+ pub fn is_negative(&self) -> bool
+ {
+ self.is_negative
+ }
+
+ pub fn is_zero(&self) -> bool
+ {
+ !self.is_negative && Self::parts_are_zero( &self.parts )
+ }
+
+ fn has_more_parts_than(&self, other: &Self) -> bool
+ {
+ self.parts.len() > other.parts.len()
+ }
+
+ fn compare_abs(&self, other: &Self) -> Ordering
+ {
+ self.parts.len().cmp( &other.parts.len() )
+ .then( self.parts.iter().rev().cmp( other.parts.iter().rev() ) )
+ }
+
+ fn carry(&mut self, to: usize, carry: u32)
+ {
+ if to < self.parts.len()
+ {
+ self.parts[ to ] += carry;
+ }
+ else if carry > 0
+ {
+ self.parts.push( carry );
+ }
+ }
+
+ fn borrow(&mut self, to: usize)
+ {
+ if to + 2 == self.parts.len() && self.parts[ to + 1 ] == 1
+ {
+ self.parts.pop();
+ }
+ else
+ {
+ self.parts[ to + 1 ] -= 1;
+ }
+
+ self.parts[ to ] += Bigint::RADIX;
+ }
+
+ fn add_diff_sign(self, other: Self) -> Self
+ {
+ match self.compare_abs( &other )
+ {
+ Ordering::Less =>
+ {
+ other.sub_parts( self )
+ }
+ Ordering::Greater =>
+ {
+ self.sub_parts( other )
+ }
+ Ordering::Equal =>
+ {
+ Self::new()
+ }
+ }
+ }
+
+ fn add_same_sign(mut self, mut other: Self) -> Self
+ {
+ let self_len = self.parts.len();
+
+ other.parts.resize( self_len, 0 );
+
+ for i in 0 .. self_len
+ {
+ self.parts[ i ] += other.parts[ i ];
+ self.carry( i + 1, self.parts[ i ] / Bigint::RADIX );
+ self.parts[ i ] %= Bigint::RADIX;
+ }
+
+ self
+ }
+
+ fn sub_diff_sign(self, mut other: Self) -> Self
+ {
+ other.is_negative = !other.is_negative;
+
+ if self.has_more_parts_than( &other )
+ {
+ self.add_same_sign( other )
+ }
+ else
+ {
+ other.add_same_sign( self )
+ }
+ }
+
+ fn sub_same_sign(self, mut other: Self) -> Self
+ {
+ other.is_negative = !other.is_negative;
+ self.add_diff_sign( other )
+ }
+
+ fn sub_parts(mut self, mut other: Self) -> Self
+ {
+ other.parts.resize( self.parts.len(), 0 );
+
+ let mut i = 0;
+ while i < self.parts.len()
+ {
+ if self.parts[ i ] < other.parts[ i ]
+ {
+ self.borrow( i );
+ }
+ self.parts[ i ] -= other.parts[ i ];
+
+ i += 1;
+ }
+
+ self
+ }
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint
{
- type Err = ParseError;
+ type Err = ParseError;
- fn from_str(s: &str) -> Result<Self, Self::Err>
- {
- // 5 times longer because the supid language doesn't have built-in regex library
- // and we can't use crates because fuck you, that's why
- let mut chars_iter = s.chars();
- match chars_iter.next()
- {
- Some( first ) =>
- {
- let mut is_negative = first == '-';
- if first == '+' || is_negative
- {
- if chars_iter.all( |c| c.is_digit( 10 ) )
- {
- let mut chars_iter2 = s.chars();
- chars_iter2.next();
- let parts = Bigint::digits_to_parts( chars_iter2.map( |c| c.to_digit( 10 ).unwrap() ).collect() );
- if Bigint::parts_are_zero( &parts )
- {
- is_negative = false;
- }
- Ok( Bigint { is_negative, parts } )
- }
- else
- {
- Err( Self::Err{} )
- }
- }
- else if s.chars().all( |c| c.is_digit( 10 ) )
- {
- let parts = Bigint::digits_to_parts( s.chars().map( |c| c.to_digit( 10 ).unwrap() ).collect() );
- Ok( Bigint { is_negative, parts } )
- }
- else
- {
- Err( Self::Err{} )
- }
- }
- None =>
- {
- Ok( Self::new() )
- }
- }
-
- //let re = Regex::new(r"^([+-])?0*(\d*)$").unwrap();
-
- //let capture_result = re.captures(s);
-
- //match capture_result
- //{
- // Some(captures) => Ok( Bigint::from_matches( &captures.get( 1 ), &captures.get( 2 ) ) ),
- // None => Err( Self::Err{} ),
- //}
- }
+ fn from_str(s: &str) -> Result<Self, Self::Err>
+ {
+ // 2.5 times longer because the supid language doesn't have built-in regex library
+ // and we can't use crates because fuck you, that's why
+ let mut chars_iter = s.chars();
+ match chars_iter.next()
+ {
+ Some( first ) =>
+ {
+ let mut is_negative = first == '-';
+ if first == '+' || is_negative
+ {
+ if chars_iter.all( |c| c.is_digit( 10 ) )
+ {
+ let mut chars_iter2 = s.chars();
+ chars_iter2.next();
+ let parts = Bigint::digits_to_parts( chars_iter2.map( |c| c.to_digit( 10 ).unwrap() ).collect() );
+ if Bigint::parts_are_zero( &parts )
+ {
+ is_negative = false;
+ }
+ Ok( Bigint { is_negative, parts } )
+ }
+ else
+ {
+ Err( Self::Err{} )
+ }
+ }
+ else if s.chars().all( |c| c.is_digit( 10 ) )
+ {
+ let parts = Bigint::digits_to_parts( s.chars().map( |c| c.to_digit( 10 ).unwrap() ).collect() );
+ Ok( Bigint { is_negative, parts } )
+ }
+ else
+ {
+ Err( Self::Err{} )
+ }
+ }
+ None =>
+ {
+ Ok( Self::new() )
+ }
+ }
+
+ // match Regex::new( r"^(([+-])?0*(0|\d+))?$" ).unwrap().captures( s )
+ // {
+ // Some( captures ) => Ok( Bigint::from_matches( &captures.get( 2 ), &captures.get( 3 ) ) ),
+ // None => Err( Self::Err{} ),
+ // }
+ }
}
use core::cmp::Ordering;
impl PartialOrd for Bigint
{
- fn partial_cmp(&self, other: &Bigint) -> Option<Ordering>
- {
- Some( self.cmp( other ) )
- }
+ fn partial_cmp(&self, other: &Bigint) -> Option<Ordering>
+ {
+ Some( self.cmp( other ) )
+ }
}
impl Ord for Bigint
{
- fn cmp(&self, other: &Bigint) -> Ordering
- {
- if self.is_negative && !other.is_negative
- {
- Ordering::Less
- }
- else if !self.is_negative && other.is_negative
- {
- Ordering::Greater
- }
- else if self.is_negative && other.is_negative
- {
- other.compare_abs( &self )
- }
- else
- {
- self.compare_abs( &other )
- }
- }
+ fn cmp(&self, other: &Bigint) -> Ordering
+ {
+ if self.is_negative && !other.is_negative
+ {
+ Ordering::Less
+ }
+ else if !self.is_negative && other.is_negative
+ {
+ Ordering::Greater
+ }
+ else if self.is_negative && other.is_negative
+ {
+ other.compare_abs( &self )
+ }
+ else
+ {
+ self.compare_abs( &other )
+ }
+ }
}
use core::ops::Add;
impl Add for Bigint
{
- type Output = Bigint;
+ type Output = Bigint;
- fn add(self, other: Self) -> Self
- {
- if self.is_zero()
- {
- other
- }
- else if other.is_zero()
- {
- self
- }
- else if self.is_negative != other.is_negative
- {
- self.add_diff_sign( other )
- }
- else if self.has_more_parts_than( &other )
- {
- self.add_same_sign( other )
- }
- else
- {
- other.add_same_sign( self )
- }
- }
+ fn add(self, other: Self) -> Self
+ {
+ if self.is_zero()
+ {
+ other
+ }
+ else if other.is_zero()
+ {
+ self
+ }
+ else if self.is_negative != other.is_negative
+ {
+ self.add_diff_sign( other )
+ }
+ else if self.has_more_parts_than( &other )
+ {
+ self.add_same_sign( other )
+ }
+ else
+ {
+ other.add_same_sign( self )
+ }
+ }
}
use core::ops::Sub;
impl Sub for Bigint
{
- type Output = Bigint;
+ type Output = Bigint;
- fn sub(self, mut other: Self) -> Self
- {
+ fn sub(self, mut other: Self) -> Self
- if self.is_zero()
+ {
- {
+ if self.is_zero()
- other.is_negative = !other.is_negative;
+ {
- other
+ other.is_negative = !other.is_negative;
- }
+ other
- else if other.is_zero()
+ }
- {
+ else if other.is_zero()
- self
+ {
- }
+ self
- else if self.is_negative != other.is_negative
+ }
- {
+ else if self.is_negative != other.is_negative
- self.sub_diff_sign( other )
+ {
- }
+ self.sub_diff_sign( other )
- else
+ }
- {
+ else
- self.sub_same_sign( other )
+ {
- }
+ self.sub_same_sign( other )
- }
+ }
-}
+ }
+}

Тодор качи решение на 22.11.2020 19:38 (преди почти 5 години)

#![allow(clippy::suspicious_else_formatting)]
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint
{
is_negative: bool,
parts: Vec<u32>,
}
// use regex::Regex;
impl Bigint
{
const RADIX: u32 = 1_000_000_000;
const RADIX_LENGTH: usize = 9;
// fn string_to_parts(s: &str) -> Vec<u32>
// {
// let mut result = Vec::<u32>::new();
// let mut str_len = s.len();
// let mut subs = ( s, "" );
// while str_len > Bigint::RADIX_LENGTH
// {
// subs = subs.0.split_at( str_len - Bigint::RADIX_LENGTH );
// result.push( subs.1.parse::<u32>().unwrap() );
// str_len -= Bigint::RADIX_LENGTH;
// }
// result.push( subs.0.parse::<u32>().unwrap_or( 0 ) );
// result
// }
// fn from_matches(sign: &Option<regex::Match>, digits: &Option<regex::Match>) -> Self
// {
// let parts = Self::string_to_parts( digits.map_or( "0", |m| m.as_str() ) );
// let is_negative = sign.map_or( "", |m| m.as_str() ) == "-" && !Self::parts_are_zero( &parts );
// Self { is_negative, parts }
// }
fn digits_to_parts(digits: Vec<u32>) -> Vec<u32>
{
let mut result = Vec::<u32>::new();
let mut counter = 0;
for digit in digits.iter().rev()
{
if counter == 0
{
result.push( *digit );
}
else
{
*result.last_mut().unwrap() += digit * 10_u32.pow( counter );
}
if counter == Bigint::RADIX_LENGTH as u32 - 1
{
counter = 0;
}
else
{
counter += 1;
}
}
while result.len() > 1 && *result.last().unwrap() == 0
{
result.pop();
}
result
}
pub fn new() -> Self
{
Self { is_negative: false, parts: vec![ 0 ] }
}
fn parts_are_zero(parts: &[u32]) -> bool
{
parts.len() == 1 && parts[ 0 ] == 0
}
pub fn is_positive(&self) -> bool
{
!self.is_negative && !Self::parts_are_zero( &self.parts )
}
pub fn is_negative(&self) -> bool
{
self.is_negative
}
pub fn is_zero(&self) -> bool
{
!self.is_negative && Self::parts_are_zero( &self.parts )
}
fn has_more_parts_than(&self, other: &Self) -> bool
{
self.parts.len() > other.parts.len()
}
fn compare_abs(&self, other: &Self) -> Ordering
{
self.parts.len().cmp( &other.parts.len() )
.then( self.parts.iter().rev().cmp( other.parts.iter().rev() ) )
}
fn carry(&mut self, to: usize, carry: u32)
{
if to < self.parts.len()
{
self.parts[ to ] += carry;
}
else if carry > 0
{
self.parts.push( carry );
}
}
fn borrow(&mut self, to: usize)
{
if to + 2 == self.parts.len() && self.parts[ to + 1 ] == 1
{
self.parts.pop();
}
else
{
self.parts[ to + 1 ] -= 1;
}
self.parts[ to ] += Bigint::RADIX;
}
fn add_diff_sign(self, other: Self) -> Self
{
match self.compare_abs( &other )
{
Ordering::Less =>
{
other.sub_parts( self )
}
Ordering::Greater =>
{
self.sub_parts( other )
}
Ordering::Equal =>
{
Self::new()
}
}
}
fn add_same_sign(mut self, mut other: Self) -> Self
{
let self_len = self.parts.len();
other.parts.resize( self_len, 0 );
for i in 0 .. self_len
{
self.parts[ i ] += other.parts[ i ];
self.carry( i + 1, self.parts[ i ] / Bigint::RADIX );
self.parts[ i ] %= Bigint::RADIX;
}
self
}
fn sub_diff_sign(self, mut other: Self) -> Self
{
other.is_negative = !other.is_negative;
if self.has_more_parts_than( &other )
{
self.add_same_sign( other )
}
else
{
other.add_same_sign( self )
}
}
fn sub_same_sign(self, mut other: Self) -> Self
{
other.is_negative = !other.is_negative;
self.add_diff_sign( other )
}
fn sub_parts(mut self, mut other: Self) -> Self
{
other.parts.resize( self.parts.len(), 0 );
let mut i = 0;
while i < self.parts.len()
{
if self.parts[ i ] < other.parts[ i ]
{
self.borrow( i );
}
self.parts[ i ] -= other.parts[ i ];
i += 1;
}
self
}
}
use std::str::FromStr;
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint
{
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err>
{
// 2.5 times longer because the supid language doesn't have built-in regex library
// and we can't use crates because fuck you, that's why
let mut chars_iter = s.chars();
match chars_iter.next()
{
Some( first ) =>
{
let mut is_negative = first == '-';
if first == '+' || is_negative
{
if chars_iter.all( |c| c.is_digit( 10 ) )
{
let mut chars_iter2 = s.chars();
chars_iter2.next();
let parts = Bigint::digits_to_parts( chars_iter2.map( |c| c.to_digit( 10 ).unwrap() ).collect() );
if Bigint::parts_are_zero( &parts )
{
is_negative = false;
}
Ok( Bigint { is_negative, parts } )
}
else
{
Err( Self::Err{} )
}
}
else if s.chars().all( |c| c.is_digit( 10 ) )
{
let parts = Bigint::digits_to_parts( s.chars().map( |c| c.to_digit( 10 ).unwrap() ).collect() );
Ok( Bigint { is_negative, parts } )
}
else
{
Err( Self::Err{} )
}
}
None =>
{
Ok( Self::new() )
}
}
- // match Regex::new( r"^(([+-])?0*(0|\d+))?$" ).unwrap().captures( s )
+ // match Regex::new( r"^(([+-])?0*(\d+))?$" ).unwrap().captures( s )
// {
// Some( captures ) => Ok( Bigint::from_matches( &captures.get( 2 ), &captures.get( 3 ) ) ),
// None => Err( Self::Err{} ),
// }
}
}
use core::cmp::Ordering;
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.is_negative && !other.is_negative
{
Ordering::Less
}
else if !self.is_negative && other.is_negative
{
Ordering::Greater
}
else if self.is_negative && other.is_negative
{
other.compare_abs( &self )
}
else
{
self.compare_abs( &other )
}
}
}
use core::ops::Add;
impl Add for Bigint
{
type Output = Bigint;
fn add(self, other: Self) -> Self
{
if self.is_zero()
{
other
}
else if other.is_zero()
{
self
}
else if self.is_negative != other.is_negative
{
self.add_diff_sign( other )
}
else if self.has_more_parts_than( &other )
{
self.add_same_sign( other )
}
else
{
other.add_same_sign( self )
}
}
}
use core::ops::Sub;
impl Sub for Bigint
{
type Output = Bigint;
fn sub(self, mut other: Self) -> Self
{
if self.is_zero()
{
other.is_negative = !other.is_negative;
other
}
else if other.is_zero()
{
self
}
else if self.is_negative != other.is_negative
{
self.sub_diff_sign( other )
}
else
{
self.sub_same_sign( other )
}
}
}