Решение на Bigint от Андрей
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
use std::str::FromStr;
use std::ops::{Add, Sub, Neg};
use std::cmp::{self, Ordering};
#[derive(Debug)]
pub struct ParseError;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint { digits: vec![], sign: 1 }
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut sign = sign;
if digits.len() == 0 {
sign = 1;
}
Bigint { digits, sign }
}
pub fn is_positive(&self) -> bool { !self.is_zero() && self.sign.is_positive() }
pub fn is_negative(&self) -> bool { !self.is_zero() && self.sign.is_negative() }
fn is_zero(&self) -> bool {
self.digits.iter().all(|&d| d == 0)
}
fn abs(self) -> Self {
Bigint::from_components(self.digits, 1)
}
}
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s.len() == 0 {
return Ok(Bigint::new());
}
let mut digits = Vec::new();
let mut sign = 1;
let mut chars = s.chars();
// Is the first character a sign?
match chars.next() {
Some('-') => { sign = -1; },
Some('+') => { sign = 1; },
_ => { chars = s.chars(); },
};
for c in chars {
if let Some(digit) = c.to_digit(10) {
if digits.len() == 0 && digit == 0 {
// Leading zero, no point in adding it
} else {
digits.push(digit as u8);
}
} else {
return Err(ParseError);
}
}
Ok(Bigint::from_components(digits, sign))
}
}
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 {
let abs_ordering =
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Equal => self.digits.cmp(&other.digits),
ordering @ _ => ordering,
};
match (self.sign, other.sign) {
(-1, 1) => Ordering::Less,
( 1, -1) => Ordering::Greater,
( 1, 1) => abs_ordering,
(-1, -1) => abs_ordering.reverse(),
_ => unreachable!()
}
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self {
Bigint::from_components(self.digits, -self.sign)
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
Bigint::from_components(add_digits(self.digits, other.digits), self.sign)
} else if self.clone().abs() > other.clone().abs() {
Bigint::from_components(subtract_digits(self.digits, other.digits), self.sign)
} else {
Bigint::from_components(subtract_digits(other.digits, self.digits), other.sign)
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut result_digits = vec![];
left.reverse();
right.reverse();
let mut carry = 0;
let max_len = cmp::max(left.len(), right.len());
for i in 0..max_len {
let left_digit = *left.get(i).unwrap_or(&0);
let right_digit = *right.get(i).unwrap_or(&0);
let sum = left_digit + right_digit + carry;
result_digits.push(sum % 10);
carry = sum / 10;
}
if carry > 0 {
result_digits.push(carry)
}
result_digits.reverse();
result_digits
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
let mut result_digits = vec![];
larger.reverse();
smaller.reverse();
let mut carry = 0;
for i in 0..larger.len() {
let left_digit = *larger.get(i).unwrap_or(&0) as i8;
let right_digit = *smaller.get(i).unwrap_or(&0) as i8;
let sum = left_digit - right_digit + carry;
if sum < 0 {
result_digits.push((sum + 10) as u8);
carry = -1;
} else {
result_digits.push(sum as u8);
carry = 0;
}
}
// Remove leading zeroes
while let Some(0) = result_digits.last() {
result_digits.pop();
}
result_digits.reverse();
result_digits
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-7w79vu/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.62s
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 ... 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 ... ok
test solution_test::test_sum_4_negative ... ok
test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
История (2 версии и 0 коментара)
Андрей качи решение на 22.11.2020 16:49 (преди почти 5 години)
use std::str::FromStr;
use std::ops::{Add, Sub, Neg};
use std::cmp::{self, Ordering};
#[derive(Debug)]
pub struct ParseError;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint { digits: vec![], sign: 1 }
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut sign = sign;
if digits.len() == 0 {
sign = 1;
}
Bigint { digits, sign }
}
pub fn is_positive(&self) -> bool { !self.is_zero() && self.sign.is_positive() }
pub fn is_negative(&self) -> bool { !self.is_zero() && self.sign.is_negative() }
fn is_zero(&self) -> bool {
self.digits.iter().all(|&d| d == 0)
}
fn abs(self) -> Self {
Bigint::from_components(self.digits, 1)
}
}
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s.len() == 0 {
return Ok(Bigint::new());
}
let mut digits = Vec::new();
let mut sign = 1;
let mut chars = s.chars();
// Is the first character a sign?
match chars.next() {
Some('-') => { sign = -1; },
Some('+') => { sign = 1; },
_ => { chars = s.chars(); },
};
for c in chars {
if let Some(digit) = c.to_digit(10) {
if digits.len() == 0 && digit == 0 {
// Leading zero, no point in adding it
} else {
digits.push(digit as u8);
}
} else {
return Err(ParseError);
}
}
Ok(Bigint::from_components(digits, sign))
}
}
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 {
- match self.digits.len().cmp(&other.digits.len()) {
- Ordering::Equal => self.digits.cmp(&other.digits),
- ordering @ _ => ordering
+ let abs_ordering =
+ match self.digits.len().cmp(&other.digits.len()) {
+ Ordering::Equal => self.digits.cmp(&other.digits),
+ ordering @ _ => ordering,
+ };
+
+ match (self.sign, other.sign) {
+ (-1, 1) => Ordering::Less,
+ ( 1, -1) => Ordering::Greater,
+ ( 1, 1) => abs_ordering,
+ (-1, -1) => abs_ordering.reverse(),
+ _ => unreachable!()
}
}
}
impl Neg for Bigint {
type Output = Bigint;
fn neg(self) -> Self {
Bigint::from_components(self.digits, -self.sign)
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
Bigint::from_components(add_digits(self.digits, other.digits), self.sign)
} else if self.clone().abs() > other.clone().abs() {
Bigint::from_components(subtract_digits(self.digits, other.digits), self.sign)
} else {
Bigint::from_components(subtract_digits(other.digits, self.digits), other.sign)
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut result_digits = vec![];
left.reverse();
right.reverse();
let mut carry = 0;
let max_len = cmp::max(left.len(), right.len());
for i in 0..max_len {
let left_digit = *left.get(i).unwrap_or(&0);
let right_digit = *right.get(i).unwrap_or(&0);
let sum = left_digit + right_digit + carry;
result_digits.push(sum % 10);
carry = sum / 10;
}
if carry > 0 {
result_digits.push(carry)
}
result_digits.reverse();
result_digits
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
let mut result_digits = vec![];
larger.reverse();
smaller.reverse();
let mut carry = 0;
for i in 0..larger.len() {
let left_digit = *larger.get(i).unwrap_or(&0) as i8;
let right_digit = *smaller.get(i).unwrap_or(&0) as i8;
let sum = left_digit - right_digit + carry;
if sum < 0 {
result_digits.push((sum + 10) as u8);
carry = -1;
} else {
result_digits.push(sum as u8);
carry = 0;
}
}
// Remove leading zeroes
while let Some(0) = result_digits.last() {
result_digits.pop();
}
result_digits.reverse();
result_digits
}