pijul nest
guest › [sign in] [explore]

35: Refactor WIP solution for Rust track exercise "Sum of Multiples".

[?]
Aaw9nJhsNmfzFih9mKyNw9mV8CgERXJkRa1kK1Kx3LQH
Oct 9, 2021, 12:45 PM
KOISBSJ3KKEP44EXD6CC3NVTTQLLOBZDONMHTVLGOSTDXUD6SJTQC

Dependencies

  • [2] SPUEEQZQ 24: Add WIP solution for Rust track exercise "Sum Of Multiples".
  • [3] YGJVWTKA 34: Improve solution for Rust track exercise "Nth Prime".
  • [4] JZN2AQ3E 10: Add Rust track exercise "nth-prime".
  • [5] IXMBS6ZP 29: Improve solution for Rust track exercise "Nth Prime".
  • [6] ZSKHCSQ5 30: Fix regression introduced in solution for Rust track exercise "Nth Prime".
  • [7] ERYD4CD7 11: Add solution for Rust track exercise "Nth Prime".
  • [8] VH5OFL55 32: Improve solution for Rust track exercise "Nth Prime".
  • [9] MXKH26RW 26: Refactor solution for Rust track exercise "Sum Of Multiples".
  • [10] UTP7D53Q 12: Improve solution for Rust track exercise "Nth Prime".
  • [11] QK6XE5XF 13: Add Rust track exercises "Beer Song", "Proverb", "Difference Of Squares", "Sum Of Multiples", "Grains", "Prime Factors", "Armstrong Numbers" and "Reverse String".
  • [12] KWE5K6XL 23: Fix panix on input `12` for solution for Rust track exercise "Nth Prime".
  • [13] XDEY7SNL 31: Improve solution for Rust track exercise "Raindrops".

