Решение на Bigint от Християн Генчев
Към профила на Християн Генчев
Резултати
- 13 точки от тестове
- 0 бонус точки
- 13 точки общо
- 13 успешни тест(а)
- 2 неуспешни тест(а)
Код
Лог от изпълнението
Compiling solution v0.1.0 (/tmp/d20201127-2274206-h5y4b7/solution)
warning: variable does not need to be mutable
--> src/lib.rs:126:15
|
126 | fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
| ----^^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> src/lib.rs:126:34
|
126 | fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
| ----^^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/lib.rs:153:20
|
153 | fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
| ----^^^^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/lib.rs:153:41
|
153 | fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
| ----^^^^^^^
| |
| help: remove this `mut`
warning: 4 warnings emitted
Finished test [unoptimized + debuginfo] target(s) in 1.64s
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 ... FAILED
test solution_test::test_comparison ... FAILED
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
failures:
---- solution_test::test_bigint_zero_sign stdout ----
thread 'main' panicked at 'assertion failed: !zero.is_positive()', tests/solution_test.rs:21:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
---- solution_test::test_comparison stdout ----
thread 'main' panicked at 'assertion failed: bigint("-1") > bigint("-2")', tests/solution_test.rs:171:5
failures:
solution_test::test_bigint_zero_sign
solution_test::test_comparison
test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'
История (2 версии и 2 коментара)
Християн качи решение на 27.11.2020 16:04 (преди почти 5 години)
use std::cmp::*;
use std::str::FromStr;
use std::ops::{Add, Sub};
use std::cmp::Ordering;
#[derive(Debug, PartialEq, Eq)]
pub struct Bigint {
sign: i8,
digits: Vec<u8>,
}
impl Bigint {
pub fn new() -> Self {
return Bigint { sign: i8::MAX, digits: Vec::new() };
}
fn get_inversed(&self) -> Self {
Self {
sign: if self.sign == i8::MAX {i8::MIN} else {i8::MAX},
digits: self.digits.clone(),
}
}
fn get_abs(&self) -> Self {
Self {
sign: i8::MAX,
digits: self.digits.clone(),
}
}
fn get_size(&self) -> usize {
self.digits.len()
}
fn get_sign_as_char(&self) -> char {
return if self.sign == i8::MAX { '+' } else { '-' }
}
pub fn print(&self) {
println!("{:?} {:?}", self.get_sign_as_char(), self.digits)
}
pub fn is_positive(&self) -> bool {
return self.sign == i8::MAX;
}
pub fn is_negative(&self) -> bool {
return self.sign == i8::MIN;
}
}
#[derive(Debug)]
pub struct ParseError;
impl FromStr for Bigint {
type Err = ParseError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
let mut digits: Vec<u8> = Vec::new();
let mut sign: i8 = i8::MAX;
let mut init_index = 0;
let chars: Vec<char> = s.chars().collect();
if chars.len() != 0 {
if chars[0] == '+' {
sign = i8::MAX;
init_index = 1;
} else if chars[0] == '-' {
sign = i8::MIN;
init_index = 1;
}
for i in init_index..chars.len() {
let char = chars[i];
if !char.is_digit(10) {
return Err(ParseError);
}
digits.push(char.to_digit(10).unwrap() as u8)
}
while !digits.is_empty() && digits[0] == 0 {
digits.remove(0);
}
}
if digits.len() == 0 {
sign = i8::MAX;
}
Ok(Bigint { digits, sign })
}
}
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 {
if self.sign < other.sign {
return Ordering::Less;
} else if self.sign > other.sign {
return Ordering::Greater;
}
}
let is_negative: bool = self.is_negative();
if self.get_size() != other.get_size() {
if self.get_size() < other.get_size() {
return if is_negative { Ordering::Greater } else { Ordering::Less };
} else if self.get_size() > other.get_size() {
return if is_negative { Ordering::Less } else { Ordering::Greater };
}
}
return self.digits.cmp(&other.digits);
}
}
fn add_digits(mut left: Vec<u8>, mut right: Vec<u8>) -> Vec<u8> {
let mut res: Vec<u8> = Vec::new();
let bigger_length = std::cmp::max(left.len(), right.len());
let mut left_reversed: Vec<u8> = left.clone();
let mut right_reversed: Vec<u8> = right.clone();
left_reversed.reverse();
right_reversed.reverse();
// pad with zeros
left_reversed.append(&mut vec![0; bigger_length - left.len()]);
right_reversed.append(&mut vec![0; bigger_length - right.len()]);
let mut carrier:u8 = 0;
for i in 0..bigger_length {
res.push((left_reversed[i] + right_reversed[i] + carrier.clone()) % 10);
carrier = (left_reversed[i] + right_reversed[i] + carrier) / 10;
}
if carrier != 0 {
res.push(carrier);
}
res.reverse();
return res;
}
fn subtract_digits(mut larger: Vec<u8>, mut smaller: Vec<u8>) -> Vec<u8> {
let mut res: Vec<u8> = Vec::new();
let bigger_length = std::cmp::max(larger.len(), smaller.len());
let mut larger_reversed: Vec<u8> = larger.clone();
let mut smaller_reversed: Vec<u8> = smaller.clone();
larger_reversed.reverse();
smaller_reversed.reverse();
// pad with zeros
larger_reversed.append(&mut vec![0; bigger_length - larger.len()]);
smaller_reversed.append(&mut vec![0; bigger_length - smaller.len()]);
let mut carrier:u8 = 0;
for i in 0..bigger_length {
let sub: u8 = 10 + larger_reversed[i] - smaller_reversed[i];
res.push((sub.clone() - carrier.clone()) % 10);
carrier = ((sub - carrier) < 10) as u8
}
res.reverse();
// remove padding
while !res.is_empty() && res[0] == 0 {
res.remove(0);
}
return res;
}
impl Add for Bigint {
type Output = Bigint;
fn add(self, other: Self) -> Self {
if self.sign == other.sign {
return Self {
sign: self.sign.clone(),
digits: add_digits(self.digits, other.digits),
}
}
let bigger: Vec<u8> = if self.get_abs() > other.get_abs() { self.digits.clone() } else { other.digits.clone() };
let smaller: Vec<u8> = if self.get_abs() < other.get_abs() { self.digits.clone() } else { other.digits.clone() };
let res: Vec<u8> = subtract_digits(bigger, smaller);
return Self {
sign: if res.is_empty() { i8::MAX } else if self.get_abs() > other.get_abs() { self.sign.clone() } else { other.sign.clone() },
digits: res,
}
}
}
impl Sub for Bigint {
type Output = Bigint;
fn sub(self, other: Self) -> Self {
if self.sign != other.sign {
return Self {
sign: self.sign.clone(),
digits: add_digits(self.get_inversed().digits, other.digits)
}
}
return self + other.get_inversed()
}
-}
+}
+
+// custom tests
+// use solution::*;
+// use std::str::FromStr;
+//
+// #[test]
+// fn test_from_str_success() {
+// Bigint::from_str("");
+// Bigint::from_str("-0");
+// Bigint::from_str("+0");
+// Bigint::from_str("0");
+//
+// Bigint::from_str("-");
+// Bigint::from_str("+");
+// }
Просто викане на from_str може би ще ти потвърди, че поне кода не panic-ва, но това е доста ниска летва. Ако тези примери създават валиден Bigint, можеше да викнеш .unwrap() за да провериш, че не връщат Err, или даже assert!(Bigint::from_str("").is_ok()).
Виждам, че долу си сложил същите извиквания със сравнение на резултат, но тогава не си заслужава да запазиш този тест.
+//
+// #[test]
+// fn test_from_str_01_error() {
+// assert!(Bigint::from_str("a").is_err());
+// assert!(Bigint::from_str("1a").is_err());
+// assert!(Bigint::from_str("111111111a").is_err());
+// assert!(Bigint::from_str("-111111111a").is_err());
+// assert!(Bigint::from_str("-+111111111a").is_err());
+// assert!(Bigint::from_str("+111111 111").is_err());
+// assert!(Bigint::from_str("++").is_err());
+// assert!(Bigint::from_str("+-").is_err());
+// assert!(Bigint::from_str("--").is_err());
+// }
+//
+// #[test]
+// fn test_equality_leading_zeros() {
+// let number_normal = Bigint::from_str("123").unwrap();
+// let number_padded = Bigint::from_str("0000123").unwrap();
+//
+// assert_eq!(number_normal, number_padded);
+// }
+//
+// #[test]
+// fn test_equality_zero() {
+// let zero_empty = Bigint::from_str("").unwrap();
+// let zero_plus = Bigint::from_str("+").unwrap();
+// let zero_minus = Bigint::from_str("-").unwrap();
+// let zero_positive = Bigint::from_str("+0").unwrap();
+// let zero_negative = Bigint::from_str("-0").unwrap();
+// let zero_neutral = Bigint::from_str("0").unwrap();
+//
+// assert_eq!(zero_empty, zero_positive);
+// assert_eq!(zero_positive, zero_plus);
+// assert_eq!(zero_plus, zero_minus);
+// assert_eq!(zero_minus, zero_negative);
+// assert_eq!(zero_negative, zero_neutral);
+// }
+//
+// #[test]
+// fn test_equality_positive() {
+// let biging_left = Bigint::from_str("1000000000000000000000000000000000000000000").unwrap();
+// let biging_right = Bigint::from_str("1000000000000000000000000000000000000000000").unwrap();
+//
+// assert_eq!(biging_left, biging_right);
+// assert_eq!(Bigint::from_str("200").unwrap(), Bigint::from_str("+200").unwrap());
+// }
+//
+// #[test]
+// fn test_equality_negative() {
+// let biging_left = Bigint::from_str("-1000000000000000000000000000000000000000000").unwrap();
+// let biging_right = Bigint::from_str("-1000000000000000000000000000000000000000000").unwrap();
+//
+// assert_eq!(biging_left, biging_right);
+// assert_eq!(Bigint::from_str("-200").unwrap(), Bigint::from_str("-200").unwrap());
+// }
+//
+// #[test]
+// fn test_ord() {
+// let positive_small = Bigint::from_str("10").unwrap();
+// let positive_big = Bigint::from_str("1000000000000000000000000000000000000000000").unwrap();
+// let negative_small = Bigint::from_str("-1").unwrap();
+// let negative_big = Bigint::from_str("-1000000000000000000000000000000000000000000").unwrap();
+//
+// assert!(positive_small < positive_big);
+// assert!(negative_small < positive_big);
+// assert!(negative_big < positive_big);
+// assert!(negative_big < negative_small);
+// }
+//
+// #[test]
+// fn test_add_positive() {
+// assert_eq!(Bigint::from_str("10").unwrap() + Bigint::from_str("10").unwrap(),
+// Bigint::from_str("20").unwrap());
+//
+// assert_eq!(Bigint::from_str("1000000000000000000000000000000000000000000").unwrap()
+// + Bigint::from_str("1000000000000000000000000000000000000000000").unwrap(),
+// Bigint::from_str("2000000000000000000000000000000000000000000").unwrap());
+//
+// assert_eq!(Bigint::from_str("501").unwrap() + Bigint::from_str("501").unwrap(),
+// Bigint::from_str("1002").unwrap());
+// }
+//
+// #[test]
+// fn test_add_negative() {
+// assert_eq!(Bigint::from_str("-10").unwrap() + Bigint::from_str("-10").unwrap(),
+// Bigint::from_str("-20").unwrap());
+//
+// assert_eq!(Bigint::from_str("-1000000000000000000000000000000000000000000").unwrap()
+// + Bigint::from_str("-1000000000000000000000000000000000000000000").unwrap(),
+// Bigint::from_str("-2000000000000000000000000000000000000000000").unwrap());
+//
+// assert_eq!(Bigint::from_str("-501").unwrap() + Bigint::from_str("-501").unwrap(),
+// Bigint::from_str("-1002").unwrap());
+// }
+//
+// #[test]
+// fn test_add_any() {
+// assert_eq!(Bigint::from_str("-11").unwrap() + Bigint::from_str("11").unwrap(),
+// Bigint::from_str("").unwrap());
+// }
+//
+// #[test]
+// fn test_sub_positive() {
+// assert_eq!(Bigint::from_str("50").unwrap() - Bigint::from_str("40").unwrap(),
+// Bigint::from_str("10").unwrap());
+//
+// assert_eq!(Bigint::from_str("1000").unwrap() - Bigint::from_str("50").unwrap(),
+// Bigint::from_str("950").unwrap());
+//
+// assert_eq!(Bigint::from_str("10").unwrap() - Bigint::from_str("10").unwrap(),
+// Bigint::from_str("0").unwrap());
+//
+// assert_eq!(Bigint::from_str("199").unwrap() - Bigint::from_str("9").unwrap(),
+// Bigint::from_str("190").unwrap());
+//
+// assert_eq!(Bigint::from_str("9").unwrap() - Bigint::from_str("199").unwrap(),
+// Bigint::from_str("-190").unwrap());
+// }
+//
+// #[test]
+// fn test_sub_negative() {
+// assert_eq!(Bigint::from_str("-50").unwrap() - Bigint::from_str("-40").unwrap(),
+// Bigint::from_str("-10").unwrap());
+//
+// assert_eq!(Bigint::from_str("-1000").unwrap() - Bigint::from_str("-50").unwrap(),
+// Bigint::from_str("-950").unwrap());
+//
+// assert_eq!(Bigint::from_str("-10").unwrap() - Bigint::from_str("-10").unwrap(),
+// Bigint::from_str("0").unwrap());
+//
+// assert_eq!(Bigint::from_str("-199").unwrap() - Bigint::from_str("-9").unwrap(),
+// Bigint::from_str("-190").unwrap());
+//
+// assert_eq!(Bigint::from_str("-9").unwrap() - Bigint::from_str("-199").unwrap(),
+// Bigint::from_str("190").unwrap());
+// }
+//
+// #[test]
+// fn test_sub_mixed() {
+// assert_eq!(Bigint::from_str("-1000").unwrap() - Bigint::from_str("50").unwrap(),
+// Bigint::from_str("-1050").unwrap());
+//
+// assert_eq!(Bigint::from_str("50").unwrap() - Bigint::from_str("-1000").unwrap(),
+// Bigint::from_str("1050").unwrap());
+//
+// assert_eq!(Bigint::from_str("-10").unwrap() - Bigint::from_str("-10").unwrap(),
+// Bigint::from_str("0").unwrap());
+//
+// assert_eq!(Bigint::from_str("10").unwrap() + Bigint::from_str("10").unwrap() + Bigint::from_str("10").unwrap(),
+// Bigint::from_str("30").unwrap());
+//
+// assert_eq!(Bigint::from_str("10").unwrap() + Bigint::from_str("10").unwrap() - Bigint::from_str("10").unwrap(),
+// Bigint::from_str("10").unwrap());
+//
+// assert_eq!(Bigint::from_str("10").unwrap() + Bigint::from_str("10").unwrap() - Bigint::from_str("-10").unwrap(),
+// Bigint::from_str("30").unwrap());
+//
+// assert_eq!(Bigint::from_str("10").unwrap() - Bigint::from_str("10").unwrap() - Bigint::from_str("-10").unwrap(),
+// Bigint::from_str("10").unwrap());
+// }
+//
+// fn bigint(s: &str) -> Bigint {
+// Bigint::from_str(s).unwrap()
+// }
+//
+// #[test]
+// fn test_basic() {
+// assert_eq!(Bigint::new(), bigint("0"));
+// assert!(Bigint::from_str("foobar").is_err());
+//
+// assert!(bigint("1").is_positive());
+// assert!(bigint("-1").is_negative());
+//
+// assert_eq!(bigint("123") + bigint("456"), bigint("579"));
+// assert_eq!(bigint("579") - bigint("456"), bigint("123"));
+//
+// assert!(bigint("123") > bigint("122"));
+// }
Липсват ти тестове за не-utf8 низове, като кирилица или emoji. Това лесно може да се сбърка и си заслужава да се тества. Липсват ти и някои случаи за други неща, като например сравнение на числа с еднакъв знак и еднакъв брой цифри.
Допълнително, нямаше нужда да си закоментираш тестовете. От начина, по който си ги написал, може би не знаеш как да ги вкараш в кода -- може да разгледаш лекция 5 и/или да видиш някое от домашните с бонус звездичка, за да видиш как става.
Просто викане на
from_strможе би ще ти потвърди, че поне кода не panic-ва, но това е доста ниска летва. Ако тези примери създават валиден Bigint, можеше да викнеш.unwrap()за да провериш, че не връщатErr, или дажеassert!(Bigint::from_str("").is_ok()).Виждам, че долу си сложил същите извиквания със сравнение на резултат, но тогава не си заслужава да запазиш този тест.