45 lines
1.4 KiB
Rust
45 lines
1.4 KiB
Rust
use std::collections::HashMap;
|
|
|
|
fn pancake_flips(len: usize) -> Option<(Vec<i32>, i32)> {
|
|
if len < 1 {
|
|
return None;
|
|
}
|
|
let goal_stack: Vec<i32> = (1..len as i32 + 1).collect();
|
|
let mut stacks: HashMap<Vec<i32>, i32> = HashMap::new();
|
|
stacks.insert(goal_stack.clone(), 0);
|
|
let mut num_stacks = 1;
|
|
let mut new_stacks = stacks.clone();
|
|
for i in 1..1001 {
|
|
let mut next_stacks: HashMap<Vec<i32>, i32> = HashMap::new();
|
|
for (arr, _steps) in &new_stacks {
|
|
for pos in 1_usize..(len + 1) {
|
|
let mut new_stack = arr[0..pos].to_vec();
|
|
new_stack.reverse();
|
|
new_stack.extend_from_slice(&arr[pos..arr.len()]);
|
|
if !stacks.contains_key(&new_stack) {
|
|
next_stacks.insert(new_stack.clone(), i);
|
|
}
|
|
}
|
|
}
|
|
new_stacks = next_stacks;
|
|
stacks.extend(new_stacks.clone().into_iter());
|
|
let perms = stacks.len();
|
|
if perms == num_stacks {
|
|
match stacks.into_iter().max_by_key(|p| p.1) {
|
|
Some(pair) => return Some(pair),
|
|
None => break,
|
|
}
|
|
}
|
|
num_stacks = perms;
|
|
}
|
|
None
|
|
}
|
|
|
|
fn main() {
|
|
for i in 1..=10 {
|
|
match pancake_flips(i) {
|
|
Some(p) => println!("pancake({:>2}) = {:<5} example: {:?}", i, p.1, p.0),
|
|
None => println!("Error: cannot flip stack with size {i}"),
|
|
}
|
|
}
|
|
}
|