Решение на Polynomial от Десислава Цветкова
Към профила на Десислава Цветкова
Резултати
- 15 точки от тестове
- 0 бонус точки
- 15 точки общо
- 15 успешни тест(а)
- 0 неуспешни тест(а)
Код
Лог от изпълнението
Compiling solution v0.1.0 (file:///tmp/d20171121-6053-o5zrse/solution)
Finished dev [unoptimized + debuginfo] target(s) in 5.84 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 версии и 3 коментара)
Десислава качи решение на 20.11.2017 16:35 (преди почти 8 години)
use std::cmp::max;
use std::ops::Mul;
use std::ops::Add;
use std::ops::Div;
use std::collections::HashSet;
use std::iter::FromIterator;
use std::iter::repeat;
use std::hash::{Hash, Hasher};
#[derive(Debug, Clone)]
pub struct Polynomial {
//a0 + a1*x + ...
coeffs: Vec<f64>
}
#[derive(Debug)]
struct Point {
x: f64,
y: f64
}
impl PartialEq for Point {
fn eq(&self, other: &Point) -> bool {
(self.x - other.x).abs() <= 1e-10 && (self.y - other.y).abs() <= 1e-10
}
}
impl Hash for Point {
fn hash<H: Hasher>(&self, state: &mut H) {
format!("{:?}", (self)).hash(state);
}
}
impl Eq for Point {}
impl Polynomial {
pub fn evaluate(&self, x: f64) -> f64 {
if !self.coeffs.is_empty() {
self.coeffs.iter().enumerate().fold(0.0, |sum, (i, &a)| x.powi(i as i32) * a + sum)
} else {
0.0
}
}
pub fn new(coeffs: Vec<f64>) -> Self {
Polynomial { coeffs: coeffs }
}
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
(self.evaluate(x) - y).abs() <= 1e-10
}
fn are_duplicates(points: &Vec<(f64, f64)>) -> bool {
let unique: HashSet<Point> = HashSet::from_iter(points.iter().map(|&(x, y)| Point {x, y}));
unique.len() != points.len()
}
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
if Self::are_duplicates(&points) {
return None
}
let n = points.len() - 1;
let count_points = points.len();
let mut s:Vec<f64> = repeat(0.0).take(count_points).collect();
let mut coeffs:Vec<f64> = repeat(0.0).take(count_points).collect();
let (x_0, _) = points[0];
s[n] = -x_0;
for i in 1..count_points {
for j in (n - i)..n {
let (x_i, _) = points[i];
s[j] -= x_i * s[j + 1];
}
let (x_i, _) = points[i];
s[count_points - 1] -= x_i;
}
for point in points.iter() {
let &(x_j, y_j) = point;
let mut product: f64 = count_points as f64;
for k in (1..count_points).rev() {
product = (k as f64) * s[k] + x_j * product;
}
let ff = y_j / product;
let mut b = 1.0;
for k in (0..count_points).rev() {
coeffs[k] += b * ff;
b = s[k] + x_j * b;
}
}
Some(Self::new(coeffs))
}
}
impl From<Vec<f64>> for Polynomial {
fn from(coefs: Vec<f64>) -> Self {
let mut coeffs = coefs.into_iter().fold(Vec::new(), |mut res, coeff| {
if (coeff - 0.0).abs() >= 1e-10 {
res.push(coeff);
}
res
});
coeffs.reverse();
Self::new(coeffs)
}
}
impl Default for Polynomial {
fn default() -> Polynomial {
Polynomial::new(vec![])
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
self.coeffs.iter().zip(rhs.coeffs.iter()).all(|(&first, &second)| (first - second).abs() <= 1e-10)
}
}
impl Mul<f64> for Polynomial {
type Output = Self;
fn mul(self, rhs: f64) -> Self::Output {
Polynomial::new(self.coeffs.iter().map(|c| c * rhs).collect())
}
}
impl Div<f64> for Polynomial {
type Output = Self;
fn div(self, rhs: f64) -> Self::Output {
Polynomial::new(self.coeffs.iter().map(|c| c / rhs).collect())
}
}
impl Mul for Polynomial {
type Output = Self;
fn mul(self, rhs: Polynomial) -> Self::Output {
- let new_coeffs = self.coeffs.iter().fold(Vec::new(), |mut coeffs, a_i| {
- let c:Vec<f64> = rhs.coeffs.iter().map(|b_j| b_j * a_i).collect();
- coeffs.extend(c);
- coeffs
- });
+ let mut new_coeffs:Vec<f64> = repeat(0.0).take(self.coeffs.len() + rhs.coeffs.len() - 1).collect();
+
+ for i in 0..self.coeffs.len() {
+ for j in 0..rhs.coeffs.len() {
+ new_coeffs[i + j] += self.coeffs[i] * rhs.coeffs[j];
+ }
+ }
+
Polynomial::new(new_coeffs)
}
}
impl Add for Polynomial {
type Output = Self;
fn add(self, rhs: Polynomial) -> Self::Output {
fn get(coeffs: &Vec<f64>, index: usize) -> f64 {
match coeffs.get(index) {
Some(val) => *val,
None => 0.0 as f64
}
}
let longest = max(self.coeffs.len(), rhs.coeffs.len());
let mut new_coeffs = Vec::new();
for i in 0..longest {
new_coeffs.push(get(&self.coeffs, i) + get(&rhs.coeffs, i));
}
Polynomial::new(new_coeffs)
}
}
Десислава качи решение на 20.11.2017 16:55 (преди почти 8 години)
use std::cmp::max;
use std::ops::Mul;
use std::ops::Add;
use std::ops::Div;
use std::collections::HashSet;
use std::iter::FromIterator;
use std::iter::repeat;
use std::hash::{Hash, Hasher};
#[derive(Debug, Clone)]
pub struct Polynomial {
//a0 + a1*x + ...
coeffs: Vec<f64>
}
#[derive(Debug)]
struct Point {
x: f64,
y: f64
}
impl PartialEq for Point {
fn eq(&self, other: &Point) -> bool {
(self.x - other.x).abs() <= 1e-10 && (self.y - other.y).abs() <= 1e-10
}
}
impl Hash for Point {
fn hash<H: Hasher>(&self, state: &mut H) {
format!("{:?}", (self)).hash(state);
}
}
Интересно решение за уникалността на точките. In general, е готино да си ползва човек някаква структурка за това, чудех се даже дали да не вкараме, ама keep it simple, I guess. Все пак, не съм сигурен, че бих разчитал на нея, щото реално форматира числата в низове преди да ги хешира, което едва ли е много ефективно :/. Ръчната проверка за уникалност ще е по-тромава, но пък по-ефективна. Идеалния вариант би било нещо като dedup_by, но пък това работи само за елементи един до друг. Не е лесно.
impl Eq for Point {}
impl Polynomial {
pub fn evaluate(&self, x: f64) -> f64 {
if !self.coeffs.is_empty() {
self.coeffs.iter().enumerate().fold(0.0, |sum, (i, &a)| x.powi(i as i32) * a + sum)
} else {
0.0
}
Добра употреба на функционален стил, Медъла би се зарадвал, ако гледаше домашните :). Не ти трябва if-клаузата, обаче -- ако коефициентите са празни, fold-а няма да извика функцията, а просто ще върне първия аргумент, което е каквото се иска.
}
pub fn new(coeffs: Vec<f64>) -> Self {
Polynomial { coeffs: coeffs }
}
pub fn has(&self, point: &(f64, f64)) -> bool {
let &(x, y) = point;
(self.evaluate(x) - y).abs() <= 1e-10
}
fn are_duplicates(points: &Vec<(f64, f64)>) -> bool {
let unique: HashSet<Point> = HashSet::from_iter(points.iter().map(|&(x, y)| Point {x, y}));
unique.len() != points.len()
}
pub fn interpolate(points: Vec<(f64, f64)>) -> Option<Self> {
if Self::are_duplicates(&points) {
return None
}
let n = points.len() - 1;
let count_points = points.len();
let mut s:Vec<f64> = repeat(0.0).take(count_points).collect();
let mut coeffs:Vec<f64> = repeat(0.0).take(count_points).collect();
let (x_0, _) = points[0];
s[n] = -x_0;
for i in 1..count_points {
for j in (n - i)..n {
let (x_i, _) = points[i];
s[j] -= x_i * s[j + 1];
}
let (x_i, _) = points[i];
s[count_points - 1] -= x_i;
}
-
for point in points.iter() {
let &(x_j, y_j) = point;
let mut product: f64 = count_points as f64;
for k in (1..count_points).rev() {
product = (k as f64) * s[k] + x_j * product;
}
let ff = y_j / product;
let mut b = 1.0;
for k in (0..count_points).rev() {
coeffs[k] += b * ff;
b = s[k] + x_j * b;
}
}
- Some(Self::new(coeffs))
-
+ if coeffs.iter().any(|&coeff| coeff.is_infinite()) {
+ None
+ } else {
+ Some(Self::new(coeffs))
+ }
}
}
impl From<Vec<f64>> for Polynomial {
- fn from(coefs: Vec<f64>) -> Self {
- let mut coeffs = coefs.into_iter().fold(Vec::new(), |mut res, coeff| {
- if (coeff - 0.0).abs() >= 1e-10 {
- res.push(coeff);
+ fn from(mut coefs: Vec<f64>) -> Self {
+ let mut removed = true;
+
+ while removed && coefs.len() > 0 {
+ if (coefs[0] - 0.0).abs() <= 1e-10 {
+ coefs.remove(0);
+ } else {
+ removed = false;
}
- res
- });
- coeffs.reverse();
- Self::new(coeffs)
+ }
+ coefs.reverse();
+ Self::new(coefs)
}
}
impl Default for Polynomial {
fn default() -> Polynomial {
Polynomial::new(vec![])
}
}
impl PartialEq for Polynomial {
fn eq(&self, rhs: &Self) -> bool {
self.coeffs.iter().zip(rhs.coeffs.iter()).all(|(&first, &second)| (first - second).abs() <= 1e-10)
Ахх, това няма да проработи, ако дължините на векторите са различни :). Полином от [2.0] ще е равен на полином от [1.0, 2.0]. Как не съм се сетил да напиша тест за това! Отърваш се тоя път :).
}
}
impl Mul<f64> for Polynomial {
type Output = Self;
fn mul(self, rhs: f64) -> Self::Output {
Polynomial::new(self.coeffs.iter().map(|c| c * rhs).collect())
}
}
impl Div<f64> for Polynomial {
type Output = Self;
fn div(self, rhs: f64) -> Self::Output {
Polynomial::new(self.coeffs.iter().map(|c| c / rhs).collect())
}
}
impl Mul for Polynomial {
type Output = Self;
fn mul(self, rhs: Polynomial) -> Self::Output {
let mut new_coeffs:Vec<f64> = repeat(0.0).take(self.coeffs.len() + rhs.coeffs.len() - 1).collect();
for i in 0..self.coeffs.len() {
for j in 0..rhs.coeffs.len() {
new_coeffs[i + j] += self.coeffs[i] * rhs.coeffs[j];
}
}
Polynomial::new(new_coeffs)
}
}
impl Add for Polynomial {
type Output = Self;
fn add(self, rhs: Polynomial) -> Self::Output {
fn get(coeffs: &Vec<f64>, index: usize) -> f64 {
match coeffs.get(index) {
Some(val) => *val,
None => 0.0 as f64
}
}
let longest = max(self.coeffs.len(), rhs.coeffs.len());
let mut new_coeffs = Vec::new();
for i in 0..longest {
new_coeffs.push(get(&self.coeffs, i) + get(&rhs.coeffs, i));
}
Polynomial::new(new_coeffs)
}
}
Интересно решение за уникалността на точките. In general, е готино да си ползва човек някаква структурка за това, чудех се даже дали да не вкараме, ама keep it simple, I guess. Все пак, не съм сигурен, че бих разчитал на нея, щото реално форматира числата в низове преди да ги хешира, което едва ли е много ефективно :/. Ръчната проверка за уникалност ще е по-тромава, но пък по-ефективна. Идеалния вариант би било нещо като
dedup_by, но пък това работи само за елементи един до друг. Не е лесно.Добра употреба на функционален стил, Медъла би се зарадвал, ако гледаше домашните :). Не ти трябва if-клаузата, обаче -- ако коефициентите са празни,
fold-а няма да извика функцията, а просто ще върне първия аргумент, което е каквото се иска.Ахх, това няма да проработи, ако дължините на векторите са различни :). Полином от
[2.0]ще е равен на полином от[1.0, 2.0]. Как не съм се сетил да напиша тест за това! Отърваш се тоя път :).