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,
53    G::State: Eq + Hash,
54{
55    game: G,
56    grundy: HashMap<G::State, u64>,
57}
58
59impl<G> ImpartialGameAnalyzer<G>
60where
61    G: ImpartialGame,
62    G::State: Eq + Hash + Clone,
63{
64    pub fn new(game: G) -> Self {
65        Self {
66            game,
67            grundy: Default::default(),
68        }
69    }
70    pub fn eval(&mut self, s: &G::State) -> u64 {
71        if let Some(g) = self.grundy.get(s).cloned() {
72            g
73        } else {
74            let next: HashSet<_> = self.game.next_state(s).map(|ns| self.eval(&ns)).collect();
75            let mut g = 0u64;
76            while next.contains(&g) {
77                g += 1;
78            }
79            self.grundy.insert(s.clone(), g);
80            g
81        }
82    }
83}
competitive/algorithm/impartial_game.rs

competitive/algorithm/
impartial_game.rs
