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

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

Решение на Bigint от Владислав Георгиев

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

Към профила на Владислав Георгиев

Резултати

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

Код

use std::str::FromStr;
use std::cmp::Ordering;
use std::cmp::max;
use std::ops::{Add, Sub, Neg};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
return Bigint{sign: 0, digits: vec![0] };
}
pub fn is_positive(&self) -> bool {
return self.sign == 1;
}
pub fn is_negative(&self) -> bool {
return self.sign == -1;
}
}
#[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 {sign: 0, digits: vec![0]})
}
let mut vec = Vec::new();
let sign;
let leading_char = s.chars().nth(0).unwrap();
let trimmed_str;
if s.len() == 1 && leading_char == '0' {
return Ok(Bigint {sign: 0, digits: vec![0]})
}
if leading_char != '+' && leading_char != '-' {
trimmed_str = s.trim_start_matches('0');
sign = 1;
} else {
trimmed_str = (&s[1..]).trim_start_matches('0');
sign = if leading_char == '-' { -1 } else { 1 };
}
if trimmed_str.len() == 0 {
return Ok(Bigint {sign: 0, digits: vec![0]});
}
for c in trimmed_str.chars() {
let numb = c.to_digit(10);
if !numb.is_some() {
return Err(ParseError {});
}
vec.push(numb.unwrap() as u8);
}
return Ok(Bigint {sign: sign, digits: vec});
}
}
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 Ordering::Greater;
} else if other.sign > self.sign {
return Ordering::Less;
}
if self.digits.len() > other.digits.len() {
return if self.is_positive() { Ordering::Greater } else { Ordering::Less };
} else if self.digits.len() < other.digits.len() {
return if self.is_positive() { Ordering::Less } else { Ordering::Greater };
}
for i in 0..self.digits.len() {
if self.digits[i] > other.digits[i] {
return if self.is_positive() { Ordering::Greater } else { Ordering::Less };
} else if self.digits[i] < other.digits[i] {
return if self.is_positive() { Ordering::Less } else { Ordering::Greater };
}
}
Ordering::Equal
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
//=
let self_len = self.digits.len();
let other_len = other.digits.len();
let mut vec: Vec<u8> = Vec::new();
let max_len = max(self_len, other_len);
let mut sign;
let mut vec1: Vec<u8> = self.digits.to_vec().into_iter().rev().collect();
let mut vec2: Vec<u8> = other.digits.to_vec().into_iter().rev().collect();
let mut zero_padding1 = vec![0; max_len - vec1.len()];
let mut zero_padding2 = vec![0; max_len - vec2.len()];
vec1.append(&mut zero_padding1);
vec2.append(&mut zero_padding2);
if self.sign == other.sign {
let mut carry = 0;
for i in 0..max_len {
let result = vec1[i] + vec2[i];
vec.push((result + carry) % 10);
carry = (result + carry) / 10;
}
if carry == 1
{
vec.push(carry);
}
sign = self.sign;
} else {
let abs1 = Bigint {sign: 1, digits: self.digits};
let abs2 = Bigint {sign: 1, digits: other.digits};
let res = abs1.cmp(&abs2);
let mut vec1_mult = 1;
let mut vec2_mult = 1;
if res == Ordering::Less {
vec1_mult = -1;
} else {
vec2_mult = -1;
}
let mut carry = 0;
for i in 0..max_len {
let result = vec1_mult * vec1[i] as i8 + vec2_mult * vec2[i] as i8 ;
if result - carry < 0 {
vec.push((10 + result - carry) as u8);
carry = 1;
} else {
vec.push((result - carry) as u8);
carry = 0;
}
}
sign = if vec1_mult == -1 { other.sign } else { self.sign }
}
vec = vec.into_iter().rev().collect();
if vec[0] == 0 && vec.len() != 1 {
let mut idx: i8 = -1;
for i in 0..vec.len(){
if vec[i] != 0 {
idx = i as i8;
break;
}
}
if idx == -1 {
idx = (vec.len() - 1) as i8;
}
vec.drain(0..idx as usize);
}
if vec.len() == 1 && vec[0] == 0 {
sign = 0;
}
return Bigint {sign: sign, digits: vec};
}
}
impl Neg for Bigint {
type Output = Self;
fn neg(mut self) -> Self {
self.sign = self.sign * -1;
self
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
return self + (-other);
}
}

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

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

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

