competitive/algorithm/
zero_sum_game.rs

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

competitive/algorithm/
zero_sum_game.rs
