36: Rewrite solution for Rust track exercise "Sum of Multiples".

[?]

Aaw9nJhsNmfzFih9mKyNw9mV8CgERXJkRa1kK1Kx3LQH

Oct 9, 2021, 12:47 PM

4XC5QHJKOXK5NXLZUMJ2O5DMJAR5HJK4Z3LQWNBOC5EJJJPISYDAC

Dependencies

[2] MXKH26RW 26: Refactor solution for Rust track exercise "Sum Of Multiples".
[3] KOISBSJ3 35: Refactor WIP solution for Rust track exercise "Sum of Multiples".
[4] S746FJJE 25: Refactor solution for Rust track exercise "Sum Of Multiples".
[5] SPUEEQZQ 24: Add WIP solution for Rust track exercise "Sum Of Multiples".
[6] QK6XE5XF 13: Add Rust track exercises "Beer Song", "Proverb", "Difference Of Squares", "Sum Of Multiples", "Grains", "Prime Factors", "Armstrong Numbers" and "Reverse String".

Change contents

replacement in rust/sum-of-multiples/src/lib.rs at line 1

[4.2029]→[3.0:135](∅→∅),[3.135]→[4.847:848](∅→∅),[4.847]→[4.847:848](∅→∅),[4.848]→[3.136:278](∅→∅),[3.278]→[4.957:958](∅→∅),[4.957]→[4.957:958](∅→∅),[4.958]→[3.279:585](∅→∅),[3.585]→[4.1277:1284](∅→∅),[4.1277]→[4.1277:1284](∅→∅),[4.1348]→[4.1348:1351](∅→∅),[4.1351]→[3.586:648](∅→∅),[3.648]→[4.1406:1407](∅→∅),[4.1406]→[4.1406:1407](∅→∅),[4.1407]→[3.649:760](∅→∅),[3.760]→[4.1471:1472](∅→∅),[4.1471]→[4.1471:1472](∅→∅),[4.1472]→[3.761:1108](∅→∅),[3.1108]→[4.1625:1626](∅→∅),[4.1625]→[4.1625:1626](∅→∅),[4.1626]→[3.1109:1855](∅→∅),[3.1855]→[4.2263:2267](∅→∅),[4.2263]→[4.2263:2267](∅→∅),[4.2267]→[3.1856:1859](∅→∅),[3.1859]→[4.2267:2268](∅→∅),[4.2267]→[4.2267:2268](∅→∅),[4.2268]→[3.1860:2048](∅→∅),[3.2048]→[4.2623:2651](∅→∅),[4.2623]→[4.2623:2651](∅→∅),[4.2651]→[3.2049:2122](∅→∅),[3.2122]→[4.2883:2889](∅→∅),[4.2883]→[4.2883:2889](∅→∅),[4.2889]→[3.2123:2418](∅→∅),[3.2418]→[4.2889:2898](∅→∅),[4.2889]→[4.2889:2898](∅→∅),[4.2898]→[3.2419:2422](∅→∅),[3.2422]→[4.2898:2899](∅→∅),[4.2898]→[4.2898:2899](∅→∅),[4.2899]→[3.2423:2609](∅→∅),[3.2609]→[4.3261:3320](∅→∅),[4.3261]→[4.3261:3320](∅→∅),[4.3320]→[3.2610:2637](∅→∅),[3.2637]→[4.3347:3352](∅→∅),[4.3347]→[4.3347:3352](∅→∅),[4.3352]→[3.2638:2793](∅→∅),[3.2793]→[4.3352:3356](∅→∅),[4.3352]→[4.3352:3356](∅→∅),[4.3356]→[3.2794:2797](∅→∅),[3.2797]→[4.3356:3357](∅→∅),[4.3356]→[4.3356:3357](∅→∅),[4.3357]→[3.2798:3123](∅→∅),[3.3123]→[4.3696:3700](∅→∅),[4.3696]→[4.3696:3700](∅→∅),[4.3700]→[3.3124:3127](∅→∅)

//! Finds the sum of all the unique multiples of particular numbers up to but not including a specified number.
use std::{error, fmt};

#[derive(Debug)]
/// Possible error from struct creation.
enum CreationError<A> {
SubsetBiggerThanSet { set: Vec<A>, subset_size: usize },
}

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
),
}
}
}

impl<A: std::fmt::Debug> error::Error for CreationError<A> {}

#[derive(PartialEq)]
/// Represents the possible states of a state machine.
enum State {
A,
B,
C,
D,
E,
}

/// 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,
}

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,
})
}
}

// 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() => {
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(),
)
}
}
}

// 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;
self.state = State::A;
} else {
self.index = 1;
self.state = State::D;
}
}

// 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;
}
}

[4.2029]

[4.3700]

use std::convert::TryInto;
edit in rust/sum-of-multiples/src/lib.rs at line 3

