Rust Implementation of Problem 14
View source code here on GitHub!
Problem Solution
- pub fn problems::p0014::p0014() -> utils::Answer
1/*
2Project Euler Problem 14
3
4This was pleasantly easy to adapt from my Python solution.
5
6Problem:
7
8The following iterative sequence is defined for the set of positive integers:
9
10n → n/2 (n is even)
11n → 3n + 1 (n is odd)
12
13Using the rule above and starting with 13, we generate the following sequence:
1413 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
15
16It can be seen that this sequence (starting at 13 and finishing at 1) contains
1710 terms. Although it has not been proved yet (Collatz Problem), it is thought
18that all starting numbers finish at 1.
19
20Which starting number, under one million, produces the longest chain?
21
22NOTE: Once the chain starts the terms are allowed to go above one million.
23*/
24use std::collections::HashMap;
25
26use crate::include::utils::Answer;
27
28fn collatz_len(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
29 if n == 1 {
30 return 0;
31 }
32 else if cache.contains_key(&n) {
33 return *(cache.get(&n).expect("We just verified it's in the map"));
34 }
35 else if n & 1 == 0 {
36 let result = 1 + collatz_len(n / 2, cache);
37 cache.insert(n, result);
38 return result;
39 }
40 else {
41 let result = 2 + collatz_len((3 * n + 1) / 2, cache);
42 cache.insert(n, result);
43 return result;
44 }
45}
46
47pub fn p0014() -> Answer {
48 let mut biggest_seen: u64 = 0;
49 let mut biggest_idx: u64 = 0;
50 let mut cache: HashMap<u64, u64> = HashMap::new();
51 for x in 1..1000000 {
52 let result = collatz_len(x, &mut cache);
53 if result > biggest_seen {
54 biggest_seen = result;
55 biggest_idx = x;
56 }
57 }
58 return Answer::Int(biggest_idx.into());
59}