Решение на Bigint от Васил Папукчиев
Към профила на Васил Папукчиев
Резултати
- 11 точки от тестове
- 0 бонус точки
- 11 точки общо
- 11 успешни тест(а)
- 4 неуспешни тест(а)
Код
#[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 {
if sign != 1 && sign != -1 {
panic!();
}
if digits.len() == 1 && digits[0] == 0 {
return Bigint::new();
}
let mut trimed_digits: Vec<u8> = Vec::new();
let mut should_add = false;
for digit in digits {
if digit == 0 {
if should_add {
trimed_digits.push(digit);
}
}
else {
should_add = true;
trimed_digits.push(digit);
}
}
Bigint { sign, digits: trimed_digits }
}
pub fn is_positive(&self) -> bool {
match self.sign {
1 => true,
-1 => false,
_ => panic!(),
}
}
pub fn is_negative(&self) -> bool {
match self.sign {
1 => false,
-1 => true,
_ => panic!(),
}
}
}
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> {
if s.is_empty() {
return Ok(Bigint::new());
}
let first_char = s.chars().next().unwrap();
let sign: i8;
let mut first_trimed_s = s;
match first_char {
'-' => { sign = -1; first_trimed_s = &s[1..] },
'+' => { sign = 1; first_trimed_s = &s[1..] },
_ => sign = 1
}
let trimed_s = first_trimed_s.trim_start_matches('0');
if trimed_s.is_empty() {
Ok(Bigint::new())
}
else {
let mut digits: Vec<u8> = Vec::new();
for single_char in trimed_s.chars() {
if single_char.is_digit(10) {
digits.push(single_char.to_digit(10).unwrap() 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 {
let mut ordering = Ordering::Equal;
if self.sign != other.sign {
ordering = self.sign.cmp(&other.sign);
}
else {
let first_length = self.digits.len();
let second_length = other.digits.len();
if first_length != second_length {
ordering = first_length.cmp(&second_length);
}
else {
for i in 0..first_length {
if self.digits[i] != other.digits[i] {
ordering = self.digits[i].cmp(&other.digits[i]);
break;
}
}
}
}
if self.sign == -1 && other.sign == -1 {
match ordering {
Ordering::Less => return Ordering::Greater,
Ordering::Greater => return Ordering::Less,
_ => return Ordering::Equal,
}
}
ordering
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
let mut digits: Vec<u8> = Vec::new();
let mut bigger_number: Vec<u8>;
let mut smaller_number: Vec<u8>;
if self > other {
bigger_number = self.digits.clone();
bigger_number.reverse();
smaller_number = other.digits.clone();
smaller_number.reverse();
}
else {
bigger_number = other.digits.clone();
bigger_number.reverse();
smaller_number = self.digits.clone();
smaller_number.reverse();
}
let mut should_add_one = false;
for i in 0..bigger_number.len() {
let first_number = bigger_number[i];
let second_number: u8;
if i < smaller_number.len() {
second_number = smaller_number[i];
}
else {
second_number = 0;
}
let number: u8;
let add_number = should_add_one as u8;
if first_number + add_number + second_number > 9 {
number = first_number + add_number + second_number - 10;
should_add_one = true;
}
else {
number = first_number + add_number + second_number;
should_add_one = false;
}
digits.push(number);
}
if should_add_one {
digits.push(1);
}
digits.reverse();
Bigint::from_components(digits, self.sign)
}
else {
let mut digits: Vec<u8> = Vec::new();
let sign: i8;
let mut bigger_number: Vec<u8>;
let mut smaller_number: Vec<u8>;
if Bigint::from_components(self.digits.clone(), 1) > Bigint::from_components(other.digits.clone(), 1) {
bigger_number = self.digits.clone();
bigger_number.reverse();
smaller_number = other.digits.clone();
smaller_number.reverse();
sign = self.sign;
}
else if Bigint::from_components(self.digits.clone(), 1) < Bigint::from_components(other.digits.clone(), 1) {
bigger_number = other.digits.clone();
bigger_number.reverse();
smaller_number = self.digits.clone();
smaller_number.reverse();
sign = other.sign;
}
else {
return Bigint::new();
}
let mut should_sub_one = false;
for i in 0..bigger_number.len() {
let first_number = bigger_number[i];
let second_number: u8;
if i < smaller_number.len() {
second_number = smaller_number[i];
}
else {
second_number = 0;
}
let number: u8;
let sub_number: u8 = should_sub_one as u8;
if first_number - sub_number < second_number {
number = 10 + first_number - sub_number - second_number;
should_sub_one = true;
}
else {
number = first_number - sub_number - second_number;
should_sub_one = false;
}
digits.push(number);
}
digits.reverse();
Bigint::from_components(digits, sign)
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + Bigint::from_components(other.digits, other.sign * -1)
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-1tu2mm5/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.63s
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 ... FAILED
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 ... 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 ... FAILED
test solution_test::test_sum_4_negative ... FAILED
failures:
---- solution_test::test_bigint_zero_sign stdout ----
thread 'main' panicked at 'assertion failed: !zero.is_positive()', tests/solution_test.rs:21: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:250:20
---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: -1, digits: [1, 0] }`,
right: `Bigint { sign: -1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:100:5
---- solution_test::test_sum_4_negative stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `Bigint { sign: -1, digits: [1, 2] }`,
right: `Bigint { sign: -1, digits: [1, 2, 0, 1, 2] }`', tests/solution_test.rs:113:5
failures:
solution_test::test_bigint_zero_sign
solution_test::test_sub_3_carry
solution_test::test_sum_3_overflow
solution_test::test_sum_4_negative
test result: FAILED. 11 passed; 4 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'