Skip to main content

Dyadic

competitive::num::dyadic

Struct Dyadic 

Source 
pub struct Dyadic<T> {
    numerator: T,
    exponent: u32,
}
Expand description

A reduced numerator / 2^exponent.

Fields§

§numerator: T§exponent: u32

Implementations§

Source§

impl<T> Dyadic<T>

Source

pub fn numerator(self) -> T

Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/value.rs (line 65)
56    fn hash<H>(&self, state: &mut H)
57    where
58        H: Hasher,
59    {
60        match self {
61            Self::NumberUpNimber(q, k, n) => (q, k, n).hash(state),
62            Self::Switches(v) => (v.number, v.up, v.nimber, v.fingerprint).hash(state),
63            Self::Options(q, v) => {
64                Rc::as_ptr(v).hash(state);
65                if q.numerator() != 0 {
66                    q.hash(state);
67                }
68            }
69        }
70    }
71}
72
73#[derive(Clone)]
74struct GameValueSwitches {
75    number: Dyadic<i64>,
76    up: i64,
77    nimber: u64,
78    temperatures: Rc<Vec<Dyadic<i64>>>,
79    start: usize,
80    // XOR of the remaining temperatures' hashes; equality still checks the contents.
81    fingerprint: u64,
82}
83
84impl GameValue {
85    pub fn nimber(value: u64) -> Self {
86        Self::number_up_nimber(0.into(), 0, value)
87    }
88
89    /// Constructs `number + up * ↑ + *nimber` without expanding options.
90    pub fn number_up_nimber(number: Dyadic<i64>, up: i64, nimber: u64) -> Self {
91        Self(GameValueNode::NumberUpNimber(number, up, nimber))
92    }
93
94    pub fn as_number(&self) -> Option<Dyadic<i64>> {
95        match self.0 {
96            GameValueNode::NumberUpNimber(n, 0, 0) => Some(n),
97            _ => None,
98        }
99    }
100
101    pub fn as_nimber(&self) -> Option<u64> {
102        match self.0 {
103            GameValueNode::NumberUpNimber(q, 0, n) if q.numerator() == 0 => Some(n),
104            _ => None,
105        }
106    }
107
108    /// Returns `(q, n)` when the value is `q + *n`.
109    pub fn as_number_nimber(&self) -> Option<(Dyadic<i64>, u64)> {
110        match self.0 {
111            GameValueNode::NumberUpNimber(q, 0, n) => Some((q, n)),
112            _ => None,
113        }
114    }
115
116    /// Returns `(q, k, n)` when the value is `q + k↑ + *n`.
117    pub fn as_number_up_nimber(&self) -> Option<(Dyadic<i64>, i64, u64)> {
118        match self.0 {
119            GameValueNode::NumberUpNimber(q, k, n) => Some((q, k, n)),
120            _ => None,
121        }
122    }
123
124    /// Returns `(q, k, n, temperatures)` for `q + k↑ + *n + Σ{t|-t}`.
125    /// Temperatures are positive and strictly decreasing; the slice may be empty.
126    #[allow(clippy::type_complexity)] // Borrows the components without a separate public type.
127    pub fn as_switch_sum(&self) -> Option<(Dyadic<i64>, i64, u64, &[Dyadic<i64>])> {
128        match &self.0 {
129            GameValueNode::NumberUpNimber(q, k, n) => Some((*q, *k, *n, &[])),
130            GameValueNode::Switches(value) => Some((
131                value.number,
132                value.up,
133                value.nimber,
134                &value.temperatures[value.start..],
135            )),
136            _ => None,
137        }
138    }
139
140    pub fn outcome(&self) -> PartisanOutcome {
141        match self.partial_cmp(&Self::from(0)) {
142            Some(Ordering::Greater) => PartisanOutcome::Left,
143            Some(Ordering::Less) => PartisanOutcome::Right,
144            Some(Ordering::Equal) => PartisanOutcome::Previous,
145            None => PartisanOutcome::Next,
146        }
147    }
148
149    /// Whether the selected starting player can force a win.
150    pub fn wins(&self, player: Player) -> bool {
151        match player {
152            Player::Left => !self.leq(&Self::from(0)),
153            Player::Right => !Self::from(0).leq(self),
154        }
155    }
156
157    /// Removes dominated and reversible options.
158    pub fn from_options(
159        left: impl IntoIterator<Item = Self>,
160        right: impl IntoIterator<Item = Self>,
161    ) -> Self {
162        Self::from_options_memoized(
163            left.into_iter().collect(),
164            right.into_iter().collect(),
165            &mut HashMap::new(),
166        )
167    }
168
169    pub fn options(&self, player: Player) -> impl Iterator<Item = Self> + '_ {
170        let mut offset = Dyadic::from(0);
171        let (single, nimbers, general) = match &self.0 {
172            GameValueNode::NumberUpNimber(n, 0, 0) => {
173                let option = if n.exponent() == 0 {
174                    match player {
175                        Player::Left if n.numerator() > 0 => Some(Dyadic::from(n.numerator() - 1)),
176                        Player::Right if n.numerator() < 0 => Some(Dyadic::from(n.numerator() + 1)),
177                        _ => None,
178                    }
179                } else {
180                    let numerator = (n.numerator() >> 1) + i64::from(player == Player::Right);
181                    Some(Dyadic::new(numerator, n.exponent() - 1))
182                };
183                (option.map(Self::from), None, &[][..])
184            }
185            GameValueNode::NumberUpNimber(q, 0, n) => (None, Some((*q, *n)), &[][..]),
186            GameValueNode::NumberUpNimber(q, k, 1)
187                if matches!((*k, player), (1, Player::Left) | (-1, Player::Right)) =>
188            {
189                (None, Some((*q, 2)), &[][..])
190            }
191            GameValueNode::NumberUpNimber(q, k, n) => {
192                let sign = if *k > 0 { 1 } else { -1 };
193                let moves_to_number = (*k > 0) == (player == Player::Left);
194                let option = if moves_to_number {
195                    Self::from(*q)
196                } else {
197                    Self::number_up_nimber(*q, k - sign, n ^ 1)
198                };
199                (Some(option), None, &[][..])
200            }
201            GameValueNode::Switches(value) => {
202                let temperatures = &value.temperatures[value.start..];
203                let t = if player == Player::Left {
204                    temperatures[0]
205                } else {
206                    -temperatures[0]
207                };
208                let option = if temperatures.len() == 1 {
209                    Self::number_up_nimber(value.number + t, value.up, value.nimber)
210                } else {
211                    Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
212                        number: value.number + t,
213                        start: value.start + 1,
214                        fingerprint: value.fingerprint ^ Self::temperature_hash(temperatures[0]),
215                        ..(**value).clone()
216                    })))
217                };
218                (Some(option), None, &[][..])
219            }
220            GameValueNode::Options(q, options) => {
221                offset = *q;
222                let (left, right) = &**options;
223                let moves = if player == Player::Left { left } else { right };
224                (None, None, moves.as_slice())
225            }
226        };
227        single
228            .into_iter()
229            .chain(
230                nimbers
231                    .into_iter()
232                    .flat_map(|(q, n)| (0..n).map(move |m| Self::number_up_nimber(q, 0, m))),
233            )
234            .chain(general.iter().map(move |g| g.translated(offset)))
235    }
236
237    fn from_options_memoized(
238        mut left: Vec<Self>,
239        mut right: Vec<Self>,
240        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
241    ) -> Self {
242        loop {
243            if left.iter().chain(&right).all(|g| g.as_number().is_some()) {
244                let l = left.iter().filter_map(Self::as_number).max();
245                let r = right.iter().filter_map(Self::as_number).min();
246                if let Some(n) = Dyadic::simplest_between(l, r) {
247                    return n.into();
248                }
249                let (l, r) = (l.unwrap(), r.unwrap());
250                if l == r {
251                    return Self::number_up_nimber(l, 0, 1);
252                }
253                let (sum, difference) = (l + r, l - r);
254                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
255                return Self::from_switches(
256                    Dyadic::new(sum.numerator(), sum.exponent() + 1),
257                    0,
258                    0,
259                    vec![temperature],
260                    Self::temperature_hash(temperature),
261                );
262            }
263            if !right.is_empty()
264                && let Some((number, _)) = left.first().and_then(Self::as_number_nimber)
265            {
266                let nimber = |g: &Self| {
267                    g.as_number_nimber()
268                        .filter(|&(q, _)| q == number)
269                        .map(|(_, n)| n)
270                };
271                let l: Option<Vec<_>> = left.iter().map(nimber).collect();
272                let r: Option<Vec<_>> = right.iter().map(nimber).collect();
273                if let (Some(l), Some(r)) = (l, r) {
274                    let value = game_mex(l);
275                    if value == game_mex(r) {
276                        return Self::number_up_nimber(number, 0, value);
277                    }
278                }
279            }
280            for (moves, replies, sign) in [(&left, &right, 1), (&right, &left, -1)] {
281                if replies.len() != 1 {
282                    continue;
283                }
284                if let Some((q, k, n)) = replies[0].as_number_up_nimber() {
285                    if moves.len() == 1
286                        && moves[0].as_number() == Some(q)
287                        && (k == 0 || k.signum() == sign)
288                    {
289                        return Self::number_up_nimber(q, k + sign, n ^ 1);
290                    }
291                    if k == 0 && n == 0 && moves.len() == 2 {
292                        let a = moves[0].as_number_nimber();
293                        let b = moves[1].as_number_nimber();
294                        if (a == Some((q, 0)) && b == Some((q, 1)))
295                            || (a == Some((q, 1)) && b == Some((q, 0)))
296                        {
297                            return Self::number_up_nimber(q, sign, 1);
298                        }
299                    }
300                }
301            }
302            if left.len() == 1
303                && right.len() == 1
304                && let (Some((a, k, n, ts)), Some((b, l, m, us))) =
305                    (left[0].as_switch_sum(), right[0].as_switch_sum())
306                && k == l
307                && n == m
308                && ts == us
309                && a > b
310            {
311                let (sum, difference) = (a + b, a - b);
312                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
313                if ts.first().is_none_or(|&t| temperature > t) {
314                    return Self::from_switches(
315                        Dyadic::new(sum.numerator(), sum.exponent() + 1),
316                        k,
317                        n,
318                        std::iter::once(temperature)
319                            .chain(ts.iter().copied())
320                            .collect(),
321                        Self::temperature_hash(temperature) ^ left[0].switch_hash(),
322                    );
323                }
324            }
325            let count = left.len() + right.len();
326            Self::remove_dominated(&mut left, Player::Left, cache);
327            Self::remove_dominated(&mut right, Player::Right, cache);
328            if count != left.len() + right.len() {
329                continue;
330            }
331            let options = Rc::new((left, right));
332            let game = Self(GameValueNode::Options(0.into(), options.clone()));
333            // Bypasses preserve the game, so all checks use the same candidate.
334            let mut reversible = Vec::new();
335            for player in [Player::Left, Player::Right] {
336                let moves = match player {
337                    Player::Left => &options.0,
338                    Player::Right => &options.1,
339                };
340                for (i, g) in moves.iter().enumerate() {
341                    if let Some((q, n)) = g.as_number_nimber()
342                        && n > 1
343                    {
344                        let number = Self::from(q);
345                        let (lower, upper) = match player {
346                            Player::Left => (&game, &number),
347                            Player::Right => (&number, &game),
348                        };
349                        // A strict inequality against q excludes every reply q + *m.
350                        if lower.leq_memoized(upper, cache) && !upper.leq_memoized(lower, cache) {
351                            continue;
352                        }
353                    }
354                    if let Some(reply) = g.options(player.opponent()).find(|r| match player {
355                        Player::Left => r.leq_memoized(&game, cache),
356                        Player::Right => game.leq_memoized(r, cache),
357                    }) {
358                        reversible.push((player, i, reply));
359                    }
360                }
361            }
362            if reversible.is_empty() {
363                return game;
364            }
365            drop(game);
366            (left, right) = Rc::unwrap_or_clone(options);
367            for (player, i, reply) in reversible.into_iter().rev() {
368                let moves = if player == Player::Left {
369                    &mut left
370                } else {
371                    &mut right
372                };
373                moves.remove(i);
374                moves.extend(reply.options(player));
375            }
376        }
377    }
378
379    fn leq(&self, rhs: &Self) -> bool {
380        self.leq_memoized(rhs, &mut HashMap::new())
381    }
382
383    fn leq_memoized(
384        &self,
385        rhs: &Self,
386        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
387    ) -> bool {
388        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
389            (self.as_switch_sum(), rhs.as_switch_sum())
390        {
391            // Both players take the hottest remaining switch. At zero, the tail
392            // decides the winner with the turn reversed once per switch.
393            let mut number = a;
394            let mut odd = false;
395            for t in Self::switch_difference(ts, us) {
396                // The unplayed alternating tail has the sign of the next term.
397                if !odd && number >= b || odd && number <= b {
398                    return odd;
399                }
400                number = if odd { number - t } else { number + t };
401                odd = !odd;
402            }
403            return match number.cmp(&b) {
404                Ordering::Less => true,
405                Ordering::Greater => false,
406                Ordering::Equal => {
407                    let up = if odd { l - k } else { k - l };
408                    let nimber = n ^ m;
409                    let wins = up > 0 || up == 0 && nimber != 0 || up == -1 && nimber == 1;
410                    wins == odd
411                }
412            };
413        }
414        if let (GameValueNode::Options(a, g), GameValueNode::Options(b, h)) = (&self.0, &rhs.0)
415            && Rc::ptr_eq(g, h)
416        {
417            return a <= b;
418        }
419        // Normalize only memo keys: from_options also compares unreduced candidates.
420        let offset = -self.number_offset();
421        let left = self.translated(offset).0;
422        let right = rhs.translated(offset).0;
423        if let Some(&value) = cache.get(&left).and_then(|row| row.get(&right)) {
424            return value;
425        }
426        // Try explicit options before expanding a compact value.
427        let mut sides = [(self, rhs, Player::Left), (rhs, self, Player::Right)];
428        if self.as_switch_sum().is_some() {
429            sides.swap(0, 1);
430        }
431        let value = sides.into_iter().all(|(game, other, player)| {
432            let mut preferred = |a: &Self, b: &Self| match player {
433                Player::Left => b.leq_memoized(a, cache),
434                Player::Right => a.leq_memoized(b, cache),
435            };
436            if let GameValueNode::NumberUpNimber(q, 0, n) = game.0
437                && n != 0
438            {
439                let number = Self::from(q);
440                !preferred(&number, other)
441                    && (preferred(other, &number)
442                        || !game.options(player).skip(1).any(|g| preferred(&g, other)))
443            } else {
444                !game.options(player).any(|g| preferred(&g, other))
445            }
446        });
447        cache.entry(left).or_default().insert(right, value);
448        value
449    }
450
451    fn negated(&self, cache: &mut HashMap<usize, Self>) -> Self {
452        match &self.0 {
453            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(-*q, -*k, *n),
454            GameValueNode::Switches(value) => {
455                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
456                    number: -value.number,
457                    up: -value.up,
458                    ..(**value).clone()
459                })))
460            }
461            GameValueNode::Options(q, options) => {
462                let key = Rc::as_ptr(options) as usize;
463                if let Some(value) = cache.get(&key) {
464                    return value.translated(-*q);
465                }
466                let (left, right) = &**options;
467                let value = Self(GameValueNode::Options(
468                    0.into(),
469                    Rc::new((
470                        right.iter().map(|g| g.negated(cache)).collect(),
471                        left.iter().map(|g| g.negated(cache)).collect(),
472                    )),
473                ));
474                cache.insert(key, value.clone());
475                value.translated(-*q)
476            }
477        }
478    }
479
480    fn sum(
481        &self,
482        rhs: &Self,
483        cache: &mut HashMap<(GameValueNode, GameValueNode), Self>,
484        comparisons: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
485    ) -> Self {
486        if let (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) =
487            (&self.0, &rhs.0)
488        {
489            return Self::number_up_nimber(*a + *b, k + l, n ^ m);
490        }
491        if let Some(q) = self.as_number() {
492            return rhs.translated(q);
493        }
494        if let Some(q) = rhs.as_number() {
495            return self.translated(q);
496        }
497        if let (Some((a, k, n, ts)), Some((b, l, m, us))) =
498            (self.as_switch_sum(), rhs.as_switch_sum())
499        {
500            return Self::from_switches(
501                a + b,
502                k + l,
503                n ^ m,
504                Self::switch_difference(ts, us).collect(),
505                self.switch_hash() ^ rhs.switch_hash(),
506            );
507        }
508        // Cache the sum of the untranslated parts, sharing it across numeric offsets.
509        let (a, b) = (self.number_offset(), rhs.number_offset());
510        if a.numerator() != 0 || b.numerator() != 0 {
511            return self
512                .translated(-a)
513                .sum(&rhs.translated(-b), cache, comparisons)
514                .translated(a + b);
515        }
516        let mut key = (self.0.clone(), rhs.0.clone());
517        let swap = match (&key.0, &key.1) {
518            (GameValueNode::Options(_, a), GameValueNode::Options(_, b)) => {
519                Rc::as_ptr(a) > Rc::as_ptr(b)
520            }
521            (GameValueNode::Options(..), _) => true,
522            _ => false,
523        };
524        if swap {
525            std::mem::swap(&mut key.0, &mut key.1);
526        }
527        if let Some(value) = cache.get(&key) {
528            return value.clone();
529        }
530        let mut options = |player| {
531            let mut moves = Vec::new();
532            for g in self.options(player) {
533                moves.push(g.sum(rhs, cache, comparisons));
534            }
535            for g in rhs.options(player) {
536                moves.push(self.sum(&g, cache, comparisons));
537            }
538            moves
539        };
540        let value =
541            Self::from_options_memoized(options(Player::Left), options(Player::Right), comparisons);
542        cache.insert(key, value.clone());
543        value
544    }
545
546    fn number_offset(&self) -> Dyadic<i64> {
547        match &self.0 {
548            GameValueNode::NumberUpNimber(q, ..) | GameValueNode::Options(q, _) => *q,
549            GameValueNode::Switches(v) => v.number,
550        }
551    }
552
553    fn translated(&self, number: Dyadic<i64>) -> Self {
554        if number.numerator() == 0 {
555            return self.clone();
556        }
557        match &self.0 {
558            GameValueNode::NumberUpNimber(q, k, n) => Self::number_up_nimber(*q + number, *k, *n),
559            GameValueNode::Switches(v) => {
560                Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
561                    number: v.number + number,
562                    ..(**v).clone()
563                })))
564            }
565            GameValueNode::Options(q, options) => {
566                Self(GameValueNode::Options(*q + number, options.clone()))
567            }
568        }
569    }
570
571    fn temperature_hash(t: Dyadic<i64>) -> u64 {
572        let mut hasher = DefaultHasher::new();
573        t.hash(&mut hasher);
574        hasher.finish()
575    }
576
577    fn switch_hash(&self) -> u64 {
578        match &self.0 {
579            GameValueNode::NumberUpNimber(..) => 0,
580            GameValueNode::Switches(v) => v.fingerprint,
581            GameValueNode::Options(..) => unreachable!(),
582        }
583    }
584
585    fn from_switches(
586        q: Dyadic<i64>,
587        k: i64,
588        n: u64,
589        temperatures: Vec<Dyadic<i64>>,
590        fingerprint: u64,
591    ) -> Self {
592        if temperatures.is_empty() {
593            Self::number_up_nimber(q, k, n)
594        } else {
595            Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
596                number: q,
597                up: k,
598                nimber: n,
599                fingerprint,
600                temperatures: Rc::new(temperatures),
601                start: 0,
602            })))
603        }
604    }
605
606    fn switch_difference<'a>(
607        mut left: &'a [Dyadic<i64>],
608        mut right: &'a [Dyadic<i64>],
609    ) -> impl Iterator<Item = Dyadic<i64>> + 'a {
610        std::iter::from_fn(move || {
611            while let (Some(a), Some(b)) = (left.first(), right.first()) {
612                if a != b {
613                    break;
614                }
615                left = &left[1..];
616                right = &right[1..];
617            }
618            if left.first() < right.first() {
619                std::mem::swap(&mut left, &mut right);
620            }
621            let (&value, tail) = left.split_first()?;
622            left = tail;
623            Some(value)
624        })
625    }
626
627    fn remove_dominated(
628        options: &mut Vec<Self>,
629        player: Player,
630        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
631    ) {
632        let mut retained = vec![true; options.len()];
633        for i in 0..options.len() {
634            let dominated = (0..options.len()).any(|j| {
635                i != j
636                    && retained[j]
637                    && match player {
638                        Player::Left => options[i].leq_memoized(&options[j], cache),
639                        Player::Right => options[j].leq_memoized(&options[i], cache),
640                    }
641            });
642            retained[i] = !dominated;
643        }
644        let mut retained = retained.into_iter();
645        options.retain(|_| retained.next().unwrap());
646    }
647}
648
649impl From<i64> for GameValue {
650    fn from(value: i64) -> Self {
651        Dyadic::from(value).into()
652    }
653}
654impl From<Dyadic<i64>> for GameValue {
655    fn from(value: Dyadic<i64>) -> Self {
656        Self::number_up_nimber(value, 0, 0)
657    }
658}
659impl Neg for GameValue {
660    type Output = Self;
661    fn neg(self) -> Self {
662        self.negated(&mut HashMap::new())
663    }
664}
665impl Add for GameValue {
666    type Output = Self;
667    fn add(self, rhs: Self) -> Self {
668        self.sum(&rhs, &mut HashMap::new(), &mut HashMap::new())
669    }
670}
671impl Sub for GameValue {
672    type Output = Self;
673    fn sub(self, rhs: Self) -> Self {
674        if self.0 == rhs.0 {
675            Self::from(0)
676        } else {
677            self + -rhs
678        }
679    }
680}
681impl Sum for GameValue {
682    fn sum<I>(iter: I) -> Self
683    where
684        I: Iterator<Item = Self>,
685    {
686        let (mut number, mut up, mut nimber) = (Dyadic::from(0), 0, 0);
687        let mut temperatures = Vec::new();
688        let mut fingerprint = 0;
689        let mut general = Self::from(0);
690        for value in iter {
691            if let Some((q, k, n, ts)) = value.as_switch_sum() {
692                number = number + q;
693                up += k;
694                nimber ^= n;
695                temperatures.extend_from_slice(ts);
696                fingerprint ^= value.switch_hash();
697            } else {
698                general = general + value;
699            }
700        }
701        temperatures.sort_unstable_by(|a, b| b.cmp(a));
702        let mut retained = 0;
703        for i in 0..temperatures.len() {
704            if retained > 0 && temperatures[retained - 1] == temperatures[i] {
705                retained -= 1;
706            } else {
707                temperatures[retained] = temperatures[i];
708                retained += 1;
709            }
710        }
711        temperatures.truncate(retained);
712        let value = Self::from_switches(number, up, nimber, temperatures, fingerprint);
713        if general.as_nimber() == Some(0) {
714            value
715        } else {
716            value + general
717        }
718    }
719}
720impl PartialEq for GameValue {
721    fn eq(&self, rhs: &Self) -> bool {
722        match (&self.0, &rhs.0) {
723            (GameValueNode::NumberUpNimber(a, k, n), GameValueNode::NumberUpNimber(b, l, m)) => {
724                return a == b && k == l && n == m;
725            }
726            (GameValueNode::Switches(_), GameValueNode::Switches(_)) => {
727                return self.0 == rhs.0;
728            }
729            _ => {}
730        }
731        let mut cache = HashMap::new();
732        self.leq_memoized(rhs, &mut cache) && rhs.leq_memoized(self, &mut cache)
733    }
734}
735impl Eq for GameValue {}
736impl PartialOrd for GameValue {
737    fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
738        let mut cache = HashMap::new();
739        match (
740            self.leq_memoized(rhs, &mut cache),
741            rhs.leq_memoized(self, &mut cache),
742        ) {
743            (true, true) => Some(Ordering::Equal),
744            (true, false) => Some(Ordering::Less),
745            (false, true) => Some(Ordering::Greater),
746            (false, false) => None,
747        }
748    }
749}
750impl fmt::Display for GameValue {
751    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
752        if let Some((q, k, n, temperatures)) = self.as_switch_sum() {
753            let mut separator = "";
754            if q.numerator() != 0 || k == 0 && n == 0 && temperatures.is_empty() {
755                write!(f, "{q}")?;
756                separator = "+";
757            }
758            if k != 0 {
759                f.write_str(separator)?;
760                if k.unsigned_abs() != 1 {
761                    write!(f, "{}", k.unsigned_abs())?;
762                }
763                f.write_str(if k > 0 { "↑" } else { "↓" })?;
764                separator = "+";
765            }
766            if n != 0 {
767                write!(f, "{separator}*")?;
768                if n != 1 {
769                    write!(f, "{n}")?;
770                }
771                separator = "+";
772            }
773            for t in temperatures {
774                write!(f, "{separator}{{{t}|{}}}", -*t)?;
775                separator = "+";
776            }
777            return Ok(());
778        }
779        f.write_str("{")?;
780        for (separator, player) in [("", Player::Left), ("|", Player::Right)] {
781            f.write_str(separator)?;
782            for (i, g) in self.options(player).enumerate() {
783                if i > 0 {
784                    f.write_str(",")?;
785                }
786                write!(f, "{g}")?;
787            }
788        }
789        f.write_str("}")
790    }
Source

