peuler 0.1.0

A Rust crate with solutions to the Project Euler problems
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

use crate::Solution;
use itertools::Itertools;
use pmath::digits::{digits, digits_to_int};
use pmath::primes::sieve_of_eratosthenes;
use std::collections::BTreeSet;

problem!(Problem0049, 49, "Prime Permutations");

impl Solution for Problem0049 {
    fn solve(&self) -> String {
        // store all 4-digit primes in a set
        let primes = sieve_of_eratosthenes(9999);
        let mut primes_set = BTreeSet::new();
        for prime in primes {
            if prime > 999 {
                primes_set.insert(prime);
            }
        }

        // vector to store found sequences, there should exist exactly 2 sequences
        let mut found_sequences = Vec::new();

        // logic:
        // take first prime from the set
        // generate its permutations
        // keep only those permutations that are also primes (and remove them from the set)
        // for those numbers, take all combinations of 3
        // and check if they are arithmetic sequences

        let mut prime_perms = Vec::new();
        'outer: while let Some(base_num) = primes_set.pop_first() {
            prime_perms.clear();
            prime_perms.push(base_num);

            // generate permutations
            for perm in digits(base_num, 10).permutations(4) {
                let perm_num = digits_to_int(perm, 10);

                // try to remove the number from the set
                // if it was in the set, true is returned and the number is added to the vector
                // if it was not in the set, false is returned and the number is not added to the vector
                if primes_set.remove(&perm_num) {
                    prime_perms.push(perm_num);
                }
            }

            // sort the permutations so that combinations are increasing for easier arithmetic sequence check
            prime_perms.sort_unstable();

            // check for arithmetic sequences
            for (n1, n2, n3) in prime_perms.iter().tuple_combinations() {
                if n2 - n1 == n3 - n2 {
                    found_sequences.push([*n1, *n2, *n3]);

                    // if 2 sequences are found, break out of the loop
                    if found_sequences.len() == 2 {
                        break 'outer;
                    }
                }
            }
        }

        // assert that there are exactly 2 sequences
        assert_eq!(
            found_sequences.len(),
            2,
            "Found {} sequences, expected 2",
            found_sequences.len()
        );

        // result string
        let mut result = String::new();

        // loop through those 2 sequences and add the non-1487 sequence to the result string
        for seq in found_sequences {
            if !seq.contains(&1487) {
                for num in seq {
                    result.push_str(&num.to_string());
                }
            }
        }

        // return
        result
    }
}