wowlab_sentinel/strategy/factorial/
screening.rs

1//! Arithmetic screening over all permutations.
2
3#![expect(
4    clippy::cast_possible_truncation,
5    clippy::cast_precision_loss,
6    clippy::cast_sign_loss,
7    reason = "screening converts bounded permutation counts through percentage arithmetic"
8)]
9
10use std::{cmp::Reverse, collections::BinaryHeap};
11
12use wowlab_common::sim::sentinel_config::ScreeningConfig;
13use wowlab_types::{constants::HUNDRED, sim::FastMap};
14
15use super::types::{FactorialSlot, InteractionEstimate, MainEffectEstimate, ScreeningResult};
16
17const TIER1_MAX: u64 = 50_000;
18const TIER2_MAX: u64 = 500_000;
19const TIER3_MAX: u64 = 5_000_000;
20const TIER2_PCT: f64 = 5.0;
21const TIER3_PCT: f64 = 2.0;
22const TIER4_PCT: f64 = 1.0;
23const DEFAULT_KEEP_MIN: u32 = 100;
24
25/// `(slot_index, item_idx)` pair identifying one item choice in one slot.
26pub(super) type SlotItemKey = (u32, u32);
27/// Ordered pair of [`SlotItemKey`]s with `slot_a < slot_b`.
28pub(super) type InteractionKey = (SlotItemKey, SlotItemKey);
29
30#[derive(Clone, Debug)]
31pub(crate) struct FactorialModel {
32    pub grand_mean_x10: i32,
33    pub main_effects: FastMap<SlotItemKey, i32>,
34    pub interactions: FastMap<InteractionKey, i32>,
35}
36
37impl FactorialModel {
38    pub(crate) fn predict(&self, picks: &[(u32, u32)]) -> i32 {
39        let mut dps = self.grand_mean_x10;
40
41        for &(slot, item) in picks {
42            if let Some(&e) = self.main_effects.get(&(slot, item)) {
43                dps = dps.saturating_add(e);
44            }
45        }
46
47        for i in 0..picks.len() {
48            for j in (i + 1)..picks.len() {
49                // BOUNDS: i, j range over `0..picks.len()`
50                let (a, b) = (picks[i], picks[j]);
51                let key = if a.0 < b.0 { (a, b) } else { (b, a) };
52
53                if let Some(&e) = self.interactions.get(&key) {
54                    dps = dps.saturating_add(e);
55                }
56            }
57        }
58
59        dps
60    }
61}
62
63pub(crate) fn reconstruct_model(
64    grand_mean_x10: i32,
65    main_effects: &[MainEffectEstimate],
66    interactions: &[InteractionEstimate],
67) -> FactorialModel {
68    let mut m: FastMap<SlotItemKey, i32> = FastMap::default();
69
70    for me in main_effects {
71        m.insert((me.slot_index, me.item_idx), me.effect_dps_x10);
72    }
73
74    let mut i: FastMap<InteractionKey, i32> = FastMap::default();
75
76    for it in interactions {
77        let a = (it.slot_a, it.item_idx_a);
78        let b = (it.slot_b, it.item_idx_b);
79        let key = if a.0 < b.0 { (a, b) } else { (b, a) };
80
81        i.insert(key, it.interaction_dps_x10);
82    }
83
84    FactorialModel {
85        grand_mean_x10,
86        main_effects: m,
87        interactions: i,
88    }
89}
90
91pub(crate) fn run_screening(
92    model: &FactorialModel,
93    slots: &[FactorialSlot],
94    screening_config: Option<&ScreeningConfig>,
95) -> ScreeningResult {
96    let total_permutations: u64 = slots
97        .iter()
98        .map(|s| s.items.len().max(1) as u64)
99        .fold(1u64, u64::saturating_mul)
100        .max(1);
101
102    let keep_pct = select_keep_pct(total_permutations, screening_config);
103    let keep_min = u64::from(screening_config.map_or(DEFAULT_KEEP_MIN, |c| c.keep_min));
104
105    let target = ((total_permutations as f64 * keep_pct) / HUNDRED).ceil() as u64;
106    let keep_count = target.max(keep_min).min(total_permutations);
107    let mut top = BinaryHeap::with_capacity(keep_count as usize);
108    let mut picks_buf: Vec<(u32, u32)> = vec![(0, 0); slots.len()];
109
110    for perm in 0..total_permutations {
111        decode_permutation(slots, perm, &mut picks_buf);
112        let dps = model.predict(&picks_buf);
113        let entry = (dps, Reverse(perm));
114
115        if top.len() < keep_count as usize {
116            top.push(Reverse(entry));
117        } else if top.peek().is_some_and(|worst| entry > worst.0) {
118            top.pop();
119            top.push(Reverse(entry));
120        }
121    }
122
123    let mut scored: Vec<(u64, i32)> = top
124        .into_iter()
125        .map(|Reverse((dps, Reverse(perm)))| (perm, dps))
126        .collect();
127
128    scored.sort_by(|(perm_a, dps_a), (perm_b, dps_b)| dps_b.cmp(dps_a).then(perm_a.cmp(perm_b)));
129    let survivors = scored.into_iter().map(|(perm, _)| perm).collect();
130
131    ScreeningResult { survivors }
132}
133
134pub(super) fn decode_permutation(slots: &[FactorialSlot], mut perm: u64, out: &mut [(u32, u32)]) {
135    // BOUNDS: caller passes `out` of length `slots.len()`
136    for (i, slot) in slots.iter().enumerate().rev() {
137        let radix = slot.items.len().max(1) as u64;
138        let item_idx = (perm % radix) as u32;
139
140        perm /= radix;
141
142        if let Some(cell) = out.get_mut(i) {
143            *cell = (slot.slot_index, item_idx);
144        }
145    }
146}
147
148pub(super) fn select_keep_pct(total_perms: u64, config: Option<&ScreeningConfig>) -> f64 {
149    if let Some(cfg) = config {
150        if let Some(pct) = cfg.keep_pct {
151            return pct;
152        }
153    }
154
155    if total_perms <= TIER1_MAX {
156        HUNDRED
157    } else if total_perms <= TIER2_MAX {
158        TIER2_PCT
159    } else if total_perms <= TIER3_MAX {
160        TIER3_PCT
161    } else {
162        TIER4_PCT
163    }
164}
165
166#[cfg(test)]
167mod tests {
168    use googletest::prelude::*;
169
170    use super::*;
171    use crate::strategy::factorial::types::FactorialItem;
172
173    fn slot(slot_index: u32, n: usize) -> FactorialSlot {
174        FactorialSlot {
175            slot_index,
176            items: (0..n).map(|_i| FactorialItem::new(false)).collect(),
177        }
178    }
179
180    #[gtest]
181    fn adaptive_keep_pct_tiers() -> Result<()> {
182        verify_that!(select_keep_pct(10_000, None), near(100.0, f64::EPSILON))?;
183        verify_that!(select_keep_pct(100_000, None), near(5.0, f64::EPSILON))?;
184        verify_that!(select_keep_pct(1_000_000, None), near(2.0, f64::EPSILON))?;
185        verify_that!(select_keep_pct(10_000_000, None), near(1.0, f64::EPSILON))?;
186
187        Ok(())
188    }
189
190    #[gtest]
191    fn explicit_keep_pct_overrides_table() -> Result<()> {
192        let cfg = ScreeningConfig {
193            keep_pct: Some(7.5),
194            keep_min: 10,
195        };
196
197        verify_that!(
198            select_keep_pct(1_000_000, Some(&cfg)),
199            near(7.5, f64::EPSILON)
200        )?;
201
202        Ok(())
203    }
204
205    #[gtest]
206    fn predict_uses_main_effects_and_interactions() -> Result<()> {
207        let me = vec![
208            MainEffectEstimate {
209                slot_index: 0,
210                item_idx: 1,
211                effect_dps_x10: 500,
212            },
213            MainEffectEstimate {
214                slot_index: 1,
215                item_idx: 1,
216                effect_dps_x10: 300,
217            },
218        ];
219        let it = vec![InteractionEstimate {
220            slot_a: 0,
221            item_idx_a: 1,
222            slot_b: 1,
223            item_idx_b: 1,
224            interaction_dps_x10: 100,
225        }];
226        let model = reconstruct_model(10_000, &me, &it);
227        let dps = model.predict(&[(0, 1), (1, 1)]);
228
229        verify_eq!(dps, 10_000 + 500 + 300 + 100)?;
230
231        Ok(())
232    }
233
234    #[gtest]
235    fn screening_keeps_top_survivors() -> Result<()> {
236        let slots = vec![slot(0, 3), slot(1, 3)];
237        let me = vec![
238            MainEffectEstimate {
239                slot_index: 0,
240                item_idx: 2,
241                effect_dps_x10: 1_000,
242            },
243            MainEffectEstimate {
244                slot_index: 1,
245                item_idx: 2,
246                effect_dps_x10: 800,
247            },
248        ];
249        let model = reconstruct_model(10_000, &me, &[]);
250        let cfg = ScreeningConfig {
251            keep_pct: Some(100.0 / 9.0 + 0.1),
252            keep_min: 1,
253        };
254        let result = run_screening(&model, &slots, Some(&cfg));
255
256        verify_true!(!result.survivors.is_empty())?;
257        let mut picks = vec![(0u32, 0u32); 2];
258
259        decode_permutation(&slots, *result.survivors.first().or_fail()?, &mut picks);
260        verify_eq!(picks, vec![(0, 2), (1, 2)])?;
261
262        Ok(())
263    }
264
265    #[gtest]
266    fn keep_min_floors_survivor_count() -> Result<()> {
267        let slots = vec![slot(0, 10), slot(1, 10)];
268        let model = reconstruct_model(10_000, &[], &[]);
269        let cfg = ScreeningConfig {
270            keep_pct: Some(1.0),
271            keep_min: 25,
272        };
273        let result = run_screening(&model, &slots, Some(&cfg));
274
275        verify_true!(result.survivors.len() >= 25)?;
276
277        Ok(())
278    }
279
280    #[gtest]
281    fn decode_permutation_is_mixed_radix() -> Result<()> {
282        let slots = vec![slot(0, 3), slot(1, 4)];
283        let mut picks = vec![(0u32, 0u32); 2];
284
285        decode_permutation(&slots, 0, &mut picks);
286        verify_eq!(picks, vec![(0, 0), (1, 0)])?;
287        decode_permutation(&slots, 11, &mut picks);
288        verify_eq!(picks, vec![(0, 2), (1, 3)])?;
289
290        Ok(())
291    }
292
293    #[gtest]
294    fn screening_ties_are_deterministic_and_prefer_lower_indices() -> Result<()> {
295        let slots = vec![slot(0, 10), slot(1, 10)];
296        let model = reconstruct_model(10_000, &[], &[]);
297        let cfg = ScreeningConfig {
298            keep_pct: Some(3.0),
299            keep_min: 0,
300        };
301
302        let result = run_screening(&model, &slots, Some(&cfg));
303
304        verify_eq!(result.survivors, vec![0, 1, 2])?;
305
306        Ok(())
307    }
308}
wowlab_sentinel/strategy/factorial/screening.rs

wowlab_sentinel/strategy/factorial/
screening.rs