pub fn exponent(self) -> u32

Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/value.rs (line 173)
169    pub fn options(&self, player: Player) -> impl Iterator<Item = Self> + '_ {
170        let mut offset = Dyadic::from(0);
171        let (single, nimbers, general) = match &self.0 {
172            GameValueNode::NumberUpNimber(n, 0, 0) => {
173                let option = if n.exponent() == 0 {
174                    match player {
175                        Player::Left if n.numerator() > 0 => Some(Dyadic::from(n.numerator() - 1)),
176                        Player::Right if n.numerator() < 0 => Some(Dyadic::from(n.numerator() + 1)),
177                        _ => None,
178                    }
179                } else {
180                    let numerator = (n.numerator() >> 1) + i64::from(player == Player::Right);
181                    Some(Dyadic::new(numerator, n.exponent() - 1))
182                };
183                (option.map(Self::from), None, &[][..])
184            }
185            GameValueNode::NumberUpNimber(q, 0, n) => (None, Some((*q, *n)), &[][..]),
186            GameValueNode::NumberUpNimber(q, k, 1)
187                if matches!((*k, player), (1, Player::Left) | (-1, Player::Right)) =>
188            {
189                (None, Some((*q, 2)), &[][..])
190            }
191            GameValueNode::NumberUpNimber(q, k, n) => {
192                let sign = if *k > 0 { 1 } else { -1 };
193                let moves_to_number = (*k > 0) == (player == Player::Left);
194                let option = if moves_to_number {
195                    Self::from(*q)
196                } else {
197                    Self::number_up_nimber(*q, k - sign, n ^ 1)
198                };
199                (Some(option), None, &[][..])
200            }
201            GameValueNode::Switches(value) => {
202                let temperatures = &value.temperatures[value.start..];
203                let t = if player == Player::Left {
204                    temperatures[0]
205                } else {
206                    -temperatures[0]
207                };
208                let option = if temperatures.len() == 1 {
209                    Self::number_up_nimber(value.number + t, value.up, value.nimber)
210                } else {
211                    Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
212                        number: value.number + t,
213                        start: value.start + 1,
214                        fingerprint: value.fingerprint ^ Self::temperature_hash(temperatures[0]),
215                        ..(**value).clone()
216                    })))
217                };
218                (Some(option), None, &[][..])
219            }
220            GameValueNode::Options(q, options) => {
221                offset = *q;
222                let (left, right) = &**options;
223                let moves = if player == Player::Left { left } else { right };
224                (None, None, moves.as_slice())
225            }
226        };
227        single
228            .into_iter()
229            .chain(
230                nimbers
231                    .into_iter()
232                    .flat_map(|(q, n)| (0..n).map(move |m| Self::number_up_nimber(q, 0, m))),
233            )
234            .chain(general.iter().map(move |g| g.translated(offset)))
235    }
236
237    fn from_options_memoized(
238        mut left: Vec<Self>,
239        mut right: Vec<Self>,
240        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
241    ) -> Self {
242        loop {
243            if left.iter().chain(&right).all(|g| g.as_number().is_some()) {
244                let l = left.iter().filter_map(Self::as_number).max();
245                let r = right.iter().filter_map(Self::as_number).min();
246                if let Some(n) = Dyadic::simplest_between(l, r) {
247                    return n.into();
248                }
249                let (l, r) = (l.unwrap(), r.unwrap());
250                if l == r {
251                    return Self::number_up_nimber(l, 0, 1);
252                }
253                let (sum, difference) = (l + r, l - r);
254                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
255                return Self::from_switches(
256                    Dyadic::new(sum.numerator(), sum.exponent() + 1),
257                    0,
258                    0,
259                    vec![temperature],
260                    Self::temperature_hash(temperature),
261                );
262            }
263            if !right.is_empty()
264                && let Some((number, _)) = left.first().and_then(Self::as_number_nimber)
265            {
266                let nimber = |g: &Self| {
267                    g.as_number_nimber()
268                        .filter(|&(q, _)| q == number)
269                        .map(|(_, n)| n)
270                };
271                let l: Option<Vec<_>> = left.iter().map(nimber).collect();
272                let r: Option<Vec<_>> = right.iter().map(nimber).collect();
273                if let (Some(l), Some(r)) = (l, r) {
274                    let value = game_mex(l);
275                    if value == game_mex(r) {
276                        return Self::number_up_nimber(number, 0, value);
277                    }
278                }
279            }
280            for (moves, replies, sign) in [(&left, &right, 1), (&right, &left, -1)] {
281                if replies.len() != 1 {
282                    continue;
283                }
284                if let Some((q, k, n)) = replies[0].as_number_up_nimber() {
285                    if moves.len() == 1
286                        && moves[0].as_number() == Some(q)
287                        && (k == 0 || k.signum() == sign)
288                    {
289                        return Self::number_up_nimber(q, k + sign, n ^ 1);
290                    }
291                    if k == 0 && n == 0 && moves.len() == 2 {
292                        let a = moves[0].as_number_nimber();
293                        let b = moves[1].as_number_nimber();
294                        if (a == Some((q, 0)) && b == Some((q, 1)))
295                            || (a == Some((q, 1)) && b == Some((q, 0)))
296                        {
297                            return Self::number_up_nimber(q, sign, 1);
298                        }
299                    }
300                }
301            }
302            if left.len() == 1
303                && right.len() == 1
304                && let (Some((a, k, n, ts)), Some((b, l, m, us))) =
305                    (left[0].as_switch_sum(), right[0].as_switch_sum())
306                && k == l
307                && n == m
308                && ts == us
309                && a > b
310            {
311                let (sum, difference) = (a + b, a - b);
312                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
313                if ts.first().is_none_or(|&t| temperature > t) {
314                    return Self::from_switches(
315                        Dyadic::new(sum.numerator(), sum.exponent() + 1),
316                        k,
317                        n,
318                        std::iter::once(temperature)
319                            .chain(ts.iter().copied())
320                            .collect(),
321                        Self::temperature_hash(temperature) ^ left[0].switch_hash(),
322                    );
323                }
324            }
325            let count = left.len() + right.len();
326            Self::remove_dominated(&mut left, Player::Left, cache);
327            Self::remove_dominated(&mut right, Player::Right, cache);
328            if count != left.len() + right.len() {
329                continue;
330            }
331            let options = Rc::new((left, right));
332            let game = Self(GameValueNode::Options(0.into(), options.clone()));
333            // Bypasses preserve the game, so all checks use the same candidate.
334            let mut reversible = Vec::new();
335            for player in [Player::Left, Player::Right] {
336                let moves = match player {
337                    Player::Left => &options.0,
338                    Player::Right => &options.1,
339                };
340                for (i, g) in moves.iter().enumerate() {
341                    if let Some((q, n)) = g.as_number_nimber()
342                        && n > 1
343                    {
344                        let number = Self::from(q);
345                        let (lower, upper) = match player {
346                            Player::Left => (&game, &number),
347                            Player::Right => (&number, &game),
348                        };
349                        // A strict inequality against q excludes every reply q + *m.
350                        if lower.leq_memoized(upper, cache) && !upper.leq_memoized(lower, cache) {
351                            continue;
352                        }
353                    }
354                    if let Some(reply) = g.options(player.opponent()).find(|r| match player {
355                        Player::Left => r.leq_memoized(&game, cache),
356                        Player::Right => game.leq_memoized(r, cache),
357                    }) {
358                        reversible.push((player, i, reply));
359                    }
360                }
361            }
362            if reversible.is_empty() {
363                return game;
364            }
365            drop(game);
366            (left, right) = Rc::unwrap_or_clone(options);
367            for (player, i, reply) in reversible.into_iter().rev() {
368                let moves = if player == Player::Left {
369                    &mut left
370                } else {
371                    &mut right
372                };
373                moves.remove(i);
374                moves.extend(reply.options(player));
375            }
376        }
377    }
Source§

