three_style_lib/moves/
alg.rs

1use crate::{
2    error::Error,
3    moves::core::{Inverse, Move, MoveKind},
4};
5use std::{collections::BTreeMap, fmt, ops::Add, str::FromStr};
6
7#[derive(Debug, Default, PartialEq, Clone)]
8pub struct Alg(Vec<Move>);
9
10impl Alg {
11    pub fn new<T>(moves: T) -> Self
12    where
13        T: IntoIterator<Item = Move>,
14    {
15        Self(moves.into_iter().collect())
16    }
17
18    pub fn len(&self) -> usize {
19        self.0.len()
20    }
21
22    pub fn is_empty(&self) -> bool {
23        self.len() == 0
24    }
25
26    pub fn iter(&self) -> impl Iterator<Item = &Move> {
27        self.0.iter()
28    }
29
30    pub fn reduce(self) -> Self {
31        let mut moves = Vec::new();
32        let mut stack = Vec::new();
33        let mut group: BTreeMap<MoveKind, Move> = BTreeMap::new();
34
35        for m in self.0 {
36            let prev_value = group.remove(&m.kind);
37            let has_prev_value = prev_value.is_some();
38
39            let result = match prev_value {
40                Some(n) => n * m,
41                None => group.contains_key(&m.kind.inverse()).then_some(m),
42            };
43
44            if let Some(value) = result {
45                group.insert(m.kind, value);
46            }
47            if result.is_some() || has_prev_value {
48                continue;
49            }
50
51            while let Some((_, m)) = group.pop_first() {
52                moves.push(m);
53            }
54
55            group.insert(m.kind, m);
56        }
57
58        moves.extend(group.into_values());
59
60        for m in moves {
61            if let Some(&last) = stack.last() {
62                if let Some(result) = last * m {
63                    stack.pop();
64                    stack.push(result);
65                    continue;
66                }
67            }
68
69            stack.push(m);
70        }
71
72        Alg::new(stack)
73    }
74}
75
76impl Inverse for Alg {
77    fn inverse(&self) -> Self {
78        Self(self.0.iter().rev().map(Move::inverse).collect())
79    }
80}
81
82impl IntoIterator for Alg {
83    type Item = Move;
84    type IntoIter = std::vec::IntoIter<Move>;
85
86    fn into_iter(self) -> Self::IntoIter {
87        self.0.into_iter()
88    }
89}
90
91impl FromStr for Alg {
92    type Err = Error;
93
94    fn from_str(s: &str) -> Result<Self, Self::Err> {
95        let moves = s
96            .split_whitespace()
97            .map(Move::from_str)
98            .collect::<Result<Vec<_>, _>>();
99
100        moves.map(Self::new)
101    }
102}
103
104impl Add<Self> for Alg {
105    type Output = Self;
106
107    fn add(self, rhs: Self) -> Self::Output {
108        Self(self.0.into_iter().chain(rhs).collect())
109    }
110}
111
112impl Add<&Alg> for &Alg {
113    type Output = Alg;
114
115    fn add(self, rhs: &Alg) -> Self::Output {
116        self.clone() + rhs.clone()
117    }
118}
119
120impl Add<&Alg> for Alg {
121    type Output = Self;
122
123    fn add(self, rhs: &Alg) -> Self::Output {
124        self + rhs.clone()
125    }
126}
127
128impl fmt::Display for Alg {
129    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
130        let s = self
131            .0
132            .iter()
133            .map(|m| m.to_string())
134            .collect::<Vec<_>>()
135            .join(" ");
136
137        write!(f, "{s}")
138    }
139}
140
141#[macro_export]
142macro_rules! alg {
143    ($moves: expr) => {{
144        use std::str::FromStr;
145        use $crate::moves::Alg;
146        Alg::from_str($moves).unwrap()
147    }};
148}
149
150#[cfg(test)]
151mod tests {
152    use super::*;
153    use crate::moves::{MoveCount, MoveKind};
154
155    #[test]
156    fn test_basics() {
157        let alg = alg!("R U R' U'");
158        let inverse = alg.inverse();
159
160        assert_eq!(
161            alg,
162            Alg(vec![
163                Move::new(MoveKind::R, MoveCount::Simple),
164                Move::new(MoveKind::U, MoveCount::Simple),
165                Move::new(MoveKind::R, MoveCount::Prime),
166                Move::new(MoveKind::U, MoveCount::Prime)
167            ])
168        );
169
170        assert_eq!(
171            inverse,
172            Alg(vec![
173                Move::new(MoveKind::U, MoveCount::Simple),
174                Move::new(MoveKind::R, MoveCount::Simple),
175                Move::new(MoveKind::U, MoveCount::Prime),
176                Move::new(MoveKind::R, MoveCount::Prime)
177            ])
178        );
179    }
180
181    #[test]
182    fn test_move_reduction() {
183        let alg = alg!("U D2 D U'").reduce();
184        let expected = alg!("D'");
185        assert_eq!(expected, alg);
186
187        let alg = alg!("R U R' U D' U2").reduce();
188        let expected = alg!("R U R' U' D''");
189        assert_eq!(expected, alg);
190
191        let alg = alg!("U2 U2 D D' R").reduce();
192        let expected = alg!("R");
193        assert_eq!(expected, alg);
194
195        let alg = alg!("M R' U r R'").reduce();
196        let expected = alg!("r' U M'");
197        assert_eq!(expected, alg);
198    }
199}
three_style_lib/moves/alg.rs

three_style_lib/moves/
alg.rs
