igs/games/
grundy_game.rs

1use std::{iter::FusedIterator, collections::HashMap};
2
3use crate::{game::{Game, DecomposableGame}, solver::{dedicated::DefSolver, Solver}};
4
5/// Grundy's game with associated initial position.
6/// 
7/// Rules of the game:
8/// The starting configuration is a single heap of objects, and the two players
9/// take turn splitting a single heap into two heaps of different sizes.
10/// See: <https://en.wikipedia.org/wiki/Grundy%27s_game>
11#[derive(Clone, Copy, PartialEq, Eq, Hash)]
12pub struct GrundyGame(pub u16);
13
14impl Game for GrundyGame {
15    type Position = u16;
16    type NimberSet = [u64; 4];
17
18    #[inline] fn moves_count(&self, position: &Self::Position) -> u16 {
19        (position+1) / 2
20    }
21
22    #[inline] fn initial_position(&self) -> Self::Position {
23        self.0.saturating_sub(2)
24    }
25}
26
27impl DecomposableGame for GrundyGame {
28    type DecomposablePosition = [u16; 2];
29
30    type Successors<'s> = GrundyGameMovesIterator where Self: 's;
31
32    type HeuristicallyOrderedSuccessors<'s> = GrundyGameMovesIterator where Self: 's;
33
34    type Components<'s> = GrundyGameComponentsIterator where Self: 's;
35
36    fn successors(&self, position: &Self::Position) -> Self::Successors<'_> {
37        Self::Successors::new(*position)
38    }
39
40    fn successors_in_heuristic_ordered(&self, position: &Self::Position) -> Self::HeuristicallyOrderedSuccessors<'_> {
41        Self::HeuristicallyOrderedSuccessors::new(*position)
42    }
43
44    fn decompose(&self, position: &Self::DecomposablePosition) -> Self::Components<'_> {
45        GrundyGameComponentsIterator(*position)
46    }
47
48    fn solver_with_stats<'s, STATS: 's+crate::solver::StatsCollector>(&'s self, stats: STATS) -> Box<dyn crate::solver::SolverForDecomposableGame<Game=Self, StatsCollector=STATS> + 's>
49    {
50        Box::new(DefSolver{solver: Solver::new(self, HashMap::new(), (), (), stats)})
51    }
52    
53}
54
55pub struct GrundyGameMovesIterator([u16; 2]);
56
57impl GrundyGameMovesIterator {
58    pub fn new(position: u16) -> Self {
59        Self([0, position])
60    }
61}
62
63impl Iterator for GrundyGameMovesIterator {
64    type Item = [u16; 2];
65
66    #[inline] fn next(&mut self) -> Option<Self::Item> {
67        (self.0[0] < self.0[1]).then(|| {
68            self.0[1] -= 1;
69            let mut result = self.0;
70            self.0[0] += 1;
71            if result[0] <= 1 { return [result[1], u16::MAX]; }
72            result[0] -= 1;
73            result
74        })
75    }
76
77    #[inline] fn size_hint(&self) -> (usize, Option<usize>) {
78        let len = self.len();
79        (len, Some(len))
80    }
81}
82
83impl ExactSizeIterator for GrundyGameMovesIterator {
84    #[inline] fn len(&self) -> usize {
85        ((self.0[1] + 1 - self.0[0]) / 2) as usize
86    }
87}
88
89impl FusedIterator for GrundyGameMovesIterator {}
90
91pub struct GrundyGameComponentsIterator([u16; 2]);
92
93impl Iterator for GrundyGameComponentsIterator {
94    type Item = u16;
95
96    fn next(&mut self) -> Option<Self::Item> {
97        (self.0[0] != u16::MAX).then(|| {
98            let result = self.0[0];
99            self.0[0] = self.0[1];
100            self.0[1] = u16::MAX;
101            result
102        })
103    }
104
105    #[inline] fn size_hint(&self) -> (usize, Option<usize>) {
106        let len = self.len();
107        (len, Some(len))
108    }
109}
110
111impl ExactSizeIterator for GrundyGameComponentsIterator {
112    #[inline] fn len(&self) -> usize {
113        (self.0[0] != u16::MAX) as usize + (self.0[1] != u16::MAX) as usize
114    }
115}
116
117impl FusedIterator for GrundyGameComponentsIterator {}
118
119#[cfg(test)]
120mod tests {
121    use super::*;
122
123    fn test_zero_game(g: GrundyGame) {
124        let inital_pos = g.initial_position();
125        assert_eq!(inital_pos, 0);
126        assert_eq!(g.moves_count(&inital_pos), 0);
127        assert_eq!(g.successors(&inital_pos).next(), None);
128    }
129
130    #[test]
131    fn grundy0() {
132        test_zero_game(GrundyGame(0));
133        test_zero_game(GrundyGame(1));
134        test_zero_game(GrundyGame(2));
135    }
136
137    #[test]
138    fn grundy3() {
139        let g = GrundyGame(3);
140        let inital_pos = g.initial_position();
141        assert_eq!(inital_pos, 1);
142        assert_eq!(g.moves_count(&inital_pos), 1);
143        let mut s = g.successors(&inital_pos);
144        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [0]);
145        assert_eq!(s.next(), None);
146    }
147
148    #[test]
149    fn grundy4() {
150        let g = GrundyGame(4);
151        let inital_pos = g.initial_position();
152        assert_eq!(inital_pos, 2);
153        assert_eq!(g.moves_count(&inital_pos), 1);
154        let mut s = g.successors(&inital_pos);
155        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [1]);
156        assert_eq!(s.next(), None);
157    }
158
159    #[test]
160    fn grundy5() {
161        let g = GrundyGame(5);
162        let inital_pos = g.initial_position();
163        assert_eq!(inital_pos, 3);
164        assert_eq!(g.moves_count(&inital_pos), 2);
165        let mut s = g.successors(&inital_pos);
166        assert_eq!(s.len(), 2);
167        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [2]);
168        assert_eq!(s.len(), 1);
169        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [1]);
170        assert_eq!(s.len(), 0);
171        assert_eq!(s.next(), None);
172    }
173
174    #[test]
175    fn grundy7() {
176        let g = GrundyGame(7);
177        let inital_pos = g.initial_position();
178        assert_eq!(inital_pos, 5);
179        assert_eq!(g.moves_count(&inital_pos), 3);
180        let mut s = g.successors(&inital_pos);
181        assert_eq!(s.len(), 3);
182        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [4]);
183        assert_eq!(s.len(), 2);
184        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [3]);
185        assert_eq!(s.len(), 1);
186        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [1, 2]);
187        assert_eq!(s.len(), 0);
188        assert_eq!(s.next(), None);
189    }
190
191    #[test]
192    fn grundy8() {
193        let g = GrundyGame(8);
194        let inital_pos = g.initial_position();
195        assert_eq!(inital_pos, 6);
196        assert_eq!(g.moves_count(&inital_pos), 3);
197        let mut s = g.successors(&inital_pos);
198        assert_eq!(s.len(), 3);
199        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [5]);
200        assert_eq!(s.len(), 2);
201        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [4]);
202        assert_eq!(s.len(), 1);
203        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [1, 3]);
204        assert_eq!(s.len(), 0);
205        assert_eq!(s.next(), None);
206    }
207
208    #[test]
209    fn grundy9() {
210        let g = GrundyGame(9);
211        let inital_pos = g.initial_position();
212        assert_eq!(inital_pos, 7);
213        assert_eq!(g.moves_count(&inital_pos), 4);
214        let mut s = g.successors(&inital_pos);
215        assert_eq!(s.len(), 4);
216        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [6]);
217        assert_eq!(s.len(), 3);
218        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [5]);
219        assert_eq!(s.len(), 2);
220        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [1, 4]);
221        assert_eq!(s.len(), 1);
222        assert_eq!(g.decompose(&s.next().unwrap()).collect::<Vec<_>>(), [2, 3]);
223        assert_eq!(s.len(), 0);
224        assert_eq!(s.next(), None);
225    }
226}
igs/games/grundy_game.rs

igs/games/
grundy_game.rs
