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