competitive/algorithm/
impartial_game.rs

1use std::{
2    collections::{HashMap, HashSet},
3    hash::Hash,
4    marker::PhantomData,
5};
6
7type Marker<T> = PhantomData<fn() -> T>;
8
9pub trait ImpartialGame {
10    type State;
11    type Iter: Iterator<Item = Self::State>;
12    fn next_state(&mut self, s: &Self::State) -> Self::Iter;
13}
14
15pub struct ImpartialGamer<S, F, I>
16where
17    F: FnMut(&S) -> I,
18    I: Iterator<Item = S>,
19{
20    f: F,
21    _marker: Marker<(S, I)>,
22}
23
24impl<S, F, I> ImpartialGamer<S, F, I>
25where
26    F: FnMut(&S) -> I,
27    I: Iterator<Item = S>,
28{
29    pub fn new(f: F) -> Self {
30        Self {
31            f,
32            _marker: PhantomData,
33        }
34    }
35}
36
37impl<S, F, I> ImpartialGame for ImpartialGamer<S, F, I>
38where
39    F: FnMut(&S) -> I,
40    I: Iterator<Item = S>,
41{
42    type State = S;
43    type Iter = I;
44    fn next_state(&mut self, s: &Self::State) -> Self::Iter {
45        (self.f)(s)
46    }
47}
48
49#[derive(Debug, Clone)]
50pub struct ImpartialGameAnalyzer<G>
51where
52    G: ImpartialGame<State: Eq + Hash>,
53{
54    game: G,
55    grundy: HashMap<G::State, u64>,
56}
57
58impl<G> ImpartialGameAnalyzer<G>
59where
60    G: ImpartialGame<State: Eq + Hash + Clone>,
61{
62    pub fn new(game: G) -> Self {
63        Self {
64            game,
65            grundy: Default::default(),
66        }
67    }
68    pub fn eval(&mut self, s: &G::State) -> u64 {
69        if let Some(g) = self.grundy.get(s).cloned() {
70            g
71        } else {
72            let next: HashSet<_> = self.game.next_state(s).map(|ns| self.eval(&ns)).collect();
73            let mut g = 0u64;
74            while next.contains(&g) {
75                g += 1;
76            }
77            self.grundy.insert(s.clone(), g);
78            g
79        }
80    }
81}
competitive/algorithm/impartial_game.rs

competitive/algorithm/
impartial_game.rs
