Problem: https://projecteuler.net/problem=51
"Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family."
repository: https://github.com/steven-omaha/euler51
dependencies: num
This code is my attempt at solving Project Euler challenge #51. This code takes ~ 1000 ms to run on my PC.
Comments from me:
primes.rsis intentionally generic, as most a good amount of Project Euler challenges involve prime numbers. This is normally a separate package.combination.rsproducesVec<bool>elements, like[1, 0, 0, 1, 1]. These vectors are used inmain.rsto identify the positions where a digit should be replaced.
Main concerns for review:
- Single-thread performance. I am aware of multithreading, but I'm not interested in that in the scope of this review. Am I giving away performance improvements somewhere?
- code cleanliness
- any code smells
Things that I'm aware are suboptimal:
apply_transformationdoes too much and would better be two functions (see comments there). I was thinking on how to transfer the data between the (hypothetical) two different functions. I tried that by collecting to aVec, but that had some performance penalty. I think the best would be to implementMap, but I have never done that.- I have a feeling that transforming an int to an array of digits via
charis suboptimal, but I have not measured that.
main.rs:
mod combination;
mod primes;
use combination::PositionCombinations;
use primes::Primes;
type Int = u64;
// EXAMPLE 1
// const MIN_VALUE: Int = 10;
// const MAX_VALUE: Int = 99;
// const LENGTH: usize = 2;
// const MIN_LENGTH: usize = 1;
// EXAMPLE 2
// const MIN_VALUE: Int = 10_000;
// const MAX_VALUE: Int = 99_999;
// const LENGTH: usize = 5;
// const MIN_LENGTH: usize = 2;
// FINAL
const MIN_VALUE: Int = 100_000;
const MAX_VALUE: Int = 999_999;
const LENGTH: usize = 6;
const MIN_LENGTH: usize = 2;
const MAX_LENGTH: usize = LENGTH - 1;
const DIGITS: [u8; 10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
fn main() {
let all_primes = Primes::get_between(MIN_VALUE, MAX_VALUE);
let mut best_of_all_combinations = vec![];
for pattern in PositionCombinations::new(MIN_LENGTH, MAX_LENGTH, LENGTH) {
let mut best_this_combination = vec![];
let mut primes_to_check = all_primes.clone();
while let Some(first) = primes_to_check.pop() {
let mut primes_matching_pattern = vec![];
let digits = first.to_digits();
for digit in DIGITS {
let could_be_prime = apply_transformation(&digits, digit, &pattern);
if primes_to_check.contains(&could_be_prime) || could_be_prime == first {
primes_matching_pattern.push(could_be_prime);
}
}
if primes_matching_pattern.len() > 2 {
best_this_combination.push(primes_matching_pattern);
}
}
if !best_this_combination.is_empty() {
best_of_all_combinations.push(get_longest(best_this_combination));
}
}
println!("{:#?}", get_longest(best_of_all_combinations));
}
fn apply_transformation(prime_as_digits: &[u8], new_digit: u8, pattern: &[bool]) -> Int {
debug_assert_eq!(prime_as_digits.len(), pattern.len());
let mut multiplier = 1;
let result = prime_as_digits
// apply the pattern to prime_as_digits
.iter()
.zip(pattern)
.map(|(old_digit, replace)| if *replace { new_digit } else { *old_digit })
.map(Int::from)
// calculate Int
.rev()
.reduce(|accum, item| {
multiplier *= 10;
accum + multiplier * item
})
.unwrap();
debug_assert_eq!(multiplier, 100_000);
result
}
fn get_longest(mut vec: Vec<Vec<Int>>) -> Vec<Int> {
assert!(
!vec.is_empty(),
"cannot get the longest element of an empty vector"
);
vec.sort_by_key(Vec::len);
let length = vec.last().unwrap().len();
vec.into_iter().find(|v| v.len() == length).unwrap()
}
trait ToDigits {
fn to_digits(&self) -> Vec<u8>;
}
impl ToDigits for Int {
fn to_digits(&self) -> Vec<u8> {
self.to_string()
.chars()
.map(|x| x.to_digit(10).unwrap() as u8)
.collect()
}
}
#[cfg(test)]
mod test {
use crate::{apply_transformation, ToDigits};
#[test]
fn test_num_to_digits() {
let num = 83371;
assert_eq!(num.to_digits(), vec![8, 3, 3, 7, 1]);
}
#[test]
fn test_apply_transformation() {
let prime_as_digits = [5, 7, 3, 8, 2, 1];
let new_digit = 0;
let pattern = [false, true, true, true, false, false];
assert_eq!(
apply_transformation(&prime_as_digits, new_digit, &pattern),
500_021
);
}
}
combination.rs:
pub struct PositionCombinations {
min_length: usize,
max_length: usize,
state: Vec<bool>,
finished: bool,
}
impl Iterator for PositionCombinations {
type Item = Vec<bool>;
fn next(&mut self) -> Option<Self::Item> {
loop {
let result = self.state.clone();
self.increment();
if self.finished {
return None;
}
if (self.min_length..=self.max_length).contains(&result.iter().filter(|x| **x).count())
{
return Some(result);
}
}
}
}
impl PositionCombinations {
pub fn new(min_length: usize, max_length: usize, length: usize) -> Self {
let state = vec![false; length];
let finished = false;
Self {
min_length,
max_length,
state,
finished,
}
}
fn increment(&mut self) {
let mut overflow = self.state[0];
self.state[0] ^= true;
for position in self.state[1..].iter_mut() {
let new_overflow = *position & overflow;
*position ^= overflow;
overflow = new_overflow;
}
if overflow {
self.finished = true;
}
}
}
pub trait ToString {
fn to_string(&self) -> String;
}
impl ToString for Vec<bool> {
fn to_string(&self) -> String {
self.iter().map(|b| if *b { 'x' } else { '.' }).collect()
}
}
#[cfg(test)]
mod test {
use crate::combination::PositionCombinations;
use std::collections::HashSet;
#[test]
fn test_combination_2_3_4() {
let combinator = PositionCombinations::new(2, 3, 4);
let result: Vec<_> = combinator.into_iter().collect();
let mut number_solutions = result.len();
let mut solution = HashSet::new();
solution.insert(vec![false, false, true, true]);
solution.insert(vec![false, true, false, true]);
solution.insert(vec![false, true, true, false]);
solution.insert(vec![false, true, true, true]);
solution.insert(vec![true, true, false, false]);
solution.insert(vec![true, false, true, false]);
solution.insert(vec![true, false, false, true]);
solution.insert(vec![true, false, true, true]);
solution.insert(vec![true, true, false, true]);
solution.insert(vec![true, true, true, false]);
for item in solution {
assert!(result.contains(&item));
number_solutions -= 1;
}
assert_eq!(number_solutions, 0);
}
#[test]
fn test_combination_2_2_3() {
let combinator = PositionCombinations::new(2, 2, 3);
let result: Vec<_> = combinator.into_iter().collect();
let mut number_solutions = result.len();
let mut solution = HashSet::new();
solution.insert(vec![false, true, true]);
solution.insert(vec![true, false, true]);
solution.insert(vec![true, true, false]);
for item in solution {
assert!(result.contains(&item));
number_solutions -= 1;
}
assert_eq!(number_solutions, 0);
}
}
primes.rs
extern crate num;
use num::FromPrimitive;
use num::Num;
use num::ToPrimitive;
use std::collections::HashSet;
use std::hash::Hash;
#[derive(Clone)]
pub struct Primes<T> {
vector: Vec<T>,
set: HashSet<T>,
}
impl<T> Primes<T>
where
T: Num + ToPrimitive + FromPrimitive + Hash + Eq + PartialEq + Copy,
{
pub fn get_between(min_value: T, max_value: T) -> Self {
let max_value = max_value.to_usize().unwrap();
let min_value = min_value.to_usize().unwrap();
assert!(min_value > 1);
assert!(max_value > min_value);
Self::from_array(
&Self::get_prime_numbers_array(min_value, max_value),
min_value,
max_value,
)
}
fn from_array(array: &[bool], min_value: usize, max_value: usize) -> Self {
let mut vector = Vec::new();
let mut set = HashSet::new();
for number in min_value..max_value {
if array[(number - min_value) as usize] {
let prime = FromPrimitive::from_usize(number).unwrap();
vector.push(prime);
set.insert(prime);
}
}
vector.reverse(); // so that self.pop removes the smallest prime
Primes { vector, set }
}
fn get_prime_numbers_array(min_value: usize, max_value: usize) -> Vec<bool> {
// Sieve of Eratosthenes
let length = max_value - min_value;
let mut result = vec![true; length];
for number_to_check in 2..(max_value / 2) {
let mut last_number = number_to_check;
loop {
let current_number = last_number + number_to_check;
if current_number < min_value {
last_number = current_number;
continue;
}
if current_number >= max_value {
break;
}
result[current_number - min_value] = false;
last_number = current_number;
}
}
result
}
pub fn pop(&mut self) -> Option<T> {
let result = self.vector.pop();
if let Some(value) = result {
self.set.remove(&value);
}
result
}
pub fn contains(&self, val: &T) -> bool {
self.set.contains(val)
}
}
#[cfg(test)]
mod test {
use crate::primes::Primes;
#[test]
fn test_example_prime() {
let primes = Primes::get_between(2, 99_999);
assert!(primes.set.contains(&56003));
assert!(primes.set.contains(&56993));
assert!(!primes.set.contains(&56002));
}
#[test]
fn test_pop() {
let mut primes = Primes::get_between(10, 20);
assert!(primes.contains(&11));
primes.pop();
assert!(!primes.contains(&11));
}
}
Thank you for your time!
