Програмиране с Rust

Курс във Факултета по Математика и Информатика към СУ

Решение на Bigint от Борислав Димитров

Обратно към всички решения

Към профила на Борислав Димитров

Резултати

  • 15 точки от тестове
  • 0 бонус точки
  • 15 точки общо
  • 15 успешни тест(а)
  • 0 неуспешни тест(а)

Код

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_components1(digits: Vec<u8>, sign: i8) -> Self {
if let Some(n) = digits.iter().position(|&x| x != 0) {
Bigint{
sign: sign,
digits: digits[n..].to_vec()
}
} else {
Bigint::new()
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.digits[0] != 0
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.digits[0] != 0
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s == "+" || s == "-" {
Err(ParseError)
} else {
let mut vec = Vec::new();
let mut str_iter = s.as_bytes().iter().peekable();
let sign: i8;
if str_iter.peek() == Some(&&45) {
sign = -1;
str_iter.next();
} else if str_iter.peek() == Some(&&43) {
sign = 1;
str_iter.next();
} else {
sign = 1;
}
let mut flag: bool = false;
for curr_char in str_iter {
if *curr_char >= 48 && *curr_char <= 57 {
vec.push(*curr_char-48);
}
else {
flag = true;
break;
}
}
if flag {
Err(ParseError)
} else {
Ok(Bigint::from_components1(vec, 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 {
match (self.sign, other.sign) {
( 1,-1) => Ordering::Greater,
(-1, 1) => Ordering::Less,
( 1, 1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
let self_iter = self.digits.iter().peekable();
let mut other_iter = other.digits.iter().peekable();
for curr_self in self_iter {
if curr_self < *other_iter.peek().unwrap() {
flag = -1;
break;
} else if curr_self > *other_iter.peek().unwrap() {
flag = 1;
break;
} else {
flag = 0;
}
other_iter.next();
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
self.digits.len().cmp(&other.digits.len())
}
}
(-1,-1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
let self_iter = self.digits.iter().peekable();
let mut other_iter = other.digits.iter().peekable();
for curr_self in self_iter {
if curr_self > *other_iter.peek().unwrap() {
flag = -1;
break;
} else if curr_self < *other_iter.peek().unwrap() {
flag = 1;
break;
} else {
flag = 0;
}
other_iter.next();
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
other.digits.len().cmp(&self.digits.len())
}
},
( _, _) => unreachable!()
}
}
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
match left.len().cmp(&right.len()) {
Ordering::Less => {
let mut res_size = right.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
for curr_right in iter_right {
res_size-= 1;
if curr_right + carry >= 10 {
res[res_size] = curr_right + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Greater => {
let mut res_size = left.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let mut iter_left = left.iter().rev().peekable();
let iter_right = right.iter().rev();
let mut carry: u8 = 0;
for curr_right in iter_right {
res_size -= 1;
if curr_right + *iter_left.peek().unwrap() + carry >= 10 {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry;
carry = 0;
}
iter_left.next();
}
for curr_left in iter_left {
res_size -= 1;
if curr_left + carry >= 10 {
res[res_size] = curr_left + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Equal => {
let mut res_size = right.len() + 1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
}
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut res_size = larger.len();
let mut res: Vec<u8> = vec![0;res_size];
let iter_larger = larger.iter().rev();
let mut iter_smaller = smaller.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_larger in iter_larger {
res_size -= 1;
if iter_smaller.peek() != None {
if 10 + curr_larger - *iter_smaller.peek().unwrap() - carry < 10 {
res[res_size] = 10 + curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 1;
} else {
res[res_size] = curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 0;
}
iter_smaller.next();
} else {
if 10 + curr_larger - carry < 10 {
res[res_size] = 10 + curr_larger - carry;
carry = 1;
} else {
res[res_size] = curr_larger - carry;
carry = 0;
}
}
}
res
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
match (self.sign,other.sign) {
( 1, 1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), 1)
},
(-1,-1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), -1)
},
(-1, 1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), 1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), -1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), 1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), -1),
_ => Bigint::new()
}
}
}
},
( 1,-1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), -1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), 1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), -1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), 1),
_ => Bigint::new()
}
}
}
}
( _, _) => unreachable!()
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + Bigint::from_components1(other.digits, other.sign*(-1))
}
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-1n1bqv5/solution)
    Finished test [unoptimized + debuginfo] target(s) in 1.73s
     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

