24: Add WIP solution for Rust track exercise "Sum Of Multiples".

[?]

Aaw9nJhsNmfzFih9mKyNw9mV8CgERXJkRa1kK1Kx3LQH

Sep 1, 2021, 11:33 AM

SPUEEQZQFZDVOLZTAXLRHXPCQ3JWN32O7YCND24XVCHYIDNNT4QQC

Dependencies

[2] 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/tests/sum-of-multiples.rs at line 5

[2.159]→[2.159:207](∅→∅)

assert_eq!(0, sum_of_multiples(1, &[3, 5]))

[2.159]

[2.207]

assert_eq!(0, sum_of_multiples(1, &[3, 5]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 11

[2.273]→[2.273:321](∅→∅)

assert_eq!(3, sum_of_multiples(4, &[3, 5]))

[2.273]

[2.321]

assert_eq!(3, sum_of_multiples(4, &[3, 5]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 17

[2.385]→[2.385:430](∅→∅)

assert_eq!(9, sum_of_multiples(7, &[3]))

[2.385]

[2.430]

assert_eq!(9, sum_of_multiples(7, &[3]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 23

[2.507]→[2.507:557](∅→∅)

assert_eq!(23, sum_of_multiples(10, &[3, 5]))

[2.507]

[2.557]

assert_eq!(23, sum_of_multiples(10, &[3, 5]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 29

[2.620]→[2.620:673](∅→∅)

assert_eq!(2318, sum_of_multiples(100, &[3, 5]))

[2.620]

[2.673]

assert_eq!(2318, sum_of_multiples(100, &[3, 5]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 35

[2.721]→[2.721:778](∅→∅)

assert_eq!(233_168, sum_of_multiples(1000, &[3, 5]))

[2.721]

[2.778]

assert_eq!(233_168, sum_of_multiples(1000, &[3, 5]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 41

[2.820]→[2.820:875](∅→∅)

assert_eq!(51, sum_of_multiples(20, &[7, 13, 17]))

[2.820]

[2.875]

assert_eq!(51, sum_of_multiples(20, &[7, 13, 17]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 47

[2.932]→[2.932:982](∅→∅)

assert_eq!(30, sum_of_multiples(15, &[4, 6]))

[2.932]

[2.982]

assert_eq!(30, sum_of_multiples(15, &[4, 6]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 53

[2.1062]→[2.1062:1118](∅→∅)

assert_eq!(4419, sum_of_multiples(150, &[5, 6, 8]))

[2.1062]

[2.1118]

assert_eq!(4419, sum_of_multiples(150, &[5, 6, 8]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 59

[2.1182]→[2.1182:1234](∅→∅)

assert_eq!(275, sum_of_multiples(51, &[5, 25]))

[2.1182]

[2.1234]

assert_eq!(275, sum_of_multiples(51, &[5, 25]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 65

[2.1282]→[2.1282:1345](∅→∅)

assert_eq!(2_203_160, sum_of_multiples(10_000, &[43, 47]))

[2.1282]

[2.1345]

assert_eq!(2_203_160, sum_of_multiples(10_000, &[43, 47]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 71

[2.1404]→[2.1404:1454](∅→∅)

assert_eq!(4950, sum_of_multiples(100, &[1]))

[2.1404]

[2.1454]

assert_eq!(4950, sum_of_multiples(100, &[1]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 77

[2.1512]→[2.1512:1561](∅→∅)

assert_eq!(0, sum_of_multiples(10_000, &[]))

[2.1512]

[2.1561]

assert_eq!(0, sum_of_multiples(10_000, &[]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 83

[2.1617]→[2.1617:1662](∅→∅)

assert_eq!(0, sum_of_multiples(1, &[0]))

[2.1617]

[2.1662]

assert_eq!(0, sum_of_multiples(1, &[0]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 89

[2.1757]→[2.1757:1805](∅→∅)

assert_eq!(3, sum_of_multiples(4, &[3, 0]))

[2.1757]

[2.1805]

assert_eq!(3, sum_of_multiples(4, &[3, 0]))
replacement in rust/sum-of-multiples/tests/sum-of-multiples.rs at line 95

[2.1907]→[2.1907:1979](∅→∅)

assert_eq!(39_614_537, sum_of_multiples(10_000, &[2, 3, 5, 7, 11]))

[2.1907]

[2.1979]

assert_eq!(39_614_537, sum_of_multiples(10_000, &[2, 3, 5, 7, 11]))
edit in rust/sum-of-multiples/src/lib.rs at line 1

[2.2029]

[2.2030]

mod error_a {
use std::{error, fmt};

#[derive(Debug)]
pub 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> {}
}

mod combinations {
use crate::error_a::CreationError;

#[derive(PartialEq)]
enum State {
A,
B,
C,
D,
E,
}

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

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

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

mod num_traits {
pub trait Unsigned {}

impl Unsigned for u32 {}
}

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

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 {
self.out += self.factor;
Some(self.out - self.factor)
} else {
None
}
}
}
}

use crate::{
combinations::CombinationsWithoutReplacement, error_a::CreationError,
multiples::UnsignedMultiples,
};

fn sum_of_multiples_go(factors: &[u32], limit: u32) -> Result<u32, CreationError<u32>> {
(1..=factors.len()).try_fold(
0,
|accumulator_a, subset_size| -> Result<u32, CreationError<u32>> {
Ok(if subset_size & 1 == 1 {
accumulator_a
+ CombinationsWithoutReplacement::new(factors, subset_size)?.fold(
0,
|accumulator_b, combination| {
accumulator_b
+ UnsignedMultiples::new(combination.iter().product(), limit)
.sum::<u32>()
},
)
} else {
accumulator_a
- CombinationsWithoutReplacement::new(factors, subset_size)?.fold(
0,
|accumulator_b, combination| {
accumulator_b
+ UnsignedMultiples::new(combination.iter().product(), limit)
.sum::<u32>()
},
)
})
},
)
}
replacement in rust/sum-of-multiples/src/lib.rs at line 265

[2.2092]→[2.2092:2216](∅→∅)

unimplemented!(
"Sum the multiples of all of {:?} which are less than {}",
factors,
limit
)

[2.2092]

[2.2216]

let factors = factors
.iter()
.copied()
.filter(|factor| *factor != 0)
.collect::<Vec<u32>>();
if factors.is_empty() {
0
} else {
sum_of_multiples_go(&factors, limit).unwrap()
}