impl<T> Dyadic<T>
where T: Signed,

Source

pub fn new(numerator: T, exponent: u32) -> Self

Examples found in repository?
crates/competitive/src/num/dyadic.rs (line 68)
46    pub fn simplest_between(left: Option<Self>, right: Option<Self>) -> Option<Self> {
47        if left.zip(right).is_some_and(|(l, r)| l >= r) {
48            return None;
49        }
50        if left.is_none_or(|l| l.numerator < T::zero())
51            && right.is_none_or(|r| r.numerator > T::zero())
52        {
53            return Some(Self::zero());
54        }
55        let negative = right.is_some_and(|r| r.numerator <= T::zero());
56        let (lower, upper) = if negative {
57            (-right.unwrap(), left.map(Neg::neg))
58        } else {
59            (left.unwrap(), right)
60        };
61        let two = T::one() + T::one();
62        for exponent in 0.. {
63            let floor = if exponent < lower.exponent {
64                lower.numerator / two.pow(lower.exponent - exponent)
65            } else {
66                lower.numerator * two.pow(exponent - lower.exponent)
67            };
68            let value = Self::new(floor + T::one(), exponent);
69            if upper.is_none_or(|u| value < u) {
70                return Some(if negative { -value } else { value });
71            }
72        }
73        unreachable!()
74    }
75}
76
77impl<T> From<T> for Dyadic<T>
78where
79    T: Signed,
80{
81    fn from(numerator: T) -> Self {
82        Self::new(numerator, 0)
83    }
84}
85impl<T> Zero for Dyadic<T>
86where
87    T: Signed,
88{
89    fn zero() -> Self {
90        T::zero().into()
91    }
92}
93impl<T> One for Dyadic<T>
94where
95    T: Signed,
96{
97    fn one() -> Self {
98        T::one().into()
99    }
100}
101impl<T> Default for Dyadic<T>
102where
103    T: Signed,
104{
105    fn default() -> Self {
106        Self::zero()
107    }
108}
109impl<T> Neg for Dyadic<T>
110where
111    T: Signed,
112{
113    type Output = Self;
114    fn neg(self) -> Self {
115        Self {
116            numerator: -self.numerator,
117            exponent: self.exponent,
118        }
119    }
120}
121impl<T> Add for Dyadic<T>
122where
123    T: Signed,
124{
125    type Output = Self;
126    fn add(self, rhs: Self) -> Self {
127        let exponent = self.exponent.max(rhs.exponent);
128        let two = T::one() + T::one();
129        let left = self.numerator * two.pow(exponent - self.exponent);
130        let right = rhs.numerator * two.pow(exponent - rhs.exponent);
131        Self::new(left + right, exponent)
132    }
More examples
Hide additional examples
crates/competitive/src/algorithm/game_analyzer/value.rs (line 181)
169    pub fn options(&self, player: Player) -> impl Iterator<Item = Self> + '_ {
170        let mut offset = Dyadic::from(0);
171        let (single, nimbers, general) = match &self.0 {
172            GameValueNode::NumberUpNimber(n, 0, 0) => {
173                let option = if n.exponent() == 0 {
174                    match player {
175                        Player::Left if n.numerator() > 0 => Some(Dyadic::from(n.numerator() - 1)),
176                        Player::Right if n.numerator() < 0 => Some(Dyadic::from(n.numerator() + 1)),
177                        _ => None,
178                    }
179                } else {
180                    let numerator = (n.numerator() >> 1) + i64::from(player == Player::Right);
181                    Some(Dyadic::new(numerator, n.exponent() - 1))
182                };
183                (option.map(Self::from), None, &[][..])
184            }
185            GameValueNode::NumberUpNimber(q, 0, n) => (None, Some((*q, *n)), &[][..]),
186            GameValueNode::NumberUpNimber(q, k, 1)
187                if matches!((*k, player), (1, Player::Left) | (-1, Player::Right)) =>
188            {
189                (None, Some((*q, 2)), &[][..])
190            }
191            GameValueNode::NumberUpNimber(q, k, n) => {
192                let sign = if *k > 0 { 1 } else { -1 };
193                let moves_to_number = (*k > 0) == (player == Player::Left);
194                let option = if moves_to_number {
195                    Self::from(*q)
196                } else {
197                    Self::number_up_nimber(*q, k - sign, n ^ 1)
198                };
199                (Some(option), None, &[][..])
200            }
201            GameValueNode::Switches(value) => {
202                let temperatures = &value.temperatures[value.start..];
203                let t = if player == Player::Left {
204                    temperatures[0]
205                } else {
206                    -temperatures[0]
207                };
208                let option = if temperatures.len() == 1 {
209                    Self::number_up_nimber(value.number + t, value.up, value.nimber)
210                } else {
211                    Self(GameValueNode::Switches(Rc::new(GameValueSwitches {
212                        number: value.number + t,
213                        start: value.start + 1,
214                        fingerprint: value.fingerprint ^ Self::temperature_hash(temperatures[0]),
215                        ..(**value).clone()
216                    })))
217                };
218                (Some(option), None, &[][..])
219            }
220            GameValueNode::Options(q, options) => {
221                offset = *q;
222                let (left, right) = &**options;
223                let moves = if player == Player::Left { left } else { right };
224                (None, None, moves.as_slice())
225            }
226        };
227        single
228            .into_iter()
229            .chain(
230                nimbers
231                    .into_iter()
232                    .flat_map(|(q, n)| (0..n).map(move |m| Self::number_up_nimber(q, 0, m))),
233            )
234            .chain(general.iter().map(move |g| g.translated(offset)))
235    }
236
237    fn from_options_memoized(
238        mut left: Vec<Self>,
239        mut right: Vec<Self>,
240        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
241    ) -> Self {
242        loop {
243            if left.iter().chain(&right).all(|g| g.as_number().is_some()) {
244                let l = left.iter().filter_map(Self::as_number).max();
245                let r = right.iter().filter_map(Self::as_number).min();
246                if let Some(n) = Dyadic::simplest_between(l, r) {
247                    return n.into();
248                }
249                let (l, r) = (l.unwrap(), r.unwrap());
250                if l == r {
251                    return Self::number_up_nimber(l, 0, 1);
252                }
253                let (sum, difference) = (l + r, l - r);
254                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
255                return Self::from_switches(
256                    Dyadic::new(sum.numerator(), sum.exponent() + 1),
257                    0,
258                    0,
259                    vec![temperature],
260                    Self::temperature_hash(temperature),
261                );
262            }
263            if !right.is_empty()
264                && let Some((number, _)) = left.first().and_then(Self::as_number_nimber)
265            {
266                let nimber = |g: &Self| {
267                    g.as_number_nimber()
268                        .filter(|&(q, _)| q == number)
269                        .map(|(_, n)| n)
270                };
271                let l: Option<Vec<_>> = left.iter().map(nimber).collect();
272                let r: Option<Vec<_>> = right.iter().map(nimber).collect();
273                if let (Some(l), Some(r)) = (l, r) {
274                    let value = game_mex(l);
275                    if value == game_mex(r) {
276                        return Self::number_up_nimber(number, 0, value);
277                    }
278                }
279            }
280            for (moves, replies, sign) in [(&left, &right, 1), (&right, &left, -1)] {
281                if replies.len() != 1 {
282                    continue;
283                }
284                if let Some((q, k, n)) = replies[0].as_number_up_nimber() {
285                    if moves.len() == 1
286                        && moves[0].as_number() == Some(q)
287                        && (k == 0 || k.signum() == sign)
288                    {
289                        return Self::number_up_nimber(q, k + sign, n ^ 1);
290                    }
291                    if k == 0 && n == 0 && moves.len() == 2 {
292                        let a = moves[0].as_number_nimber();
293                        let b = moves[1].as_number_nimber();
294                        if (a == Some((q, 0)) && b == Some((q, 1)))
295                            || (a == Some((q, 1)) && b == Some((q, 0)))
296                        {
297                            return Self::number_up_nimber(q, sign, 1);
298                        }
299                    }
300                }
301            }
302            if left.len() == 1
303                && right.len() == 1
304                && let (Some((a, k, n, ts)), Some((b, l, m, us))) =
305                    (left[0].as_switch_sum(), right[0].as_switch_sum())
306                && k == l
307                && n == m
308                && ts == us
309                && a > b
310            {
311                let (sum, difference) = (a + b, a - b);
312                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
313                if ts.first().is_none_or(|&t| temperature > t) {
314                    return Self::from_switches(
315                        Dyadic::new(sum.numerator(), sum.exponent() + 1),
316                        k,
317                        n,
318                        std::iter::once(temperature)
319                            .chain(ts.iter().copied())
320                            .collect(),
321                        Self::temperature_hash(temperature) ^ left[0].switch_hash(),
322                    );
323                }
324            }
325            let count = left.len() + right.len();
326            Self::remove_dominated(&mut left, Player::Left, cache);
327            Self::remove_dominated(&mut right, Player::Right, cache);
328            if count != left.len() + right.len() {
329                continue;
330            }
331            let options = Rc::new((left, right));
332            let game = Self(GameValueNode::Options(0.into(), options.clone()));
333            // Bypasses preserve the game, so all checks use the same candidate.
334            let mut reversible = Vec::new();
335            for player in [Player::Left, Player::Right] {
336                let moves = match player {
337                    Player::Left => &options.0,
338                    Player::Right => &options.1,
339                };
340                for (i, g) in moves.iter().enumerate() {
341                    if let Some((q, n)) = g.as_number_nimber()
342                        && n > 1
343                    {
344                        let number = Self::from(q);
345                        let (lower, upper) = match player {
346                            Player::Left => (&game, &number),
347                            Player::Right => (&number, &game),
348                        };
349                        // A strict inequality against q excludes every reply q + *m.
350                        if lower.leq_memoized(upper, cache) && !upper.leq_memoized(lower, cache) {
351                            continue;
352                        }
353                    }
354                    if let Some(reply) = g.options(player.opponent()).find(|r| match player {
355                        Player::Left => r.leq_memoized(&game, cache),
356                        Player::Right => game.leq_memoized(r, cache),
357                    }) {
358                        reversible.push((player, i, reply));
359                    }
360                }
361            }
362            if reversible.is_empty() {
363                return game;
364            }
365            drop(game);
366            (left, right) = Rc::unwrap_or_clone(options);
367            for (player, i, reply) in reversible.into_iter().rev() {
368                let moves = if player == Player::Left {
369                    &mut left
370                } else {
371                    &mut right
372                };
373                moves.remove(i);
374                moves.extend(reply.options(player));
375            }
376        }
377    }
Source