История (5 версии и 0 коментара)

Борислав качи първо решение на 26.11.2020 13:41 (преди почти 5 години)

Борислав качи решение на 26.11.2020 13:43 (преди почти 5 години)

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_components1(digits: Vec<u8>, sign: i8) -> Self { //performance & clean...
+ fn from_components1(digits: Vec<u8>, sign: i8) -> Self {
if let Some(n) = digits.iter().position(|&x| x != 0) {
Bigint{
sign: sign,
digits: digits[n..].to_vec()
}
} else {
Bigint::new()
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.digits[0] != 0
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.digits[0] != 0
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s == "+" || s == "-" {
Err(ParseError)
} else {
let mut vec = Vec::new();
let mut str_iter = s.as_bytes().iter().peekable();
let sign: i8;
if str_iter.peek() == Some(&&45) {
sign = -1;
str_iter.next();
} else if str_iter.peek() == Some(&&43) {
sign = 1;
str_iter.next();
} else {
sign = 1;
}
let mut flag: bool = false;
for curr_char in str_iter {
if *curr_char >= 48 && *curr_char <= 57 {
vec.push(*curr_char-48);
}
else {
flag = true;
break;
}
}
if flag {
Err(ParseError)
} else {
Ok(Bigint::from_components1(vec, 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 {
match (self.sign, other.sign) {
( 1,-1) => Ordering::Greater,
(-1, 1) => Ordering::Less,
( 1, 1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
self.digits.len().cmp(&other.digits.len())
}
}
( _, _) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self > *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self < *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
other.digits.len().cmp(&self.digits.len())
}
}
}
}
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
match left.len().cmp(&right.len()) {
Ordering::Less => {
let mut res_size = right.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
for curr_right in iter_right {
res_size-= 1;
if curr_right + carry >= 10 {
res[res_size] = curr_right + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Greater => {
let mut res_size = left.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let mut iter_left = left.iter().rev().peekable();
let iter_right = right.iter().rev();
let mut carry: u8 = 0;
for curr_right in iter_right {
res_size -= 1;
if curr_right + *iter_left.peek().unwrap() + carry >= 10 {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry;
carry = 0;
}
iter_left.next();
}
for curr_left in iter_left {
res_size -= 1;
if curr_left + carry >= 10 {
res[res_size] = curr_left + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Equal => {
let mut res_size = right.len() + 1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
}
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut res_size = larger.len();
let mut res: Vec<u8> = vec![0;res_size];
let iter_larger = larger.iter().rev();
let mut iter_smaller = smaller.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_larger in iter_larger {
res_size -= 1;
if iter_smaller.peek() != None {
if 10 + curr_larger - *iter_smaller.peek().unwrap() - carry < 10 {
res[res_size] = 10 + curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 1;
} else {
res[res_size] = curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 0;
}
iter_smaller.next();
} else {
if 10 + curr_larger - carry < 10 {
res[res_size] = 10 + curr_larger - carry;
carry = 1;
} else {
res[res_size] = curr_larger - carry;
carry = 0;
}
}
}
res
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
match (self.sign,other.sign) {
( 1, 1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), 1)
},
(-1,-1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), -1)
},
(-1, 1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), 1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), -1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), 1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), -1),
_ => Bigint::new()
}
}
}
},
( 1,-1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), -1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), 1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), -1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), 1),
_ => Bigint::new()
}
}
}
}
( _, _) => {Bigint::new()}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + Bigint::from_components1(other.digits, other.sign*(-1))
}
}

