Решение на Bigint от Илиян Руйков
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign : 1,
digits : vec![0]
}
}
fn from_components(input: &str) -> Self {
let mut curr_sign: i8 = 1;
let mut met_nonzero = false;
let mut number = Vec::<u8>::new();
for index in input.chars() {
if index == '-' {
curr_sign = -1;
continue;
}
if index == '0' && met_nonzero == false {
continue;
}
else {
met_nonzero = true;
}
match index {
'0' => number.push(0),
'1' => number.push(1),
'2' => number.push(2),
'3' => number.push(3),
'4' => number.push(4),
'5' => number.push(5),
'6' => number.push(6),
'7' => number.push(7),
'8' => number.push(8),
'9' => number.push(9),
_ => continue,
}
}
if number.is_empty(){
number.push(0);
curr_sign = 1;
}
Bigint {sign: curr_sign, digits: number}
}
pub fn is_positive(&self) -> bool {
if self.sign == 1 && self.digits[0] != 0 {
true
}
else {
false
}
}
pub fn is_negative(&self) -> bool {
if self.sign == -1 && self.digits[0] != 0 {
true
}
else {
false
}
}
fn add_digits(left: &Vec<u8>, right: &Vec<u8>) -> Vec<u8> {
let length_left = left.len();
let length_right = right.len();
let longer: usize;
if length_left > length_right {
longer = length_left;
}
else {
longer = length_right;
}
let mut output: Vec<u8> = vec![0; longer];
let mut remainder: u8 = 0;
let mut current_left: u8;
let mut current_right: u8;
let mut current: u8;
for i in 0..longer {
current_left = 0;
current_right = 0;
if i < length_left {
current_left = left[length_left - i - 1];
}
if i < length_right {
current_right = right[length_right - i - 1];
}
current = current_left + current_right + remainder;
if current >= 10 {
remainder = 1;
}
else {
remainder = 0;
}
output[longer - i -1] = current % 10;
}
if remainder == 1 {
let mut add_remainder: Vec<u8> = vec![1];
add_remainder.append(&mut output);
return add_remainder
}
output
}
fn subtract_digits(larger: &Vec<u8>, smaller: &Vec<u8>) -> Vec<u8> {
let length = larger.len();
let length_smaller = smaller.len();
let mut output: Vec<u8> = vec![0; length];
let mut remainder: u8 = 0;
let mut current: u8;
let mut current_left: u8;
let mut current_right: u8;
for i in 0..length {
current_right = 0;
current_left = larger[length - i - 1];
if i < length_smaller {
current_right = smaller[length_smaller - i -1];
}
if current_left < (current_right + remainder) {
current = 10 + current_left - current_right - remainder;
remainder = 1;
}
else {
current = current_left - current_right - remainder;
remainder = 0;
}
output[length - i -1] = current;
}
let mut met_nonzero = false;
let mut filtered_output = Vec::<u8>::new();
for i in 0..length {
if output[i] == 0 && met_nonzero == false {
continue;
}
if output[i] != 0 {
met_nonzero = true;
}
filtered_output.push(output[i]);
}
filtered_output
}
fn larger_by_module(left: &Vec<u8>, right: &Vec<u8>) -> bool {
if left.len() > right.len() {
return true
}
if left.len() == right.len(){
let length = left.len();
for i in 0..length{
if left[i] > right[i] {
return true
}
}
}
false
}
}
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 length = s.chars().count();
if length == 0 {
return Ok(Bigint::new())
}
let mut iter = s.chars().into_iter();
let mut current = 0;
while let Some(index) = iter.next() {
if length == 1 && (index < '0' || index > '9') {
return Err(ParseError)
}
if (index < '0' || index > '9') && (current != 0 || (index != '+' && index != '-')) {
return Err(ParseError)
}
current += 1;
}
Ok(Bigint::from_components(s))
}
}
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)
}
if self.sign == 1 {
if self.digits.len() != other.digits.len(){
return self.digits.len().cmp(&other.digits.len())
}
else {
for i in 0..self.digits.len() {
if self.digits[i] != other.digits[i] {
return self.digits[i].cmp(&other.digits[i])
}
}
return Ordering::Equal
}
}
else {
if self.digits.len() != other.digits.len(){
return self.digits.len().cmp(&other.digits.len()).reverse()
}
else {
for i in 0..self.digits.len() {
if self.digits[i] != other.digits[i] {
return self.digits[i].cmp(&other.digits[i]).reverse()
}
}
return Ordering::Equal
}
}
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let output_digits: Vec<u8>;
let mut output_sign: i8 = 1;
if self.sign == other.sign {
if self.sign == -1 {
output_sign = -1;
}
output_digits = Bigint::add_digits(&self.digits, &other.digits);
return Bigint{sign: output_sign, digits: output_digits,}
}
else {
if Bigint::larger_by_module(&self.digits, &other.digits) {
output_digits = Bigint::subtract_digits(&self.digits, &other.digits);
output_sign = self.sign;
return Bigint {sign: output_sign, digits: output_digits,}
}
else {
if Bigint::larger_by_module(&other.digits, &self.digits){
output_digits = Bigint::subtract_digits(&other.digits, &self.digits);
output_sign = other.sign;
return Bigint {sign: output_sign, digits: output_digits,}
}
else {
output_sign = 1;
output_digits = vec![0];
}
}
}
Bigint {sign: output_sign, digits: output_digits,}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let copy_other = Bigint {sign: other.sign*(-1), digits: other.digits.clone(),};
self.add(copy_other)
}
}
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-bgn6bh/solution)
Finished test [unoptimized + debuginfo] target(s) in 1.95s
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