main.rs

mail@pastecode.io avatar
unknown
rust
a month ago
3.1 kB
2
Indexable
Never
#!/usr/bin/rustc

type Pair = (usize, usize);

fn gen_figurates(k: usize) -> Vec<Pair> {
    let mut n: usize = 1;
    let mut x: usize;
    let mut output: Vec<Pair> = Vec::new();
    loop {
        x = n*((k - 2)*n + 4 - k) / 2;
        n += 1;
        if x < 1_000 {
            continue;
        }
        if x >= 10_000 {
            break;
        }
        output.push((x / 100, x % 100));
    }
    output
}

fn find_nexts(
        path: &Vec<Pair>,
        nodes: &Vec<Vec<Pair>>,
        mapping: &Vec<Vec<Pair>>
        ) -> Vec<Pair> {
    // Given a path, find all possible next nodes (if any) of a cycle.
    let end: Pair = path[path.len() - 1];
    let visited: Vec<usize> = path
        .iter()
        .map(|x| x.0)
        .collect();
    let nexts: &Vec<Pair> = &mapping[nodes[end.0][end.1].1]
        .iter()
        .filter(|(a, _)| !visited.contains(a))
        .map(|x| *x)
        .collect();
    nexts.to_vec()
}

fn main() {
    // :nodes: Figurate numbers given as <first 2 digits> <last 2 digit> tuples.
    // :mapping: When indexed with a <last 2 digits> number, gives the indices
    //   corresponding to nodes with those as <first 2 digits>.
    let nodes: Vec<Vec<Pair>> = (3_usize..=8)
        .map(gen_figurates)
        .collect();
    let mut mapping: Vec<Vec<Pair>> = vec![Vec::new(); 100];
    for (i, fig_set) in nodes.iter().enumerate() {
        for (j, (start, _end)) in fig_set.iter().enumerate() {
            mapping[*start as usize].push((i, j));
        }
    }
    for seed_index in 0..nodes[nodes.len() - 1].len() {
        let mut paths: Vec<Vec<Pair>> = vec![vec![(5, seed_index)]];
        for _ in 0..5 {
            if paths.len() == 0 {
                break;
            }
            let mut new_paths: Vec<Vec<Pair>> = Vec::new();
            for path in &paths {
                let nexts: Vec<Pair> = find_nexts(path, &nodes, &mapping);
                for next in nexts {
                    let mut new_path = path.clone();
                    new_path.push(next);
                    new_paths.push(new_path);
                }
            }
            paths = new_paths;
        }
        for path in &paths {
            let (f0, f1) = path[0];
            let (l0, l1) = path[5];
            if nodes[f0][f1].0 == nodes[l0][l1].1 {
                let mut unique_check = path.clone();
                unique_check.sort();
                unique_check.dedup();
                if unique_check.len() == 6 {
                    // for node in path {
                    //     let digits = nodes[node.0][node.1];
                    //     print!("{}", 100*digits.0 + digits.1);
                    //     print!(" <{}>, ", node.0 + 3);
                    // }
                    // println!();
                    let ans: usize = path
                        .iter()
                        .map(|(a, b)| nodes[*a][*b])
                        .map(|(x, y)| 100*x + y)
                        .sum();
                    println!("{}", ans);
                    return;
                }
            }
        }
    }
}

Leave a Comment