Решение на Polynomial от Иван Иванов
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
Лог от изпълнението
Compiling solution v0.1.0 (file:///tmp/d20171121-6053-1elndmx/solution)
Finished dev [unoptimized + debuginfo] target(s) in 5.82 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
История (3 версии и 1 коментар)
Иван качи решение на 20.11.2017 12:41 (преди почти 8 години)
use std::ops::{Mul, Div, Add};
#[derive(Debug, Clone)]
pub struct Polynomial {
coeffitions: Vec<f64>,
}
// Should be done with only one copying, to be reworked
fn remove_leading_zeroes(v: &mut Vec<f64>) -> &mut Vec<f64> {
if v.len() == 0 {
v.push(0.0);
v
} else if v.first() == Some(&0.0) {
v.remove(0);
remove_leading_zeroes(v)
} else {
v
}
}
// Use Horner's method, rev() as we have to start with the lowest degree
fn calculate(p: &Polynomial, x: f64) -> f64 {
p.coeffitions.iter().rev().fold(
0.0,
|acc, elem| acc * x + elem,
)
}
// the Xj term is removed from the vector of points when passed
// unsafe function
fn lagrangian(points: &Vec<f64>, xj: f64) -> Polynomial {
let mut result = Polynomial::from(vec![1.0, -points[0]]);
println!();
result = result / (xj - points[0]);
println!("poly: {:?}", Polynomial::from(vec![1.0, -points[0]]));
println!("bot: {:?}", (xj - points[0]));
let mut it = points.iter();
it.next();
for elem in it {
let tmp = Polynomial::from(vec![1.0, -(*elem)]) / (xj - (*elem));
println!("poly: {:?}", Polynomial::from(vec![1.0, -(*elem)]));
println!("bot: {:?}", (xj - (*elem)));
result = result * tmp;
}
println!("Returning result {:?}", result);
result
}
impl Polynomial {
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
let diff = calculate(self, x) - y;
diff.abs() < 1e-10
}
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let xes: Vec<f64> = points.iter().map(|&(x, _)| x).collect();
- println!("xes: {:?}", xes);
let mut copy_xes = xes.clone();
copy_xes.sort_by(|a, b| a.partial_cmp(b).unwrap());
copy_xes.dedup();
if xes.len() == copy_xes.len() && xes.len() > 0 {
let mut result = Polynomial::default();
for (pos, &(_, y)) in points.iter().enumerate() {
let xj = xes[pos];
let mut tmp_xes = xes.clone();
tmp_xes.remove(pos);
- //println!("lagrangian: {:?}", lagrangian(&tmp_xes, xj));
result = result + (lagrangian(&tmp_xes, xj) * y);
}
Some(result)
} else {
None
}
}
}
impl From<Vec<f64>> for Polynomial {
fn from(mut coefs: Vec<f64>) -> Self {
Polynomial { coeffitions: remove_leading_zeroes(&mut coefs).to_vec() }
}
}
-/// Създава полином отговарящ на константата `0.0`
impl Default for Polynomial {
fn default() -> Self {
Polynomial::from(vec![0.0])
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
- self.coeffitions == rhs.coeffitions
+ if self.coeffitions.len() != rhs.coeffitions.len() {
+ false
+ } else {
+ let mut result = true; //iterates all when not needed, will be fixed
+ for (a, b) in self.coeffitions.iter().zip(rhs.coeffitions.iter()) {
+ result = result && (a - b).abs() < 1e-10;
+ }
+ result
+ }
}
}
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
let v: Vec<f64> = self.coeffitions.iter().map(|x| x * rhs).collect();
Polynomial::from(v)
}
}
-/// Дели полином с f64 -- всички коефициенти биват разделени на дясната страна.
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
let v: Vec<f64> = self.coeffitions.iter().map(|x| x / rhs).collect();
Polynomial::from(v)
}
}
impl Mul for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: Polynomial) -> Self::Output {
let mut coeffs = Vec::new();
for _ in 1..(self.coeffitions.len() + rhs.coeffitions.len()) {
coeffs.push(0.0);
}
for (pow1, elem1) in self.coeffitions.iter().rev().enumerate() {
for (pow2, elem2) in rhs.coeffitions.iter().rev().enumerate() {
if let Some(elem) = coeffs.get_mut(pow1 + pow2) {
*elem += elem1 * elem2;
}
}
}
coeffs.reverse();
Polynomial::from(coeffs)
}
}
// ugly af
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let (mut coeffs, adds) = if self.coeffitions.len() > rhs.coeffitions.len() {
(self.coeffitions.clone(), rhs.coeffitions.clone())
} else {
(rhs.coeffitions.clone(), self.coeffitions.clone())
};
coeffs.reverse();
for (pos, elem) in adds.iter().rev().enumerate() {
coeffs[pos] += *elem;
}
coeffs.reverse();
Polynomial::from(coeffs)
}
}
Иван качи решение на 20.11.2017 20:30 (преди почти 8 години)
use std::ops::{Mul, Div, Add};
#[derive(Debug, Clone)]
pub struct Polynomial {
coeffitions: Vec<f64>,
}
// Should be done with only one copying, to be reworked
fn remove_leading_zeroes(v: &mut Vec<f64>) -> &mut Vec<f64> {
if v.len() == 0 {
v.push(0.0);
v
} else if v.first() == Some(&0.0) {
v.remove(0);
remove_leading_zeroes(v)
} else {
v
}
}
Най-смисления начин, който аз намерих, е:
if let Some(non_zero_position) = coefs.iter().rposition(|x| x.abs() > 1e-10) {
coefs.truncate(non_zero_position + 1);
Polynomial { coefs: coefs }
} else {
Polynomial { coefs: vec![0.0] }
}
Като това е ако са наобратно. Ако са отпред, може би ще трябва с няколко викания на remove все пак.
// Use Horner's method, rev() as we have to start with the lowest degree
fn calculate(p: &Polynomial, x: f64) -> f64 {
- p.coeffitions.iter().rev().fold(
+ p.coeffitions.iter().fold(
0.0,
|acc, elem| acc * x + elem,
)
}
// the Xj term is removed from the vector of points when passed
// unsafe function
fn lagrangian(points: &Vec<f64>, xj: f64) -> Polynomial {
let mut result = Polynomial::from(vec![1.0, -points[0]]);
println!();
result = result / (xj - points[0]);
println!("poly: {:?}", Polynomial::from(vec![1.0, -points[0]]));
println!("bot: {:?}", (xj - points[0]));
let mut it = points.iter();
it.next();
for elem in it {
let tmp = Polynomial::from(vec![1.0, -(*elem)]) / (xj - (*elem));
println!("poly: {:?}", Polynomial::from(vec![1.0, -(*elem)]));
println!("bot: {:?}", (xj - (*elem)));
result = result * tmp;
}
println!("Returning result {:?}", result);
result
}
impl Polynomial {
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
let diff = calculate(self, x) - y;
diff.abs() < 1e-10
}
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
let xes: Vec<f64> = points.iter().map(|&(x, _)| x).collect();
let mut copy_xes = xes.clone();
copy_xes.sort_by(|a, b| a.partial_cmp(b).unwrap());
copy_xes.dedup();
if xes.len() == copy_xes.len() && xes.len() > 0 {
let mut result = Polynomial::default();
for (pos, &(_, y)) in points.iter().enumerate() {
let xj = xes[pos];
let mut tmp_xes = xes.clone();
tmp_xes.remove(pos);
result = result + (lagrangian(&tmp_xes, xj) * y);
}
Some(result)
} else {
None
}
}
}
impl From<Vec<f64>> for Polynomial {
fn from(mut coefs: Vec<f64>) -> Self {
Polynomial { coeffitions: remove_leading_zeroes(&mut coefs).to_vec() }
}
}
impl Default for Polynomial {
fn default() -> Self {
Polynomial::from(vec![0.0])
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
if self.coeffitions.len() != rhs.coeffitions.len() {
false
} else {
let mut result = true; //iterates all when not needed, will be fixed
for (a, b) in self.coeffitions.iter().zip(rhs.coeffitions.iter()) {
result = result && (a - b).abs() < 1e-10;
}
result
}
}
}
impl Mul<f64> for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: f64) -> Self::Output {
let v: Vec<f64> = self.coeffitions.iter().map(|x| x * rhs).collect();
Polynomial::from(v)
}
}
impl Div<f64> for Polynomial {
type Output = Polynomial;
fn div(self, rhs: f64) -> Self::Output {
let v: Vec<f64> = self.coeffitions.iter().map(|x| x / rhs).collect();
Polynomial::from(v)
}
}
impl Mul for Polynomial {
type Output = Polynomial;
fn mul(self, rhs: Polynomial) -> Self::Output {
let mut coeffs = Vec::new();
for _ in 1..(self.coeffitions.len() + rhs.coeffitions.len()) {
coeffs.push(0.0);
}
for (pow1, elem1) in self.coeffitions.iter().rev().enumerate() {
for (pow2, elem2) in rhs.coeffitions.iter().rev().enumerate() {
if let Some(elem) = coeffs.get_mut(pow1 + pow2) {
*elem += elem1 * elem2;
}
}
}
coeffs.reverse();
Polynomial::from(coeffs)
}
}
// ugly af
impl Add for Polynomial {
type Output = Polynomial;
fn add(self, rhs: Polynomial) -> Self::Output {
let (mut coeffs, adds) = if self.coeffitions.len() > rhs.coeffitions.len() {
(self.coeffitions.clone(), rhs.coeffitions.clone())
} else {
(rhs.coeffitions.clone(), self.coeffitions.clone())
};
coeffs.reverse();
for (pos, elem) in adds.iter().rev().enumerate() {
coeffs[pos] += *elem;
}
coeffs.reverse();
Polynomial::from(coeffs)
}
}
Най-смисления начин, който аз намерих, е:
Като това е ако са наобратно. Ако са отпред, може би ще трябва с няколко викания на
removeвсе пак.