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

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

Решение на Bigint от Николай Георгиев

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

Към профила на Николай Георгиев

Резултати

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

Код

use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::Add;
use std::ops::Sub;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign : 1,
digits : vec![0]
}
}
pub fn is_positive(&self) -> bool {
if *&self.digits[0] != 0 && *&self.sign == 1 as i8{
return true
}else{
return false
}
}
pub fn is_negative(&self) -> bool {
if *&self.digits[0] != 0 && *&self.sign == -1 as i8{
return true
}else{
return false
}
}

Вместо return true и return false, може просто да върнеш резултата от сравнението. Допълнително, комбинацията *& се неутрализира, така че не прави нищо. self.digits[0] би трябвало да работи, също както и self.sign.

Андрей
}
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut v: Vec<char> = s.chars().collect();
let mut new_v: Vec<u8> = Vec::new();
let mut sign: i8 = 1;
let mut zeros = 0;
if v.len() == 0{
v.push('0');
}
let end_id = v.len() - 1;
//reversed order
v.reverse();
//remove sign from vector
if v[end_id] == '-' {
sign = -1;
v.pop();
}else if v[end_id] == '+' {
v.pop();
}
if v.len() == 0 {
return Err(Self::Err{})
}
//normal order
v.reverse();
//check for non-numeric chars
for c in &v{
if *c < '0' || *c > '9'{
return Err(Self::Err{})
}
}
//count zeros in the beginning
for c in &v{
if *c == '0'{
zeros += 1;
}else {
break;
}
}
if zeros == v.len() && v.len() != 0 {
return Ok(Self{ sign: 1, digits:vec![0] })
}
//reversed order
v.reverse();
//remove zeros in the beginning
while zeros != 0{
v.pop();
zeros -= 1;
}
//normal order
v.reverse();
//turn the chars into u8 in a new vector
for c in &v{
new_v.push(*c as u8 - '0' as u8);
}
Ok(Self{ sign: sign, digits: new_v })
}
}
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 dif: i32 = *&self.digits.len() as i32 - other.digits.len() as i32;
let mut i = 0;
//different signs
if *&self.sign == -1 && other.sign == 1{
return Ordering::Less
}else if *&self.sign == 1 && other.sign == -1{
return Ordering::Greater
}
//same signs
if dif == 0{
while i < other.digits.len() {
if *&self.digits[i] < other.digits[i]{
if other.sign == -1 {
return Ordering::Greater
}else{
return Ordering::Less
}
}else if *&self.digits[i] > other.digits[i]{
if other.sign == -1 {
return Ordering::Less
}else{
return Ordering::Greater
}
}
i += 1;
}
return Ordering::Equal;
}else if dif < 0{
if other.sign == -1 {
return Ordering::Greater
}else{
return Ordering::Less
}
}else{
if other.sign == -1{
return Ordering::Less
}else{
return Ordering::Greater
}
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
let mut v: Vec<u8>;
let mut new_sign: i8 = 1;
if self.sign == other.sign{
v = add_digits(self.digits, other.digits);
new_sign = self.sign;
}else{
let sv: Vec<u8> = cp(&self.digits);
let ov: Vec<u8> = cp(&other.digits);
let s = Bigint{ sign: 1, digits: sv };
let o: Bigint = Bigint{ sign: 1, digits: ov };
&s.cmp(&o);
if &s.cmp(&o) == &Ordering::Greater{
v = sub_digits(self.digits, other.digits);
new_sign = self.sign;
}else{
v = sub_digits(other.digits, self.digits);
if &s.cmp(&o) != &Ordering::Equal {
new_sign = other.sign;
}
}
}
v.reverse();
return Bigint{ sign: new_sign, digits: v};
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
if other.sign == -1{
let new_other = Bigint{ sign: 1, digits: other.digits.clone() };
return self.add(new_other);
}else{
let new_other = Bigint{ sign: -1, digits: other.digits.clone() };
return self.add(new_other);
}
}
}
fn add_digits(v1: Vec<u8>, v2: Vec<u8>) -> Vec<u8>{
let mut d: u8;
let mut i = v1.len();
let mut j = v2.len();
let mut add1 = false;
let mut v: Vec<u8> = Vec::new();
while i > 0 && j > 0 {
d = v1[i - 1] + v2[j - 1];
if add1 == true{
d += 1;
add1 = false;
}
if d >= 10 {
add1 = true;
d = d % 10;
}
v.push(d);
i -= 1;
j -= 1;
}
let vp: &Vec<u8>;
if v1.len() > v2.len(){
vp = &v1;
}else{
vp = &v2;
i = j;
}
if add1 == true{
if i != 0{
v.push(vp[i - 1] + 1);
i -= 1;
}else{
v.push(1);
}
}
while i > 0 {
v.push(vp[i - 1]);
i -= 1;
}
return v;
}
fn sub_digits(pos: Vec<u8>, neg: Vec<u8>) -> Vec<u8>{
let mut sub1 = false;
let mut d: i8;
let mut i = pos.len();
let mut j = neg.len();
let mut v: Vec<u8> = Vec::new();
while i > 0 && j > 0 {
d = pos[i - 1] as i8 - neg[j - 1] as i8;
if sub1 == true{
d -= 1;
}
if d < 0 {
d = (pos[i - 1] + 10 - neg[j - 1]) as i8;
if sub1 == true{
d -= 1;
}
sub1 = true;
}else if sub1 == true && d >= 0 {
sub1 = false;
}
v.push(d as u8);
i -= 1;
j -= 1;
}
let vp: &Vec<u8>;
if pos.len() > neg.len(){
vp = &pos;
}else{
vp = &neg;
i = j;
}
while i > 0 {
if sub1 == false {
v.push(vp[i - 1]);
}else{
if vp[i - 1] != 0{
v.push(vp[i - 1] - 1);
sub1 = false;
}else{
v.push(9);
}
}
i -= 1;
}
i = v.len();
while i > 1 && v[i - 1] == 0{
v.pop();
i -= 1;
}
return v;
}
fn cp(old: &Vec<u8>) -> Vec<u8> {
let mut i = 0;
let mut new: Vec<u8> = Vec::new();
while i < *&old.len() {
new.push(*&old[i]);
i += 1;
}
new
}

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

