1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

use crate::game::{Base, Playable, Singleplayer, SingleplayerGameBuilder};

use async_trait::async_trait;
use std::cmp::Ordering;
use std::fmt;
use std::hash::Hasher;
use std::hash::*;

const K: usize = 9;
const WS_RULE: bool = true;

/// Weak schur number game.
#[derive(Clone, Eq)]
pub struct WeakSchurNumber {
    partitions: [Vec<usize>; K],
    last_value: usize,
}

impl fmt::Debug for WeakSchurNumber {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        writeln!(f, "Partitions")?;
        for i in 0..K {
            writeln!(f, "{:?}", self.partitions[i])?;
        }
        write!(f, "")
    }
}

impl WeakSchurNumber {
    /* assumes values is in increasing order. */
    fn is_valid(last_value: usize, values: &[usize]) -> bool {
        let mut begin = 0;
        let mut end = values.len() as isize - 1;
        let target = last_value + 1;

        while begin < end {
            let sum = values[begin as usize] + values[end as usize];
            match sum.cmp(&target) {
                Ordering::Equal => return false,
                Ordering::Less => begin += 1,
                Ordering::Greater => end -= 1,
            };
        }
        true
    }

    fn best_sequence(values: &[usize]) -> usize {
        let mut best_length = 0;
        let mut cur_length = 0;

        for i in 1..values.len() {
            if values[i] == values[i - 1] + 1 {
                cur_length += 1;
                if cur_length + 1 > best_length {
                    best_length = cur_length + 1
                };
            } else {
                cur_length = 0
            }
        }
        best_length
    }

    fn score(&self) -> f32 {
        self.partitions
            .iter()
            .map(|p| Self::best_sequence(&p))
            .max()
            .unwrap() as f32
    }
}

impl Singleplayer for WeakSchurNumber {}

/// Weak schur number game builder
#[derive(Clone)]
pub struct WeakSchurNumberBuilder {}

#[async_trait]
impl SingleplayerGameBuilder for WeakSchurNumberBuilder {
    type G = WeakSchurNumber;
    async fn create(&self) -> WeakSchurNumber {
        let partitions = Default::default();
        let last_value = 0;

        WeakSchurNumber {
            partitions,
            last_value,
        }
    }
}

impl Base for WeakSchurNumber {
    type Move = usize;

    fn possible_moves(&self) -> Vec<Self::Move> {
        let valid_moves = self
            .partitions
            .iter()
            .enumerate()
            .filter(move |(_, partition)| {
                WeakSchurNumber::is_valid(self.last_value + 1, partition)
            });

        if WS_RULE {
            if let Some((idx, _)) = valid_moves
                .clone()
                .find(|(_, partition)| partition.last() == Some(&self.last_value))
            {
                return vec![idx];
            }
        }

        valid_moves.map(|(i, _)| i).collect()
    }
}

impl Hash for WeakSchurNumber {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.partitions.hash(state)
    }
}

impl PartialEq for WeakSchurNumber {
    fn eq(&self, other: &WeakSchurNumber) -> bool {
        self.partitions.eq(&other.partitions)
    }
}

#[async_trait]
impl Playable for WeakSchurNumber {
    #[allow(clippy::trivially_copy_pass_by_ref)]
    async fn play(&mut self, m: &<Self as Base>::Move) -> f32 {
        self.last_value += 1;
        self.partitions[*m].push(self.last_value);
        if self.is_finished() {
            self.score()
        } else {
            0.
        }
    }
}