Решение на Bigint от Мартин Дацев
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-1qyd44t/solution)
Finished test [unoptimized + debuginfo] target(s) in 2.27s
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 версии и 1 коментар)
Мартин качи решение на 27.11.2020 12:14 (преди почти 5 години)
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint{sign: 0, digits: vec![0]}
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
let mut digits_trimmed = Vec::<u8>::new();
let mut started = false;
for &d in digits.iter().rev() {
if d == 0 && !started {
continue;
}
started = true;
digits_trimmed.push(d);
}
digits_trimmed.reverse();
if digits_trimmed.len() == 0 {
Bigint{sign: 0, digits: vec![0]}
} else {
Bigint{sign, digits: digits_trimmed}
}
}
pub fn is_positive(&self) -> bool {
self.sign > 0
}
pub fn is_negative(&self) -> bool {
self.sign < 0
}
fn abs(&self) -> Self {
Bigint::from_components(self.digits.clone(), self.sign.abs())
}
}
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> {
let mut digits: Vec<u8> = vec![];
let mut sign: i8 = 1;
for (i, c) in s.chars().rev().enumerate() {
if i == s.len() - 1 {
match c {
'-' => { sign = -1; break; }
'+' => { sign = 1; break; }
_ => { sign = 1; }
}
}
if let Some(digit) = c.to_digit(10) {
digits.push(digit as u8);
} else {
return Err(ParseError{});
}
}
Ok(Bigint::from_components(digits, sign))
}
Хитро решение да минеш в обратната посока за знака, добре си го измислил.
}
use std::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.sign != other.sign {
return self.sign.cmp(&other.sign);
}
let s = self.sign;
if s == 0 {
return Ordering::Equal;
}
let count_ord : Ordering = self.digits.len().cmp(&other.digits.len());
- if count_ord != Ordering::Equal {
+ if count_ord != Ordering::Equal {
if s < 0 {
return count_ord.reverse();
}
return count_ord;
}
let len = self.digits.len();
for i in (0..len).rev() {
let dig_ord : Ordering = self.digits[i].cmp(&other.digits[i]);
if dig_ord != Ordering::Equal {
if s < 0 {
return dig_ord.reverse();
}
return dig_ord;
}
}
Ordering::Equal
}
}
-impl std::fmt::Display for Bigint {
- fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
- let mut s = (if self.sign < 0 { "-" } else { "" }).to_owned();
-
- for d in self.digits.iter().rev() {
- s.push_str(&d.to_string());
- }
-
- write!(f, "{}", s)
- }
-}
-
use std::ops::{Add, Sub, Neg};
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 {
let mut a = self;
let mut b = other;
if b.abs() > a.abs() {
std::mem::swap(&mut a, &mut b);
}
let sign =
if a.sign < 0 {
a = -a;
b = -b;
-1
} else {
1
};
let max_len = std::cmp::max(a.digits.len(), b.digits.len()) + 1;
let mut result = Vec::<u8>::new();
let mut carry = 0;
for i in 0..max_len {
-
- let d1 = if i >= a.digits.len() { 0 } else { a.digits[i] as i8 * a.sign };
- let d2 = if i >= b.digits.len() { 0 } else { b.digits[i] as i8 * b.sign };
+ let d1 = *a.digits.get(i).unwrap_or(&0) as i8 * a.sign;
+ let d2 = *b.digits.get(i).unwrap_or(&0) as i8 * b.sign;
let d = d1 + d2 + carry + 10;
- carry = -1;
-
- if d > 0 {
- result.push((d % 10) as u8);
- }
-
- carry += d / 10;
+ result.push((d % 10) as u8);
+ carry = d / 10 - 1;
}
Bigint::from_components(result, sign)
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + (-other)
}
}
Хитро решение да минеш в обратната посока за знака, добре си го измислил.