Борислав качи решение на 26.11.2020 14:35 (преди почти 5 години)

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_components1(digits: Vec<u8>, sign: i8) -> Self {
if let Some(n) = digits.iter().position(|&x| x != 0) {
Bigint{
sign: sign,
digits: digits[n..].to_vec()
}
} else {
Bigint::new()
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.digits[0] != 0
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.digits[0] != 0
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s == "+" || s == "-" {
Err(ParseError)
} else {
let mut vec = Vec::new();
let mut str_iter = s.as_bytes().iter().peekable();
let sign: i8;
if str_iter.peek() == Some(&&45) {
sign = -1;
str_iter.next();
} else if str_iter.peek() == Some(&&43) {
sign = 1;
str_iter.next();
} else {
sign = 1;
}
let mut flag: bool = false;
for curr_char in str_iter {
if *curr_char >= 48 && *curr_char <= 57 {
vec.push(*curr_char-48);
}
else {
flag = true;
break;
}
}
if flag {
Err(ParseError)
} else {
Ok(Bigint::from_components1(vec, 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 {
match (self.sign, other.sign) {
( 1,-1) => Ordering::Greater,
(-1, 1) => Ordering::Less,
( 1, 1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
self.digits.len().cmp(&other.digits.len())
}
}
- ( _, _) => {
+ (-1,-1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self > *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self < *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
other.digits.len().cmp(&self.digits.len())
}
- }
+ },
+ ( _, _) => {Ordering::Equal}
}
}
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
match left.len().cmp(&right.len()) {
Ordering::Less => {
let mut res_size = right.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
for curr_right in iter_right {
res_size-= 1;
if curr_right + carry >= 10 {
res[res_size] = curr_right + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Greater => {
let mut res_size = left.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let mut iter_left = left.iter().rev().peekable();
let iter_right = right.iter().rev();
let mut carry: u8 = 0;
for curr_right in iter_right {
res_size -= 1;
if curr_right + *iter_left.peek().unwrap() + carry >= 10 {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry;
carry = 0;
}
iter_left.next();
}
for curr_left in iter_left {
res_size -= 1;
if curr_left + carry >= 10 {
res[res_size] = curr_left + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Equal => {
let mut res_size = right.len() + 1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
}
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut res_size = larger.len();
let mut res: Vec<u8> = vec![0;res_size];
let iter_larger = larger.iter().rev();
let mut iter_smaller = smaller.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_larger in iter_larger {
res_size -= 1;
if iter_smaller.peek() != None {
if 10 + curr_larger - *iter_smaller.peek().unwrap() - carry < 10 {
res[res_size] = 10 + curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 1;
} else {
res[res_size] = curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 0;
}
iter_smaller.next();
} else {
if 10 + curr_larger - carry < 10 {
res[res_size] = 10 + curr_larger - carry;
carry = 1;
} else {
res[res_size] = curr_larger - carry;
carry = 0;
}
}
}
res
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
match (self.sign,other.sign) {
( 1, 1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), 1)
},
(-1,-1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), -1)
},
(-1, 1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), 1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), -1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), 1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), -1),
_ => Bigint::new()
}
}
}
},
( 1,-1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), -1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), 1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), -1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), 1),
_ => Bigint::new()
}
}
}
}
( _, _) => {Bigint::new()}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + Bigint::from_components1(other.digits, other.sign*(-1))
}
}