Compiling solution v0.1.0 (/tmp/d20201127-2274206-1f0vh0w/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 ... FAILED
test solution_test::test_sum_4_negative ... ok

failures:

---- solution_test::test_sum_3_overflow stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `Bigint { sign: 1, digits: [9, 10, 0] }`,
 right: `Bigint { sign: 1, digits: [1, 0, 0, 0] }`', tests/solution_test.rs:97:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    solution_test::test_sum_3_overflow

test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '--test solution_test'

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

Николай качи първо решение на 22.11.2020 14:45 (преди почти 5 години)

Имай предвид, че в момента събирането и изваждането ти работят като акумулират резултата в 32-битово число. Целта на bigint-а е да държи потенциално безкрайно голямо число, т.е. операциите да се правят по цифри без никога да се стига до истинско конкретно число.

Ако го пускаш като частично/временно решение, това е ок -- не всички тестове ще проверяват операциите с големи числа. Просто имай предвид, ако това е нещо, което не си разбрал. Ще го доуточня и в условието.

Николай качи решение на 23.11.2020 20:42 (преди почти 5 години)

use std::str::FromStr;
use std::cmp::Ordering;
use std::ops::Add;
use std::ops::Sub;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Self {
sign : 1,
digits : vec![0]
}
}
pub fn is_positive(&self) -> bool {
if *&self.digits[0] != 0 && *&self.sign == 1 as i8{
return true
}else{
return false
}
}
pub fn is_negative(&self) -> bool {
if *&self.digits[0] != 0 && *&self.sign == -1 as i8{
return true
}else{
return false
}
}

