rusty_rubik/
cube.rs

1//! A module providing functions to interact with the
2//! structure and state of the Rubik's Cube.
3//!
4//! The state of the Rubik's Cube is internally represented
5//! by four properties of the cube: corner permutation, corner
6//! orientation, edge permutation, and edge orientation. A tuple
7//! of these four properties (with correct parity relations)
8//! uniquely determines the state of the cube.
9
10use strum_macros::EnumString;
11
12/// An enum for the faces of the Rubik's Cube.
13///
14/// - U: top face
15/// - D: bottom face
16/// - L: left face
17/// - R: right face
18/// - F: front face
19/// - B: back face
20#[derive(PartialEq, Eq, EnumString, Debug, Clone, Copy)]
21pub enum BaseMoveToken {
22    U,
23    D,
24    L,
25    R,
26    F,
27    B,
28}
29
30impl std::fmt::Display for BaseMoveToken {
31    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
32        write!(f, "{:?}", self)
33    }
34}
35
36/// Represents the direction which to turn a face. `Prime` represents
37/// a counter-clockwise rotation of a face, and `Double` represents
38/// a 180 degree rotation of a face.
39#[derive(PartialEq, Eq, Debug, Clone, Copy)]
40pub enum Direction {
41    Normal,
42    Prime,
43    Double,
44}
45
46impl std::fmt::Display for Direction {
47    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
48        match self {
49            Direction::Normal => write!(f, ""),
50            Direction::Prime => write!(f, "'"),
51            Direction::Double => write!(f, "2"),
52        }
53    }
54}
55
56/// An instantiation of a certain face equipped with a direction.
57#[derive(PartialEq, Eq, Debug, Clone, Copy)]
58pub struct MoveInstance {
59    pub basemove: BaseMoveToken,
60    pub dir: Direction,
61}
62
63impl MoveInstance {
64    pub fn new(basemove: BaseMoveToken, dir: Direction) -> Self {
65        Self { basemove, dir }
66    }
67
68    pub fn invert(&self) -> Self {
69        Self::new(
70            self.basemove,
71            match self.dir {
72                Direction::Normal => Direction::Prime,
73                Direction::Prime => Direction::Normal,
74                x => x,
75            },
76        )
77    }
78}
79
80impl std::fmt::Display for MoveInstance {
81    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
82        write!(f, "{}{}", self.basemove, self.dir)
83    }
84}
85
86/// A struct representing sequences of moves, used for representing
87/// scramble sequences and solution sequences.
88pub struct MoveSequence(pub Vec<MoveInstance>);
89
90impl MoveSequence {
91    pub fn get_moves(&self) -> &Vec<MoveInstance> {
92        &self.0
93    }
94    pub fn get_moves_mut(&mut self) -> &mut Vec<MoveInstance> {
95        &mut self.0
96    }
97
98    pub fn invert(&self) -> Self {
99        let mut moves = vec![];
100        for m in self.get_moves().iter().rev() {
101            moves.push(m.invert());
102        }
103        MoveSequence(moves)
104    }
105}
106
107impl std::fmt::Display for MoveSequence {
108    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
109        let mut strs = vec![];
110        for m in self.get_moves().iter() {
111            strs.push(m.to_string());
112        }
113        write!(f, "{}", strs.join(" "))
114    }
115}
116
117/// A struct representing a commutator, taking the form of a tuple.
118///
119/// If the first element of this tuple is $A$, and the second is $B$, then
120/// the commutator represented by this is $[A,B] = ABA^{-1}B^{-1}$.
121///
122/// One can create a Commutator object as such:
123/// ```
124/// use rusty_rubik::cube::*;
125/// use rusty_rubik::cube_move;
126///
127/// fn main() {
128///     let a = MoveSequence(vec![
129///         cube_move!(R, Normal),
130///         cube_move!(U, Prime),
131///         cube_move!(R, Prime),
132///     ]);
133///     let b = MoveSequence(vec![cube_move!(D, Normal)]);
134///
135///     // commutator representing [R U' R', D] = R U' R' D R U R' D'
136///     let comm = Commutator(a,b);
137///     
138/// }
139/// ```
140pub struct Commutator(pub MoveSequence, pub MoveSequence);
141
142/// A struct representing a conjugate, taking the form of a tuple.
143///
144/// If the first element of this tuple is $C$, and the second is a commutator $B$,
145/// then the conjugate represented by this is $[C: B] = CBC^{-1}$.
146///
147/// One can create a Conjugate object as such:
148///
149/// ```
150/// use rusty_rubik::cube::*;
151/// use rusty_rubik::cube_move;
152///
153/// fn main() {
154///     let c = MoveSequence(vec![
155///         cube_move!(R, Normal),
156///     ]);
157///     let a = MoveSequence(vec![
158///         cube_move!(R, Normal),
159///         cube_move!(D, Normal),
160///         cube_move!(R, Prime),
161///     ]);
162///     let b = MoveSequence(vec![
163///         cube_move!(U, Double),
164///     ]);
165///
166///     // conjugate representing [R: [R D R', U2]] = R2 D R' U2 R D' R' U2 R'
167///     let comm = Commutator(a,b);
168///     
169/// }
170/// ```
171pub struct Conjugate(pub MoveSequence, pub Commutator);
172
173/// An internal set of permutation vectors representing what action
174/// is done to a configuration of the Rubik's Cube when a move is applied.
175///
176/// The order of the corners and edges is as follows:
177/// - Corners: UBL UBR UFR UFL DFL DFR DBR DBL
178/// - Edges: UB UR UF UL BL BR FR FL DF DR DB DL
179struct Move {
180    pub cp_change: [u8; 8], // a[i] gives the position that i goes to
181    pub co_change: [i8; 8],
182    pub ep_change: [u8; 12],
183    pub eo_change: [i8; 12],
184}
185
186/// A shorthand macro that can be used to construct MoveInstances.
187///
188/// ```
189/// use rusty_rubik::cube::*;
190/// use rusty_rubik::cube_move;
191///
192/// fn main() {
193///     let r_prime: MoveInstance = cube_move!(R, Prime);
194///     let u2: MoveInstance = cube_move!(U, Double);
195/// }
196/// ```
197#[macro_export]
198macro_rules! cube_move {
199    ($basemove: ident, $dir:ident) => {{
200        MoveInstance {
201            basemove: BaseMoveToken::$basemove,
202            dir: Direction::$dir,
203        }
204    }};
205}
206
207macro_rules! apply_permutation {
208    ($og_state: expr, $delta: expr) => {{
209        if $og_state.len() != $delta.len() {
210            panic!("Size mismatch in applying permutation");
211        } else {
212            let mut new_array = $og_state.clone();
213            for i in 0..$og_state.len() {
214                new_array[$delta[i] as usize] = $og_state[i];
215            }
216            new_array
217        }
218    }};
219}
220
221macro_rules! apply_orientation {
222    ($og_state: expr, $delta: expr, $num_orientations: expr) => {{
223        if $og_state.len() != $delta.len() {
224            panic!("Size mismatch in applying orientation");
225        } else {
226            let mut new_array = $og_state.clone();
227            for i in 0..$og_state.len() {
228                new_array[i] = (($og_state[i] + $delta[i] + $num_orientations) % $num_orientations);
229                if new_array[i] == 2 {
230                    new_array[i] = -1;
231                }
232            }
233            new_array
234        }
235    }};
236}
237
238pub(crate) fn get_basemove_pos(token: BaseMoveToken) -> u8 {
239    match token {
240        BaseMoveToken::U => 5,
241        BaseMoveToken::D => 4,
242        BaseMoveToken::L => 3,
243        BaseMoveToken::R => 2,
244        BaseMoveToken::F => 1,
245        BaseMoveToken::B => 0,
246    }
247}
248
249fn get_antipode(token: BaseMoveToken) -> BaseMoveToken {
250    match token {
251        BaseMoveToken::U => BaseMoveToken::D,
252        BaseMoveToken::D => BaseMoveToken::U,
253        BaseMoveToken::L => BaseMoveToken::R,
254        BaseMoveToken::R => BaseMoveToken::L,
255        BaseMoveToken::F => BaseMoveToken::B,
256        BaseMoveToken::B => BaseMoveToken::F,
257    }
258}
259
260// bitvector: [UDLRFB], 0 means it's allowed
261pub(crate) fn get_allowed_post_moves(prev_bv: u8, last_move: Option<BaseMoveToken>) -> u8 {
262    if let Some(lm) = last_move {
263        let antipode = get_antipode(lm);
264        if prev_bv & (1 << get_basemove_pos(antipode)) != 0 {
265            // then the antipode was already applied
266            (1 << get_basemove_pos(lm)) + (1 << get_basemove_pos(antipode))
267        } else {
268            1 << get_basemove_pos(lm)
269        }
270    } else {
271        0
272    }
273}
274
275/// Determines which moves are allowed after the given move sequence,
276/// to speed up solver methods.
277///
278/// This is to avoid double rotations of faces (e.g. R R') and
279/// excessive rotations of antipodal faces (e.g. R L R can be simplified
280/// to R2 L).
281// TODO: refactor into struct method
282pub fn allowed_moves_after_seq(moves: &MoveSequence) -> u8 {
283    let sol = moves.get_moves();
284    match sol.len() {
285        0 => 0,
286        1 => {
287            let last_move = sol[sol.len() - 1];
288            1 << get_basemove_pos(last_move.basemove)
289        }
290        _ => {
291            let last_move = sol[sol.len() - 1];
292            let second_to_last = sol[sol.len() - 2];
293            if get_antipode(last_move.basemove) == second_to_last.basemove {
294                (1 << get_basemove_pos(last_move.basemove))
295                    + (1 << get_basemove_pos(second_to_last.basemove))
296            } else {
297                1 << get_basemove_pos(last_move.basemove)
298            }
299        }
300    }
301}
302
303/// The underlying struct for representing a configuration of the Rubik's Cube.
304#[derive(Clone, Debug, Hash, PartialEq, Eq)]
305pub struct CubeState {
306    pub cp: [u8; 8],
307    pub co: [i8; 8],
308    pub ep: [u8; 12],
309    pub eo: [i8; 12],
310}
311
312impl Default for CubeState {
313    fn default() -> CubeState {
314        CubeState {
315            cp: [0, 1, 2, 3, 4, 5, 6, 7],
316            co: [0 as i8; 8],
317            ep: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
318            eo: [0 as i8; 12],
319        }
320    }
321}
322
323fn get_move_matrix(mov: &BaseMoveToken) -> Move {
324    match mov {
325        BaseMoveToken::U => MOVE_U,
326        BaseMoveToken::D => MOVE_D,
327        BaseMoveToken::L => MOVE_L,
328        BaseMoveToken::R => MOVE_R,
329        BaseMoveToken::F => MOVE_F,
330        BaseMoveToken::B => MOVE_B,
331    }
332}
333
334fn factorial(num: u32) -> u32 {
335    match num {
336        0 => 1,
337        1 => 1,
338        _ => factorial(num - 1) * num,
339    }
340}
341
342// range:
343// corners: [0, 8! - 1]
344// edges: [0, 12! - 1]
345fn get_index_of_permutation(perm: &[u8]) -> u32 {
346    // 2 bytes suffice for 12!
347    let mut fin = 0;
348    for i in 0..perm.len() {
349        let mut res = 0;
350        for j in (i + 1)..perm.len() {
351            if perm[j] < perm[i] {
352                res += 1;
353            }
354        }
355        fin += res * factorial((perm.len() - i - 1) as u32);
356    }
357    fin as u32
358}
359
360// range:
361// corners: [0, 3^7 - 1]
362// edges: [0, 2^11 - 1]
363fn get_index_of_orientation(ori: &[i8], num_orientations: u8) -> u16 {
364    let mut result = 0;
365    for (i, val) in ori.iter().enumerate() {
366        if i == ori.len() - 1 {
367            break;
368        }
369        let pos = (val + num_orientations as i8) % num_orientations as i8;
370        result += pos as u16;
371        if i != ori.len() - 2 {
372            result *= num_orientations as u16;
373        }
374    }
375    result
376}
377
378/// Returns a triple representing a compressed representation of a Rubik's
379/// Cube configuration.
380///
381/// The elements of the triple consist of a corner index, an
382/// edge orientation (EO) index, and an edge permutation (EP) index.
383// TODO: refactor into struct method
384pub fn get_index_of_state(state: &CubeState) -> (u32, u16, u64) {
385    let cp_index = get_index_of_permutation(&state.cp);
386    let co_index = get_index_of_orientation(&state.co, 3);
387    let corner_index = cp_index * u32::pow(3, 7) + (co_index as u32);
388    let ep_index = get_index_of_permutation(&state.ep) as u64;
389    let eo_index = get_index_of_orientation(&state.eo, 2);
390    (corner_index, eo_index, ep_index)
391}
392
393impl CubeState {
394    fn apply_basemove(&self, m: &BaseMoveToken) -> Self {
395        let mov = get_move_matrix(m);
396        let oriented_corners = apply_orientation!(&self.co, &mov.co_change, 3);
397        let oriented_edges = apply_orientation!(&self.eo, &mov.eo_change, 2);
398        CubeState {
399            cp: apply_permutation!(&self.cp, &mov.cp_change),
400            co: apply_permutation!(oriented_corners, &mov.cp_change),
401            ep: apply_permutation!(&self.ep, &mov.ep_change),
402            eo: apply_permutation!(oriented_edges, &mov.ep_change),
403        }
404    }
405
406    /// Applies a move to a Rubik's Cube configuration.
407    pub fn apply_move_instance(&self, m: &MoveInstance) -> Self {
408        let num_turns = match &m.dir {
409            Direction::Normal => 1,
410            Direction::Prime => 3,
411            Direction::Double => 2,
412        };
413        (0..num_turns).fold(self.clone(), |acc, _| acc.apply_basemove(&m.basemove))
414    }
415
416    /// Applies a sequence of moves, in order to a Rubik's Cube configuration.
417    pub fn apply_move_instances(&self, moves: &MoveSequence) -> Self {
418        moves
419            .get_moves()
420            .iter()
421            .fold(self.clone(), |acc, mov| acc.apply_move_instance(&mov))
422    }
423
424    // pub fn random() -> Self {
425
426    // }
427}
428
429/// A vector of all allowed moves on a Rubik's Cube.
430pub const ALL_MOVES: [MoveInstance; 18] = [
431    cube_move!(U, Normal),
432    cube_move!(U, Prime),
433    cube_move!(U, Double),
434    cube_move!(D, Normal),
435    cube_move!(D, Prime),
436    cube_move!(D, Double),
437    cube_move!(L, Normal),
438    cube_move!(L, Prime),
439    cube_move!(L, Double),
440    cube_move!(R, Normal),
441    cube_move!(R, Prime),
442    cube_move!(R, Double),
443    cube_move!(F, Normal),
444    cube_move!(F, Prime),
445    cube_move!(F, Double),
446    cube_move!(B, Normal),
447    cube_move!(B, Prime),
448    cube_move!(B, Double),
449];
450
451const MOVE_U: Move = Move {
452    cp_change: [1, 2, 3, 0, 4, 5, 6, 7],
453    co_change: [0, 0, 0, 0, 0, 0, 0, 0],
454    ep_change: [1, 2, 3, 0, 4, 5, 6, 7, 8, 9, 10, 11],
455    eo_change: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
456};
457
458const MOVE_D: Move = Move {
459    cp_change: [0, 1, 2, 3, 5, 6, 7, 4],
460    co_change: [0, 0, 0, 0, 0, 0, 0, 0],
461    ep_change: [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8],
462    eo_change: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
463};
464
465const MOVE_R: Move = Move {
466    cp_change: [0, 6, 1, 3, 4, 2, 5, 7],
467    co_change: [0, -1, 1, 0, 0, -1, 1, 0],
468    ep_change: [0, 5, 2, 3, 4, 9, 1, 7, 8, 6, 10, 11],
469    eo_change: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
470};
471
472const MOVE_L: Move = Move {
473    cp_change: [3, 1, 2, 4, 7, 5, 6, 0],
474    co_change: [1, 0, 0, -1, 1, 0, 0, -1],
475    ep_change: [0, 1, 2, 7, 3, 5, 6, 11, 8, 9, 10, 4],
476    eo_change: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
477};
478
479const MOVE_F: Move = Move {
480    cp_change: [0, 1, 5, 2, 3, 4, 6, 7],
481    co_change: [0, 0, -1, 1, -1, 1, 0, 0],
482    ep_change: [0, 1, 6, 3, 4, 5, 8, 2, 7, 9, 10, 11],
483    eo_change: [0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0],
484};
485
486const MOVE_B: Move = Move {
487    cp_change: [7, 0, 2, 3, 4, 5, 1, 6],
488    co_change: [-1, 1, 0, 0, 0, 0, -1, 1],
489    ep_change: [4, 1, 2, 3, 10, 0, 6, 7, 8, 9, 5, 11],
490    eo_change: [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0],
491};
rusty_rubik/cube.rs

rusty_rubik/
cube.rs