pub fn simplest_between(left: Option<Self>, right: Option<Self>) -> Option<Self>

The simplest number strictly between the bounds; absent bounds are unbounded. Returns None for an empty interval.

Examples found in repository?
crates/competitive/src/algorithm/game_analyzer/value.rs (line 246)
237    fn from_options_memoized(
238        mut left: Vec<Self>,
239        mut right: Vec<Self>,
240        cache: &mut HashMap<GameValueNode, HashMap<GameValueNode, bool>>,
241    ) -> Self {
242        loop {
243            if left.iter().chain(&right).all(|g| g.as_number().is_some()) {
244                let l = left.iter().filter_map(Self::as_number).max();
245                let r = right.iter().filter_map(Self::as_number).min();
246                if let Some(n) = Dyadic::simplest_between(l, r) {
247                    return n.into();
248                }
249                let (l, r) = (l.unwrap(), r.unwrap());
250                if l == r {
251                    return Self::number_up_nimber(l, 0, 1);
252                }
253                let (sum, difference) = (l + r, l - r);
254                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
255                return Self::from_switches(
256                    Dyadic::new(sum.numerator(), sum.exponent() + 1),
257                    0,
258                    0,
259                    vec![temperature],
260                    Self::temperature_hash(temperature),
261                );
262            }
263            if !right.is_empty()
264                && let Some((number, _)) = left.first().and_then(Self::as_number_nimber)
265            {
266                let nimber = |g: &Self| {
267                    g.as_number_nimber()
268                        .filter(|&(q, _)| q == number)
269                        .map(|(_, n)| n)
270                };
271                let l: Option<Vec<_>> = left.iter().map(nimber).collect();
272                let r: Option<Vec<_>> = right.iter().map(nimber).collect();
273                if let (Some(l), Some(r)) = (l, r) {
274                    let value = game_mex(l);
275                    if value == game_mex(r) {
276                        return Self::number_up_nimber(number, 0, value);
277                    }
278                }
279            }
280            for (moves, replies, sign) in [(&left, &right, 1), (&right, &left, -1)] {
281                if replies.len() != 1 {
282                    continue;
283                }
284                if let Some((q, k, n)) = replies[0].as_number_up_nimber() {
285                    if moves.len() == 1
286                        && moves[0].as_number() == Some(q)
287                        && (k == 0 || k.signum() == sign)
288                    {
289                        return Self::number_up_nimber(q, k + sign, n ^ 1);
290                    }
291                    if k == 0 && n == 0 && moves.len() == 2 {
292                        let a = moves[0].as_number_nimber();
293                        let b = moves[1].as_number_nimber();
294                        if (a == Some((q, 0)) && b == Some((q, 1)))
295                            || (a == Some((q, 1)) && b == Some((q, 0)))
296                        {
297                            return Self::number_up_nimber(q, sign, 1);
298                        }
299                    }
300                }
301            }
302            if left.len() == 1
303                && right.len() == 1
304                && let (Some((a, k, n, ts)), Some((b, l, m, us))) =
305                    (left[0].as_switch_sum(), right[0].as_switch_sum())
306                && k == l
307                && n == m
308                && ts == us
309                && a > b
310            {
311                let (sum, difference) = (a + b, a - b);
312                let temperature = Dyadic::new(difference.numerator(), difference.exponent() + 1);
313                if ts.first().is_none_or(|&t| temperature > t) {
314                    return Self::from_switches(
315                        Dyadic::new(sum.numerator(), sum.exponent() + 1),
316                        k,
317                        n,
318                        std::iter::once(temperature)
319                            .chain(ts.iter().copied())
320                            .collect(),
321                        Self::temperature_hash(temperature) ^ left[0].switch_hash(),
322                    );
323                }
324            }
325            let count = left.len() + right.len();
326            Self::remove_dominated(&mut left, Player::Left, cache);
327            Self::remove_dominated(&mut right, Player::Right, cache);
328            if count != left.len() + right.len() {
329                continue;
330            }
331            let options = Rc::new((left, right));
332            let game = Self(GameValueNode::Options(0.into(), options.clone()));
333            // Bypasses preserve the game, so all checks use the same candidate.
334            let mut reversible = Vec::new();
335            for player in [Player::Left, Player::Right] {
336                let moves = match player {
337                    Player::Left => &options.0,
338                    Player::Right => &options.1,
339                };
340                for (i, g) in moves.iter().enumerate() {
341                    if let Some((q, n)) = g.as_number_nimber()
342                        && n > 1
343                    {
344                        let number = Self::from(q);
345                        let (lower, upper) = match player {
346                            Player::Left => (&game, &number),
347                            Player::Right => (&number, &game),
348                        };
349                        // A strict inequality against q excludes every reply q + *m.
350                        if lower.leq_memoized(upper, cache) && !upper.leq_memoized(lower, cache) {
351                            continue;
352                        }
353                    }
354                    if let Some(reply) = g.options(player.opponent()).find(|r| match player {
355                        Player::Left => r.leq_memoized(&game, cache),
356                        Player::Right => game.leq_memoized(r, cache),
357                    }) {
358                        reversible.push((player, i, reply));
359                    }
360                }
361            }
362            if reversible.is_empty() {
363                return game;
364            }
365            drop(game);
366            (left, right) = Rc::unwrap_or_clone(options);
367            for (player, i, reply) in reversible.into_iter().rev() {
368                let moves = if player == Player::Left {
369                    &mut left
370                } else {
371                    &mut right
372                };
373                moves.remove(i);
374                moves.extend(reply.options(player));
375            }
376        }
377    }

