Решение на Polynomial от Димитър Узунов
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
use std::ops::{Add, Mul, Div};
#[derive(Debug, Clone, Default)]
pub struct Polynomial {
coefs: Vec<f64>,
}
impl Polynomial {
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
(self.value_at(x) - y).abs() < 1e-10
}
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
if Self::same_xs(&points) {
return None;
}
let xs = points.iter()
.map(|&(x, _)| x)
.collect();
let result = points.into_iter()
.enumerate()
.fold(Self::default(), |acc, (j, (x, y))| {
acc + Self::l(&xs, j, x) * y
});
Some(result)
}
fn value_at(&self, x: f64) -> f64 {
self.coefs.iter()
.rev()
.enumerate()
.fold(0.0, |acc, (exp, coef)| acc + coef * x.powi(exp as i32))
}
fn l(xs: &Vec<f64>, j: usize, x_j: f64) -> Self {
xs.into_iter()
.enumerate()
.filter(|&(m, _)| m != j)
.fold(Self::from(vec![1.0]), |acc, (_, x)| {
let difference = x_j - x;
acc * Self::from(vec![1.0 / difference, -x / difference])
})
}
fn same_xs(points: &Vec<(f64, f64)>) -> bool {
for (i, &(x1, _)) in points.iter().enumerate() {
for (j, &(x2, _)) in points.iter().enumerate() {
if i != j && (x1 - x2).abs() < 1e-10 {
return true;
}
}
}
false
}
}
impl From<Vec<f64>> for Polynomial {
fn from(coefs: Vec<f64>) -> Self {
let coefs = coefs.into_iter()
.skip_while(|&coef| coef == 0.0)
.collect();
Self { coefs }
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
let have_eq_lengths = self.coefs.len() == rhs.coefs.len();
let mut coefs_iter = self.coefs.iter().zip(rhs.coefs.iter());
have_eq_lengths && coefs_iter.all(|(a, b)| (a - b).abs() < 1e-10)
}
}
impl Mul<f64> for Polynomial {
type Output = Self;
fn mul(self, rhs: f64) -> Self {
let coefs = self.coefs.into_iter()
.map(|coef| coef * rhs)
.collect::<Vec<f64>>();
Self::from(coefs)
}
}
impl Div<f64> for Polynomial {
type Output = Self;
fn div(self, rhs: f64) -> Self {
let coefs = self.coefs.into_iter()
.map(|coef| coef / rhs)
.collect::<Vec<f64>>();
Self::from(coefs)
}
}
impl Mul for Polynomial {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
let mut coefs = vec![0.0; self.coefs.len() + rhs.coefs.len() - 1];
for (i, a) in self.coefs.into_iter().enumerate() {
for (j, b) in rhs.coefs.iter().enumerate() {
coefs[i + j] += a * b;
}
}
Self::from(coefs)
}
}
impl Add for Polynomial {
type Output = Self;
fn add(self, rhs: Self) -> Self {
let (first_iter, second_iter) =
match self.coefs.len() < rhs.coefs.len() {
true => (rhs.coefs.into_iter(), self.coefs.into_iter()),
_ => (self.coefs.into_iter(), rhs.coefs.into_iter()),
};
let length_difference = first_iter.len() - second_iter.len();
let take_first = first_iter.clone().take(length_difference);
let calculate_rest = first_iter.skip(length_difference)
.zip(second_iter)
.map(|(a, b)| a + b);
let coefs: Vec<f64> = take_first.chain(calculate_rest).collect();
Self::from(coefs)
}
}
Лог от изпълнението
Compiling solution v0.1.0 (file:///tmp/d20171121-6053-7pvyns/solution)
Finished dev [unoptimized + debuginfo] target(s) in 5.78 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 ... ok
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 ... ok
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
test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Doc-tests solution
running 0 tests
test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
История (2 версии и 0 коментара)
Димитър качи решение на 21.11.2017 10:36 (преди почти 8 години)
use std::ops::{Add, Mul, Div};
#[derive(Debug, Clone, Default)]
pub struct Polynomial {
coefs: Vec<f64>,
}
impl Polynomial {
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
(self.value_at(x) - y).abs() < 1e-10
}
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
if Self::same_xs(&points) {
return None;
}
let xs = points.iter()
.map(|&(x, _)| x)
.collect();
let result = points.into_iter()
.enumerate()
.fold(Self::default(), |acc, (j, (x, y))| {
acc + Self::l(&xs, j, x) * y
});
Some(result)
}
fn value_at(&self, x: f64) -> f64 {
self.coefs.iter()
.rev()
.enumerate()
.fold(0.0, |acc, (exp, coef)| acc + coef * x.powi(exp as i32))
}
fn l(xs: &Vec<f64>, j: usize, x_j: f64) -> Self {
xs.into_iter()
.enumerate()
.filter(|&(m, _)| m != j)
.fold(Self::from(vec![1.0]), |acc, (_, x)| {
let difference = x_j - x;
acc * Self::from(vec![1.0 / difference, -x / difference])
})
}
fn same_xs(points: &Vec<(f64, f64)>) -> bool {
for (i, &(x1, _)) in points.iter().enumerate() {
for (j, &(x2, _)) in points.iter().enumerate() {
if i != j && (x1 - x2).abs() < 1e-10 {
return true;
}
}
}
false
}
}
impl From<Vec<f64>> for Polynomial {
fn from(coefs: Vec<f64>) -> Self {
let coefs = coefs.into_iter()
.skip_while(|&coef| coef == 0.0)
.collect();
Self { coefs }
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
let have_eq_lengths = self.coefs.len() == rhs.coefs.len();
let mut coefs_iter = self.coefs.iter().zip(rhs.coefs.iter());
have_eq_lengths && coefs_iter.all(|(a, b)| (a - b).abs() < 1e-10)
}
}
impl Mul<f64> for Polynomial {
type Output = Self;
fn mul(self, rhs: f64) -> Self {
let coefs = self.coefs.into_iter()
.map(|coef| coef * rhs)
.collect::<Vec<f64>>();
Self::from(coefs)
}
}
impl Div<f64> for Polynomial {
type Output = Self;
fn div(self, rhs: f64) -> Self {
let coefs = self.coefs.into_iter()
.map(|coef| coef / rhs)
.collect::<Vec<f64>>();
Self::from(coefs)
}
}
impl Mul for Polynomial {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
let mut coefs = vec![0.0; self.coefs.len() + rhs.coefs.len() - 1];
- for (i, a) in self.coefs.into_iter().rev().enumerate() {
- for (j, b) in rhs.coefs.iter().rev().enumerate() {
+ for (i, a) in self.coefs.into_iter().enumerate() {
+ for (j, b) in rhs.coefs.iter().enumerate() {
coefs[i + j] += a * b;
}
}
Self::from(coefs)
}
}
impl Add for Polynomial {
type Output = Self;
fn add(self, rhs: Self) -> Self {
let (first_iter, second_iter) =
match self.coefs.len() < rhs.coefs.len() {
true => (rhs.coefs.into_iter(), self.coefs.into_iter()),
_ => (self.coefs.into_iter(), rhs.coefs.into_iter()),
};
let length_difference = first_iter.len() - second_iter.len();
let take_first = first_iter.clone().take(length_difference);
let calculate_rest = first_iter.skip(length_difference)
.zip(second_iter)
.map(|(a, b)| a + b);
let coefs: Vec<f64> = take_first.chain(calculate_rest).collect();
Self::from(coefs)
}
}