Решение на 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(digits: Vec<u8>, sign: i8) -> Self {
if digits.len() == 0 {
return Bigint::new();
}
let mut n_digits: Vec<u8> = Vec::new();
let mut non_zero_integer = false;
let mut iterator = digits.iter();
let mut current_digit = iterator.next();
while current_digit != None {
match current_digit {
Some(&0) => {
match non_zero_integer {
true => {
&n_digits.push(0);
current_digit = iterator.next();
}
false => {
current_digit = iterator.next();
}
}
}
Some(&number @1..=9) => {
non_zero_integer = true;
&n_digits.push(number);
current_digit = iterator.next();
}
_ => panic!{"Iterator out of bounds."}
}
}
if current_digit == None && non_zero_integer == false {
return Bigint::new();
} else {
return Bigint{sign: sign, digits: n_digits};
}
}
pub fn is_positive(&self) -> bool {
if self.sign == 1 {
if self.digits == vec![0] {
return false;
} else {
return true;
}
} else {
return false;
}
}
pub fn is_negative(&self) -> bool {
if self.digits == vec![0] {
return false;
} else {
return !self.is_positive();
}
}
}
//helper function for parse
fn is_digit(c: char) -> bool {
return c >= '0' && c <= '9';
}
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.len() == 0 {
return Ok(Bigint::new());
}
let mut n_digits: Vec<u8> = Vec::new();
let mut n_sign: i8 = 1;
let mut iterator = s.chars();
let first_char = iterator.next();
match first_char {
Some('+') => n_sign = 1,
Some('-') => n_sign = -1,
Some(x) => {
if is_digit(x) {
let op_digit: Option<u32> = x.to_digit(10);
match op_digit {
Some(x) => n_digits.push(x as u8),
_ => return Err(ParseError)
}
} else {
return Err(ParseError);
}
},
_ => return Err(ParseError)
}
let mut current_char = iterator.next();
while current_char != None {
match current_char {
Some(x) => {
if is_digit(x) {
let op_digit: Option<u32> = x.to_digit(10);
match op_digit {
Some(x) => n_digits.push(x as u8),
_ => return Err(ParseError)
}
current_char = iterator.next();
} else {
return Err(ParseError);
}
}
_ => return Err(ParseError)
}
}
let big_int: Bigint = Bigint::from_components(n_digits, n_sign);
return Ok(big_int);
}
}
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 sign_comparison: Ordering = self.sign.cmp(&other.sign);
if sign_comparison == Ordering::Less {
return Ordering::Less;
} else if sign_comparison == Ordering::Greater {
return Ordering::Greater;
} else {
let length_comparison: Ordering = self.digits.len().cmp(&other.digits.len());
if length_comparison == Ordering::Less {
if self.sign == 1 {
return Ordering::Less;
} else {
return Ordering::Greater;
}
} else if length_comparison == Ordering::Greater {
if self.sign == 1 {
return Ordering::Greater;
} else {
return Ordering::Less;
}
} else {
let length = self.digits.len();
if self.sign == 1 {
for i in 0..length {
let digit_comparison = self.digits[i].cmp(&other.digits[i]);
if digit_comparison == Ordering::Greater {
return Ordering::Greater;
} else if digit_comparison == Ordering::Less {
return Ordering::Less;
}
}
return Ordering::Equal;
} else {
for i in 0..length {
let digit_comparison = self.digits[i].cmp(&other.digits[i]);
if digit_comparison == Ordering::Greater {
return Ordering::Less;
} else if digit_comparison == Ordering::Less {
return Ordering::Greater;
}
}
return Ordering::Equal;
}
}
}
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut result: Vec<u8> = Vec::new();
left.reverse();
right.reverse();
let len_lhs: usize = left.len();
let len_rhs: usize = right.len();
if len_lhs != len_rhs {
let difference: isize = ((len_lhs as isize) - (len_rhs as isize)).abs();
if len_lhs < len_rhs {
for _ in 0..difference {
left.push(0);
}
} else {
for _ in 0..difference {
right.push(0);
}
}
}
let current_length: usize = left.len();
let mut carry_forward_digit: u8 = 0;
let mut current_result: u8;
for i in 0..current_length {
current_result = left[i] + right[i] + carry_forward_digit;
if current_result <= 9 {
result.push(current_result);
carry_forward_digit = 0;
} else {
result.push(current_result % 10);
carry_forward_digit = 1;
if i == current_length - 1 {
result.push(1);
}
}
}
result.reverse();
return 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 len_larger: usize = larger.len();
let len_smaller: usize = smaller.len();
if len_larger != len_smaller {
let difference: usize = len_larger - len_smaller;
for _ in 0..difference {
smaller.push(0);
}
}
let mut carry_forward_digit: u8 = 0;
let mut current_result: i8;
for i in 0..len_larger {
current_result = (larger[i] as i8) - (smaller[i] as i8) - (carry_forward_digit as i8);
if current_result >= 0 {
if current_result == 0 && i == len_larger - 1 {
carry_forward_digit = 0;
} else {
result.push(current_result as u8);
carry_forward_digit = 0;
}
} else {
current_result = ((larger[i] + 10) as i8) - (smaller[i] as i8) - (carry_forward_digit as i8);
carry_forward_digit = 1;
result.push(current_result as u8);
}
}
result.reverse();
return result;
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
let result: Vec<u8> = add_digits(self.digits, other.digits);
let mut sign: i8 = 1;
if self.sign == -1 {
sign = -1;
}
let bigint: Bigint = Bigint::from_components(result, sign);
return bigint;
} else {
//different signs
let lhs: Vec<u8> = self.digits.clone();
let rhs: Vec<u8> = other.digits.clone();
let sign: i8 = 1;
let lhs_bigint: Bigint = Bigint::from_components(self.digits, sign);
let rhs_bigint: Bigint = Bigint::from_components(other.digits, sign);
let result: Vec<u8>;
if lhs_bigint > rhs_bigint {
result = subtract_digits(lhs, rhs);
let bigint: Bigint = Bigint::from_components(result, self.sign);
return bigint;
} else if lhs_bigint < rhs_bigint {
result = subtract_digits(rhs, lhs);
let bigint: Bigint = Bigint::from_components(result, other.sign);
return bigint;
} else {
return Bigint::new();
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let rhs_bigint: Bigint;
match other.sign {
1 => rhs_bigint = Bigint::from_components(other.digits, -1),
-1 => rhs_bigint = Bigint::from_components(other.digits, 1),
_ => panic!("Unexpected sign")
}
let result: Bigint = self + rhs_bigint;
return result;
}
}