Борислав качи решение на 26.11.2020 14:42 (преди почти 5 години)

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_components1(digits: Vec<u8>, sign: i8) -> Self {
if let Some(n) = digits.iter().position(|&x| x != 0) {
Bigint{
sign: sign,
digits: digits[n..].to_vec()
}
} else {
Bigint::new()
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.digits[0] != 0
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.digits[0] != 0
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s == "+" || s == "-" {
Err(ParseError)
} else {
let mut vec = Vec::new();
let mut str_iter = s.as_bytes().iter().peekable();
let sign: i8;
if str_iter.peek() == Some(&&45) {
sign = -1;
str_iter.next();
} else if str_iter.peek() == Some(&&43) {
sign = 1;
str_iter.next();
} else {
sign = 1;
}
let mut flag: bool = false;
for curr_char in str_iter {
if *curr_char >= 48 && *curr_char <= 57 {
vec.push(*curr_char-48);
}
else {
flag = true;
break;
}
}
if flag {
Err(ParseError)
} else {
Ok(Bigint::from_components1(vec, 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 {
match (self.sign, other.sign) {
( 1,-1) => Ordering::Greater,
(-1, 1) => Ordering::Less,
( 1, 1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
self.digits.len().cmp(&other.digits.len())
}
}
(-1,-1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self > *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self < *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
other.digits.len().cmp(&self.digits.len())
}
},
- ( _, _) => {Ordering::Equal}
+ ( _, _) => unreachable!()
}
}
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
match left.len().cmp(&right.len()) {
Ordering::Less => {
let mut res_size = right.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
for curr_right in iter_right {
res_size-= 1;
if curr_right + carry >= 10 {
res[res_size] = curr_right + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Greater => {
let mut res_size = left.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let mut iter_left = left.iter().rev().peekable();
let iter_right = right.iter().rev();
let mut carry: u8 = 0;
for curr_right in iter_right {
res_size -= 1;
if curr_right + *iter_left.peek().unwrap() + carry >= 10 {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry;
carry = 0;
}
iter_left.next();
}
for curr_left in iter_left {
res_size -= 1;
if curr_left + carry >= 10 {
res[res_size] = curr_left + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Equal => {
let mut res_size = right.len() + 1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
}
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut res_size = larger.len();
let mut res: Vec<u8> = vec![0;res_size];
let iter_larger = larger.iter().rev();
let mut iter_smaller = smaller.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_larger in iter_larger {
res_size -= 1;
if iter_smaller.peek() != None {
if 10 + curr_larger - *iter_smaller.peek().unwrap() - carry < 10 {
res[res_size] = 10 + curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 1;
} else {
res[res_size] = curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 0;
}
iter_smaller.next();
} else {
if 10 + curr_larger - carry < 10 {
res[res_size] = 10 + curr_larger - carry;
carry = 1;
} else {
res[res_size] = curr_larger - carry;
carry = 0;
}
}
}
res
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
match (self.sign,other.sign) {
( 1, 1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), 1)
},
(-1,-1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), -1)
},
(-1, 1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), 1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), -1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), 1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), -1),
_ => Bigint::new()
}
}
}
},
( 1,-1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), -1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), 1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), -1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), 1),
_ => Bigint::new()
}
}
}
}
- ( _, _) => {Bigint::new()}
+ ( _, _) => unreachable!()
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + Bigint::from_components1(other.digits, other.sign*(-1))
}
}