[4.3701]→[3.3128:3520](∅→∅),[3.3520]→[4.3988:4000](∅→∅),[4.3988]→[4.3988:4000](∅→∅),[4.4000]→[3.3521:3559](∅→∅),[3.3559]→[4.4162:4174](∅→∅),[4.4162]→[4.4162:4174](∅→∅),[4.4174]→[3.3560:3562](∅→∅),[3.3562]→[4.4174:4175](∅→∅),[4.4174]→[4.4174:4175](∅→∅),[4.4175]→[3.3563:3662](∅→∅),[3.3662]→[4.4279:4280](∅→∅),[4.4279]→[4.4279:4280](∅→∅),[4.4280]→[3.3663:4027](∅→∅),[3.4027]→[4.4663:4670](∅→∅),[4.4663]→[4.4663:4670](∅→∅),[4.4687]→[4.4687:4693](∅→∅),[4.4693]→[3.4028:4044](∅→∅),[3.4044]→[4.4693:4708](∅→∅),[4.4693]→[4.4693:4708](∅→∅),[4.4708]→[3.4045:4089](∅→∅),[3.4089]→[4.4748:4749](∅→∅),[4.4748]→[4.4748:4749](∅→∅),[4.4749]→[3.4090:4277](∅→∅),[3.4277]→[4.4775:4778](∅→∅),[4.4775]→[4.4775:4778](∅→∅),[4.4778]→[3.4278:4591](∅→∅),[3.4591]→[4.5141:5148](∅→∅),[4.5141]→[4.5141:5148](∅→∅),[4.5148]→[3.4592:4594](∅→∅),[3.4594]→[4.5148:5149](∅→∅),[4.5148]→[4.5148:5149](∅→∅),[4.5149]→[3.4595:4747](∅→∅),[3.4747]→[4.5306:5307](∅→∅),[4.5306]→[4.5306:5307](∅→∅),[4.5307]→[3.4748:4904](∅→∅),[3.4904]→[4.5470:5479](∅→∅),[4.5470]→[4.5470:5479](∅→∅),[4.5598]→[4.5598:5724](∅→∅),[4.5724]→[2.0:265](∅→∅),[4.233]→[4.5792:5824](∅→∅),[2.265]→[4.5792:5824](∅→∅),[4.5792]→[4.5792:5824](∅→∅),[4.5824]→[2.266:288](∅→∅),[4.258]→[4.6090:6102](∅→∅),[2.288]→[4.6090:6102](∅→∅),[4.6090]→[4.6090:6102](∅→∅),[4.6102]→[2.289:311](∅→∅),[4.283]→[4.6368:6385](∅→∅),[2.311]→[4.6368:6385](∅→∅),[4.6368]→[4.6368:6385](∅→∅),[4.6385]→[3.4905:5017](∅→∅)

// 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;
} else {
// End
self.state = State::E;
}
}
}
}

impl<A> Iterator for CombinationsWithoutReplacement<'_, A>
where
A: Clone,
{
type Item = Vec<A>;

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(),
_ => (),
}
}
self.next()
}
}
}
}

trait Unsigned {}

impl Unsigned for u32 {}

#[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,
}

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,
}
}
}

impl<A> Iterator for UnsignedMultiples<A>
where
A: core::ops::AddAssign + core::ops::Sub<Output = A> + Copy + PartialOrd + Unsigned,
{
type Item = A;

fn next(&mut self) -> Option<Self::Item> {
if self.out < self.limit {
let out = self.out;
self.out += self.factor;
Some(out)
} else {
None
}
}
}

fn sum_of_multiples_go(factors: &[u32], limit: u32) -> Result<u32, CreationError<u32>> {
(1..=factors.len()).try_fold(
0,
|accumulator, subset_size| -> Result<u32, CreationError<u32>> {
let sum: u32 = CombinationsWithoutReplacement::new(factors, subset_size)?
.map(|combination| {
UnsignedMultiples::new(combination.iter().product(), limit).sum::<u32>()
})
.sum();
Ok(if subset_size & 1 == 1 {
accumulator + sum
} else {
accumulator - sum
})
},
)
}

/// 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 4

[4.2092]→[3.5018:5202](∅→∅)

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());

[4.2092]

[3.5202]

let (mut done, mut out) = (Vec::with_capacity(factors.len()), 0);
replacement in rust/sum-of-multiples/src/lib.rs at line 7

[4.6419]→[4.6419:6431](∅→∅),[4.6431]→[3.5212:5361](∅→∅)

.copied()
.filter(|&factor| factor != 0)
.for_each(|factor| {
if done.iter().all(|&done_factor| factor % done_factor != 0) {
out.push(factor);
}

[4.6419]

[3.5361]

.filter(|&&factor| factor != 0)
.for_each(|&factor| {
out += (factor..limit)
.step_by(factor.try_into().unwrap())
.filter(|&multiple| !done.iter().any(|&done_factor| multiple % done_factor == 0))
.sum::<u32>();
replacement in rust/sum-of-multiples/src/lib.rs at line 15

[3.5389]→[3.5389:5410](∅→∅),[3.5410]→[4.6515:6529](∅→∅),[4.6515]→[4.6515:6529](∅→∅),[4.6529]→[3.5411:5455](∅→∅),[3.5455]→[4.6577:6580](∅→∅),[4.6577]→[4.6577:6580](∅→∅)

if out.is_empty() {
0
} else {
sum_of_multiples_go(&out, limit).unwrap()
}

[3.5389]

[4.2216]

out