128 lines
3.8 KiB
Rust
128 lines
3.8 KiB
Rust
use itertools::Itertools;
|
|
use std::collections::HashSet;
|
|
|
|
fn n_to_v(n: &i32) -> Vec<i32> {
|
|
return n
|
|
.to_string()
|
|
.as_bytes()
|
|
.iter()
|
|
.map(|c| *c as i32 - '0' as i32)
|
|
.collect_vec();
|
|
}
|
|
|
|
fn v_to_s(v: &Vec<i32>) -> String {
|
|
return v
|
|
.iter()
|
|
.map(|i| {
|
|
assert!(*i < 10 && *i >= 0);
|
|
i.to_string()
|
|
})
|
|
.join("");
|
|
}
|
|
|
|
fn v_to_n(v: &Vec<i32>) -> i32 {
|
|
let mut r = v.to_vec();
|
|
r.reverse();
|
|
return r.iter().fold(0, |sum, i| sum * 10 + i);
|
|
}
|
|
|
|
fn generate_next_term(digits: Vec<i32>) -> Vec<i32> {
|
|
let mut counts = vec![0; 10];
|
|
let mut next: Vec<i32> = vec![];
|
|
for i in digits {
|
|
assert!(i < 10);
|
|
counts[i as usize] += 1;
|
|
}
|
|
for i in [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] {
|
|
if counts[i as usize] > 0 {
|
|
for d in n_to_v(&counts[i as usize]) {
|
|
next.push(d);
|
|
}
|
|
next.push(i);
|
|
}
|
|
}
|
|
return next;
|
|
}
|
|
|
|
fn generate_sequence(seedterm: &Vec<i32>) -> (usize, Vec<Vec<i32>>, usize) {
|
|
let mut seen = HashSet::new();
|
|
let mut term_vec = seedterm.clone();
|
|
let mut term_string = v_to_s(&term_vec);
|
|
let mut sequence: Vec<Vec<i32>> = vec![];
|
|
for iterations in 0..1000 {
|
|
sequence.push(term_vec.to_vec());
|
|
if !seen.contains(&term_string) {
|
|
seen.insert(term_string.clone());
|
|
term_vec = generate_next_term(term_vec);
|
|
term_string = v_to_s(&term_vec);
|
|
} else {
|
|
// found a repeat in the sequence, so find where last one was
|
|
let prev = (0..sequence.len())
|
|
.find(|i| sequence[*i] == term_vec)
|
|
.unwrap();
|
|
return (iterations, sequence, prev);
|
|
}
|
|
}
|
|
panic!("Could not find a repeat in sequence within 1000 iterations")
|
|
}
|
|
|
|
// To decrease memory usage, just save the seeds and recalculate sequence later
|
|
// To speed up loop, just calculate the numbers with presorted digit sequences
|
|
// and then use permutations of results to regenerate the skipped seeds
|
|
fn find_max_sequences(start: i32, stop: i32) {
|
|
let mut max_length = 1_usize;
|
|
let mut max_length_seeds: Vec<i32> = vec![];
|
|
for i in start..=stop {
|
|
let v = n_to_v(&i);
|
|
let mut dup_seq = v.to_vec();
|
|
dup_seq.sort();
|
|
dup_seq.reverse();
|
|
if v != dup_seq {
|
|
continue;
|
|
}
|
|
let (seq_len, _seq, _prev) = generate_sequence(&v);
|
|
if seq_len > max_length {
|
|
max_length_seeds.clear();
|
|
max_length_seeds.push(i);
|
|
max_length = seq_len;
|
|
} else if seq_len == max_length {
|
|
max_length_seeds.push(i);
|
|
}
|
|
}
|
|
let mut perm_seeds: Vec<i32> = vec![];
|
|
for seed in max_length_seeds.clone() {
|
|
let v = n_to_v(&seed);
|
|
let minresult = 10_i32.pow(v.len() as u32 - 1_u32);
|
|
for p in v.iter().permutations(v.len()) {
|
|
let perm = p.iter().map(|x| **x).collect_vec();
|
|
let n = v_to_n(&perm);
|
|
if n >= minresult {
|
|
perm_seeds.push(v_to_n(&perm));
|
|
}
|
|
}
|
|
}
|
|
perm_seeds.sort();
|
|
perm_seeds.dedup();
|
|
println!(
|
|
"Seeds: {}",
|
|
perm_seeds.iter().map(|n| n.to_string()).join(" ")
|
|
);
|
|
println!("\n Iterations: {max_length}\n\nExample sequence:\n");
|
|
let (_len, seq, prev) = generate_sequence(&n_to_v(&max_length_seeds[0]));
|
|
for (idx, v) in seq.iter().enumerate() {
|
|
println!(
|
|
"{:<2}: {}{}",
|
|
idx + 1,
|
|
v.iter().map(|i| i.to_string()).join(""),
|
|
if idx == seq.len() - 1 {
|
|
format!(" <-- repeats the sequence from line {}.", prev + 1)
|
|
} else {
|
|
"".to_string()
|
|
},
|
|
);
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
find_max_sequences(1, 999_999);
|
|
}
|