Борислав качи решение на 27.11.2020 16:53 (преди почти 5 години)

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_components1(digits: Vec<u8>, sign: i8) -> Self {
if let Some(n) = digits.iter().position(|&x| x != 0) {
Bigint{
sign: sign,
digits: digits[n..].to_vec()
}
} else {
Bigint::new()
}
}
pub fn is_positive(&self) -> bool {
self.sign == 1 && self.digits[0] != 0
}
pub fn is_negative(&self) -> bool {
self.sign == -1 && self.digits[0] != 0
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
if s == "+" || s == "-" {
Err(ParseError)
} else {
let mut vec = Vec::new();
let mut str_iter = s.as_bytes().iter().peekable();
let sign: i8;
if str_iter.peek() == Some(&&45) {
sign = -1;
str_iter.next();
} else if str_iter.peek() == Some(&&43) {
sign = 1;
str_iter.next();
} else {
sign = 1;
}
let mut flag: bool = false;
for curr_char in str_iter {
if *curr_char >= 48 && *curr_char <= 57 {
vec.push(*curr_char-48);
}
else {
flag = true;
break;
}
}
if flag {
Err(ParseError)
} else {
Ok(Bigint::from_components1(vec, 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 {
match (self.sign, other.sign) {
( 1,-1) => Ordering::Greater,
(-1, 1) => Ordering::Less,
( 1, 1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
- for curr_self in self.digits.clone() {
- if curr_self < *other.digits.iter().next().unwrap() {
+ let self_iter = self.digits.iter().peekable();
+ let mut other_iter = other.digits.iter().peekable();
+ for curr_self in self_iter {
+ if curr_self < *other_iter.peek().unwrap() {
flag = -1;
break;
- } else if curr_self > *other.digits.iter().next().unwrap() {
+ } else if curr_self > *other_iter.peek().unwrap() {
flag = 1;
break;
} else {
flag = 0;
- continue;
}
+ other_iter.next();
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
self.digits.len().cmp(&other.digits.len())
}
}
(-1,-1) => {
if self.digits.len() == other.digits.len() && self.digits == other.digits {
Ordering::Equal
} else if self.digits.len() == other.digits.len() {
let mut flag: i8 = 0;
- for curr_self in self.digits.clone() {
- if curr_self > *other.digits.iter().next().unwrap() {
+ let self_iter = self.digits.iter().peekable();
+ let mut other_iter = other.digits.iter().peekable();
+ for curr_self in self_iter {
+ if curr_self > *other_iter.peek().unwrap() {
flag = -1;
break;
- } else if curr_self < *other.digits.iter().next().unwrap() {
+ } else if curr_self < *other_iter.peek().unwrap() {
flag = 1;
break;
} else {
flag = 0;
- continue;
}
+ other_iter.next();
}
match flag {
-1 => Ordering::Less,
1 => Ordering::Greater,
_ => Ordering::Equal
}
} else {
other.digits.len().cmp(&self.digits.len())
}
},
( _, _) => unreachable!()
}
}
}
fn add_digits(left: Vec<u8>, right: Vec<u8>) -> Vec<u8> {
match left.len().cmp(&right.len()) {
Ordering::Less => {
let mut res_size = right.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
for curr_right in iter_right {
res_size-= 1;
if curr_right + carry >= 10 {
res[res_size] = curr_right + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Greater => {
let mut res_size = left.len()+1;
let mut res: Vec<u8> = vec![0;res_size];
let mut iter_left = left.iter().rev().peekable();
let iter_right = right.iter().rev();
let mut carry: u8 = 0;
for curr_right in iter_right {
res_size -= 1;
if curr_right + *iter_left.peek().unwrap() + carry >= 10 {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_right + *iter_left.peek().unwrap() + carry;
carry = 0;
}
iter_left.next();
}
for curr_left in iter_left {
res_size -= 1;
if curr_left + carry >= 10 {
res[res_size] = curr_left + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + carry;
carry = 0;
}
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
Ordering::Equal => {
let mut res_size = right.len() + 1;
let mut res: Vec<u8> = vec![0;res_size];
let iter_left = left.iter().rev();
let mut iter_right = right.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_left in iter_left {
res_size -= 1;
if curr_left + *iter_right.peek().unwrap() + carry >= 10 {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry - 10;
carry = 1;
} else {
res[res_size] = curr_left + *iter_right.peek().unwrap() + carry;
carry = 0;
}
iter_right.next();
}
if carry == 0 {
res
} else {
res[0] = 1;
res
}
}
}
}
fn subtract_digits(larger: Vec<u8>, smaller: Vec<u8>) -> Vec<u8> {
let mut res_size = larger.len();
let mut res: Vec<u8> = vec![0;res_size];
let iter_larger = larger.iter().rev();
let mut iter_smaller = smaller.iter().rev().peekable();
let mut carry: u8 = 0;
for curr_larger in iter_larger {
res_size -= 1;
if iter_smaller.peek() != None {
if 10 + curr_larger - *iter_smaller.peek().unwrap() - carry < 10 {
res[res_size] = 10 + curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 1;
} else {
res[res_size] = curr_larger - *iter_smaller.peek().unwrap() - carry;
carry = 0;
}
iter_smaller.next();
} else {
if 10 + curr_larger - carry < 10 {
res[res_size] = 10 + curr_larger - carry;
carry = 1;
} else {
res[res_size] = curr_larger - carry;
carry = 0;
}
}
}
res
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
match (self.sign,other.sign) {
( 1, 1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), 1)
},
(-1,-1) => {
Bigint::from_components1( add_digits(self.digits, other.digits), -1)
},
(-1, 1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), 1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), -1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), 1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), -1),
_ => Bigint::new()
}
}
}
},
( 1,-1) => {
match self.digits.len().cmp(&other.digits.len()) {
Ordering::Less => {
Bigint::from_components1( subtract_digits(other.digits, self.digits), -1)
},
Ordering::Greater => {
Bigint::from_components1( subtract_digits(self.digits, other.digits), 1)
},
Ordering::Equal => {
let mut flag: i8 = 0;
for curr_self in self.digits.clone() {
if curr_self < *other.digits.iter().next().unwrap() {
flag = -1;
break;
} else if curr_self > *other.digits.iter().next().unwrap() {
flag = 1;
break;
} else {
flag = 0;
continue;
}
}
match flag {
-1 => Bigint::from_components1( subtract_digits(other.digits, self.digits), -1),
1 => Bigint::from_components1( subtract_digits(self.digits, other.digits), 1),
_ => Bigint::new()
}
}
}
}
( _, _) => unreachable!()
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
self + Bigint::from_components1(other.digits, other.sign*(-1))
}
}