mnk_games/
board.rs

1use std::error::Error;
2use std::ops::Not;
3use std::{fmt, iter};
4
5/// One of two players.
6#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
7pub enum Player {
8    /// The player who makes the first move.
9    X,
10    /// The player who makes the second move.
11    O,
12}
13
14impl fmt::Display for Player {
15    /// Writes `"X"` for [`Player::X`] and `"O"` for [`Player::O`].
16    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
17        match *self {
18            Self::X => write!(f, "X"),
19            Self::O => write!(f, "O"),
20        }
21    }
22}
23
24impl Not for Player {
25    type Output = Self;
26
27    fn not(self) -> Self::Output {
28        match self {
29            Self::X => Self::O,
30            Self::O => Self::X,
31        }
32    }
33}
34
35/// A space that can be played on by a [`Player`].
36#[derive(Clone, Copy, Debug, Default, Eq, Hash, PartialEq)]
37pub enum Space {
38    /// A space that has not been played on yet.
39    #[default]
40    Empty,
41    /// A space that has been taken by the indicated [`Player`].
42    Stone(Player),
43}
44
45impl fmt::Display for Space {
46    /// Writes a space character for [`Space::Empty`] and the player name for a [`Space::Stone`].
47    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
48        match *self {
49            Self::Empty => write!(f, " "),
50            Self::Stone(player) => write!(f, "{player}"),
51        }
52    }
53}
54
55impl From<Option<Player>> for Space {
56    /// Maps [`None`] and [`Some`] to [`Space::Empty`] and [`Space::Stone`], respectively.
57    fn from(player: Option<Player>) -> Self {
58        player.map_or(Self::Empty, Self::Stone)
59    }
60}
61
62impl From<Space> for Option<Player> {
63    /// Maps [`Space::Empty`] and [`Space::Stone`] to [`None`] and [`Some`],
64    /// respectively.
65    fn from(space: Space) -> Self {
66        match space {
67            Space::Empty => None,
68            Space::Stone(player) => Some(player),
69        }
70    }
71}
72
73/// An error which can occur when trying to place a stone.
74#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
75#[non_exhaustive]
76pub enum PlaceError {
77    /// An error which can occur when the location already contains a [`Space::Stone`].
78    Occupied {
79        /// The player who owns the blocking [`Space::Stone`].
80        player: Player,
81    },
82    /// An error which can occur when the intended location is not within the board's bounds.
83    OutOfBounds {
84        /// The intended (potentially out-of-bounds) row.
85        row: usize,
86        /// The intended (potentially out-of-bounds) column.
87        column: usize,
88    },
89}
90
91impl fmt::Display for PlaceError {
92    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
93        match self {
94            Self::Occupied { player } => {
95                write!(f, "already occupied by {player}")
96            }
97            Self::OutOfBounds { row, column } => {
98                write!(f, "out of bounds (row {row}, column {column})")
99            }
100        }
101    }
102}
103
104impl Error for PlaceError {}
105
106/// The board state of an [*m,n,k*-game].
107///
108/// An `MnkBoard<R, C, K>` struct has `R` rows and `C` columns of [`Space`]s and considers a winner
109/// to be a [`Player`] with `K` [`Space::Stone`]s in a row.
110///
111/// Methods for this struct are 0-indexed. Row indices at least `R` and column indices at least `C`
112/// are considered out of bounds.
113///
114/// This struct performs very little input validation. It is intended to be wrapped by other types
115/// that perform more thorough validation based on a particular game's rules, not used in
116/// user-facing code directly.
117///
118/// [*m,n,k*-game]: https://en.wikipedia.org/wiki/M,n,k-game
119#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
120pub struct MnkBoard<const R: usize, const C: usize, const K: usize> {
121    row_array: [[Space; C]; R],
122}
123
124impl<const R: usize, const C: usize, const K: usize> MnkBoard<R, C, K> {
125    /// Returns a board filled with [`Space::Empty`].
126    #[must_use]
127    pub const fn new() -> Self {
128        Self {
129            row_array: [[Space::Empty; C]; R],
130        }
131    }
132
133    /// Returns `true` if every [`Space`] on the board is a [`Space::Stone`] and `false` otherwise.
134    #[must_use]
135    pub fn full(&self) -> bool {
136        self.row_array
137            .iter()
138            .all(|row| row.iter().all(|space| space != &Space::Empty))
139    }
140
141    /// Attempts to place a stone on the board.
142    ///
143    /// If and only if the [`Space`] at the specified row and column is [`Space::Empty`], replaces
144    /// it with a [`Space::Stone`] corresponding to `player`.
145    ///
146    /// # Errors
147    ///
148    ///  - [`PlaceError::Occupied`] if the corresponding `Space` is already a `Space::Stone`.
149    ///  - [`PlaceError::OutOfBounds`] if either index is out of bounds.
150    pub fn place(&mut self, player: Player, row: usize, column: usize) -> Result<(), PlaceError> {
151        let location = self
152            .row_array
153            .get_mut(row)
154            .and_then(|row| row.get_mut(column));
155        location.map_or(
156            Err(PlaceError::OutOfBounds { row, column }),
157            |space| match space {
158                Space::Stone(player) => Err(PlaceError::Occupied { player: *player }),
159                Space::Empty => {
160                    *space = Space::Stone(player);
161                    Ok(())
162                }
163            },
164        )
165    }
166
167    /// Place a stone on the board without bounds or overlap checking.
168    ///
169    /// Places a new [`Space::Stone`] even if the [`Space`] is already one. [`MnkBoard::place`] is
170    /// a safe alternative.
171    ///
172    /// # Safety
173    ///
174    /// Both `row` and `column` must be in bounds.
175    pub unsafe fn place_unchecked(&mut self, player: Player, row: usize, column: usize) {
176        let location;
177        unsafe {
178            location = self
179                .row_array
180                .get_unchecked_mut(row)
181                .get_unchecked_mut(column);
182        }
183        *location = Space::Stone(player);
184    }
185
186    /// Returns the [`Space`] at the specified row and column.
187    ///
188    /// Returns [`None`] if either index is out of bounds.
189    #[must_use]
190    pub fn get(&self, row: usize, column: usize) -> Option<&Space> {
191        self.row_array.get(row).and_then(|row| row.get(column))
192    }
193
194    /// Returns the [`Space`] at the specified row and column, without checking bounds.
195    ///
196    /// [`MnkBoard::get`] is a safe alternative.
197    ///
198    /// # Safety
199    ///
200    /// Both `row` and `column` must be in bounds.
201    #[must_use]
202    pub unsafe fn get_unchecked(&self, row: usize, column: usize) -> &Space {
203        unsafe { self.row_array.get_unchecked(row).get_unchecked(column) }
204    }
205
206    /// Returns the winner of the game, or [`None`] if neither [`Player`] has won.
207    ///
208    /// It is possible, but ill-advised, for a board to have multiple winners. In such a case,
209    /// returns an arbitrary `Player` but not `None`.
210    #[must_use]
211    pub fn winner(&self) -> Option<Player> {
212        if C >= K {
213            let winner = Self::winner_in_runs(self.rows());
214            if winner.is_some() {
215                return winner;
216            }
217        }
218        if R >= K {
219            let winner = Self::winner_in_runs(self.columns());
220            if winner.is_some() {
221                return winner;
222            }
223        }
224        if R >= K && C >= K {
225            let mut winner = Self::winner_in_runs(self.top_right_diagonals());
226            if winner.is_some() {
227                return winner;
228            }
229            winner = Self::winner_in_runs(self.left_down_diagonals());
230            if winner.is_some() {
231                return winner;
232            }
233            winner = Self::winner_in_runs(self.top_left_diagonals());
234            if winner.is_some() {
235                return winner;
236            }
237            Self::winner_in_runs(self.right_down_diagonals())
238        } else {
239            None
240        }
241    }
242
243    /// Returns the first [`Player`] to be a winner in any of the passed runs.
244    #[must_use]
245    fn winner_in_runs<'a>(
246        runs: impl IntoIterator<Item = impl IntoIterator<Item = &'a Space>>,
247    ) -> Option<Player> {
248        let mut winners = runs.into_iter().map(Self::winner_in_run);
249        winners.find(Option::is_some).flatten()
250    }
251
252    /// Returns the first [`Player`] to have `K` consecutive [`Space`]s in the [`Iterator`].
253    #[must_use]
254    fn winner_in_run<'a>(run: impl IntoIterator<Item = &'a Space>) -> Option<Player> {
255        let mut consecutive = 0;
256        let mut previous = &Space::Empty;
257        for space in run {
258            match *space {
259                Space::Empty => {
260                    consecutive = 0;
261                }
262                Space::Stone(player) => {
263                    if space == previous {
264                        consecutive += 1;
265                    } else {
266                        consecutive = 1;
267                    }
268                    if consecutive == K {
269                        return Some(player);
270                    }
271                }
272            }
273            previous = space;
274        }
275        None
276    }
277
278    /// Converts (row, column) pairs to their corresponding [`Space`]s.
279    ///
280    /// # Panics
281    ///
282    /// If a coordinate pair is out of bounds.
283    fn coords_to_spaces(
284        &self,
285        coords: impl Iterator<Item = (usize, usize)>,
286    ) -> impl Iterator<Item = &'_ Space> {
287        coords.map(move |(r, c)| &self.row_array[r][c])
288    }
289
290    /// Returns an [`Iterator`] over the rows of the board.
291    fn rows(&self) -> impl Iterator<Item = impl Iterator<Item = &'_ Space>> {
292        self.row_array.iter().map(|row| row.iter())
293    }
294
295    /// Returns an [`Iterator`] over the columns of the board.
296    fn columns(&self) -> impl Iterator<Item = impl Iterator<Item = &'_ Space>> {
297        (0..C).map(move |c| self.row_array.iter().map(move |row| &row[c]))
298    }
299
300    /// Returns an [`Iterator`] over diagonals that start at the top and move right.
301    ///
302    /// Only iterates over diagonals of length at least `K`.
303    fn top_right_diagonals(&self) -> impl Iterator<Item = impl Iterator<Item = &'_ Space>> {
304        (0..=(C - K)).map(move |left_col| self.coords_to_spaces(iter::zip(0..R, left_col..C)))
305    }
306
307    /// Returns an [`Iterator`] over diagonals that start on the left and move down.
308    ///
309    /// Skips the highest such diagonal. Only iterates over diagonals of length at least `K`. (This
310    /// avoids overlap with [`MnkBoard::top_right_diagonals`].)
311    fn left_down_diagonals(&self) -> impl Iterator<Item = impl Iterator<Item = &'_ Space>> {
312        (1..=(R - K)).map(move |top_row| self.coords_to_spaces(iter::zip(top_row..R, 0..C)))
313    }
314
315    /// Returns an [`Iterator`] over the diagonals that start at the top and move left.
316    ///
317    /// Only iterates over diagonals of length at least `K`.
318    fn top_left_diagonals(&self) -> impl Iterator<Item = impl Iterator<Item = &'_ Space>> {
319        ((K - 1)..C)
320            .map(move |last_col| self.coords_to_spaces(iter::zip(0..R, (0..=last_col).rev())))
321    }
322
323    /// Returns an [`Iterator`] over the diagonals that start on the right and move down.
324    ///
325    /// Skips the highest such diagonal. Only iterates over diagonals of length at least `K`. (This
326    /// avoids overlap with [`MnkBoard::top_left_diagonals`].)
327    fn right_down_diagonals(&self) -> impl Iterator<Item = impl Iterator<Item = &'_ Space>> {
328        (1..=(R - K))
329            .map(move |last_row| self.coords_to_spaces(iter::zip(last_row..R, (0..C).rev())))
330    }
331}
332
333impl<const R: usize, const C: usize, const K: usize> Default for MnkBoard<R, C, K> {
334    /// Returns a board filled with [`Space::Empty`].
335    fn default() -> Self {
336        Self::new()
337    }
338}
339
340impl<const R: usize, const C: usize, const K: usize> From<[[Space; C]; R]> for MnkBoard<R, C, K> {
341    /// Converts a row-major array into an `MnkBoard`.
342    fn from(rows: [[Space; C]; R]) -> Self {
343        Self { row_array: rows }
344    }
345}
346
347impl<const R: usize, const C: usize, const K: usize> From<MnkBoard<R, C, K>> for [[Space; C]; R] {
348    /// Converts an `MnkBoard` into a row-major array.
349    fn from(game: MnkBoard<R, C, K>) -> Self {
350        game.row_array
351    }
352}
353
354impl<const R: usize, const C: usize, const K: usize> fmt::Display for MnkBoard<R, C, K> {
355    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
356        let border = "+-".repeat(C) + "+";
357        let vertical_sep = "\n".to_owned() + &border + "\n";
358        let middle_rows = self
359            .row_array
360            .map(|row| format!("|{}|", row.map(|square| square.to_string()).join("|")))
361            .join(&vertical_sep);
362        write!(f, "{border}\n{middle_rows}\n{border}")
363    }
364}
365
366#[cfg(test)]
367mod test_placers {
368    use super::*;
369
370    #[test]
371    fn place_success() {
372        let mut empty = MnkBoard::<2, 2, 2>::new();
373
374        let top_left = empty.place(Player::X, 0, 0);
375        assert_eq!(top_left, Ok(()));
376        assert_eq!(
377            empty.row_array,
378            [
379                [Space::Stone(Player::X), Space::Empty],
380                [Space::Empty, Space::Empty]
381            ]
382        );
383
384        let top_right = empty.place(Player::O, 0, 1);
385        assert_eq!(top_right, Ok(()));
386        assert_eq!(
387            empty.row_array,
388            [
389                [Space::Stone(Player::X), Space::Stone(Player::O)],
390                [Space::Empty, Space::Empty]
391            ]
392        );
393
394        let bottom_left = empty.place(Player::O, 1, 0);
395        assert_eq!(bottom_left, Ok(()));
396        assert_eq!(
397            empty.row_array,
398            [
399                [Space::Stone(Player::X), Space::Stone(Player::O)],
400                [Space::Stone(Player::O), Space::Empty]
401            ]
402        );
403
404        let bottom_right = empty.place(Player::X, 1, 1);
405        assert_eq!(bottom_right, Ok(()));
406        assert_eq!(
407            empty.row_array,
408            [
409                [Space::Stone(Player::X), Space::Stone(Player::O)],
410                [Space::Stone(Player::O), Space::Stone(Player::X)]
411            ]
412        );
413    }
414
415    #[test]
416    fn place_occupied() {
417        let mut full = MnkBoard::<2, 2, 2>::from([
418            [Space::Stone(Player::X), Space::Stone(Player::O)],
419            [Space::Stone(Player::O), Space::Stone(Player::X)],
420        ]);
421
422        let top_left_x = full.place(Player::X, 0, 0);
423        assert_eq!(top_left_x, Err(PlaceError::Occupied { player: Player::X }));
424        let top_left_o = full.place(Player::O, 0, 0);
425        assert_eq!(top_left_o, Err(PlaceError::Occupied { player: Player::X }));
426
427        let top_right_x = full.place(Player::X, 0, 1);
428        assert_eq!(top_right_x, Err(PlaceError::Occupied { player: Player::O }));
429        let top_right_o = full.place(Player::O, 0, 1);
430        assert_eq!(top_right_o, Err(PlaceError::Occupied { player: Player::O }));
431
432        let bottom_left_x = full.place(Player::X, 1, 0);
433        assert_eq!(
434            bottom_left_x,
435            Err(PlaceError::Occupied { player: Player::O })
436        );
437        let bottom_left_o = full.place(Player::O, 1, 0);
438        assert_eq!(
439            bottom_left_o,
440            Err(PlaceError::Occupied { player: Player::O })
441        );
442
443        let bottom_right_x = full.place(Player::X, 1, 1);
444        assert_eq!(
445            bottom_right_x,
446            Err(PlaceError::Occupied { player: Player::X })
447        );
448        let bottom_right_o = full.place(Player::O, 1, 1);
449        assert_eq!(
450            bottom_right_o,
451            Err(PlaceError::Occupied { player: Player::X })
452        );
453    }
454
455    #[test]
456    fn place_out_of_bounds() {
457        let mut empty = MnkBoard::<2, 2, 2>::new();
458
459        let high_row_x = empty.place(Player::X, 2, 0);
460        assert_eq!(
461            high_row_x,
462            Err(PlaceError::OutOfBounds { row: 2, column: 0 })
463        );
464        let high_row_o = empty.place(Player::O, 2, 0);
465        assert_eq!(
466            high_row_o,
467            Err(PlaceError::OutOfBounds { row: 2, column: 0 })
468        );
469
470        let high_column_x = empty.place(Player::X, 0, 2);
471        assert_eq!(
472            high_column_x,
473            Err(PlaceError::OutOfBounds { row: 0, column: 2 })
474        );
475        let high_column_o = empty.place(Player::O, 0, 2);
476        assert_eq!(
477            high_column_o,
478            Err(PlaceError::OutOfBounds { row: 0, column: 2 })
479        );
480    }
481
482    #[test]
483    fn place_unchecked_empty() {
484        let mut empty = MnkBoard::<2, 2, 2>::new();
485
486        unsafe {
487            empty.place_unchecked(Player::X, 0, 0);
488        }
489        assert_eq!(
490            empty.row_array,
491            [
492                [Space::Stone(Player::X), Space::Empty],
493                [Space::Empty, Space::Empty]
494            ]
495        );
496
497        unsafe {
498            empty.place_unchecked(Player::O, 0, 1);
499        }
500        assert_eq!(
501            empty.row_array,
502            [
503                [Space::Stone(Player::X), Space::Stone(Player::O)],
504                [Space::Empty, Space::Empty]
505            ]
506        );
507
508        unsafe {
509            empty.place_unchecked(Player::O, 1, 0);
510        }
511        assert_eq!(
512            empty.row_array,
513            [
514                [Space::Stone(Player::X), Space::Stone(Player::O)],
515                [Space::Stone(Player::O), Space::Empty]
516            ]
517        );
518
519        unsafe {
520            empty.place_unchecked(Player::X, 1, 1);
521        }
522        assert_eq!(
523            empty.row_array,
524            [
525                [Space::Stone(Player::X), Space::Stone(Player::O)],
526                [Space::Stone(Player::O), Space::Stone(Player::X)]
527            ]
528        );
529    }
530
531    #[test]
532    fn place_unchecked_occupied() {
533        let mut all_x = MnkBoard::<2, 2, 2>::from([
534            [Space::Stone(Player::X), Space::Stone(Player::X)],
535            [Space::Stone(Player::X), Space::Stone(Player::X)],
536        ]);
537
538        unsafe {
539            all_x.place_unchecked(Player::O, 0, 0);
540        }
541        assert_eq!(
542            all_x.row_array,
543            [
544                [Space::Stone(Player::O), Space::Stone(Player::X)],
545                [Space::Stone(Player::X), Space::Stone(Player::X)],
546            ]
547        );
548
549        unsafe {
550            all_x.place_unchecked(Player::O, 0, 1);
551        }
552        assert_eq!(
553            all_x.row_array,
554            [
555                [Space::Stone(Player::O), Space::Stone(Player::O)],
556                [Space::Stone(Player::X), Space::Stone(Player::X)],
557            ]
558        );
559
560        unsafe {
561            all_x.place_unchecked(Player::O, 1, 0);
562        }
563        assert_eq!(
564            all_x.row_array,
565            [
566                [Space::Stone(Player::O), Space::Stone(Player::O)],
567                [Space::Stone(Player::O), Space::Stone(Player::X)],
568            ]
569        );
570
571        unsafe {
572            all_x.place_unchecked(Player::O, 1, 1);
573        }
574        assert_eq!(
575            all_x.row_array,
576            [
577                [Space::Stone(Player::O), Space::Stone(Player::O)],
578                [Space::Stone(Player::O), Space::Stone(Player::O)],
579            ]
580        );
581    }
582}
583
584#[cfg(test)]
585mod test_getters {
586    use super::*;
587
588    fn square() -> MnkBoard<2, 2, 2> {
589        MnkBoard::<2, 2, 2>::from([
590            [Space::Stone(Player::X), Space::Empty],
591            [Space::Empty, Space::Stone(Player::O)],
592        ])
593    }
594
595    #[test]
596    fn get_in_bounds() {
597        let board = square();
598
599        assert_eq!(board.get(0, 0), Some(&Space::Stone(Player::X)));
600        assert_eq!(board.get(0, 1), Some(&Space::Empty));
601        assert_eq!(board.get(1, 0), Some(&Space::Empty));
602        assert_eq!(board.get(1, 1), Some(&Space::Stone(Player::O)));
603    }
604
605    #[test]
606    fn get_out_of_bounds() {
607        let board = square();
608
609        assert_eq!(board.get(2, 0), None);
610        assert_eq!(board.get(0, 2), None);
611    }
612
613    #[test]
614    fn get_unchecked() {
615        let board = square();
616
617        let top_left;
618        let top_right;
619        let bottom_left;
620        let bottom_right;
621        unsafe {
622            top_left = board.get_unchecked(0, 0);
623            top_right = board.get_unchecked(0, 1);
624            bottom_left = board.get_unchecked(1, 0);
625            bottom_right = board.get_unchecked(1, 1);
626        }
627        assert_eq!(top_left, &Space::Stone(Player::X));
628        assert_eq!(top_right, &Space::Empty);
629        assert_eq!(bottom_left, &Space::Empty);
630        assert_eq!(bottom_right, &Space::Stone(Player::O));
631    }
632}
633
634#[cfg(test)]
635mod test_winner {
636    use super::*;
637
638    #[test]
639    fn draws() {
640        let empty_0x0 = MnkBoard::<0, 0, 1>::new();
641        assert!(empty_0x0.winner().is_none());
642
643        let empty_3x3 = MnkBoard::<3, 3, 3>::new();
644        assert!(empty_3x3.winner().is_none());
645
646        let drawn_3x3 = MnkBoard::<3, 3, 3>::from([
647            [
648                Space::Stone(Player::X),
649                Space::Stone(Player::O),
650                Space::Stone(Player::X),
651            ],
652            [
653                Space::Stone(Player::X),
654                Space::Stone(Player::O),
655                Space::Stone(Player::O),
656            ],
657            [
658                Space::Stone(Player::O),
659                Space::Stone(Player::X),
660                Space::Stone(Player::X),
661            ],
662        ]);
663        assert!(drawn_3x3.winner().is_none());
664    }
665
666    #[test]
667    fn row_win() {
668        let row_win = MnkBoard::<3, 3, 3>::from([
669            [
670                Space::Stone(Player::X),
671                Space::Stone(Player::X),
672                Space::Stone(Player::X),
673            ],
674            [Space::Empty, Space::Empty, Space::Empty],
675            [Space::Empty, Space::Empty, Space::Empty],
676        ]);
677        assert_eq!(row_win.winner(), Some(Player::X));
678    }
679
680    #[test]
681    fn column_win() {
682        let column_win = MnkBoard::<3, 3, 3>::from([
683            [Space::Stone(Player::X), Space::Empty, Space::Empty],
684            [Space::Stone(Player::X), Space::Empty, Space::Empty],
685            [Space::Stone(Player::X), Space::Empty, Space::Empty],
686        ]);
687        assert_eq!(column_win.winner(), Some(Player::X));
688    }
689
690    #[test]
691    fn top_right_win() {
692        let top_right_win = MnkBoard::<3, 3, 2>::from([
693            [Space::Stone(Player::X), Space::Empty, Space::Empty],
694            [Space::Empty, Space::Stone(Player::X), Space::Empty],
695            [Space::Empty, Space::Empty, Space::Empty],
696        ]);
697        assert_eq!(top_right_win.winner(), Some(Player::X));
698    }
699
700    #[test]
701    fn left_down_win() {
702        let left_down_win = MnkBoard::<4, 3, 3>::from([
703            [Space::Empty, Space::Empty, Space::Empty],
704            [Space::Stone(Player::X), Space::Empty, Space::Empty],
705            [Space::Empty, Space::Stone(Player::X), Space::Empty],
706            [Space::Empty, Space::Empty, Space::Stone(Player::X)],
707        ]);
708        assert_eq!(left_down_win.winner(), Some(Player::X));
709    }
710
711    #[test]
712    fn top_left_win() {
713        let top_left_win = MnkBoard::<3, 3, 2>::from([
714            [Space::Empty, Space::Empty, Space::Stone(Player::X)],
715            [Space::Empty, Space::Stone(Player::X), Space::Empty],
716            [Space::Empty, Space::Empty, Space::Empty],
717        ]);
718        assert_eq!(top_left_win.winner(), Some(Player::X));
719    }
720
721    #[test]
722    fn right_down_win() {
723        let right_down_win = MnkBoard::<4, 3, 3>::from([
724            [Space::Empty, Space::Empty, Space::Empty],
725            [Space::Empty, Space::Empty, Space::Stone(Player::X)],
726            [Space::Empty, Space::Stone(Player::X), Space::Empty],
727            [Space::Stone(Player::X), Space::Empty, Space::Empty],
728        ]);
729        assert_eq!(right_down_win.winner(), Some(Player::X));
730    }
731}
732
733#[cfg(test)]
734mod test_winner_in_runs {
735    use super::*;
736
737    #[test]
738    fn trivial() {
739        let empty: iter::Empty<iter::Empty<&Space>> = iter::empty();
740        assert!(MnkBoard::<0, 0, 1>::winner_in_runs(empty).is_none());
741
742        let single = iter::once(iter::once(&Space::Stone(Player::X)));
743        assert_eq!(MnkBoard::<0, 0, 1>::winner_in_runs(single), Some(Player::X));
744    }
745
746    #[test]
747    fn several_runs() {
748        let delayed = [
749            iter::once(&Space::Empty),
750            iter::once(&Space::Stone(Player::X)),
751        ];
752        assert_eq!(
753            MnkBoard::<0, 0, 1>::winner_in_runs(delayed),
754            Some(Player::X)
755        );
756
757        let all_empty = [
758            iter::once(&Space::Empty),
759            iter::once(&Space::Empty),
760            iter::once(&Space::Empty),
761        ];
762        assert!(MnkBoard::<0, 0, 1>::winner_in_runs(all_empty).is_none());
763    }
764}
765
766#[cfg(test)]
767mod test_winner_in_run {
768    use super::*;
769
770    #[test]
771    fn trivial() {
772        let empty: [&Space; 0] = [];
773        assert!(MnkBoard::<0, 0, 1>::winner_in_run(empty).is_none());
774        assert!(MnkBoard::<0, 0, 2>::winner_in_run(empty).is_none());
775        assert!(MnkBoard::<0, 0, 3>::winner_in_run(empty).is_none());
776
777        let one_empty = [&Space::Empty];
778        assert!(MnkBoard::<0, 0, 1>::winner_in_run(one_empty).is_none());
779        assert!(MnkBoard::<0, 0, 2>::winner_in_run(one_empty).is_none());
780
781        let one_x = [&Space::Stone(Player::X)];
782        assert_eq!(MnkBoard::<1, 1, 1>::winner_in_run(one_x), Some(Player::X));
783        assert!(MnkBoard::<1, 1, 2>::winner_in_run(one_x).is_none());
784
785        let one_o = [&Space::Stone(Player::O)];
786        assert_eq!(MnkBoard::<1, 1, 1>::winner_in_run(one_o), Some(Player::O));
787        assert!(MnkBoard::<1, 1, 2>::winner_in_run(one_o).is_none());
788    }
789
790    #[test]
791    fn single_player() {
792        let right_run = [
793            &Space::Empty,
794            &Space::Empty,
795            &Space::Stone(Player::X),
796            &Space::Stone(Player::X),
797            &Space::Stone(Player::X),
798        ];
799        assert_eq!(
800            MnkBoard::<0, 0, 3>::winner_in_run(right_run),
801            Some(Player::X)
802        );
803        assert!(MnkBoard::<0, 0, 4>::winner_in_run(right_run).is_none());
804
805        let interrupted = [
806            &Space::Stone(Player::X),
807            &Space::Stone(Player::X),
808            &Space::Empty,
809            &Space::Stone(Player::X),
810            &Space::Stone(Player::X),
811        ];
812        assert_eq!(
813            MnkBoard::<0, 0, 2>::winner_in_run(interrupted),
814            Some(Player::X)
815        );
816        assert!(MnkBoard::<0, 0, 3>::winner_in_run(interrupted).is_none());
817
818        let bookend = [
819            &Space::Empty,
820            &Space::Stone(Player::X),
821            &Space::Stone(Player::X),
822            &Space::Stone(Player::X),
823            &Space::Empty,
824        ];
825        assert_eq!(MnkBoard::<0, 0, 3>::winner_in_run(bookend), Some(Player::X));
826        assert!(MnkBoard::<0, 0, 4>::winner_in_run(bookend).is_none());
827    }
828
829    #[test]
830    fn two_player() {
831        let left_heavy = [
832            &Space::Stone(Player::X),
833            &Space::Stone(Player::X),
834            &Space::Stone(Player::O),
835        ];
836        assert_eq!(
837            MnkBoard::<0, 0, 2>::winner_in_run(left_heavy),
838            Some(Player::X)
839        );
840        assert!(MnkBoard::<0, 0, 3>::winner_in_run(left_heavy).is_none());
841
842        let right_heavy = [
843            &Space::Stone(Player::O),
844            &Space::Stone(Player::X),
845            &Space::Stone(Player::X),
846        ];
847        assert_eq!(
848            MnkBoard::<0, 0, 2>::winner_in_run(right_heavy),
849            Some(Player::X)
850        );
851        assert!(MnkBoard::<0, 0, 3>::winner_in_run(right_heavy).is_none());
852
853        let interrupted = [
854            &Space::Stone(Player::X),
855            &Space::Stone(Player::O),
856            &Space::Stone(Player::X),
857        ];
858        assert!(MnkBoard::<0, 0, 2>::winner_in_run(interrupted).is_none());
859        assert!(MnkBoard::<0, 0, 3>::winner_in_run(interrupted).is_none());
860    }
861}
862
863#[cfg(test)]
864mod test_square_board {
865    // These tests use `Vec::contains` for durability against changes in iteration order.
866    use super::*;
867
868    fn square_board() -> MnkBoard<5, 5, 3> {
869        MnkBoard::from([
870            [
871                Space::Empty,
872                Space::Stone(Player::X),
873                Space::Stone(Player::O),
874                Space::Empty,
875                Space::Stone(Player::X),
876            ],
877            [
878                Space::Stone(Player::X),
879                Space::Stone(Player::O),
880                Space::Empty,
881                Space::Stone(Player::X),
882                Space::Stone(Player::O),
883            ],
884            [
885                Space::Stone(Player::O),
886                Space::Empty,
887                Space::Stone(Player::X),
888                Space::Stone(Player::O),
889                Space::Empty,
890            ],
891            [
892                Space::Stone(Player::O),
893                Space::Stone(Player::X),
894                Space::Empty,
895                Space::Stone(Player::O),
896                Space::Stone(Player::X),
897            ],
898            [
899                Space::Stone(Player::X),
900                Space::Stone(Player::O),
901                Space::Empty,
902                Space::Stone(Player::O),
903                Space::Stone(Player::X),
904            ],
905        ])
906    }
907
908    #[test]
909    fn rows() {
910        let board = square_board();
911        let rows: Vec<Vec<&Space>> = board.rows().map(Iterator::collect).collect();
912        assert_eq!(rows.len(), 5);
913
914        let top_row = vec![
915            &Space::Empty,
916            &Space::Stone(Player::X),
917            &Space::Stone(Player::O),
918            &Space::Empty,
919            &Space::Stone(Player::X),
920        ];
921        assert!(rows.contains(&top_row));
922
923        let second_row = vec![
924            &Space::Stone(Player::X),
925            &Space::Stone(Player::O),
926            &Space::Empty,
927            &Space::Stone(Player::X),
928            &Space::Stone(Player::O),
929        ];
930        assert!(rows.contains(&second_row));
931
932        let third_row = vec![
933            &Space::Stone(Player::O),
934            &Space::Empty,
935            &Space::Stone(Player::X),
936            &Space::Stone(Player::O),
937            &Space::Empty,
938        ];
939        assert!(rows.contains(&third_row));
940
941        let fourth_row = vec![
942            &Space::Stone(Player::O),
943            &Space::Stone(Player::X),
944            &Space::Empty,
945            &Space::Stone(Player::O),
946            &Space::Stone(Player::X),
947        ];
948        assert!(rows.contains(&fourth_row));
949
950        let fifth_row = vec![
951            &Space::Stone(Player::X),
952            &Space::Stone(Player::O),
953            &Space::Empty,
954            &Space::Stone(Player::O),
955            &Space::Stone(Player::X),
956        ];
957        assert!(rows.contains(&fifth_row));
958    }
959
960    #[test]
961    fn columns() {
962        let board = square_board();
963        let columns: Vec<Vec<&Space>> = board.columns().map(Iterator::collect).collect();
964        assert_eq!(columns.len(), 5);
965
966        let first_col = vec![
967            &Space::Empty,
968            &Space::Stone(Player::X),
969            &Space::Stone(Player::O),
970            &Space::Stone(Player::O),
971            &Space::Stone(Player::X),
972        ];
973        assert!(columns.contains(&first_col));
974
975        let second_col = vec![
976            &Space::Stone(Player::X),
977            &Space::Stone(Player::O),
978            &Space::Empty,
979            &Space::Stone(Player::X),
980            &Space::Stone(Player::O),
981        ];
982        assert!(columns.contains(&second_col));
983
984        let third_col = vec![
985            &Space::Stone(Player::O),
986            &Space::Empty,
987            &Space::Stone(Player::X),
988            &Space::Empty,
989            &Space::Empty,
990        ];
991        assert!(columns.contains(&third_col));
992
993        let fourth_col = vec![
994            &Space::Empty,
995            &Space::Stone(Player::X),
996            &Space::Stone(Player::O),
997            &Space::Stone(Player::O),
998            &Space::Stone(Player::O),
999        ];
1000        assert!(columns.contains(&fourth_col));
1001
1002        let fifth_col = vec![
1003            &Space::Stone(Player::X),
1004            &Space::Stone(Player::O),
1005            &Space::Empty,
1006            &Space::Stone(Player::X),
1007            &Space::Stone(Player::X),
1008        ];
1009        assert!(columns.contains(&fifth_col));
1010    }
1011
1012    #[test]
1013    fn top_right() {
1014        let board = square_board();
1015        let diags: Vec<Vec<&Space>> = board.top_right_diagonals().map(Iterator::collect).collect();
1016        assert_eq!(diags.len(), 3);
1017
1018        let first_diag = vec![
1019            &Space::Empty,
1020            &Space::Stone(Player::O),
1021            &Space::Stone(Player::X),
1022            &Space::Stone(Player::O),
1023            &Space::Stone(Player::X),
1024        ];
1025        assert!(diags.contains(&first_diag));
1026
1027        let second_diag = vec![
1028            &Space::Stone(Player::X),
1029            &Space::Empty,
1030            &Space::Stone(Player::O),
1031            &Space::Stone(Player::X),
1032        ];
1033        assert!(diags.contains(&second_diag));
1034
1035        let third_diag = vec![
1036            &Space::Stone(Player::O),
1037            &Space::Stone(Player::X),
1038            &Space::Empty,
1039        ];
1040        assert!(diags.contains(&third_diag));
1041    }
1042
1043    #[test]
1044    fn left_down() {
1045        let board = square_board();
1046        let diags: Vec<Vec<&Space>> = board.left_down_diagonals().map(Iterator::collect).collect();
1047        assert_eq!(diags.len(), 2);
1048
1049        let first_diag = vec![
1050            &Space::Stone(Player::X),
1051            &Space::Empty,
1052            &Space::Empty,
1053            &Space::Stone(Player::O),
1054        ];
1055        assert!(diags.contains(&first_diag));
1056
1057        let second_diag = vec![
1058            &Space::Stone(Player::O),
1059            &Space::Stone(Player::X),
1060            &Space::Empty,
1061        ];
1062        assert!(diags.contains(&second_diag));
1063    }
1064
1065    #[test]
1066    fn top_left() {
1067        let board = square_board();
1068        let diags: Vec<Vec<&Space>> = board.top_left_diagonals().map(Iterator::collect).collect();
1069        assert_eq!(diags.len(), 3);
1070
1071        let first_diag = vec![
1072            &Space::Stone(Player::O),
1073            &Space::Stone(Player::O),
1074            &Space::Stone(Player::O),
1075        ];
1076        assert!(diags.contains(&first_diag));
1077        let second_diag = vec![
1078            &Space::Empty,
1079            &Space::Empty,
1080            &Space::Empty,
1081            &Space::Stone(Player::O),
1082        ];
1083        assert!(diags.contains(&second_diag));
1084
1085        let third_diag = vec![
1086            &Space::Stone(Player::X),
1087            &Space::Stone(Player::X),
1088            &Space::Stone(Player::X),
1089            &Space::Stone(Player::X),
1090            &Space::Stone(Player::X),
1091        ];
1092        assert!(diags.contains(&third_diag));
1093    }
1094
1095    #[test]
1096    fn right_down() {
1097        let board = square_board();
1098        let diags: Vec<Vec<&Space>> = board
1099            .right_down_diagonals()
1100            .map(Iterator::collect)
1101            .collect();
1102        assert_eq!(diags.len(), 2);
1103
1104        let first_diag = vec![
1105            &Space::Stone(Player::O),
1106            &Space::Stone(Player::O),
1107            &Space::Empty,
1108            &Space::Stone(Player::O),
1109        ];
1110        assert!(diags.contains(&first_diag));
1111
1112        let second_diag = vec![&Space::Empty, &Space::Stone(Player::O), &Space::Empty];
1113        assert!(diags.contains(&second_diag));
1114    }
1115}
1116
1117#[cfg(test)]
1118mod test_rectangular_boards {
1119    use super::*;
1120
1121    fn tall_board() -> MnkBoard<5, 4, 3> {
1122        MnkBoard::from([
1123            [
1124                Space::Empty,
1125                Space::Stone(Player::X),
1126                Space::Stone(Player::O),
1127                Space::Empty,
1128            ],
1129            [
1130                Space::Stone(Player::X),
1131                Space::Stone(Player::O),
1132                Space::Empty,
1133                Space::Stone(Player::X),
1134            ],
1135            [
1136                Space::Stone(Player::O),
1137                Space::Empty,
1138                Space::Stone(Player::X),
1139                Space::Stone(Player::O),
1140            ],
1141            [
1142                Space::Stone(Player::O),
1143                Space::Stone(Player::X),
1144                Space::Empty,
1145                Space::Stone(Player::O),
1146            ],
1147            [
1148                Space::Stone(Player::X),
1149                Space::Stone(Player::O),
1150                Space::Empty,
1151                Space::Stone(Player::O),
1152            ],
1153        ])
1154    }
1155
1156    fn wide_board() -> MnkBoard<4, 5, 3> {
1157        MnkBoard::from([
1158            [
1159                Space::Empty,
1160                Space::Stone(Player::X),
1161                Space::Stone(Player::O),
1162                Space::Empty,
1163                Space::Stone(Player::X),
1164            ],
1165            [
1166                Space::Stone(Player::X),
1167                Space::Stone(Player::O),
1168                Space::Empty,
1169                Space::Stone(Player::X),
1170                Space::Stone(Player::O),
1171            ],
1172            [
1173                Space::Stone(Player::O),
1174                Space::Empty,
1175                Space::Stone(Player::X),
1176                Space::Stone(Player::O),
1177                Space::Empty,
1178            ],
1179            [
1180                Space::Stone(Player::O),
1181                Space::Stone(Player::X),
1182                Space::Empty,
1183                Space::Stone(Player::O),
1184                Space::Stone(Player::X),
1185            ],
1186        ])
1187    }
1188
1189    #[test]
1190    fn tall_top_right_diags() {
1191        let board = tall_board();
1192        let diags: Vec<Vec<&Space>> = board.top_right_diagonals().map(Iterator::collect).collect();
1193        assert_eq!(diags.len(), 2);
1194
1195        let first_diag = vec![
1196            &Space::Empty,
1197            &Space::Stone(Player::O),
1198            &Space::Stone(Player::X),
1199            &Space::Stone(Player::O),
1200        ];
1201        assert!(diags.contains(&first_diag));
1202
1203        let second_diag = vec![
1204            &Space::Stone(Player::X),
1205            &Space::Empty,
1206            &Space::Stone(Player::O),
1207        ];
1208        assert!(diags.contains(&second_diag));
1209    }
1210
1211    #[test]
1212    fn tall_left_down_diags() {
1213        let board = tall_board();
1214        let diags: Vec<Vec<&Space>> = board.left_down_diagonals().map(Iterator::collect).collect();
1215        assert_eq!(diags.len(), 2);
1216
1217        let first_diag = vec![
1218            &Space::Stone(Player::X),
1219            &Space::Empty,
1220            &Space::Empty,
1221            &Space::Stone(Player::O),
1222        ];
1223        assert!(diags.contains(&first_diag));
1224
1225        let second_diag = vec![
1226            &Space::Stone(Player::O),
1227            &Space::Stone(Player::X),
1228            &Space::Empty,
1229        ];
1230        assert!(diags.contains(&second_diag));
1231    }
1232
1233    #[test]
1234    fn tall_top_left_diags() {
1235        let board = tall_board();
1236        let diags: Vec<Vec<&Space>> = board.top_left_diagonals().map(Iterator::collect).collect();
1237        assert_eq!(diags.len(), 2);
1238
1239        let first_diag = vec![
1240            &Space::Empty,
1241            &Space::Empty,
1242            &Space::Empty,
1243            &Space::Stone(Player::O),
1244        ];
1245        assert!(diags.contains(&first_diag));
1246
1247        let second_diag = vec![
1248            &Space::Stone(Player::O),
1249            &Space::Stone(Player::O),
1250            &Space::Stone(Player::O),
1251        ];
1252        assert!(diags.contains(&second_diag));
1253    }
1254
1255    #[test]
1256    fn tall_right_down_diags() {
1257        let board = tall_board();
1258        let diags: Vec<Vec<&Space>> = board
1259            .right_down_diagonals()
1260            .map(Iterator::collect)
1261            .collect();
1262        assert_eq!(diags.len(), 2);
1263
1264        let first_diag = vec![
1265            &Space::Stone(Player::X),
1266            &Space::Stone(Player::X),
1267            &Space::Stone(Player::X),
1268            &Space::Stone(Player::X),
1269        ];
1270        assert!(diags.contains(&first_diag));
1271
1272        let second_diag = vec![
1273            &Space::Stone(Player::O),
1274            &Space::Empty,
1275            &Space::Stone(Player::O),
1276        ];
1277        assert!(diags.contains(&second_diag));
1278    }
1279
1280    #[test]
1281    fn wide_top_right_diags() {
1282        let board = wide_board();
1283        let diags: Vec<Vec<&Space>> = board.top_right_diagonals().map(Iterator::collect).collect();
1284        assert_eq!(diags.len(), 3);
1285
1286        let first_diag = vec![
1287            &Space::Empty,
1288            &Space::Stone(Player::O),
1289            &Space::Stone(Player::X),
1290            &Space::Stone(Player::O),
1291        ];
1292        assert!(diags.contains(&first_diag));
1293
1294        let second_diag = vec![
1295            &Space::Stone(Player::X),
1296            &Space::Empty,
1297            &Space::Stone(Player::O),
1298            &Space::Stone(Player::X),
1299        ];
1300        assert!(diags.contains(&second_diag));
1301
1302        let third_diag = vec![
1303            &Space::Stone(Player::O),
1304            &Space::Stone(Player::X),
1305            &Space::Empty,
1306        ];
1307        assert!(diags.contains(&third_diag));
1308    }
1309
1310    #[test]
1311    fn wide_left_down_diags() {
1312        let board = wide_board();
1313        let diags: Vec<Vec<&Space>> = board.left_down_diagonals().map(Iterator::collect).collect();
1314        let diag = vec![&Space::Stone(Player::X), &Space::Empty, &Space::Empty];
1315        assert_eq!(diags, [diag]);
1316    }
1317
1318    #[test]
1319    fn wide_top_left_diags() {
1320        let board = wide_board();
1321        let diags: Vec<Vec<&Space>> = board.top_left_diagonals().map(Iterator::collect).collect();
1322        assert_eq!(diags.len(), 3);
1323
1324        let first_diag = vec![
1325            &Space::Stone(Player::X),
1326            &Space::Stone(Player::X),
1327            &Space::Stone(Player::X),
1328            &Space::Stone(Player::X),
1329        ];
1330        assert!(diags.contains(&first_diag));
1331
1332        let second_diag = vec![
1333            &Space::Empty,
1334            &Space::Empty,
1335            &Space::Empty,
1336            &Space::Stone(Player::O),
1337        ];
1338        assert!(diags.contains(&second_diag));
1339
1340        let third_diag = vec![
1341            &Space::Stone(Player::O),
1342            &Space::Stone(Player::O),
1343            &Space::Stone(Player::O),
1344        ];
1345        assert!(diags.contains(&third_diag));
1346    }
1347
1348    #[test]
1349    fn wide_right_up_diags() {
1350        let board = wide_board();
1351        let diags: Vec<Vec<&Space>> = board
1352            .right_down_diagonals()
1353            .map(Iterator::collect)
1354            .collect();
1355        let diag = vec![
1356            &Space::Stone(Player::O),
1357            &Space::Stone(Player::O),
1358            &Space::Empty,
1359        ];
1360        assert_eq!(diags, [diag]);
1361    }
1362}
1363
1364#[cfg(test)]
1365mod test_mnk_board_display {
1366    use super::*;
1367
1368    #[test]
1369    fn squares() {
1370        let one = MnkBoard::<1, 1, 1>::from([[Space::Stone(Player::X)]]);
1371        assert_eq!(
1372            one.to_string(),
1373            "+-+\n\
1374             |X|\n\
1375             +-+"
1376        );
1377
1378        let two = MnkBoard::<2, 2, 2>::from([
1379            [Space::Stone(Player::X), Space::Empty],
1380            [Space::Empty, Space::Stone(Player::O)],
1381        ]);
1382        assert_eq!(
1383            two.to_string(),
1384            "+-+-+\n\
1385             |X| |\n\
1386             +-+-+\n\
1387             | |O|\n\
1388             +-+-+"
1389        );
1390
1391        let three = MnkBoard::<3, 3, 3>::from([
1392            [
1393                Space::Stone(Player::X),
1394                Space::Empty,
1395                Space::Stone(Player::O),
1396            ],
1397            [
1398                Space::Stone(Player::O),
1399                Space::Stone(Player::X),
1400                Space::Empty,
1401            ],
1402            [
1403                Space::Stone(Player::X),
1404                Space::Stone(Player::O),
1405                Space::Empty,
1406            ],
1407        ]);
1408        assert_eq!(
1409            three.to_string(),
1410            "+-+-+-+\n\
1411             |X| |O|\n\
1412             +-+-+-+\n\
1413             |O|X| |\n\
1414             +-+-+-+\n\
1415             |X|O| |\n\
1416             +-+-+-+"
1417        );
1418    }
1419
1420    #[test]
1421    fn rectangles() {
1422        let tall = MnkBoard::<3, 2, 2>::from([
1423            [Space::Stone(Player::X), Space::Empty],
1424            [Space::Empty, Space::Stone(Player::O)],
1425            [Space::Stone(Player::X), Space::Stone(Player::O)],
1426        ]);
1427        assert_eq!(
1428            tall.to_string(),
1429            "+-+-+\n\
1430             |X| |\n\
1431             +-+-+\n\
1432             | |O|\n\
1433             +-+-+\n\
1434             |X|O|\n\
1435             +-+-+"
1436        );
1437
1438        let wide = MnkBoard::<2, 3, 2>::from([
1439            [
1440                Space::Stone(Player::X),
1441                Space::Empty,
1442                Space::Stone(Player::X),
1443            ],
1444            [
1445                Space::Empty,
1446                Space::Stone(Player::O),
1447                Space::Stone(Player::O),
1448            ],
1449        ]);
1450        assert_eq!(
1451            wide.to_string(),
1452            "+-+-+-+\n\
1453             |X| |X|\n\
1454             +-+-+-+\n\
1455             | |O|O|\n\
1456             +-+-+-+"
1457        );
1458    }
1459}
mnk_games/board.rs

mnk_games/
board.rs