Владислав качи първо решение на 26.11.2020 11:47 (преди почти 5 години)

Владислав качи решение на 26.11.2020 11:48 (преди почти 5 години)

use std::str::FromStr;
use std::cmp::Ordering;
use std::cmp::max;
use std::ops::{Add, Sub, Neg};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
return Bigint{sign: 1, digits: Vec::new() };
}
pub fn is_positive(&self) -> bool {
return self.sign == 1;
}
pub fn is_negative(&self) -> bool {
return self.sign == -1;
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut vec = Vec::new();
let sign;
let leading_char = s.chars().nth(0).unwrap();
let trimmed_str;
if s.len() == 1 && leading_char == '0' {
return Ok(Bigint {sign: 0, digits: vec![0]})
}
if leading_char != '+' && leading_char != '-' {
trimmed_str = s.trim_start_matches('0');
sign = 1;
} else {
trimmed_str = (&s[1..]).trim_start_matches('0');
sign = if leading_char == '-' { -1 } else { 1 };
}
if trimmed_str.len() == 0 {
return Ok(Bigint {sign: 0, digits: vec![0]});
}
for c in trimmed_str.chars() {
let numb = c.to_digit(10);
if !numb.is_some() {
return Err(ParseError {});
}
vec.push(numb.unwrap() as u8);
}
return Ok(Bigint {sign: sign, digits: vec});
}
}
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 Ordering::Greater;
} else if other.sign > self.sign {
return Ordering::Less;
}
if self.digits.len() > other.digits.len() {
return if self.is_positive() { Ordering::Greater } else { Ordering::Less };
} else if self.digits.len() < other.digits.len() {
return if self.is_positive() { Ordering::Less } else { Ordering::Greater };
}
for i in 0..self.digits.len() {
if self.digits[i] > other.digits[i] {
return if self.is_positive() { Ordering::Greater } else { Ordering::Less };
} else if self.digits[i] < other.digits[i] {
return if self.is_positive() { Ordering::Less } else { Ordering::Greater };
}
}
Ordering::Equal
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
//=
let self_len = self.digits.len();
let other_len = other.digits.len();
let mut vec: Vec<u8> = Vec::new();
let max_len = max(self_len, other_len);
let mut sign;
let mut vec1: Vec<u8> = self.digits.to_vec().into_iter().rev().collect();
let mut vec2: Vec<u8> = other.digits.to_vec().into_iter().rev().collect();
let mut zero_padding1 = vec![0; max_len - vec1.len()];
let mut zero_padding2 = vec![0; max_len - vec2.len()];
vec1.append(&mut zero_padding1);
vec2.append(&mut zero_padding2);
if self.sign == other.sign {
let mut carry = 0;
for i in 0..max_len {
let result = vec1[i] + vec2[i];
vec.push((result + carry) % 10);
carry = (result + carry) / 10;
}
if carry == 1
{
vec.push(carry);
}
sign = self.sign;
} else {
let abs1 = Bigint {sign: 1, digits: self.digits};
let abs2 = Bigint {sign: 1, digits: other.digits};
let res = abs1.cmp(&abs2);
let mut vec1_mult = 1;
let mut vec2_mult = 1;
if res == Ordering::Less {
vec1_mult = -1;
} else {
vec2_mult = -1;
}
let mut carry = 0;
for i in 0..max_len {
let result = vec1_mult * vec1[i] as i8 + vec2_mult * vec2[i] as i8 ;
if result - carry < 0 {
vec.push((10 + result - carry) as u8);
carry = 1;
} else {
vec.push((result - carry) as u8);
carry = 0;
}
}
sign = if vec1_mult == -1 { other.sign } else { self.sign }
}
vec = vec.into_iter().rev().collect();
if vec[0] == 0 && vec.len() != 1 {
let mut idx: i8 = -1;
for i in 0..vec.len(){
if vec[i] != 0 {
idx = i as i8;
break;
}
}
if idx == -1 {
idx = (vec.len() - 1) as i8;
}
vec.drain(0..idx as usize);
}
if vec.len() == 1 && vec[0] == 0 {
sign = 0;
}
return Bigint {sign: sign, digits: vec};
}
}
impl Neg for Bigint {
type Output = Self;
fn neg(mut self) -> Self {
self.sign = self.sign * -1;
self
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
return self + (-other);
}
}
-
-fn main() {
-
-}