Лог от изпълнението

Compiling solution v0.1.0 (/tmp/d20201127-2274206-18lc4ib/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.61s
     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 коментара)

Ася качи първо решение на 27.11.2020 09:07 (преди 8 месеца)

Ася качи решение на 27.11.2020 16:51 (преди 8 месеца)

#[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(digits: Vec<u8>, sign: i8) -> Self {
if digits.len() == 0 {
return Bigint::new();
}
let mut n_digits: Vec<u8> = Vec::new();
let mut non_zero_integer = false;
let mut iterator = digits.iter();
let mut current_digit = iterator.next();
while current_digit != None {
match current_digit {
Some(&0) => {
match non_zero_integer {
true => {
&n_digits.push(0);
current_digit = iterator.next();
}
false => {
current_digit = iterator.next();
}
}
}
Some(&number @1..=9) => {
non_zero_integer = true;
&n_digits.push(number);
current_digit = iterator.next();
}
_ => panic!{"Iterator out of bounds."}
}
}
if current_digit == None && non_zero_integer == false {
return Bigint::new();
} else {
return Bigint{sign: sign, digits: n_digits};
}
}
pub fn is_positive(&self) -> bool {
if self.sign == 1 {
- if self.digits[0] == 0 {
+ if self.digits == vec![0] {
return false;
} else {
return true;
}
} else {
return false;
}
}
pub fn is_negative(&self) -> bool {
- if self.digits[0] == 0 {
+ if self.digits == vec![0] {
return false;
} else {
return !self.is_positive();
}
}
}
//helper function for parse
fn is_digit(c: char) -> bool {
return c >= '0' && c <= '9';
}
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.len() == 0 {
return Ok(Bigint::new());
}
let mut n_digits: Vec<u8> = Vec::new();
let mut n_sign: i8 = 1;
let mut iterator = s.chars();
let first_char = iterator.next();
match first_char {
Some('+') => n_sign = 1,
Some('-') => n_sign = -1,
Some(x) => {
if is_digit(x) {
let op_digit: Option<u32> = x.to_digit(10);
match op_digit {
Some(x) => n_digits.push(x as u8),
_ => return Err(ParseError)
}
} else {
return Err(ParseError);
}
},
_ => return Err(ParseError)
}
let mut current_char = iterator.next();
while current_char != None {
match current_char {
Some(x) => {
if is_digit(x) {
let op_digit: Option<u32> = x.to_digit(10);
match op_digit {
Some(x) => n_digits.push(x as u8),
_ => return Err(ParseError)
}
current_char = iterator.next();
} else {
return Err(ParseError);
}
}
_ => return Err(ParseError)
}
}
let big_int: Bigint = Bigint::from_components(n_digits, n_sign);
return Ok(big_int);
}
}
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 sign_comparison: Ordering = self.sign.cmp(&other.sign);
if sign_comparison == Ordering::Less {
return Ordering::Less;
} else if sign_comparison == Ordering::Greater {
return Ordering::Greater;
} else {
let length_comparison: Ordering = self.digits.len().cmp(&other.digits.len());
if length_comparison == Ordering::Less {
if self.sign == 1 {
return Ordering::Less;
} else {
return Ordering::Greater;
}
} else if length_comparison == Ordering::Greater {
if self.sign == 1 {
return Ordering::Greater;
} else {
return Ordering::Less;
}
} else {
let length = self.digits.len();
if self.sign == 1 {
for i in 0..length {
let digit_comparison = self.digits[i].cmp(&other.digits[i]);
if digit_comparison == Ordering::Greater {
return Ordering::Greater;
} else if digit_comparison == Ordering::Less {
return Ordering::Less;
}
}
return Ordering::Equal;
} else {
for i in 0..length {
let digit_comparison = self.digits[i].cmp(&other.digits[i]);
if digit_comparison == Ordering::Greater {
return Ordering::Less;
} else if digit_comparison == Ordering::Less {
return Ordering::Greater;
}
}
return Ordering::Equal;
}
}
}
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut result: Vec<u8> = Vec::new();
left.reverse();
right.reverse();
let len_lhs: usize = left.len();
let len_rhs: usize = right.len();
if len_lhs != len_rhs {
let difference: isize = ((len_lhs as isize) - (len_rhs as isize)).abs();
if len_lhs < len_rhs {
for _ in 0..difference {
left.push(0);
}
} else {
for _ in 0..difference {
right.push(0);
}
}
}
let current_length: usize = left.len();
let mut carry_forward_digit: u8 = 0;
let mut current_result: u8;
for i in 0..current_length {
current_result = left[i] + right[i] + carry_forward_digit;
if current_result <= 9 {
result.push(current_result);
carry_forward_digit = 0;
} else {
result.push(current_result % 10);
carry_forward_digit = 1;
if i == current_length - 1 {
result.push(1);
}
}
}
result.reverse();
return 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 len_larger: usize = larger.len();
let len_smaller: usize = smaller.len();
if len_larger != len_smaller {
let difference: usize = len_larger - len_smaller;
for _ in 0..difference {
smaller.push(0);
}
}
let mut carry_forward_digit: u8 = 0;
let mut current_result: i8;
for i in 0..len_larger {
current_result = (larger[i] as i8) - (smaller[i] as i8) - (carry_forward_digit as i8);
if current_result >= 0 {
if current_result == 0 && i == len_larger - 1 {
carry_forward_digit = 0;
} else {
result.push(current_result as u8);
carry_forward_digit = 0;
}
} else {
current_result = ((larger[i] + 10) as i8) - (smaller[i] as i8) - (carry_forward_digit as i8);
carry_forward_digit = 1;
result.push(current_result as u8);
}
}
result.reverse();
return result;
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
let result: Vec<u8> = add_digits(self.digits, other.digits);
let mut sign: i8 = 1;
if self.sign == -1 {
sign = -1;
}
let bigint: Bigint = Bigint::from_components(result, sign);
return bigint;
} else {
//different signs
let lhs: Vec<u8> = self.digits.clone();
let rhs: Vec<u8> = other.digits.clone();
let sign: i8 = 1;
let lhs_bigint: Bigint = Bigint::from_components(self.digits, sign);
let rhs_bigint: Bigint = Bigint::from_components(other.digits, sign);
let result: Vec<u8>;
if lhs_bigint > rhs_bigint {
result = subtract_digits(lhs, rhs);
let bigint: Bigint = Bigint::from_components(result, self.sign);
return bigint;
} else if lhs_bigint < rhs_bigint {
result = subtract_digits(rhs, lhs);
let bigint: Bigint = Bigint::from_components(result, other.sign);
return bigint;
} else {
return Bigint::new();
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
let rhs_bigint: Bigint;
match other.sign {
1 => rhs_bigint = Bigint::from_components(other.digits, -1),
-1 => rhs_bigint = Bigint::from_components(other.digits, 1),
_ => panic!("Unexpected sign")
}
let result: Bigint = self + rhs_bigint;
return result;
}
}