Trait Implementations§

Source§

impl<T> Add for Dyadic<T>
where T: Signed,

Source§

type Output = Dyadic<T>

The resulting type after applying the + operator.
Source§

fn add(self, rhs: Self) -> Self

Performs the + operation. Read more
Source§

impl<T: Clone> Clone for Dyadic<T>

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<T: Copy> Copy for Dyadic<T>

Source§

impl<T> Debug for Dyadic<T>
where T: Signed,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<T> Default for Dyadic<T>
where T: Signed,

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<T> Display for Dyadic<T>
where T: Signed,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<T: Eq> Eq for Dyadic<T>

Source§

impl From<Dyadic<i64>> for GameValue

Source§

fn from(value: Dyadic<i64>) -> Self

Converts to this type from the input type.
Source§

impl<T> From<T> for Dyadic<T>
where T: Signed,

Source§

fn from(numerator: T) -> Self

Converts to this type from the input type.
Source§

impl<T: Hash> Hash for Dyadic<T>

Source§

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher. Read more
1.3.0 · Source§

fn hash_slice<H>(data: &[Self], state: &mut H)
where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher. Read more
Source§

impl<T> Neg for Dyadic<T>
where T: Signed,

Source§

type Output = Dyadic<T>

The resulting type after applying the - operator.
Source§