Вместо return true и return false, може просто да върнеш резултата от сравнението. Допълнително, комбинацията *& се неутрализира, така че не прави нищо. self.digits[0] би трябвало да работи, също както и self.sign.

Андрей
}
#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut v: Vec<char> = s.chars().collect();
let mut new_v: Vec<u8> = Vec::new();
let mut sign: i8 = 1;
let mut zeros = 0;
if v.len() == 0{
v.push('0');
}
let end_id = v.len() - 1;
//reversed order
v.reverse();
//remove sign from vector
if v[end_id] == '-' {
sign = -1;
v.pop();
}else if v[end_id] == '+' {
v.pop();
}
if v.len() == 0 {
return Err(Self::Err{})
}
//normal order
v.reverse();
//check for non-numeric chars
for c in &v{
if *c < '0' || *c > '9'{
return Err(Self::Err{})
}
}
//count zeros in the beginning
for c in &v{
if *c == '0'{
zeros += 1;
}else {
break;
}
}
if zeros == v.len() && v.len() != 0 {
return Ok(Self{ sign: 1, digits:vec![0] })
}
//reversed order
v.reverse();
//remove zeros in the beginning
while zeros != 0{
v.pop();
zeros -= 1;
}
//normal order
v.reverse();
//turn the chars into u8 in a new vector
for c in &v{
new_v.push(*c as u8 - '0' as u8);
}
Ok(Self{ sign: sign, digits: new_v })
}
}
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 dif: i32 = (&self.digits.len() - other.digits.len()) as i32;
+ let dif: i32 = *&self.digits.len() as i32 - other.digits.len() as i32;
let mut i = 0;
//different signs
if *&self.sign == -1 && other.sign == 1{
return Ordering::Less
}else if *&self.sign == 1 && other.sign == -1{
return Ordering::Greater
}
//same signs
if dif == 0{
while i < other.digits.len() {
if *&self.digits[i] < other.digits[i]{
if other.sign == -1 {
return Ordering::Greater
}else{
return Ordering::Less
}
}else if *&self.digits[i] > other.digits[i]{
if other.sign == -1 {
return Ordering::Less
}else{
return Ordering::Greater
}
}
i += 1;
}
return Ordering::Equal;
}else if dif < 0{
if other.sign == -1 {
return Ordering::Greater
}else{
return Ordering::Less
}
}else{
if other.sign == -1{
return Ordering::Less
}else{
return Ordering::Greater
}
}
}
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
- let mut n1: i32 = 0;
- let mut n2: i32 = 0;
- let mut i= self.digits.len();
+ let mut v: Vec<u8>;
+ let mut new_sign: i8 = 1;
- for d1 in &self.digits{
- i -= 1;
- n1 += *d1 as i32 * 10_i32.pow(i as u32);
- }
+ if self.sign == other.sign{
+ v = add_digits(self.digits, other.digits);
+ new_sign = self.sign;
+ }else{
+ let sv: Vec<u8> = cp(&self.digits);
+ let ov: Vec<u8> = cp(&other.digits);
- i = other.digits.len();
+ let s = Bigint{ sign: 1, digits: sv };
+ let o: Bigint = Bigint{ sign: 1, digits: ov };
- for d2 in &other.digits{
- i -= 1;
- n2 += *d2 as i32 * 10_i32.pow(i as u32);
- }
+ &s.cmp(&o);
- let n: i32 = n1 * self.sign as i32 + n2 * other.sign as i32;
+ if &s.cmp(&o) == &Ordering::Greater{
+ v = sub_digits(self.digits, other.digits);
+ new_sign = self.sign;
+ }else{
+ v = sub_digits(other.digits, self.digits);
- println!("{} {} {}", n1, n2, n);
+ if &s.cmp(&o) != &Ordering::Equal {
+ new_sign = other.sign;
+ }
+ }
+ }
- return Bigint::from_str(&(n.to_string())).unwrap();
+ v.reverse();
+ return Bigint{ sign: new_sign, digits: v};
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
- let mut n1: i32 = 0;
- let mut n2: i32 = 0;
- let mut i= self.digits.len();
+ if other.sign == -1{
+ let new_other = Bigint{ sign: 1, digits: other.digits.clone() };
- for d1 in &self.digits{
- i -= 1;
- n1 += *d1 as i32 * 10_i32.pow(i as u32);
+ return self.add(new_other);
+ }else{
+ let new_other = Bigint{ sign: -1, digits: other.digits.clone() };
+
+ return self.add(new_other);
}
+ }
+}
- i = other.digits.len();
+fn add_digits(v1: Vec<u8>, v2: Vec<u8>) -> Vec<u8>{
+ let mut d: u8;
+ let mut i = v1.len();
+ let mut j = v2.len();
+ let mut add1 = false;
+ let mut v: Vec<u8> = Vec::new();
- for d2 in &other.digits{
+ while i > 0 && j > 0 {
+ d = v1[i - 1] + v2[j - 1];
+
+ if add1 == true{
+ d += 1;
+ add1 = false;
+ }
+
+ if d >= 10 {
+ add1 = true;
+ d = d % 10;
+ }
+
+ v.push(d);
+ i -= 1;
+ j -= 1;
+ }
+
+ let vp: &Vec<u8>;
+
+ if v1.len() > v2.len(){
+ vp = &v1;
+ }else{
+ vp = &v2;
+ i = j;
+ }
+
+ if add1 == true{
+ if i != 0{
+ v.push(vp[i - 1] + 1);
+
i -= 1;
- n2 += *d2 as i32 * 10_i32.pow(i as u32);
+ }else{
+ v.push(1);
}
+
+ }
- let n: i32 = n1 * self.sign as i32 - n2 * other.sign as i32;
+ while i > 0 {
+ v.push(vp[i - 1]);
+ i -= 1;
+ }
- println!("{} {} {}", n1, n2, n);
+ return v;
+}
- return Bigint::from_str(&(n.to_string())).unwrap();
+fn sub_digits(pos: Vec<u8>, neg: Vec<u8>) -> Vec<u8>{
+ let mut sub1 = false;
+ let mut d: i8;
+ let mut i = pos.len();
+ let mut j = neg.len();
+ let mut v: Vec<u8> = Vec::new();
+
+ while i > 0 && j > 0 {
+ d = pos[i - 1] as i8 - neg[j - 1] as i8;
+
+ if sub1 == true{
+ d -= 1;
+ }
+
+ if d < 0 {
+ d = (pos[i - 1] + 10 - neg[j - 1]) as i8;
+
+ if sub1 == true{
+ d -= 1;
+ }
+
+ sub1 = true;
+ }else if sub1 == true && d >= 0 {
+ sub1 = false;
+ }
+
+ v.push(d as u8);
+ i -= 1;
+ j -= 1;
}
+
+ let vp: &Vec<u8>;
+
+ if pos.len() > neg.len(){
+ vp = &pos;
+ }else{
+ vp = &neg;
+ i = j;
+ }
+
+ while i > 0 {
+ if sub1 == false {
+ v.push(vp[i - 1]);
+ }else{
+ if vp[i - 1] != 0{
+ v.push(vp[i - 1] - 1);
+ sub1 = false;
+ }else{
+ v.push(9);
+ }
+ }
+
+ i -= 1;
+ }
+
+ i = v.len();
+
+ while i > 1 && v[i - 1] == 0{
+ v.pop();
+ i -= 1;
+ }
+
+ return v;
+}
+
+fn cp(old: &Vec<u8>) -> Vec<u8> {
+ let mut i = 0;
+ let mut new: Vec<u8> = Vec::new();
+
+ while i < *&old.len() {
+ new.push(*&old[i]);
+ i += 1;
+ }
+
+ new
}