Решение на Polynomial от Михаил Стойков
Резултати
- 13 точки от тестове
- 0 бонус точки
- 13 точки общо
- 13 успешни тест(а)
- 2 неуспешни тест(а)
Код
use std::ops::{Add, Div, Mul};
use std::default::Default;
use std::iter::{IntoIterator, FromIterator};
/// Структура която представя полином от `n`та степен на една променлива
///
/// Пример за такъв полином e `x^2 + 2*x + 1`.
#[derive(Debug, Clone)]
pub struct Polynomial {
coefficients: Vec<f64>,
}
/// TODO: figure out the magic incantatiton that will let me use an expression that is evaluated
/// once
macro_rules! add_two {
($longer:ident, $shorter:ident, $length:ident) => (
$longer.coefficients
.iter()
.take($length)
.map(|x| *x)
.chain($longer.coefficients.iter().skip($length).zip($shorter).map(
|x| {
x.0 + x.1
},
))
.collect::<Vec<f64>>()
.into()
)
}
impl Polynomial {
/// Проверява дали една точка удовлетворява полинома
///
/// Ако имаме точка (x, y) тогава тя удовлетворява полинома P(X), ако `|P(x) - y| < 1e-10`.
pub fn has(&self, point: &(f64, f64)) -> bool {
let l = self.coefficients.len();
(self.coefficients
.iter()
.enumerate()
.map(|(index, coef)| coef * point.0.powi((l - index - 1) as i32))
.sum::<f64>() - point.1)
.abs() < 1e-10
}
fn lj(x_s: &Vec<f64>, j: usize) -> Self {
let x_j = x_s[j];
let rest = x_s.iter().take(j).chain(x_s.iter().skip(j + 1));
let (numerator, denominator): (Vec<_>, Vec<_>) =
rest.map(|&x| (Self::from(vec![1.0, -x]), x_j - x)).unzip();
numerator.into_iter().fold::<Self, _>(
vec![1.0].into(),
|acc, p| p * acc,
) / denominator.iter().product()
}
/// Намира полином, който минава през подадените точки, по метода на Лагранж, описан
/// по-долу.
///
/// Примерен полином, който минава през точките (-1.0, 0.0), (0.0, 1.0), (1.0, 4.0)
/// е `x^2 + 2*x + 1`.
///
/// Ако две точки имат равни X координати, върнете `None`.
///
/// Няма да тестваме с NAN или INFINITY, така че не е нужно да проверявате специфично за тези
/// стойности. Можете да го направите, разбира се, ако решите.
///
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let (x, y): (Vec<_>, Vec<_>) = points.into_iter().unzip();
let numerator: Vec<_> = y.iter()
.enumerate()
.map::<Self, _>(|(index, &y)| Self::lj(&x, index) * y)
.collect();
if !numerator.iter().all(|p| {
p.coefficients.iter().all(|coef| coef.is_finite())
})
{
return None;
}
let result: Polynomial = numerator.into_iter().fold(
vec![0.0].into(),
|acc, p| acc + p,
);
return Some(result);
}
}
impl IntoIterator for Polynomial {
type Item = f64;
type IntoIter = ::std::vec::IntoIter<f64>;
fn into_iter(self) -> Self::IntoIter {
self.coefficients.into_iter()
}
}
impl FromIterator<f64> for Polynomial {
fn from_iter<T>(iter: T) -> Self
where
T: IntoIterator<Item = f64>,
{
// TODO! find out how this is overflows the stack if ::<Vec<f64>>().into() is removed
iter.into_iter().collect::<Vec<f64>>().into()
}
}
impl From<Vec<f64>> for Polynomial {
/// Създава нов полином от подадените коефициенти
///
/// Редът на коефициентите е от най-високата степен на променливата към най-малката.
///
/// Ако е подаден празен вектор се създава полином отговарящ на константата `0.0`. Ако на
/// най-високите степени на полинома има нули, премахнете ги. (Това е причината аргумента
/// `coefs` да се предава като `mut coefs`. Тоест:
///
/// - Polynomial::from(vec![]) == Polynomial::from(vec![0.0]);
/// - Polynomial::from(vec![0.0, 1.0]) == Polynomial::from(vec![1.0]);
///
/// Полином който отговаря на Polynomial::from(vec![1.0, 2.0, 0.0, 3.0])
/// е `x^3 + 2.0*x^2 + 3.0`.
///
fn from(mut coefs: Vec<f64>) -> Self {
coefs = coefs.into_iter().skip_while(|x| (*x) == 0.0).collect();
Self { coefficients: coefs }
}
}
/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial {
fn default() -> Self {
Self { coefficients: vec![] }
}
}
/// Проверява дали два полинома са равни.
///
/// Сравнява коефициентите пред всяка степен от двата полинома. Приемаме, че два коефициента
/// са равни ако разликата между тях е по-малка от 1e-10, т.е. |Ai - Bi| < 1e-10.
///
/// Ако полиномите имат водещи нули те трябва да се игнорират. Например следните два полинома
/// са равни:
///
/// - x^3 + 2.0*x^2 + 3.0
/// - 0.0*x^5 + 0.0*x^4 + x^3 + 2.0*x^2 + 3.0
///
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
self.coefficients == rhs.coefficients
}
}
/// Умножава полином с f64 -- всички коефициенти биват умножени с дясната страна.
///
/// За този метод, и по-долните, вижте внимателно сигнатурата на метода и мислете по какъв
/// начин се предава `self` и как може да използвате това. Може да си опростите живота, ако
/// мислите за ownership-а на стойността.
///
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
self.into_iter().map(|x| x * rhs).collect()
}
}
/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
return self.into_iter().map(|x| x / rhs).collect();
}
}
/// Умножава полином с полином -- всички компоненти на полинома биват умножени с всички
/// компоненти на десния полином.
///
/// Пример:
///
/// Polynomial::from(vec![1.0, 2.0]) * Polynomial::from(vec![2.0, 1.0])
/// // => Polynomial::from(vec![2.0, 5.0, 2.0])
///
impl Mul for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: Polynomial) -> Self::Output {
let new_size = self.coefficients.len() + rhs.coefficients.len() - 1;
let mut result: Vec<f64> = vec![0.0; new_size];
self.coefficients.iter().enumerate().for_each(
|(lindex, lcoef)| {
rhs.coefficients
.iter()
.enumerate()
.map(|(rindex, rcoef)| (lindex + rindex, lcoef * rcoef))
.for_each(|(index, coef)| result[index] += coef)
},
);
result.into()
}
}
/// Събира полином с полином -- коефициентите на едни и същи степени се събират. Ако това
/// докара най-високите степени до 0, не забравяйте да премахнете нулите, също както `from`
/// метода по-горе.
///
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let llen = self.coefficients.len();
let rlen = rhs.coefficients.len();
if llen > rlen {
let len = llen - rlen;
return add_two!(self, rhs, len);
}
let len = rlen - llen;
return add_two!(rhs, self, len);
}
}
Лог от изпълнението
Compiling solution v0.1.0 (file:///tmp/d20171121-6053-1jch6c4/solution)
Finished dev [unoptimized + debuginfo] target(s) in 6.46 secs
Running target/debug/deps/solution-200db9172ea1f728
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Running target/debug/deps/solution_test-e3c9eb714e09105e
running 15 tests
test solution_test::test_add_poly ... ok
test solution_test::test_add_poly_zero_one ... ok
test solution_test::test_arithmetic_properties ... FAILED
test solution_test::test_create_poly ... ok
test solution_test::test_div_poly_f64 ... ok
test solution_test::test_div_poly_f64_zero ... ok
test solution_test::test_fp_comparison ... FAILED
test solution_test::test_has_point ... ok
test solution_test::test_lagrange_poly_1 ... ok
test solution_test::test_lagrange_poly_2 ... ok
test solution_test::test_lagrange_poly_err_eq_x ... ok
test solution_test::test_mul_poly ... ok
test solution_test::test_mul_poly_f64 ... ok
test solution_test::test_mul_poly_f64_zero ... ok
test solution_test::test_mul_poly_zero_one ... ok
failures:
---- solution_test::test_arithmetic_properties stdout ----
thread 'solution_test::test_arithmetic_properties' panicked at 'assertion failed: `(left == right)`
left: `Polynomial { coefficients: [4, 15.3, 39.97, 236.64000000000001, 416.11, 564, 0] }`,
right: `Polynomial { coefficients: [4, 15.3, 39.97, 236.64, 416.11, 564, 0] }`', tests/solution_test.rs:131:4
note: Run with `RUST_BACKTRACE=1` for a backtrace.
---- solution_test::test_fp_comparison stdout ----
thread 'solution_test::test_fp_comparison' panicked at 'assertion failed: `(left == right)`
left: `Polynomial { coefficients: [3, 0.00000000000000000000000030000000000000002] }`,
right: `Polynomial { coefficients: [3, 0.0000000000000000000000003] }`', tests/solution_test.rs:32:4
failures:
solution_test::test_arithmetic_properties
solution_test::test_fp_comparison
test result: FAILED. 13 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out
error: test failed, to rerun pass '--test solution_test'