Решение на Bigint от Илиян Йорданов

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

Към профила на Илиян Йорданов

Резултати

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

Код

#[cfg(test)]
mod tests {
#[test]
fn it_works() {
assert_eq!(2 + 2, 4);
}
use crate::Bigint;
#[test]
fn first_test() {
assert_eq!(Bigint::new(),Bigint::from_components(vec![0,0,0,0],-1));
assert_eq!(Bigint::from_components(vec![0,1,2,3],-1),Bigint::from_components(vec![1,2,3],-1));
let mut num = Bigint::from_components(vec![1,2],1);
assert_eq!(true,num.is_positive());
assert_eq!(false,num.is_negative());
num = Bigint::from_components(vec![1,2],-1);
assert_eq!(false,num.is_positive());
assert_eq!(true,num.is_negative());
num = Bigint::from_components(vec![0],-1);
assert_eq!(false,num.is_positive());
assert_eq!(false,num.is_negative());
}
use std::str::FromStr;
use crate::ParseError;
#[test]
fn second_test() {
assert_eq!(Bigint::new(),Bigint::from_str("-000000").unwrap());
assert_eq!(Bigint::from_components(vec![1,2,3],-1),Bigint::from_str("-00123").unwrap());
assert_eq!(Bigint::from_components(vec![1,2,3],1),Bigint::from_str("+00123").unwrap());
assert_eq!(Bigint::from_components(vec![1,2,3],1),Bigint::from_str("00123").unwrap());
assert_eq!(Bigint::from_components(vec![1,2,3],1),Bigint::from_str("123").unwrap());
assert_eq!(Err(ParseError{}),Bigint::from_str("00k123"));
assert_eq!(Err(ParseError{}),Bigint::from_str("*00123"));
assert_eq!(Err(ParseError{}),Bigint::from_str("+-"));
assert_eq!(Ok(Bigint::new()),Bigint::from_str(""));
}
use std::cmp::Ordering;
#[test]
fn third_test() {
assert_eq!(Bigint::from_str("-0000").unwrap().cmp(&Bigint::from_str("0").unwrap()),Ordering::Equal);
assert_eq!(Bigint::from_str("-0000123").unwrap().cmp(&Bigint::from_str("-123").unwrap()),Ordering::Equal);
assert_eq!(Bigint::from_str("13").unwrap().cmp(&Bigint::from_str("123").unwrap()),Ordering::Less);
assert_eq!(Bigint::from_str("-123").unwrap().cmp(&Bigint::from_str("+1").unwrap()),Ordering::Less);
assert_eq!(Bigint::from_str("+12").unwrap().cmp(&Bigint::from_str("-42").unwrap()),Ordering::Greater);
assert_eq!(Bigint::from_str("-42").unwrap().cmp(&Bigint::from_str("-123").unwrap()),Ordering::Greater);
}
use std::ops::{Add, Sub};
#[test]
fn fourth_test() {
let a = Bigint::from_str("123").unwrap();
let b = Bigint::from_str("99").unwrap();
let c = Bigint::from_str("999").unwrap();
assert_eq!(a.clone().add(b.clone()),Bigint::from_str("222").unwrap());
assert_eq!(a.clone().add(c.clone()),Bigint::from_str("1122").unwrap());
assert_eq!((-a.clone()).add(-b.clone()),Bigint::from_str("-222").unwrap());
assert_eq!((-a.clone()).add(b.clone()),Bigint::from_str("-24").unwrap());
assert_eq!(a.clone().add(-b.clone()),Bigint::from_str("24").unwrap());
assert_eq!(a.clone().add(-c.clone()),Bigint::from_str("-876").unwrap());
assert_eq!((-b.clone()).add(a.clone()),Bigint::from_str("24").unwrap());
assert_eq!(a.clone().sub(b.clone()),Bigint::from_str("24").unwrap());
assert_eq!(a.clone().sub(c.clone()),Bigint::from_str("-876").unwrap());
assert_eq!((-a.clone()).sub(-b.clone()),Bigint::from_str("-24").unwrap());
assert_eq!((-b.clone()).sub(-a.clone()),Bigint::from_str("24").unwrap());
assert_eq!((-a.clone()).sub(b.clone()),Bigint::from_str("-222").unwrap());
assert_eq!(a.clone().sub(-b.clone()),Bigint::from_str("222").unwrap());
assert_eq!(a.clone().sub(a.clone()),Bigint::from_str("0").unwrap());
assert_eq!(a.clone().add(Bigint::new()),a);
assert_eq!(Bigint::new().sub(a.clone()),-a.clone());
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
}
}
fn from_components(digits: Vec<u8>, sign: i8) -> Self {
if (sign!=1)&&(sign!=-1) {
panic!("Wrong sign in from_components");
}
let mut d = Vec::<u8>::new();
let mut flag : bool;
flag=false;
for digit in digits.iter() {
if (digit==&0)&&(flag==false) {
continue;
}
if digit!=&0 {
flag=true;
}
d.push(*digit);
}
if d.len()==0 {
d.push(0);
Bigint {
sign: 1,
digits: d,
}
}
else {
Bigint {
sign: sign,
digits: d
}
}
}
pub fn is_positive(&self) -> bool {
if (self.sign==1)&&(self.digits!=vec![0]) {
true
}
else {
false
}
}
pub fn is_negative(&self) -> bool {
if (self.sign==-1)&&(self.digits!=vec![0]) {
true
}
else {
false
}
}
}
fn abs(num: &Bigint) -> Bigint {
if num.is_negative()==true {
-(num.clone())
}
else {
num.clone()
}
}
use std::str::FromStr;
#[derive(Debug,PartialEq)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut chars = s.chars();
let first = chars.next();
match first {
None => Ok(Bigint::new()),
Some('0'..='9') | Some('+') | Some ('-') => {
let mut sign : i8;
let mut digs = Vec::<u8>::new();
sign=1;
if first==Some('-') {
sign=-1;
}
else if first!=Some('+') {
digs.push((first.unwrap() as u8)-('0' as u8));
}
let mut flag = false;
for c in chars {
if (c<'0')||(c>'9') {
flag=true;
break;
}
digs.push((c as u8)-('0' as u8));
}
if flag==true {
Err(ParseError{})
}
else {
Ok(Bigint::from_components(digs,sign))
}
},
_ => Err(ParseError{}),
}
}
}
use std::ops::Neg;
impl Neg for Bigint {
type Output = Self;
fn neg(self) -> Self::Output {
Bigint {
sign: -self.sign,
digits: self.digits,
}
}
}
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==-1)&&(other.sign==1) {
Ordering::Less
}
else if (self.sign==1)&&(other.sign==-1) {
Ordering::Greater
}
else if self.sign==1 {
if self.digits.len()<other.digits.len() {
Ordering::Less
}
else if self.digits.len()>other.digits.len() {
Ordering::Greater
}
else {
self.digits.cmp(&other.digits)
}
}
else {
abs(&self).cmp(&abs(&other)).reverse()
}
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign==other.sign {
let mut result = Vec::<u8>::new();
let mut carry = 0u8;
let mut ind1 = (self.digits.len() as isize) -1;
let mut ind2 = (other.digits.len() as isize) -1;
let mut digit;
while (ind1>=0)||(ind2>=0) {
digit = carry;
if ind1>=0 {
digit+=self.digits[ind1 as usize];
}
if ind2>=0 {
digit+=other.digits[ind2 as usize];
}
result.push(digit%10);
carry=digit/10;
ind1-=1;
ind2-=1;
}
result.push(carry);
result.reverse();
Bigint::from_components(result, self.sign)
}
else if self.sign==1 {
if abs(&self).cmp(&abs(&other))==Ordering::Less {
-(-other).sub(self)
}
else {
self.sub(-other)
}
}
else {
if abs(&self).cmp(&abs(&other))==Ordering::Less {
other.sub(-self)
}
else {
-(-self).sub(other)
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
if self.sign==other.sign {
if abs(&self).cmp(&abs(&other))==Ordering::Less {
-other.sub(self)
}
else {
let mut result = Vec::<u8>::new();
let mut carry = 0u8;
let mut ind1 = (self.digits.len() as isize) -1;
let mut ind2 = (other.digits.len() as isize) -1;
let mut digit;
while (ind1>=0)||(ind2>=0) {
digit = 10;
if ind1>=0 {
digit+=self.digits[ind1 as usize];
}
if ind2>=0 {
digit-=other.digits[ind2 as usize];
}
digit-=carry;
if digit>=10 {
digit-=10;
carry=0;
}
else {
carry=1;
}
result.push(digit);
ind1-=1;
ind2-=1;
}
result.reverse();
Bigint::from_components(result, self.sign)
}
}
else if self.sign==1 {
self.add(-other)
}
else {
-(-self).add(other)
}
}
}

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

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

