turing_machine_ai/
game.rs

1use std::{fmt::Debug, iter};
2
3use arrayvec::ArrayVec;
4
5use crate::{
6    code::Set,
7    verifier::{Intersection, Verifier, VerifierOption, get_verifier_by_number}, gametree::State,
8};
9
10/// The maximum amount of verifiers allowed in a game.
11const MAX_VERIFIERS: usize = 6;
12
13/// A game layout, consisting of the chosen verifiers.
14#[derive(Clone, Eq, PartialEq, Hash)]
15pub struct Game {
16    verifiers: Vec<Verifier>,
17}
18
19impl Debug for Game {
20    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
21        for (verifier, letter) in self.verifiers.iter().zip('A'..) {
22            writeln!(f, "Verifier {letter}")?;
23            writeln!(f, "{verifier:?}")?;
24        }
25        Ok(())
26    }
27}
28
29/// A particular assignment for a game. For example, this might indicate that
30/// for the first verifier, the second option is selected, for the second
31/// verifier the third option, etc.
32#[derive(Clone, Debug, Eq, PartialEq, Hash)]
33pub struct Assignment {
34    choice: ArrayVec<u8, MAX_VERIFIERS>,
35}
36
37impl Assignment {
38    /// Go through all chosen options, in the order of the verifiers.
39    pub fn choices(&self) -> impl Iterator<Item = u8> + '_ {
40        self.choice.iter().copied()
41    }
42
43    /// Create an assignment from the individual choices.
44    pub fn from_choices<T: Into<ArrayVec<u8, MAX_VERIFIERS>>>(choices: T) -> Self {
45        Assignment {
46            choice: choices.into(),
47        }
48    }
49}
50
51impl Game {
52    #[must_use]
53    pub fn starting_state(&self) -> State<'_> {
54        State::new(self)
55    }
56
57    // TODO: Index by custom type?
58    #[must_use]
59    pub fn verfier(&self, index: u8) -> &Verifier {
60        &self.verifiers[index as usize]
61    }
62
63    #[must_use]
64    pub fn verifier_count(&self) -> usize {
65        self.verifiers.len()
66    }
67
68    pub fn verifier_options_for_assignment<'a, 'b: 'a>(
69        &'a self,
70        assignment: &'b Assignment,
71    ) -> impl Iterator<Item = VerifierOption> + 'a {
72        self.verifiers
73            .iter()
74            .zip(assignment.choices())
75            .map(|(verifier, choice)| *verifier.option(choice))
76    }
77
78    #[must_use]
79    pub fn new_from_verifiers(verifiers: Vec<Verifier>) -> Game {
80        Game { verifiers }
81    }
82
83    #[must_use]
84    pub fn new_from_verifier_numbers(verifier_numbers: impl Iterator<Item = usize>) -> Game {
85        Game { verifiers: verifier_numbers.map(get_verifier_by_number).collect() }
86    }
87
88    /// Get all assignments, regardless of their validity.
89    pub fn all_assignments(&self) -> impl Iterator<Item = Assignment> + '_ {
90        let len = self.verifiers.len();
91        iter::successors(
92            Some(Assignment {
93                choice: iter::repeat(0).take(len).collect(),
94            }),
95            move |prev| {
96                let mut new = prev.clone();
97                new.choice[0] += 1;
98                for index in 0..len {
99                    // Carry to the right
100                    if usize::from(new.choice[index]) >= self.verifiers[index].number_of_options() {
101                        new.choice[index] = 0;
102                        if index + 1 >= len {
103                            return None;
104                        }
105                        new.choice[index + 1] += 1;
106                    }
107                }
108                Some(new)
109            },
110        )
111    }
112
113    /// Get all codes that adhere to a particular assignment.
114    #[must_use]
115    pub fn possible_codes_for_assignment(&self, assignment: &Assignment) -> Set {
116        self.verifiers
117            .iter()
118            .zip(assignment.choices())
119            .map(|(verifier, choice)| verifier.option(choice).code_set())
120            .intersect()
121    }
122
123    pub fn print_assigment(&self, assignment: &Assignment) {
124        for (verifier, assignment) in self.verifiers.iter().zip(assignment.choice.iter()) {
125            println!("{}", verifier.description());
126            println!("- {}", verifier.option(*assignment).description);
127        }
128    }
129
130    /// Check if the assignment is a possible puzzle solution. This means that
131    /// there should be a single code that adheres to the verifiers, and that
132    /// none of the verifiers are redundant.
133    #[must_use]
134    pub fn is_possible_solution(&self, assignment: &Assignment) -> bool {
135        if self.possible_codes_for_assignment(assignment).size() != 1 {
136            return false;
137        }
138
139        // Test for reduncancy
140        for excluded_verifier in 0..self.verifiers.len() {
141            let possible_codes = self
142                .verifier_options_for_assignment(assignment)
143                .enumerate()
144                .filter_map(|(index, verifier_and_choice)| {
145                    Some(verifier_and_choice).filter(|_| index != excluded_verifier)
146                })
147                .map(|verifier_option| verifier_option.code_set())
148                .intersect();
149            if possible_codes.size() <= 1 {
150                return false;
151            }
152        }
153        true
154    }
155
156    /// Get all possible solutions, i.e. those codes that correspond to a
157    /// verifier result that have exactly one solution.
158    #[must_use]
159    pub fn possible_solutions(&self) -> Set {
160        self.all_assignments()
161            .filter(|assignment| self.is_possible_solution(assignment))
162            .map(|assignment| self.possible_codes_for_assignment(&assignment))
163            .fold(Set::empty(), Set::union_with)
164    }
165}
turing_machine_ai/game.rs

turing_machine_ai/
game.rs