Change contents

  • replacement in rust/sum-of-multiples/src/lib.rs at line 1
    [4.2029]→[2.809:847](∅→∅)
    mod error_a {
    use std::{error, fmt};
    [4.2029]
    [2.847]
    //! Finds the sum of all the unique multiples of particular numbers up to but not including a specified number.
    use std::{error, fmt};
  • replacement in rust/sum-of-multiples/src/lib.rs at line 4
    [2.848]→[2.848:957](∅→∅)
    #[derive(Debug)]
    pub enum CreationError<A> {
    SubsetBiggerThanSet { set: Vec<A>, subset_size: usize },
    }
    [2.848]
    [2.957]
    #[derive(Debug)]
    /// Possible error from struct creation.
    enum CreationError<A> {
    SubsetBiggerThanSet { set: Vec<A>, subset_size: usize },
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 10
    [2.958]→[2.958:1277](∅→∅)
    impl<A: std::fmt::Debug> fmt::Display for CreationError<A> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    match self {
    CreationError::SubsetBiggerThanSet { set, subset_size } => write!(
    f,
    "Subset can't be bigger than set.\nset: {:?}\nsubset_size: {:?}",
    set, subset_size
    ),
    }
    [2.958]
    [2.1277]
    impl<A: std::fmt::Debug> fmt::Display for CreationError<A> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    match self {
    CreationError::SubsetBiggerThanSet { set, subset_size } => write!(
    f,
    "Subset can't be bigger than set.\nset: {:?}\nsubset_size: {:?}",
    set, subset_size
    ),
  • edit in rust/sum-of-multiples/src/lib.rs at line 20
    [2.1284]→[2.1284:1348](∅→∅)
    impl<A: std::fmt::Debug> error::Error for CreationError<A> {}
  • replacement in rust/sum-of-multiples/src/lib.rs at line 22
    [2.1351]→[2.1351:1406](∅→∅)
    mod combinations {
    use crate::error_a::CreationError;
    [2.1351]
    [2.1406]
    impl<A: std::fmt::Debug> error::Error for CreationError<A> {}
  • replacement in rust/sum-of-multiples/src/lib.rs at line 24
    [2.1407]→[2.1407:1471](∅→∅)
    #[derive(PartialEq)]
    enum State {
    A,
    B,
    C,
    D,
    E,
    }
    [2.1407]
    [2.1471]
    #[derive(PartialEq)]
    /// Represents the possible states of a state machine.
    enum State {
    A,
    B,
    C,
    D,
    E,
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 34
    [2.1472]→[2.1472:1625](∅→∅)
    pub struct CombinationsWithoutReplacement<'a, A>
    where
    A: Clone,
    {
    set: &'a [A],
    subset_indices: Vec<usize>,
    index: usize,
    state: State,
    }
    [2.1472]
    [2.1625]
    /// Generates combinations of elements of a set without replacement/repetition of the elements.
    /// Implements the [Revolving Door algorithm](http://math0.wvstateu.edu/~baker/cs405/code/RevolvingDoor.html).
    struct CombinationsWithoutReplacement<'a, A>
    where
    A: Clone,
    {
    set: &'a [A],
    subset_indices: Vec<usize>,
    index: usize,
    state: State,
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 46
    [2.1626]→[2.1626:2263](∅→∅)
    impl<A> CombinationsWithoutReplacement<'_, A>
    where
    A: Clone,
    {
    // R1: Initialise
    pub fn new(
    set: &[A],
    subset_size: usize,
    ) -> Result<CombinationsWithoutReplacement<A>, CreationError<A>> {
    if set.len() < subset_size {
    Err(CreationError::SubsetBiggerThanSet {
    set: set.to_owned(),
    subset_size,
    })
    } else {
    Ok(CombinationsWithoutReplacement {
    set,
    subset_indices: {
    let mut a: Vec<usize> = Vec::with_capacity(subset_size + 1);
    for b in 0..subset_size {
    a.push(b);
    }
    a.push(set.len());
    a
    },
    index: 0,
    state: State::A,
    })
    }
    [2.1626]
    [2.2263]
    impl<A> CombinationsWithoutReplacement<'_, A>
    where
    A: Clone,
    {
    // R1: Initialise
    /// # Arguments
    ///
    /// * `set`: Set to generate combinations of.
    /// * `subset_size`: Size of subsets containing the combinations to output.
    fn new(
    set: &[A],
    subset_size: usize,
    ) -> Result<CombinationsWithoutReplacement<A>, CreationError<A>> {
    if set.len() < subset_size {
    Err(CreationError::SubsetBiggerThanSet {
    set: set.to_owned(),
    subset_size,
    })
    } else {
    Ok(CombinationsWithoutReplacement {
    set,
    subset_indices: {
    let mut a: Vec<usize> = Vec::with_capacity(subset_size + 1);
    for b in 0..subset_size {
    a.push(b);
    }
    a.push(set.len());
    a
    },
    index: 0,
    state: State::A,
    })
  • edit in rust/sum-of-multiples/src/lib.rs at line 79
    [2.2267]
    [2.2267]
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 81
    [2.2268]→[2.2268:2623](∅→∅)
    // R2: State::A
    fn visit(&mut self) -> Option<Vec<A>> {
    match self.subset_indices.len() - 1 {
    0 => Some(vec![]),
    1 => {
    self.index += 1;
    if self.index > self.set.len() {
    self.state = State::E;
    None
    } else {
    Some(vec![self.set[self.index - 1].clone()])
    }
    }
    index if index == self.set.len() => {
    [2.2268]
    [2.2623]
    // R2: State::A
    fn visit(&mut self) -> Option<Vec<A>> {
    match self.subset_indices.len() - 1 {
    0 => Some(vec![]),
    1 => {
    self.index += 1;
    if self.index > self.set.len() {
  • replacement in rust/sum-of-multiples/src/lib.rs at line 89
    [2.2651]→[2.2651:2883](∅→∅)
    Some(self.set.to_vec())
    }
    _ => {
    self.state = State::B;
    Some(
    self.subset_indices[0..self.subset_indices.len() - 1]
    .iter()
    .map(|index| self.set[*index].clone())
    .collect(),
    )
    [2.2651]
    [2.2883]
    None
    } else {
    Some(vec![self.set[self.index - 1].clone()])
  • edit in rust/sum-of-multiples/src/lib.rs at line 93
    [2.2889]
    [2.2889]
    }
    index if index == self.set.len() => {
    self.state = State::E;
    Some(self.set.to_vec())
    }
    _ => {
    self.state = State::B;
    Some(
    self.subset_indices[0..self.subset_indices.len() - 1]
    .iter()
    .map(|&index| self.set[index].clone())
    .collect(),
    )
  • edit in rust/sum-of-multiples/src/lib.rs at line 108
    [2.2898]
    [2.2898]
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 110
    [2.2899]→[2.2899:3261](∅→∅)
    // R3: State::B
    fn easy_cases(&mut self) {
    if (self.subset_indices.len() - 1) & 1 == 1 {
    if self.subset_indices[0] + 1 < self.subset_indices[1] {
    self.subset_indices[0] += 1;
    self.state = State::A;
    } else {
    self.index = 1;
    self.state = State::C;
    }
    } else if self.subset_indices[0] > 0 {
    self.subset_indices[0] -= 1;
    [2.2899]
    [2.3261]
    // R3: State::B
    fn easy_cases(&mut self) {
    if (self.subset_indices.len() - 1) & 1 == 1 {
    if self.subset_indices[0] + 1 < self.subset_indices[1] {
    self.subset_indices[0] += 1;
  • replacement in rust/sum-of-multiples/src/lib.rs at line 118
    [2.3320]→[2.3320:3347](∅→∅)
    self.state = State::D;
    [2.3320]
    [2.3347]
    self.state = State::C;
  • edit in rust/sum-of-multiples/src/lib.rs at line 120
    [2.3352]
    [2.3352]
    } else if self.subset_indices[0] > 0 {
    self.subset_indices[0] -= 1;
    self.state = State::A;
    } else {
    self.index = 1;
    self.state = State::D;
  • edit in rust/sum-of-multiples/src/lib.rs at line 127
    [2.3356]
    [2.3356]
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 129
    [2.3357]→[2.3357:3696](∅→∅)
    // R4: State::C
    fn try_to_decrease_at_index(&mut self) {
    if self.subset_indices[self.index] > self.index {
    self.subset_indices[self.index] = self.subset_indices[self.index - 1];
    self.subset_indices[self.index - 1] = self.index - 1;
    self.state = State::A;
    } else {
    self.index += 1;
    self.state = State::D;
    }
    [2.3357]
    [2.3696]
    // R4: State::C
    fn try_to_decrease_at_index(&mut self) {
    if self.subset_indices[self.index] > self.index {
    self.subset_indices[self.index] = self.subset_indices[self.index - 1];
    self.subset_indices[self.index - 1] = self.index - 1;
    self.state = State::A;
    } else {
    self.index += 1;
    self.state = State::D;
  • edit in rust/sum-of-multiples/src/lib.rs at line 139
    [2.3700]
    [2.3700]
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 141
    [2.3701]→[2.3701:3988](∅→∅)
    // R5: State::D
    fn try_to_increase_at_index(&mut self) {
    if self.subset_indices[self.index] + 1 < self.subset_indices[self.index + 1] {
    self.subset_indices[self.index - 1] = self.subset_indices[self.index];
    self.subset_indices[self.index] += 1;
    self.state = State::A;
    [2.3701]
    [2.3988]
    // R5: State::D
    fn try_to_increase_at_index(&mut self) {
    if self.subset_indices[self.index] + 1 < self.subset_indices[self.index + 1] {
    self.subset_indices[self.index - 1] = self.subset_indices[self.index];
    self.subset_indices[self.index] += 1;
    self.state = State::A;
    } else {
    self.index += 1;
    if self.index < (self.subset_indices.len() - 1) {
    self.state = State::C;
  • replacement in rust/sum-of-multiples/src/lib.rs at line 152
    [2.4000]→[2.4000:4162](∅→∅)
    self.index += 1;
    if self.index < (self.subset_indices.len() - 1) {
    self.state = State::C;
    } else {
    // End
    self.state = State::E;
    }
    [2.4000]
    [2.4162]
    // End
    self.state = State::E;
  • edit in rust/sum-of-multiples/src/lib.rs at line 157
    [2.4174]
    [2.4174]
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 159
    [2.4175]→[2.4175:4279](∅→∅)
    impl<A> Iterator for CombinationsWithoutReplacement<'_, A>
    where
    A: Clone,
    {
    type Item = Vec<A>;
    [2.4175]
    [2.4279]
    impl<A> Iterator for CombinationsWithoutReplacement<'_, A>
    where
    A: Clone,
    {
    type Item = Vec<A>;
  • replacement in rust/sum-of-multiples/src/lib.rs at line 165
    [2.4280]→[2.4280:4663](∅→∅)
    fn next(&mut self) -> Option<Self::Item> {
    match self.state {
    State::A => self.visit(),
    State::E => None,
    _ => {
    while self.state != State::A && self.state != State::E {
    match self.state {
    State::B => self.easy_cases(),
    State::C => self.try_to_decrease_at_index(),
    State::D => self.try_to_increase_at_index(),
    _ => (),
    }
    [2.4280]
    [2.4663]
    fn next(&mut self) -> Option<Self::Item> {
    match self.state {
    State::A => self.visit(),
    State::E => None,
    _ => {
    while self.state != State::A && self.state != State::E {
    match self.state {
    State::B => self.easy_cases(),
    State::C => self.try_to_decrease_at_index(),
    State::D => self.try_to_increase_at_index(),
    _ => (),
  • edit in rust/sum-of-multiples/src/lib.rs at line 177
    [2.4670]→[2.4670:4687](∅→∅)
    self.next()
  • edit in rust/sum-of-multiples/src/lib.rs at line 178
    [2.4693]
    [2.4693]
    self.next()
  • replacement in rust/sum-of-multiples/src/lib.rs at line 184
    [2.4708]→[2.4708:4748](∅→∅)
    mod num_traits {
    pub trait Unsigned {}
    [2.4708]
    [2.4748]
    trait Unsigned {}
    impl Unsigned for u32 {}
  • replacement in rust/sum-of-multiples/src/lib.rs at line 188
    [2.4749]→[2.4749:4775](∅→∅)
    impl Unsigned for u32 {}
    [2.4749]
    [2.4775]
    #[derive(Debug)]
    /// Returns the multiples of a number up to but not including a specified limit.
    struct UnsignedMultiples<A>
    where
    A: Copy + Unsigned,
    {
    factor: A,
    limit: A,
    out: A,
  • replacement in rust/sum-of-multiples/src/lib.rs at line 199
    [2.4778]→[2.4778:5141](∅→∅)
    mod multiples {
    use crate::num_traits::Unsigned;
    #[derive(Debug)]
    pub struct UnsignedMultiples<A>
    where
    A: Copy + Unsigned,
    {
    factor: A,
    limit: A,
    out: A,
    }
    impl<A> UnsignedMultiples<A>
    where
    A: Copy + Unsigned,
    {
    pub fn new(factor: A, limit: A) -> UnsignedMultiples<A> {
    UnsignedMultiples {
    factor,
    limit,
    out: factor,
    }
    [2.4778]
    [2.5141]
    impl<A> UnsignedMultiples<A>
    where
    A: Copy + Unsigned,
    {
    /// # Arguments
    ///
    /// * `factor`: Number to generate multiples of.
    /// * `limit`: Number at which no more multiples will be generated.
    fn new(factor: A, limit: A) -> UnsignedMultiples<A> {
    UnsignedMultiples {
    factor,
    limit,
    out: factor,
  • edit in rust/sum-of-multiples/src/lib.rs at line 214
    [2.5148]
    [2.5148]
    }
  • replacement in rust/sum-of-multiples/src/lib.rs at line 216
    [2.5149]→[2.5149:5306](∅→∅)
    impl<A> Iterator for UnsignedMultiples<A>
    where
    A: core::ops::AddAssign + core::ops::Sub<Output = A> + Copy + PartialOrd + Unsigned,
    {
    type Item = A;
    [2.5149]
    [2.5306]
    impl<A> Iterator for UnsignedMultiples<A>
    where
    A: core::ops::AddAssign + core::ops::Sub<Output = A> + Copy + PartialOrd + Unsigned,
    {
    type Item = A;
  • replacement in rust/sum-of-multiples/src/lib.rs at line 222
    [2.5307]→[2.5307:5470](∅→∅)
    fn next(&mut self) -> Option<Self::Item> {
    if self.out < self.limit {
    self.out += self.factor;
    Some(self.out - self.factor)
    } else {
    None
    }
    [2.5307]
    [2.5470]
    fn next(&mut self) -> Option<Self::Item> {
    if self.out < self.limit {
    let out = self.out;
    self.out += self.factor;
    Some(out)
    } else {
    None
  • edit in rust/sum-of-multiples/src/lib.rs at line 232
    [2.5479]→[2.5479:5598](∅→∅)
    use crate::{
    combinations::CombinationsWithoutReplacement, error_a::CreationError,
    multiples::UnsignedMultiples,
    };
  • edit in rust/sum-of-multiples/src/lib.rs at line 251
    [2.6385]
    [4.2030]
    /// Finds the sum of all the unique multiples of particular numbers up to but not including a specified number.
  • replacement in rust/sum-of-multiples/src/lib.rs at line 253
    [4.2092]→[2.6386:6409](∅→∅)
    let factors = factors
    [4.2092]
    [2.6409]
    let mut factors = factors.to_vec();
    factors.sort_unstable();
    let mut done: Vec<u32> = Vec::with_capacity(factors.len());
    let mut out: Vec<u32> = Vec::with_capacity(factors.len());
    factors
  • replacement in rust/sum-of-multiples/src/lib.rs at line 260
    [2.6431]→[2.6431:6515](∅→∅)
    .filter(|factor| *factor != 0)
    .collect::<Vec<u32>>();
    if factors.is_empty() {
    [2.6431]
    [2.6515]
    .filter(|&factor| factor != 0)
    .for_each(|factor| {
    if done.iter().all(|&done_factor| factor % done_factor != 0) {
    out.push(factor);
    }
    done.push(factor);
    });
    if out.is_empty() {
  • replacement in rust/sum-of-multiples/src/lib.rs at line 270
    [2.6529]→[2.6529:6577](∅→∅)
    sum_of_multiples_go(&factors, limit).unwrap()
    [2.6529]
    [2.6577]
    sum_of_multiples_go(&out, limit).unwrap()
  • edit in rust/nth-prime/src/lib.rs at line 1
    [4.452]
    [4.128]
    use std::convert::TryInto;
  • edit in rust/nth-prime/src/lib.rs at line 9
    [3.54]
    [4.0]
    TODO:
    * Use bases 2, 3, 5, 7 for wheel factorisation.
    * Implement segmented sieve algorithm.
    * Multi-thread with Mutex and lazy_static.
    * Use bitbox from bitvec for bit compression.
  • edit in rust/nth-prime/src/lib.rs at line 16
    [4.3]
    [4.453]
  • replacement in rust/nth-prime/src/lib.rs at line 31
    [4.264]→[3.55:309](∅→∅)
    // Approximated size of the list required using the inverse of an approximation of the prime-counting function, halved (as we're only interested in odd numbers).
    let list_size = (corrected_n * (corrected_n * corrected_n.ln()).ln() / 2.0) as usize + 1;
    [4.264]
    [4.984]
    // Approximated size of the list required using the inverse of an approximation of the prime-counting function, halved (as we're only interested in odd numbers). Lossy cast.
    let list_size = (corrected_n * (corrected_n * corrected_n.ln()).ln() / 2.0).ceil() as usize;
  • replacement in rust/nth-prime/src/lib.rs at line 39
    [4.1133]→[4.1133:1175](∅→∅)
    (list_size as f64).sqrt() as usize + 1,
    [4.1133]
    [3.310]
    // Lossy cast.
    (list_size as f64).sqrt().ceil() as usize,
  • replacement in rust/nth-prime/src/lib.rs at line 49
    [4.1291]→[4.826:887](∅→∅),[4.887]→[3.362:397](∅→∅)
    // Might panic if values greater than u32::MAX are cast.
    return (index * 2 + 1) as u32;
    [4.1291]
    [4.26]
    // Might panic if values greater than u32::MAX are converted.
    return (index * 2 + 1).try_into().unwrap();
  • replacement in rust/nth-prime/src/lib.rs at line 61
    [4.124]→[4.951:1012](∅→∅),[4.1012]→[3.575:610](∅→∅)
    // Might panic if values greater than u32::MAX are cast.
    return (index * 2 + 1) as u32;
    [4.124]
    [4.574]
    // Might panic if values greater than u32::MAX are converted.
    return (index * 2 + 1).try_into().unwrap();