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<State: Eq + Hash>,
49{
50    game: G,
51    scores: HashMap<G::State, i64>,
52}
53
54impl<G> ZeroSumGameAnalyzer<G>
55where
56    G: ZeroSumGame<State: Eq + Hash + Clone>,
57{
58    pub fn new(game: G) -> Self {
59        Self {
60            game,
61            scores: Default::default(),
62        }
63    }
64    pub fn eval(&mut self, s: &G::State) -> i64 {
65        if let Some(score) = self.scores.get(s).cloned() {
66            score
67        } else {
68            let score = self
69                .game
70                .next_state(s)
71                .map(|ns| ns.unwrap_or_else(|ns| -self.eval(&ns)))
72                .max()
73                .unwrap();
74            self.scores.insert(s.clone(), score);
75            score
76        }
77    }
78}
competitive/algorithm/zero_sum_game.rs

competitive/algorithm/
zero_sum_game.rs