fn neg(self) -> Self

Performs the unary - operation. Read more
Source§

impl<T> One for Dyadic<T>
where T: Signed,

Source§

fn one() -> Self

Source§

fn is_one(&self) -> bool
where Self: PartialEq,

Source§

fn set_one(&mut self)

Source§

impl<T> Ord for Dyadic<T>
where T: Signed,

Source§

fn cmp(&self, rhs: &Self) -> Ordering

This method returns an Ordering between self and other. Read more
1.21.0 (const: unstable) · Source§

fn max(self, other: Self) -> Self
where Self: Sized,

Compares and returns the maximum of two values. Read more
1.21.0 (const: unstable) · Source§

fn min(self, other: Self) -> Self
where Self: Sized,

Compares and returns the minimum of two values. Read more
1.50.0 (const: unstable) · Source§

fn clamp(self, min: Self, max: Self) -> Self
where Self: Sized,

Restrict a value to a certain interval. Read more
Source§

fn clamp_to<R>(self, range: R) -> Self
where Self: Sized, R: ClampBounds<Self>,

🔬This is a nightly-only experimental API. (clamp_to)
Restrict a value to a certain range. Read more
Source§

impl<T: PartialEq> PartialEq for Dyadic<T>

Source§

fn eq(&self, other: &Self) -> bool