failures:

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


failures:
    solution_test::test_neutralization

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

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

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

Илиян качи първо решение на 24.11.2020 17:35 (преди 8 месеца)

Илиян качи решение на 27.11.2020 15:32 (преди 8 месеца)

#[cfg(test)]
mod tests {
#[test]
fn it_works() {
assert_eq!(2 + 2, 4);
}
use crate::Bigint;
#[test]
fn first_test() {
assert_eq!(Bigint::new(),Bigint::from_components(vec![0,0,0,0],-1));
assert_eq!(Bigint::from_components(vec![0,1,2,3],-1),Bigint::from_components(vec![1,2,3],-1));
let mut num = Bigint::from_components(vec![1,2],1);
assert_eq!(true,num.is_positive());
assert_eq!(false,num.is_negative());
num = Bigint::from_components(vec![1,2],-1);
assert_eq!(false,num.is_positive());
assert_eq!(true,num.is_negative());
num = Bigint::from_components(vec![0],-1);
assert_eq!(false,num.is_positive());
assert_eq!(false,num.is_negative());
}
use std::str::FromStr;
use crate::ParseError;
#[test]
fn second_test() {
assert_eq!(Bigint::new(),Bigint::from_str("-000000").unwrap());
assert_eq!(Bigint::from_components(vec![1,2,3],-1),Bigint::from_str("-00123").unwrap());
assert_eq!(Bigint::from_components(vec![1,2,3],1),Bigint::from_str("+00123").unwrap());
assert_eq!(Bigint::from_components(vec![1,2,3],1),Bigint::from_str("00123").unwrap());
assert_eq!(Bigint::from_components(vec![1,2,3],1),Bigint::from_str("123").unwrap());
assert_eq!(Err(ParseError{}),Bigint::from_str("00k123"));
assert_eq!(Err(ParseError{}),Bigint::from_str("*00123"));
assert_eq!(Err(ParseError{}),Bigint::from_str("+-"));
assert_eq!(Ok(Bigint::new()),Bigint::from_str(""));
}
use std::cmp::Ordering;
#[test]
fn third_test() {
assert_eq!(Bigint::from_str("-0000").unwrap().cmp(&Bigint::from_str("0").unwrap()),Ordering::Equal);
assert_eq!(Bigint::from_str("-0000123").unwrap().cmp(&Bigint::from_str("-123").unwrap()),Ordering::Equal);
assert_eq!(Bigint::from_str("13").unwrap().cmp(&Bigint::from_str("123").unwrap()),Ordering::Less);
assert_eq!(Bigint::from_str("-123").unwrap().cmp(&Bigint::from_str("+1").unwrap()),Ordering::Less);
assert_eq!(Bigint::from_str("+12").unwrap().cmp(&Bigint::from_str("-42").unwrap()),Ordering::Greater);
assert_eq!(Bigint::from_str("-42").unwrap().cmp(&Bigint::from_str("-123").unwrap()),Ordering::Greater);
}
use std::ops::{Add, Sub};
#[test]
fn fourth_test() {
let a = Bigint::from_str("123").unwrap();
let b = Bigint::from_str("99").unwrap();
let c = Bigint::from_str("999").unwrap();
assert_eq!(a.clone().add(b.clone()),Bigint::from_str("222").unwrap());
assert_eq!(a.clone().add(c.clone()),Bigint::from_str("1122").unwrap());
assert_eq!((-a.clone()).add(-b.clone()),Bigint::from_str("-222").unwrap());
assert_eq!((-a.clone()).add(b.clone()),Bigint::from_str("-24").unwrap());
assert_eq!(a.clone().add(-b.clone()),Bigint::from_str("24").unwrap());
assert_eq!(a.clone().add(-c.clone()),Bigint::from_str("-876").unwrap());
assert_eq!((-b.clone()).add(a.clone()),Bigint::from_str("24").unwrap());
assert_eq!(a.clone().sub(b.clone()),Bigint::from_str("24").unwrap());
assert_eq!(a.clone().sub(c.clone()),Bigint::from_str("-876").unwrap());
assert_eq!((-a.clone()).sub(-b.clone()),Bigint::from_str("-24").unwrap());
assert_eq!((-b.clone()).sub(-a.clone()),Bigint::from_str("24").unwrap());
assert_eq!((-a.clone()).sub(b.clone()),Bigint::from_str("-222").unwrap());
assert_eq!(a.clone().sub(-b.clone()),Bigint::from_str("222").unwrap());
assert_eq!(a.clone().sub(a.clone()),Bigint::from_str("0").unwrap());
assert_eq!(a.clone().add(Bigint::new()),a);
assert_eq!(Bigint::new().sub(a.clone()),-a.clone());
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
Bigint {
sign: 1,
digits: vec![0],
}
}
- pub fn from_components(digits: Vec<u8>, sign: i8) -> Self {
+ fn from_components(digits: Vec<u8>, sign: i8) -> Self {
if (sign!=1)&&(sign!=-1) {
panic!("Wrong sign in from_components");
}
let mut d = Vec::<u8>::new();
let mut flag : bool;
flag=false;
for digit in digits.iter() {
if (digit==&0)&&(flag==false) {
continue;
}
if digit!=&0 {
flag=true;
}
d.push(*digit);
}
if d.len()==0 {
d.push(0);
Bigint {
sign: 1,
digits: d,
}
}
else {
Bigint {
sign: sign,
digits: d
}
}
}
pub fn is_positive(&self) -> bool {
if (self.sign==1)&&(self.digits!=vec![0]) {
true
}
else {
false
}
}
pub fn is_negative(&self) -> bool {
if (self.sign==-1)&&(self.digits!=vec![0]) {
true
}
else {
false
}
}
}
fn abs(num: &Bigint) -> Bigint {
if num.is_negative()==true {
-(num.clone())
}
else {
num.clone()
}
}
use std::str::FromStr;
#[derive(Debug,PartialEq)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut chars = s.chars();
let first = chars.next();
match first {
None => Ok(Bigint::new()),
Some('0'..='9') | Some('+') | Some ('-') => {
let mut sign : i8;
let mut digs = Vec::<u8>::new();
sign=1;
if first==Some('-') {
sign=-1;
}
else if first!=Some('+') {
digs.push((first.unwrap() as u8)-('0' as u8));
}
let mut flag = false;
for c in chars {
if (c<'0')||(c>'9') {
flag=true;
break;
}
digs.push((c as u8)-('0' as u8));
}
if flag==true {
Err(ParseError{})
}
else {
Ok(Bigint::from_components(digs,sign))
}
},
_ => Err(ParseError{}),
}
}
}
use std::ops::Neg;
impl Neg for Bigint {
type Output = Self;
fn neg(self) -> Self::Output {
Bigint {
sign: -self.sign,
digits: self.digits,
}
}
}
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==-1)&&(other.sign==1) {
Ordering::Less
}
else if (self.sign==1)&&(other.sign==-1) {
Ordering::Greater
}
else if self.sign==1 {
if self.digits.len()<other.digits.len() {
Ordering::Less
}
else if self.digits.len()>other.digits.len() {
Ordering::Greater
}
else {
self.digits.cmp(&other.digits)
}
}
else {
abs(&self).cmp(&abs(&other)).reverse()
}
}
}
use std::ops::{Add, Sub};
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign==other.sign {
let mut result = Vec::<u8>::new();
let mut carry = 0u8;
let mut ind1 = (self.digits.len() as isize) -1;
let mut ind2 = (other.digits.len() as isize) -1;
let mut digit;
while (ind1>=0)||(ind2>=0) {
digit = carry;
if ind1>=0 {
digit+=self.digits[ind1 as usize];
}
if ind2>=0 {
digit+=other.digits[ind2 as usize];
}
result.push(digit%10);
carry=digit/10;
ind1-=1;
ind2-=1;
}
result.push(carry);
result.reverse();
Bigint::from_components(result, self.sign)
}
else if self.sign==1 {
if abs(&self).cmp(&abs(&other))==Ordering::Less {
-(-other).sub(self)
}
else {
self.sub(-other)
}
}
else {
if abs(&self).cmp(&abs(&other))==Ordering::Less {
other.sub(-self)
}
else {
-(-self).sub(other)
}
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
if self.sign==other.sign {
if abs(&self).cmp(&abs(&other))==Ordering::Less {
-other.sub(self)
}
else {
let mut result = Vec::<u8>::new();
let mut carry = 0u8;
let mut ind1 = (self.digits.len() as isize) -1;
let mut ind2 = (other.digits.len() as isize) -1;
let mut digit;
while (ind1>=0)||(ind2>=0) {
digit = 10;
if ind1>=0 {
digit+=self.digits[ind1 as usize];
}
if ind2>=0 {
digit-=other.digits[ind2 as usize];
}
digit-=carry;
if digit>=10 {
digit-=10;
carry=0;
}
else {
carry=1;
}
result.push(digit);
ind1-=1;
ind2-=1;
}
result.reverse();
Bigint::from_components(result, self.sign)
}
}
else if self.sign==1 {
self.add(-other)
}
else {
-(-self).add(other)
}
}
}

Тестовете за невалиден низ е добре да включват UTF8 низове, примерно кирилица или emoji. Лесно е да се обърка някой и да използва достъп до низа през байтове, и е добре да има тестове да го хванат.

Все пак, за останалите неща си покрил доста разумни случаи, и при сравнение, и при събиране и изваждане, така че ще ти дам бонус точка. Разгледай обаче пълния тест и моето решение -- мисля че можеш доста да си опростиш и кода, и особено тестовете.