Решение на Bigint от Кирил Костов
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
use std::cmp::Ordering;
use std::ops::{Add, Sub};
use std::str::FromStr;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
}
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let skip_zero = digits.iter().take_while(|&x| *x == 0).count();
if skip_zero == digits.len() {
return Bigint::new();
}
Bigint {
sign,
digits: digits[skip_zero..].to_vec(),
}
}
fn is_zero(&self) -> bool {
self.digits.len() == 1 && self.digits[0] == 0
}
pub fn is_positive(&self) -> bool {
if self.is_zero() {
return false;
}
self.sign == 1
}
pub fn is_negative(&self) -> bool {
if self.is_zero() {
return false;
}
self.sign == -1
}
}
#[derive(Debug)]
pub struct ParseError;
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 c = s.chars().next().unwrap();
if c != '-' && c != '+' && !char::is_numeric(c) {
return Err(ParseError);
}
if s.len() == 1 && (c == '-' || c == '+') {
return Ok(Bigint::new());
}
let sign = if c == '-' { -1 } else { 1 };
let mut digits: Vec<u8> = Vec::new();
if char::is_numeric(c) {
digits.push(c as u8 - '0' as u8);
}
for c in s[1..].chars() {
if !char::is_numeric(c) {
return Err(ParseError);
}
digits.push(c as u8 - '0' as u8);
}
Ok(Bigint::from_components(digits, sign))
}
}
impl PartialOrd for Bigint {
fn partial_cmp(&self, other: &Bigint) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn cmp_digits(lhs: &Vec<u8>, rhs: &Vec<u8>) -> Ordering {
if lhs.len() > rhs.len() {
return Ordering::Greater;
}
if lhs.len() < rhs.len() {
return Ordering::Less;
}
for it in lhs.iter().zip(rhs.iter()) {
let (ld, rd) = it;
if ld > rd {
return Ordering::Greater;
} else if ld < rd {
return Ordering::Less;
}
}
Ordering::Equal
}
impl Ord for Bigint {
fn cmp(&self, other: &Bigint) -> Ordering {
if self.sign != other.sign {
if self.sign == -1 {
return Ordering::Less;
}
return Ordering::Greater;
}
if self.sign == -1 {
return cmp_digits(&self.digits, &other.digits).reverse();
}
cmp_digits(&self.digits, &other.digits)
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut result: Vec<u8> = Vec::new();
let l_len = left.len();
let r_len = right.len();
left.reverse();
right.reverse();
if l_len < r_len {
let mut zeroes = vec![0; r_len - l_len];
left.append(&mut zeroes);
}
if l_len > r_len {
let mut zeroes = vec![0; l_len - r_len];
right.append(&mut zeroes);
}
let mut carry_over: u8 = 0;
for it in left.iter().zip(right.iter()) {
let (l, r) = it;
let res = r + l + carry_over;
if res > 9 {
carry_over = 1;
result.push(res - 10);
} else {
carry_over = 0;
result.push(res);
}
}
if carry_over == 1 {
result.push(1);
}
result.reverse();
result
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
let mut result: Vec<u8> = Vec::new();
larger.reverse();
smaller.reverse();
let mut zeroes = vec![0; larger.len() - smaller.len()];
smaller.append(&mut zeroes);
let mut carry_over = 0;
for it in larger.iter().zip(smaller.iter()) {
let (l, r) = it;
if l < &(r + carry_over) {
result.push(l + 10 - r - carry_over);
carry_over = 1;
} else {
result.push(l - r - carry_over);
carry_over = 0;
}
}
if *result.last().unwrap() == 0 {
result.pop();
}
result.reverse();
result
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
return Bigint::from_components(add_digits(self.digits, other.digits), self.sign);
}
match cmp_digits(&self.digits, &other.digits) {
Ordering::Greater => {
Bigint::from_components(subtract_digits(self.digits, other.digits), self.sign)
}
Ordering::Less => {
Bigint::from_components(subtract_digits(other.digits, self.digits), other.sign)
}
Ordering::Equal => Bigint::new(),
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let rhs = Bigint::from_components(other.digits, -other.sign);
self + rhs
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-w47uip/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.70s
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