Equality operator ==. Read more
1.0.0 (const: unstable) · Source§

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=. Read more
Source§

impl<T> PartialOrd for Dyadic<T>
where T: Signed,

Source§

fn partial_cmp(&self, rhs: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists. Read more
1.0.0 (const: unstable) · Source§

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator. Read more
1.0.0 (const: unstable) · Source§

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator. Read more
1.0.0 (const: unstable) · Source§

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator. Read more
1.0.0 (const: unstable) · Source§

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator. Read more
Source§

impl<T: PartialEq> StructuralPartialEq for Dyadic<T>

Source§

impl<T> Sub for Dyadic<T>
where T: Signed,

Source§

type Output = Dyadic<T>

The resulting type after applying the - operator.
Source§

fn sub(self, rhs: Self) -> Self

Performs the - operation. Read more
Source§

impl<T> Zero for Dyadic<T>
where T: Signed,

Source§

fn zero() -> Self

Source§

fn is_zero(&self) -> bool
where Self: PartialEq,

Source§

fn set_zero(&mut self)

Auto Trait Implementations§

§

impl<T> Forget for Dyadic<T>

§

impl<T> Freeze for Dyadic<T>
where T: Freeze,

§

impl<T> Move for Dyadic<T>

§

impl<T> RefUnwindSafe for Dyadic<T>
where T: RefUnwindSafe,

§

impl<T> Send for Dyadic<T>
where T: Send,

§

impl<T> Sync for Dyadic<T>
where T: Sync,

§

impl<T> Unpin for Dyadic<T>
where T: Unpin,

§

impl<T> UnsafeUnpin for Dyadic<T>
where T: UnsafeUnpin,

§

impl<T> UnwindSafe for Dyadic<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> AsTotalOrd for T
where T: PartialOrd,

Source§

fn as_total_ord(&self) -> TotalOrd<&T>

Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> PartialOrdExt for T
where T: PartialOrd,

Source§

fn chmin(&mut self, other: T)

Source§

fn chmax(&mut self, other: T)

Source§

fn minmax(self, other: T) -> (T, T)

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T> ToString for T
where T: Display + ?Sized,

Source§

fn to_string(&self) -> String

Converts the given value to a String. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.