Function game_mex 

pub fn game_mex(values: Vec<u64>) -> u64

Examples found in repository

crates/competitive/src/algorithm/game_analyzer/impartial.rs (line 291)

    fn grundy(&mut self, state: &S) -> u64 {
        memoized_game(
            state,
            &mut self.grundy,
            &mut HashSet::new(),
            &mut |s| {
                if self.outcomes[0].get(s) == Some(&false) {
                    return ControlFlow::Break(0);
                }
                let moves = (self.moves)(s).into_iter().map(|n| (n.to, ()));
                ControlFlow::Continue((moves, Vec::new()))
            },
            &mut |_, moves| moves.next(),
            &mut |values, (), value| {
                values.push(value);
                ControlFlow::Continue(())
            },
            &mut |_, values| game_mex(values),
        )
    }

crates/competitive/src/algorithm/game_analyzer/graph.rs (line 395)

    pub fn best_move(&mut self, state: &[S]) -> Option<Neighbor<Vec<S>, (usize, L)>> {
        if state.is_empty() {
            return None;
        }
        if let [single] = state {
            let mut query: GameAnalysis<'_, _, S, GameOutcome, MISERE> =
                GameAnalysis::new(self.game, |g: &mut ImpartialGraph<'_, G>, s| {
                    g.outcome(s, MISERE)
                });
            return query
                .best_move(single)
                .map(|next| Neighbor::new(vec![next.to], (0, next.label)));
        }
        let outcome = self.eval(state);
        if outcome == GameOutcome::Lose {
            return None;
        }
        let mut indices = self.game.sum_indices(state);
        let game = &self.game;
        if MISERE {
            let key = GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
            let winner = game.sums.outcomes.winning[game.sums.indices[&key]];
            for (i, &component) in state.iter().enumerate() {
                let original = indices[i];
                for next in game.graph.neighbors(component) {
                    indices[i] = game.index_of(next.to);
                    let key =
                        GraphSums::canonical(indices.clone(), &game.index.as_ref().unwrap().edges);
                    let id = game.sums.indices[&key];
                    if Some(id) == winner
                        || outcome == GameOutcome::Draw
                            && game.sums.outcomes.values[id] == GameOutcome::Draw
                    {
                        let mut to = state.to_vec();
                        to[i] = next.to;
                        return Some(Neighbor::new(to, (i, next.label)));
                    }
                }
                indices[i] = original;
            }
            return None;
        }
        let mut xor = 0;
        let mut infinite = None;
        let mut multiple = false;
        for (i, &v) in indices.iter().enumerate() {
            if let Some((value, _)) = game.generalized_grundy[v] {
                xor ^= value;
            } else if infinite.replace(i).is_some() {
                multiple = true;
                break;
            }
        }
        if outcome == GameOutcome::Draw {
            let i = infinite.unwrap();
            let v = indices[i];
            let edges = &game.index.as_ref().unwrap().edges;
            let target = (!multiple).then(|| {
                let values = edges[v]
                    .iter()
                    .filter_map(|&u| game.generalized_grundy[u].map(|(g, _)| g))
                    .collect();
                game_mex(values)
            });
            // Preserve two infinite components, or keep the finite XOR outside
            // the remaining infinite component's finite follower values.
            if target.is_none_or(|g| g == xor) {
                let to = edges[v]
                    .iter()
                    .copied()
                    .find(|&u| {
                        game.generalized_grundy[u].is_none()
                            && target.is_none_or(|g| {
                                !edges[u].iter().any(|&w| {
                                    game.generalized_grundy[w].is_some_and(|(value, _)| value == g)
                                })
                            })
                    })
                    .unwrap();
                let next = game
                    .graph
                    .neighbors(state[i])
                    .find(|next| game.index_of(next.to) == to)
                    .unwrap();
                let mut to = state.to_vec();
                to[i] = next.to;
                return Some(Neighbor::new(to, (i, next.label)));
            }
            // The current finite XOR exceeds this mex, so a finite component
            // can decrease it to the mex without moving the infinite component.
            xor ^= target.unwrap();
            infinite = None;
        }
        // Reduce the largest (Grundy, counter) pair, then minimize the
        // destination counter so repeated winning moves terminate.
        let (i, target) = if let Some(i) = infinite {
            (i, xor)
        } else {
            let (i, (g, _)) = indices
                .iter()
                .enumerate()
                .filter_map(|(i, &v)| game.generalized_grundy[v].map(|g| (i, g)))
                .filter(|(_, (g, _))| g ^ xor < *g)
                .max_by_key(|&(i, g)| (g, Reverse(i)))?;
            (i, g ^ xor)
        };
        let next = game
            .graph
            .neighbors(state[i])
            .filter_map(|next| {
                let (g, counter) = game.generalized_grundy[game.index_of(next.to)]?;
                (g == target).then_some((next, counter))
            })
            .min_by_key(|&(_, counter)| counter)?
            .0;
        let mut to = state.to_vec();
        to[i] = next.to;
        Some(Neighbor::new(to, (i, next.label)))
    }
}

