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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

use crate::Solution;
use pmath::digits::digits_to_int;
use std::collections::HashMap;
use std::sync::LazyLock;

problem!(Problem0043, 43, "Sub-string Divisibility");

impl Solution for Problem0043 {
    fn solve(&self) -> String {
        let mut sum = 0;
        let mut working = Vec::new();

        recursive_search(&mut working, &mut sum, 1);

        sum.to_string()
    }
}

/// The digits that can be used in each position.
static DIGITS: LazyLock<HashMap<u8, Vec<u8>>> = LazyLock::new(|| {
    let mut digits = HashMap::with_capacity(10);
    digits.insert(1, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
    digits.insert(2, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    digits.insert(3, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    digits.insert(4, vec![0, 2, 4, 6, 8]);
    digits.insert(5, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    digits.insert(6, vec![0, 5]);
    digits.insert(7, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    digits.insert(8, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    digits.insert(9, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    digits.insert(10, vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    digits
});

/// Recursively search for all pandigital numbers with the given properties.
fn recursive_search(working: &mut Vec<u8>, sum: &mut u64, depth: u8) {
    // if depth is 1, just use every digit for that position
    // (there is no need to check if the digit is already used since it is the first digit)
    // first property needs to be checked at d4, so for 2 and 3
    // just use every digit (but check if the digit was already used)
    // also for d4 use every digit since divisibility by 2 is ensured by using even digits for d4
    // the same goes for d6 (divisibility by 5 is ensured by using 0 or 5 for d6)
    // for other positions, use every digit in the position, checking the divisibility property
    // and if the divisibility property is satisfied, continue the recursive search
    // if we get to d11, we have a pandigital number with the given properties

    match depth {
        1 => {
            for i in DIGITS.get(&depth).unwrap() {
                working.push(*i);
                recursive_search(working, sum, depth + 1);
                working.pop();
            }
        }
        2..=4 | 6 => {
            for i in DIGITS.get(&depth).unwrap() {
                if !working.contains(i) {
                    working.push(*i);
                    recursive_search(working, sum, depth + 1);
                    working.pop();
                }
            }
        }
        5 => {
            for i in DIGITS.get(&depth).unwrap() {
                if !working.contains(i) {
                    working.push(*i);
                    let value: i32 = digits_to_int(working[2..5].iter().rev(), 10);
                    if value % 3 == 0 {
                        recursive_search(working, sum, depth + 1);
                    }
                    working.pop();
                }
            }
        }
        7 => {
            for i in DIGITS.get(&depth).unwrap() {
                if !working.contains(i) {
                    working.push(*i);
                    let value: i32 = digits_to_int(working[4..7].iter().rev(), 10);
                    if value % 7 == 0 {
                        recursive_search(working, sum, depth + 1);
                    }
                    working.pop();
                }
            }
        }
        8 => {
            for i in DIGITS.get(&depth).unwrap() {
                if !working.contains(i) {
                    working.push(*i);
                    let value: i32 = digits_to_int(working[5..8].iter().rev(), 10);
                    if value % 11 == 0 {
                        recursive_search(working, sum, depth + 1);
                    }
                    working.pop();
                }
            }
        }
        9 => {
            for i in DIGITS.get(&depth).unwrap() {
                if !working.contains(i) {
                    working.push(*i);
                    let value: i32 = digits_to_int(working[6..9].iter().rev(), 10);
                    if value % 13 == 0 {
                        recursive_search(working, sum, depth + 1);
                    }
                    working.pop();
                }
            }
        }
        10 => {
            for i in DIGITS.get(&depth).unwrap() {
                if !working.contains(i) {
                    working.push(*i);
                    let value: i32 = digits_to_int(working[7..10].iter().rev(), 10);
                    if value % 17 == 0 {
                        recursive_search(working, sum, depth + 1);
                    }
                    working.pop();
                }
            }
        }
        11 => {
            let value: u64 = digits_to_int(working.iter().rev(), 10);
            *sum += value;
        }
        _ => unreachable!("Invalid depth"),
    }
}