growth.rs

1use crate::series::Rep;2use crate::word::{render, CODES};34pub fn family(prefix: u8, last: u8, length: usize) -> Vec<u8> {5    let mut word = vec![prefix; length - 1];6    word.push(last);7    word8}910pub fn components(word: &[u8]) -> u64 {11    render(word).components()12}1314pub fn merging(word: &[u8]) -> u64 {15    render(word).merging()16}1718pub fn max_components(length: usize) -> (u64, Vec<u8>) {19    let mut best = 0u64;20    let mut witness: Vec<u8> = Vec::new();21    let mut word = vec![0u8; length];22    walk(&mut word, 0, &mut |candidate: &[u8]| {23        let count = render(candidate).components();24        if count > best {25            best = count;26            witness = candidate.to_vec();27        }28    });29    (best, witness)30}3132pub fn max_merging(length: usize) -> (u64, Vec<u8>) {33    let mut best = 0u64;34    let mut witness: Vec<u8> = Vec::new();35    let mut word = vec![0u8; length];36    walk(&mut word, 0, &mut |candidate: &[u8]| {37        let count = render(candidate).merging();38        if count > best {39            best = count;40            witness = candidate.to_vec();41        }42    });43    (best, witness)44}4546fn walk(word: &mut Vec<u8>, at: usize, visit: &mut dyn FnMut(&[u8])) {47    if at == word.len() {48        visit(word);49        return;50    }51    for &code in CODES.iter() {52        word[at] = code;53        walk(word, at + 1, visit);54    }55}5657pub fn max_predicted(rep: &Rep, length: usize) -> i64 {58    let state: Vec<i128> = rep.lambda.iter().map(|value| *value as i128).collect();59    let mut best = i64::MIN;60    descend(rep, &state, length, &mut best);61    best62}6364fn descend(rep: &Rep, state: &[i128], left: usize, best: &mut i64) {65    if left == 0 {66        let value: i128 = state67            .iter()68            .zip(rep.gamma.iter())69            .map(|(a, b)| a * *b as i128)70            .sum();71        if value as i64 > *best {72            *best = value as i64;73        }74        return;75    }76    for &code in CODES.iter() {77        let matrix = &rep.matrices[&code];78        let mut next = vec![0i128; state.len()];79        for (i, weight) in state.iter().enumerate() {80            if *weight == 0 {81                continue;82            }83            for (j, slot) in next.iter_mut().enumerate() {84                *slot += weight * matrix[i][j] as i128;85            }86        }87        descend(rep, &next, left - 1, best);88    }89}9091pub fn independent_bound(length: usize) -> u64 {92    let side = 1u64 << length;93    side * side / 294}