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