Владислав качи решение на 26.11.2020 11:57 (преди почти 5 години)

use std::str::FromStr;
use std::cmp::Ordering;
use std::cmp::max;
use std::ops::{Add, Sub, Neg};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
- return Bigint{sign: 1, digits: Vec::new() };
+ return Bigint{sign: 0, digits: vec![0] };
}
pub fn is_positive(&self) -> bool {
return self.sign == 1;
}
pub fn is_negative(&self) -> bool {
return self.sign == -1;
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut vec = Vec::new();
let sign;
let leading_char = s.chars().nth(0).unwrap();
let trimmed_str;
if s.len() == 1 && leading_char == '0' {
return Ok(Bigint {sign: 0, digits: vec![0]})
}
if leading_char != '+' && leading_char != '-' {
trimmed_str = s.trim_start_matches('0');
sign = 1;
} else {
trimmed_str = (&s[1..]).trim_start_matches('0');
sign = if leading_char == '-' { -1 } else { 1 };
}
if trimmed_str.len() == 0 {
return Ok(Bigint {sign: 0, digits: vec![0]});
}
for c in trimmed_str.chars() {
let numb = c.to_digit(10);
if !numb.is_some() {
return Err(ParseError {});
}
vec.push(numb.unwrap() as u8);
}
return Ok(Bigint {sign: sign, digits: vec});
}
}
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 Ordering::Greater;
} else if other.sign > self.sign {
return Ordering::Less;
}
if self.digits.len() > other.digits.len() {
return if self.is_positive() { Ordering::Greater } else { Ordering::Less };
} else if self.digits.len() < other.digits.len() {
return if self.is_positive() { Ordering::Less } else { Ordering::Greater };
}
for i in 0..self.digits.len() {
if self.digits[i] > other.digits[i] {
return if self.is_positive() { Ordering::Greater } else { Ordering::Less };
} else if self.digits[i] < other.digits[i] {
return if self.is_positive() { Ordering::Less } else { Ordering::Greater };
}
}
Ordering::Equal
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
//=
let self_len = self.digits.len();
let other_len = other.digits.len();
let mut vec: Vec<u8> = Vec::new();
let max_len = max(self_len, other_len);
let mut sign;
let mut vec1: Vec<u8> = self.digits.to_vec().into_iter().rev().collect();
let mut vec2: Vec<u8> = other.digits.to_vec().into_iter().rev().collect();
let mut zero_padding1 = vec![0; max_len - vec1.len()];
let mut zero_padding2 = vec![0; max_len - vec2.len()];
vec1.append(&mut zero_padding1);
vec2.append(&mut zero_padding2);
if self.sign == other.sign {
let mut carry = 0;
for i in 0..max_len {
let result = vec1[i] + vec2[i];
vec.push((result + carry) % 10);
carry = (result + carry) / 10;
}
if carry == 1
{
vec.push(carry);
}
sign = self.sign;
} else {
let abs1 = Bigint {sign: 1, digits: self.digits};
let abs2 = Bigint {sign: 1, digits: other.digits};
let res = abs1.cmp(&abs2);
let mut vec1_mult = 1;
let mut vec2_mult = 1;
if res == Ordering::Less {
vec1_mult = -1;
} else {
vec2_mult = -1;
}
let mut carry = 0;
for i in 0..max_len {
let result = vec1_mult * vec1[i] as i8 + vec2_mult * vec2[i] as i8 ;
if result - carry < 0 {
vec.push((10 + result - carry) as u8);
carry = 1;
} else {
vec.push((result - carry) as u8);
carry = 0;
}
}
sign = if vec1_mult == -1 { other.sign } else { self.sign }
}
vec = vec.into_iter().rev().collect();
if vec[0] == 0 && vec.len() != 1 {
let mut idx: i8 = -1;
for i in 0..vec.len(){
if vec[i] != 0 {
idx = i as i8;
break;
}
}
if idx == -1 {
idx = (vec.len() - 1) as i8;
}
vec.drain(0..idx as usize);
}
if vec.len() == 1 && vec[0] == 0 {
sign = 0;
}
return Bigint {sign: sign, digits: vec};
}
}
impl Neg for Bigint {
type Output = Self;
fn neg(mut self) -> Self {
self.sign = self.sign * -1;
self
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
return self + (-other);
}
}

