kcode_k1_kmap_selection/
lib.rs

1pub const DEPTH_DECAY: f64 = 0.7;
2
3pub fn score(value: f64, depth: usize) -> f64 {
4    value * DEPTH_DECAY.powf(depth as f64)
5}
6
7pub fn choose<R>(
8    candidates: &[(usize, f64, u64)],
9    temperature: f64,
10    random: &mut R,
11) -> Result<usize, String>
12where
13    R: FnMut() -> Result<f64, String>,
14{
15    if candidates.is_empty() {
16        return Err("Kmap candidate set was empty".to_owned());
17    }
18    if temperature == 0.0 {
19        let maximum = candidates
20            .iter()
21            .map(|candidate| candidate.1)
22            .max_by(f64::total_cmp)
23            .ok_or_else(|| "Kmap candidate set was empty".to_owned())?;
24        let maxima: Vec<usize> = candidates
25            .iter()
26            .enumerate()
27            .filter(|(_, candidate)| candidate.1.total_cmp(&maximum).is_eq())
28            .map(|(index, _)| index)
29            .collect();
30        let index = (random_unit(random)? * maxima.len() as f64) as usize;
31        return maxima
32            .get(index.min(maxima.len() - 1))
33            .copied()
34            .ok_or_else(|| "Kmap maximum candidate set was empty".to_owned());
35    }
36
37    let maximum_log = candidates
38        .iter()
39        .map(|candidate| candidate.1.ln())
40        .max_by(f64::total_cmp)
41        .ok_or_else(|| "Kmap candidate set was empty".to_owned())?;
42    let weights: Vec<f64> = candidates
43        .iter()
44        .map(|candidate| ((candidate.1.ln() - maximum_log) / temperature).exp())
45        .collect();
46    let total: f64 = weights.iter().sum();
47    let threshold = random_unit(random)? * total;
48    let mut cumulative = 0.0;
49    for (index, weight) in weights.into_iter().enumerate() {
50        cumulative += weight;
51        if threshold < cumulative {
52            return Ok(index);
53        }
54    }
55    Ok(candidates.len() - 1)
56}
57
58fn random_unit<R>(random: &mut R) -> Result<f64, String>
59where
60    R: FnMut() -> Result<f64, String>,
61{
62    let value = random()?;
63    if value.is_finite() && (0.0..1.0).contains(&value) {
64        Ok(value)
65    } else {
66        Err("Kmap random value must be finite and in [0, 1)".to_owned())
67    }
68}
69
70pub fn os_random_unit() -> Result<f64, String> {
71    let mut bytes = [0_u8; 8];
72    getrandom::fill(&mut bytes).map_err(|error| format!("Kmap randomness failed: {error}"))?;
73    let value = u64::from_ne_bytes(bytes) >> 11;
74    Ok(value as f64 / (1_u64 << 53) as f64)
75}
76
77#[cfg(test)]
78mod tests {
79    use super::{choose, os_random_unit, score};
80
81    #[test]
82    fn scores_and_selects_deterministically() {
83        assert_eq!(score(1.0, 1), 0.7);
84        let tied = [(0, 0.5, 0), (1, 0.5, 0)];
85        assert_eq!(choose(&tied, 0.0, &mut || Ok(0.75)).unwrap(), 1);
86        let weighted = [(0, 1.0, 0), (1, 2.0, 0)];
87        assert_eq!(choose(&weighted, 1.0, &mut || Ok(0.0)).unwrap(), 0);
88        assert_eq!(choose(&weighted, 1.0, &mut || Ok(0.99)).unwrap(), 1);
89    }
90
91    #[test]
92    fn rejects_invalid_inputs_and_entropy_is_bounded() {
93        let candidates = [(0, 1.0, 0)];
94        assert_eq!(
95            choose(&candidates, 0.0, &mut || Ok(1.0)).unwrap_err(),
96            "Kmap random value must be finite and in [0, 1)"
97        );
98        assert_eq!(
99            choose(&[], 0.0, &mut || Ok(0.0)).unwrap_err(),
100            "Kmap candidate set was empty"
101        );
102        assert!((0.0..1.0).contains(&os_random_unit().unwrap()));
103    }
104}
kcode_k1_kmap_selection/lib.rs

kcode_k1_kmap_selection/
lib.rs