impl<G> ImpartialGraph<'_, G>
where
    G: Graph + VertexMap<Option<usize>>,
{
    fn grundy(&mut self, state: &G::Vertex) -> u64 {
        self.prepare();
        let root = self.index_of(*state);
        let index = self.index.as_ref().unwrap();
        self.grundy.resize(index.edges.len(), None);
        if let Some(value) = self.grundy[root] {
            return value;
        }
        let mut active = HashSet::from([root]);
        let mut stack = vec![(root, index.edges[root].iter())];
        while let Some((v, moves)) = stack.last_mut() {
            if let Some(&u) = moves.next() {
                if self.grundy[u].is_none() {
                    assert!(active.insert(u), "cycle in a finite game");
                    stack.push((u, index.edges[u].iter()));
                }
            } else {
                let values = index.edges[*v]
                    .iter()
                    .map(|&u| self.grundy[u].unwrap())
                    .collect();
                self.grundy[*v] = Some(game_mex(values));
                active.remove(v);
                stack.pop();
            }
        }
        self.grundy[root].unwrap()
    }

    fn outcome(&mut self, state: &G::Vertex, misere: bool) -> GameOutcome {
        self.prepare();
        let index = self.index.as_ref().unwrap();
        let outcome = &mut self.outcomes[usize::from(misere)];
        if outcome.values.is_empty() {
            outcome.extend(&index.edges, &index.reverse, misere);
        }
        self.outcomes[usize::from(misere)].values[self.index_of(*state)]
    }

    fn sum_grundy(&mut self, state: &[G::Vertex]) -> u64 {
        state.iter().fold(0, |value, s| value ^ self.grundy(s))
    }

    fn sum_outcome(&mut self, state: &[G::Vertex], misere: bool) -> GameOutcome {
        match state {
            [] => return GameOutcome::from_win(misere),
            [single] => return self.outcome(single, misere),
            _ => {}
        }
        let indices = self.sum_indices(state);
        if !misere {
            self.solve_generalized_grundy();
            return self.sum_normal_outcome(&indices);
        }
        let edges = &self.index.as_ref().unwrap().edges;
        let root = self.sums.prepare(indices, edges);
        self.sums.outcomes.values[root]
    }

    fn sum_normal_outcome(&self, state: &[usize]) -> GameOutcome {
        let mut xor = 0;
        let mut infinite = None;
        for &v in state {
            if let Some((value, _)) = self.generalized_grundy[v] {
                xor ^= value;
            } else if infinite.replace(v).is_some() {
                return GameOutcome::Draw;
            }
        }
        if let Some(v) = infinite {
            let can_win = self.index.as_ref().unwrap().edges[v]
                .iter()
                .any(|&u| self.generalized_grundy[u].is_some_and(|(value, _)| value == xor));
            if can_win {
                GameOutcome::Win
            } else {
                GameOutcome::Draw
            }
        } else if xor == 0 {
            GameOutcome::Lose
        } else {
            GameOutcome::Win
        }
    }

    fn sum_indices(&mut self, state: &[G::Vertex]) -> Vec<usize> {
        self.prepare();
        state.iter().map(|&s| self.index_of(s)).collect()
    }

    fn prepare(&mut self) {
        if self.index.is_some() {
            return;
        }
        let vertices: Vec<_> = self.graph.vertices().collect();
        let mut indices = self.graph.construct_vmap(|| None);
        for (i, &v) in vertices.iter().enumerate() {
            self.graph.vmap_set(&mut indices, v, Some(i));
        }
        let mut edges = vec![Vec::new(); vertices.len()];
        let mut reverse = vec![Vec::new(); vertices.len()];
        let mut seen = vec![None; vertices.len()];
        for (i, &v) in vertices.iter().enumerate() {
            for next in self.graph.neighbors(v) {
                let j = self
                    .graph
                    .vmap_get(&indices, next.to)
                    .expect("vertex is not enumerated by the graph");
                if seen[j] != Some(i) {
                    seen[j] = Some(i);
                    edges[i].push(j);
                    reverse[j].push(i);
                }
            }
        }
        self.index = Some(GraphIndex {
            indices,
            edges,
            reverse,
        });
    }

    fn index_of(&self, v: G::Vertex) -> usize {
        self.graph
            .vmap_get(&self.index.as_ref().unwrap().indices, v)
            .expect("vertex is not enumerated by the graph")
    }

    fn solve_generalized_grundy(&mut self) {
        let index = self.index.as_ref().unwrap();
        let n = index.edges.len();
        if self.generalized_grundy.len() == n {
            return;
        }
        let mut values: Vec<Option<(u64, usize)>> = vec![None; n];
        // Visit acyclic followers first, so DAGs need only one pass.
        let reverse = UsizeGraph::new(n, |v: usize| index.reverse[v].iter().map(|&u| (u, ())));
        let order = reverse.topological_sort();
        if order.len() == n {
            for (counter, v) in order.into_iter().enumerate() {
                let mex = self.grundy.get(v).copied().flatten().unwrap_or_else(|| {
                    let options = index.edges[v]
                        .iter()
                        .map(|&u| values[u].unwrap().0)
                        .collect();
                    game_mex(options)
                });
                values[v] = Some((mex, counter));
            }
            self.generalized_grundy = values;
            return;
        }
        let mut queue: VecDeque<_> = order.into();
        let mut queued = vec![false; n];
        for &v in &queue {
            queued[v] = true;
        }
        for (v, pending) in queued.iter_mut().enumerate() {
            if !*pending {
                *pending = true;
                queue.push_back(v);
            }
        }
        let mut counter = 0;
        let mut options = vec![HashSet::new(); n];
        let mut mexes = vec![0; n];
        while let Some(v) = queue.pop_front() {
            queued[v] = false;
            let mex = mexes[v];
            // Every unresolved option must be able to return to this mex.
            let ready = index.edges[v]
                .iter()
                .all(|&u| values[u].is_some() || options[u].contains(&mex));
            if !ready {
                continue;
            }
            values[v] = Some((mex, counter));
            counter += 1;
            for &u in &index.reverse[v] {
                if values[u].is_some() {
                    continue;
                }
                let inserted = options[u].insert(mex);
                if inserted {
                    while options[u].contains(&mexes[u]) {
                        mexes[u] += 1;
                    }
                }
                // A larger value already had a follower at this vertex's mex.
                if mex < mexes[u] && !queued[u] {
                    queued[u] = true;
                    queue.push_back(u);
                }
                if inserted {
                    for &w in &index.reverse[u] {
                        if queue.len() == n - counter {
                            break; // All unresolved vertices are already queued.
                        }
                        if values[w].is_none() && !queued[w] && mexes[w] == mex {
                            queued[w] = true;
                            queue.push_back(w);
                        }
                    }
                }
            }
        }
        self.generalized_grundy = values;
    }

crates/competitive/src/algorithm/game_analyzer/value.rs (line 274)

    fn from_options_memoized(
        mut left: Vec<Self>,
        mut right: Vec<Self>,
        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
    ) -> Self {
        loop {
            if left.iter().chain(&right).all(|g| g.as_number().is_some()) {
                let l = left.iter().filter_map(Self::as_number).max();
                let r = right.iter().filter_map(Self::as_number).min();
                if let Some(n) = Dyadic::simplest_between(l, r) {
                    return n.into();
                }
                let (l, r) = (l.unwrap(), r.unwrap());
                if l == r {
                    return Self::number_up_nimber(l, 0, 1);
                }
                let (sum, difference) = (l + r, l - r);
                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
                return Self::from_switches(
                    Dyadic::new(sum.numerator(), sum.exponent() + 1),
                    0,
                    0,
                    vec![temperature],
                    Self::temperature_hash(temperature),
                );
            }
            if !right.is_empty()
                && let Some((number, _)) = left.first().and_then(Self::as_number_nimber)
            {
                let nimber = |g: &Self| {
                    g.as_number_nimber()
                        .filter(|&(q, _)| q == number)
                        .map(|(_, n)| n)
                };
                let l: Option<Vec<_>> = left.iter().map(nimber).collect();
                let r: Option<Vec<_>> = right.iter().map(nimber).collect();
                if let (Some(l), Some(r)) = (l, r) {
                    let value = game_mex(l);
                    if value == game_mex(r) {
                        return Self::number_up_nimber(number, 0, value);
                    }
                }
            }
            for (moves, replies, sign) in [(&left, &right, 1), (&right, &left, -1)] {
                if replies.len() != 1 {
                    continue;
                }
                if let Some((q, k, n)) = replies[0].as_number_up_nimber() {
                    if moves.len() == 1
                        && moves[0].as_number() == Some(q)
                        && (k == 0 || k.signum() == sign)
                    {
                        return Self::number_up_nimber(q, k + sign, n ^ 1);
                    }
                    if k == 0 && n == 0 && moves.len() == 2 {
                        let a = moves[0].as_number_nimber();
                        let b = moves[1].as_number_nimber();
                        if (a == Some((q, 0)) && b == Some((q, 1)))
                            || (a == Some((q, 1)) && b == Some((q, 0)))
                        {
                            return Self::number_up_nimber(q, sign, 1);
                        }
                    }
                }
            }
            if left.len() == 1
                && right.len() == 1
                && let (Some((a, k, n, ts)), Some((b, l, m, us))) =
                    (left[0].as_switch_sum(), right[0].as_switch_sum())
                && k == l
                && n == m
                && ts == us
                && a > b
            {
                let (sum, difference) = (a + b, a - b);
                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
                if ts.first().is_none_or(|&t| temperature > t) {
                    return Self::from_switches(
                        Dyadic::new(sum.numerator(), sum.exponent() + 1),
                        k,
                        n,
                        std::iter::once(temperature)
                            .chain(ts.iter().copied())
                            .collect(),
                        Self::temperature_hash(temperature) ^ left[0].switch_hash(),
                    );
                }
            }
            let count = left.len() + right.len();
            Self::remove_dominated(&mut left, Player::Left, cache);
            Self::remove_dominated(&mut right, Player::Right, cache);
            if count != left.len() + right.len() {
                continue;
            }
            let options = Rc::new((left, right));
            let game = Self(GameValueNode::Options(0.into(), options.clone()));
            // Bypasses preserve the game, so all checks use the same candidate.
            let mut reversible = Vec::new();
            for player in [Player::Left, Player::Right] {
                let moves = match player {
                    Player::Left => &options.0,
                    Player::Right => &options.1,
                };
                for (i, g) in moves.iter().enumerate() {
                    if let Some((q, n)) = g.as_number_nimber()
                        && n > 1
                    {
                        let number = Self::from(q);
                        let (lower, upper) = match player {
                            Player::Left => (&game, &number),
                            Player::Right => (&number, &game),
                        };
                        // A strict inequality against q excludes every reply q + *m.
                        if lower.leq_memoized(upper, cache) && !upper.leq_memoized(lower, cache) {
                            continue;
                        }
                    }
                    if let Some(reply) = g.options(player.opponent()).find(|r| match player {
                        Player::Left => r.leq_memoized(&game, cache),
                        Player::Right => game.leq_memoized(r, cache),
                    }) {
                        reversible.push((player, i, reply));
                    }
                }
            }
            if reversible.is_empty() {
                return game;
            }
            drop(game);
            (left, right) = Rc::unwrap_or_clone(options);
            for (player, i, reply) in reversible.into_iter().rev() {
                let moves = if player == Player::Left {
                    &mut left
                } else {
                    &mut right
                };
                moves.remove(i);
                moves.extend(reply.options(player));
            }
        }
    }