Владислав качи решение на 27.11.2020 12:19 (преди почти 5 години)

use std::str::FromStr;
use std::cmp::Ordering;
use std::cmp::max;
use std::ops::{Add, Sub, Neg};
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
return Bigint{sign: 0, digits: vec![0] };
}
pub fn is_positive(&self) -> bool {
return self.sign == 1;
}
pub fn is_negative(&self) -> bool {
return self.sign == -1;
}
}
#[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 {sign: 0, digits: vec![0]})
+ }
+
let mut vec = Vec::new();
let sign;
let leading_char = s.chars().nth(0).unwrap();
let trimmed_str;
if s.len() == 1 && leading_char == '0' {
return Ok(Bigint {sign: 0, digits: vec![0]})
}
if leading_char != '+' && leading_char != '-' {
trimmed_str = s.trim_start_matches('0');
sign = 1;
} else {
trimmed_str = (&s[1..]).trim_start_matches('0');
sign = if leading_char == '-' { -1 } else { 1 };
}
if trimmed_str.len() == 0 {
return Ok(Bigint {sign: 0, digits: vec![0]});
}
for c in trimmed_str.chars() {
let numb = c.to_digit(10);
if !numb.is_some() {
return Err(ParseError {});
}
vec.push(numb.unwrap() as u8);
}
return Ok(Bigint {sign: sign, digits: vec});
}
}
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 Ordering::Greater;
} else if other.sign > self.sign {
return Ordering::Less;
}
if self.digits.len() > other.digits.len() {
return if self.is_positive() { Ordering::Greater } else { Ordering::Less };
} else if self.digits.len() < other.digits.len() {
return if self.is_positive() { Ordering::Less } else { Ordering::Greater };
}
for i in 0..self.digits.len() {
if self.digits[i] > other.digits[i] {
return if self.is_positive() { Ordering::Greater } else { Ordering::Less };
} else if self.digits[i] < other.digits[i] {
return if self.is_positive() { Ordering::Less } else { Ordering::Greater };
}
}
Ordering::Equal
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
//=
let self_len = self.digits.len();
let other_len = other.digits.len();
let mut vec: Vec<u8> = Vec::new();
let max_len = max(self_len, other_len);
let mut sign;
let mut vec1: Vec<u8> = self.digits.to_vec().into_iter().rev().collect();
let mut vec2: Vec<u8> = other.digits.to_vec().into_iter().rev().collect();
let mut zero_padding1 = vec![0; max_len - vec1.len()];
let mut zero_padding2 = vec![0; max_len - vec2.len()];
vec1.append(&mut zero_padding1);
vec2.append(&mut zero_padding2);
if self.sign == other.sign {
let mut carry = 0;
for i in 0..max_len {
let result = vec1[i] + vec2[i];
vec.push((result + carry) % 10);
carry = (result + carry) / 10;
}
if carry == 1
{
vec.push(carry);
}
sign = self.sign;
} else {
let abs1 = Bigint {sign: 1, digits: self.digits};
let abs2 = Bigint {sign: 1, digits: other.digits};
let res = abs1.cmp(&abs2);
let mut vec1_mult = 1;
let mut vec2_mult = 1;
if res == Ordering::Less {
vec1_mult = -1;
} else {
vec2_mult = -1;
}
let mut carry = 0;
for i in 0..max_len {
let result = vec1_mult * vec1[i] as i8 + vec2_mult * vec2[i] as i8 ;
if result - carry < 0 {
vec.push((10 + result - carry) as u8);
carry = 1;
} else {
vec.push((result - carry) as u8);
carry = 0;
}
}
sign = if vec1_mult == -1 { other.sign } else { self.sign }
}
vec = vec.into_iter().rev().collect();
if vec[0] == 0 && vec.len() != 1 {
let mut idx: i8 = -1;
for i in 0..vec.len(){
if vec[i] != 0 {
idx = i as i8;
break;
}
}
if idx == -1 {
idx = (vec.len() - 1) as i8;
}
vec.drain(0..idx as usize);
}
if vec.len() == 1 && vec[0] == 0 {
sign = 0;
}
return Bigint {sign: sign, digits: vec};
}
}
impl Neg for Bigint {
type Output = Self;
fn neg(mut self) -> Self {
self.sign = self.sign * -1;
self
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
return self + (-other);
}
-}
+}