1use std::{fmt::Display, ops::Add};
3
4use itertools::Itertools;
5use nom::{
6 branch::alt, bytes::complete::tag, character::complete::space1, combinator::map,
7 multi::separated_list0, IResult,
8};
9use thiserror::Error;
10
11use crate::cube::Cube;
12
13#[derive(Debug, PartialEq, Eq, Clone, Copy)]
19pub enum FaceTurn {
20 U(u8),
21 D(u8),
22 F(u8),
23 B(u8),
24 L(u8),
25 R(u8),
26}
27
28#[derive(Debug, PartialEq, Eq, Clone, Copy)]
30pub enum Move {
31 FaceTurn(FaceTurn),
32}
33
34#[derive(Debug, PartialEq, Eq, Clone, Default)]
44pub struct Algorithm {
45 pub(crate) moves: Vec<Move>,
46}
47
48#[derive(Debug, Error, PartialEq, Eq)]
50pub enum MoveParseError {
51 #[error("Unknown Symbol {0}")]
52 UnknownSymbol(String),
53}
54
55impl FaceTurn {
56 #[must_use]
69 pub const fn inverse(&self) -> Self {
70 const fn inv(t: u8) -> u8 {
71 (t * 3) % 4
72 }
73 match self {
74 Self::U(t) => Self::U(inv(*t)),
75 Self::D(t) => Self::D(inv(*t)),
76 Self::F(t) => Self::F(inv(*t)),
77 Self::B(t) => Self::B(inv(*t)),
78 Self::L(t) => Self::L(inv(*t)),
79 Self::R(t) => Self::R(inv(*t)),
80 }
81 }
82}
83
84impl Move {
85 #[must_use]
98 pub const fn inverse(&self) -> Self {
99 match self {
100 Self::FaceTurn(t) => Self::FaceTurn(t.inverse()),
101 }
102 }
103}
104
105impl Algorithm {
106 #[must_use]
108 pub const fn new() -> Self {
109 Self { moves: Vec::new() }
110 }
111
112 #[must_use]
128 pub fn simplify(&self) -> Self {
129 let mut prev_ter = self.clone();
130 let mut current_iter = self.single_pass();
131 while prev_ter != current_iter {
132 prev_ter = current_iter.clone();
133 current_iter = current_iter.single_pass();
134 }
135 current_iter
136 }
137
138 fn single_pass(&self) -> Self {
139 self.moves.iter().fold(Self::default(), |mut moves, &m| {
140 if moves.moves.is_empty() {
141 vec![m].into()
142 } else {
143 let last_move = moves.moves.pop().expect("list is not empty");
144 let ms = last_move + m;
145 let k = [moves.moves, ms.moves].concat();
146 k.into()
147 }
148 })
149 }
150
151 pub fn from(s: &str) -> Result<Self, MoveParseError> {
165 let (s, m) = separated_list0(
166 space1,
167 alt((u_moves, d_moves, f_moves, b_moves, l_moves, r_moves)),
168 )(s)?;
169 if s.is_empty() {
170 Ok(m.into())
171 } else {
172 Err(MoveParseError::UnknownSymbol(s.to_string()))
173 }
174 }
175
176 #[must_use]
191 pub fn inverse(&self) -> Self {
192 Self {
193 moves: self.moves.iter().rev().map(Move::inverse).collect(),
194 }
195 }
196
197 #[must_use]
212 pub fn commute(&self, other: &Self) -> Self {
213 self.clone() + other + &self.inverse() + &other.inverse()
214 }
215
216 #[must_use]
231 pub fn permute(&self, other: &Self) -> Self {
232 self.clone() + other + &self.inverse()
233 }
234
235 #[must_use]
237 pub fn sexy() -> Self {
238 Self::from("R U R' U'").expect("this doesn't panic")
239 }
240
241 #[must_use]
253 pub fn order(&self) -> u32 {
254 let solved_cube = Cube::new();
255 let mut cube = Cube::new();
256 cube = cube.apply(self.clone());
257 let mut count = 1;
258
259 while cube != solved_cube {
260 cube = cube.apply(self.clone());
261 count += 1;
262 }
263 count
264 }
265
266 #[must_use]
279 pub fn solves(&self, other: &Self) -> bool {
280 let mut cube = Cube::new();
281 cube = cube.apply(self.clone());
282 cube = cube.apply(other.clone());
283 cube == Cube::new()
284 }
285}
286
287impl IntoIterator for Algorithm {
288 type Item = Move;
289
290 type IntoIter = std::vec::IntoIter<Self::Item>;
291
292 fn into_iter(self) -> Self::IntoIter {
293 self.moves.into_iter()
294 }
295}
296
297impl Display for Algorithm {
298 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
299 let moves = self.moves.iter().map(|m| format!("{m}")).join(" ");
300 write!(f, "{moves}")
301 }
302}
303
304impl Display for Move {
305 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
306 let m = match self {
307 Self::FaceTurn(turn) => format!("{turn}"),
308 };
309 write!(f, "{m}")
310 }
311}
312
313impl Display for FaceTurn {
314 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
315 let m = match self {
316 Self::U(1) => "U",
317 Self::U(2) => "U2",
318 Self::U(3) => "U'",
319 Self::D(1) => "D",
320 Self::D(2) => "D2",
321 Self::D(3) => "D'",
322 Self::F(1) => "F",
323 Self::F(2) => "F2",
324 Self::F(3) => "F'",
325 Self::B(1) => "B",
326 Self::B(2) => "B2",
327 Self::B(3) => "B'",
328 Self::L(1) => "L",
329 Self::L(2) => "L2",
330 Self::L(3) => "L'",
331 Self::R(1) => "R",
332 Self::R(2) => "R2",
333 Self::R(3) => "R'",
334 m => panic!("Unknown turn: {m}"),
335 };
336 write!(f, "{m}")
337 }
338}
339
340impl Add<Self> for FaceTurn {
341 type Output = Algorithm;
342
343 fn add(self, rhs: Self) -> Self::Output {
344 let new_moves = match (self, rhs) {
345 (Self::U(a), Self::U(b)) => match (a + b) % 4 {
346 0 => Vec::new(),
347 t => vec![Self::U(t)],
348 },
349 (Self::D(a), Self::D(b)) => match (a + b) % 4 {
350 0 => Vec::new(),
351 t => vec![Self::D(t)],
352 },
353 (Self::F(a), Self::F(b)) => match (a + b) % 4 {
354 0 => Vec::new(),
355 t => vec![Self::F(t)],
356 },
357 (Self::B(a), Self::B(b)) => match (a + b) % 4 {
358 0 => Vec::new(),
359 t => vec![Self::B(t)],
360 },
361 (Self::L(a), Self::L(b)) => match (a + b) % 4 {
362 0 => Vec::new(),
363 t => vec![Self::L(t)],
364 },
365 (Self::R(a), Self::R(b)) => match (a + b) % 4 {
366 0 => Vec::new(),
367 t => vec![Self::R(t)],
368 },
369
370 (Self::U(u), Self::D(d)) => vec![Self::D(d), Self::U(u)],
371 (Self::L(l), Self::R(r)) => vec![Self::R(r), Self::L(l)],
372 (Self::F(f), Self::B(b)) => vec![Self::B(b), Self::F(f)],
373
374 (left, right) => vec![left, right],
375 };
376 new_moves.into()
377 }
378}
379
380impl From<FaceTurn> for Move {
381 fn from(value: FaceTurn) -> Self {
382 Self::FaceTurn(value)
383 }
384}
385
386impl Add<Self> for Move {
387 type Output = Algorithm;
388
389 fn add(self, rhs: Self) -> Self::Output {
390 match (self, rhs) {
391 (Self::FaceTurn(a), Self::FaceTurn(b)) => a + b,
392 }
393 }
394}
395
396impl Add<&Self> for Algorithm {
397 type Output = Self;
398
399 fn add(self, rhs: &Self) -> Self::Output {
400 Self {
401 moves: [self.moves, rhs.moves.clone()].concat(),
402 }
403 }
404}
405
406macro_rules! move_parser {
407 ($fn_name: ident, $dir: ident, $d: expr ) => {
408 fn $fn_name(input: &str) -> IResult<&str, FaceTurn> {
409 let (input, t) = alt((
410 map(tag(format!("{}2", $d).as_str()), |_| 2),
411 map(tag(format!("{}'", $d).as_str()), |_| 3),
412 map(tag(format!("{}", $d).as_str()), |_| 1),
413 ))(input)?;
414 Ok((input, FaceTurn::$dir(t)))
415 }
416 };
417}
418
419move_parser!(u_moves, U, "U");
420move_parser!(d_moves, D, "D");
421move_parser!(f_moves, F, "F");
422move_parser!(b_moves, B, "B");
423move_parser!(l_moves, L, "L");
424move_parser!(r_moves, R, "R");
425
426impl From<nom::Err<nom::error::Error<&str>>> for MoveParseError {
427 fn from(value: nom::Err<nom::error::Error<&str>>) -> Self {
428 Self::UnknownSymbol(value.to_string())
429 }
430}
431
432impl<T> From<Vec<T>> for Algorithm
433where
434 T: Into<Move> + Copy,
435{
436 fn from(moves: Vec<T>) -> Self {
437 Self {
438 moves: moves.iter().map(|&m| m.into()).collect(),
439 }
440 }
441}
442
443#[cfg(test)]
444mod simplification_tests {
445 use super::*;
446 use pretty_assertions::{assert_eq, assert_ne};
447
448 #[test]
449 #[allow(non_snake_case)]
450 fn U_then_U_rev_does_nothing() {
451 let moves: Algorithm = vec![FaceTurn::U(1), FaceTurn::U(3)].into();
452 let actual = moves.simplify();
453
454 assert_eq!(actual, Algorithm::default());
455 }
456
457 #[test]
458 #[allow(non_snake_case)]
459 fn U_simplifies_to_U() {
460 let moves: Algorithm = vec![FaceTurn::U(1)].into();
461 let actual = moves.simplify();
462
463 assert_eq!(actual, moves);
464 }
465
466 #[test]
467 #[allow(non_snake_case)]
468 fn U_is_not_the_same_as_U_rev() {
469 let u: Algorithm = vec![FaceTurn::U(1)].into();
470 let u_rev: Algorithm = vec![FaceTurn::U(3)].into();
471
472 assert_ne!(u, u_rev);
473 }
474
475 #[test]
476 #[allow(non_snake_case)]
477 fn two_Us_simplifies_to_U2() {
478 let us: Algorithm = vec![FaceTurn::U(1), FaceTurn::U(1)].into();
479 let actual = us.simplify();
480 let expected: Algorithm = vec![FaceTurn::U(2)].into();
481
482 assert_eq!(actual, expected);
483 }
484
485 #[test]
486 #[allow(non_snake_case)]
487 fn U_then_U2_simplifies_to_URev() {
488 let turns: Algorithm = vec![FaceTurn::U(1), FaceTurn::U(2)].into();
489 let actual = turns.simplify();
490 let expected: Algorithm = vec![FaceTurn::U(3)].into();
491
492 assert_eq!(actual, expected);
493 }
494
495 #[test]
496 #[allow(non_snake_case)]
497 fn U2_then_U_simplifies_to_URev() {
498 let turns: Algorithm = vec![FaceTurn::U(2), FaceTurn::U(1)].into();
499 let actual = turns.simplify();
500 let expected: Algorithm = vec![FaceTurn::U(3)].into();
501
502 assert_eq!(actual, expected);
503 }
504
505 #[test]
506 #[allow(non_snake_case)]
507 fn four_Us_simplifies_to_nothing() {
508 let turns: Algorithm = vec![
509 FaceTurn::U(1),
510 FaceTurn::U(1),
511 FaceTurn::U(1),
512 FaceTurn::U(1),
513 ]
514 .into();
515 let actual = turns.simplify();
516 let expected: Algorithm = Algorithm { moves: Vec::new() };
517
518 assert_eq!(actual, expected);
519 }
520
521 #[test]
522 #[allow(non_snake_case)]
523 fn U_F_does_not_simplify() {
524 let turns: Algorithm = vec![FaceTurn::U(1), FaceTurn::F(1)].into();
525 let actual = turns.simplify();
526 let expected = turns.clone();
527
528 assert_eq!(actual, expected);
529 }
530
531 #[test]
532 #[allow(non_snake_case)]
533 fn F_U_does_not_simplify() {
534 let turns: Algorithm = vec![FaceTurn::F(1), FaceTurn::U(1)].into();
535 let actual = turns.simplify();
536 let expected = turns;
537
538 assert_eq!(actual, expected);
539 }
540
541 #[test]
542 fn complicated_move_simplification() {
543 let turns: Algorithm = vec![
544 FaceTurn::U(1),
545 FaceTurn::R(3),
546 FaceTurn::F(1),
547 FaceTurn::F(3),
548 FaceTurn::R(1),
549 FaceTurn::U(2),
550 FaceTurn::L(2),
551 FaceTurn::D(1),
552 FaceTurn::D(3),
553 FaceTurn::L(2),
554 FaceTurn::U(1),
555 ]
556 .into();
557 let actual = turns.simplify();
558 let expected = Algorithm::default();
559
560 assert_eq!(actual, expected);
561 }
562
563 #[test]
564 #[allow(non_snake_case)]
565 fn U2_D2_U2_simplifies_the_two_outside_U2s() {
566 let moves: Algorithm = vec![FaceTurn::U(2), FaceTurn::D(2), FaceTurn::U(2)].into();
567 let actual = moves.simplify();
568 let expected = vec![FaceTurn::D(2)].into();
569
570 assert_eq!(actual, expected);
571 }
572
573 #[test]
574 #[allow(non_snake_case)]
575 fn D2_U2_D2_simplifies_the_two_outside_D2s() {
576 let moves: Algorithm = vec![FaceTurn::D(2), FaceTurn::U(2), FaceTurn::D(2)].into();
577 let actual = moves.simplify();
578 let expected = vec![FaceTurn::U(2)].into();
579
580 assert_eq!(actual, expected);
581 }
582}
583
584#[cfg(test)]
585mod parsing_tests {
586 use super::*;
587 #[allow(unused_imports)]
588 use pretty_assertions::{assert_eq, assert_ne, assert_str_eq};
589
590 #[test]
591 #[allow(non_snake_case)]
592 fn U() {
593 let s = "U";
594 let actual = Algorithm::from(s).unwrap();
595 let expected = vec![FaceTurn::U(1)].into();
596
597 assert_eq!(actual, expected);
598 }
599
600 #[test]
601 #[allow(non_snake_case)]
602 fn F() {
603 let s = "F";
604 let actual = Algorithm::from(s).unwrap();
605 let expected = vec![FaceTurn::F(1)].into();
606
607 assert_eq!(actual, expected);
608 }
609
610 #[test]
611 #[allow(non_snake_case)]
612 fn U2() {
613 let s = "U2";
614 let actual = Algorithm::from(s).unwrap();
615 let expected = vec![FaceTurn::U(2)].into();
616
617 assert_eq!(actual, expected);
618 }
619
620 #[test]
621 fn t_perm_spaces() {
622 let s = "R U R' U' R' F R2 U' R' U' R U R' F'";
623 let actual = Algorithm::from(s).unwrap();
624 let expected = vec![
625 FaceTurn::R(1),
626 FaceTurn::U(1),
627 FaceTurn::R(3),
628 FaceTurn::U(3),
629 FaceTurn::R(3),
630 FaceTurn::F(1),
631 FaceTurn::R(2),
632 FaceTurn::U(3),
633 FaceTurn::R(3),
634 FaceTurn::U(3),
635 FaceTurn::R(1),
636 FaceTurn::U(1),
637 FaceTurn::R(3),
638 FaceTurn::F(3),
639 ]
640 .into();
641
642 assert_eq!(actual, expected);
643 }
644
645 #[test]
646 fn errors_on_unknown_input() {
647 let s = "R U foobar R' U'";
648 let actual = Algorithm::from(s).unwrap_err();
649 let expected = MoveParseError::UnknownSymbol(" foobar R' U'".to_string());
650
651 assert_eq!(actual, expected);
652 }
653}
654
655#[cfg(test)]
656mod inverse_tests {
657 use super::*;
658 #[allow(unused_imports)]
659 use pretty_assertions::{assert_eq, assert_ne, assert_str_eq};
660
661 #[test]
662 #[allow(non_snake_case)]
663 fn U_moves_to_U_rev() {
664 let m = Algorithm::from("U").unwrap();
665 let actual = m.inverse();
666 let expected = Algorithm::from("U'").unwrap();
667
668 assert_eq!(actual, expected);
669 }
670
671 #[test]
672 #[allow(non_snake_case)]
673 fn sexy_inverses_to_inverse_sexy() {
674 let m = Algorithm::from("R U R' U'").unwrap();
675 let actual = m.inverse();
676 let expected = Algorithm::from("U R U' R'").unwrap();
677
678 assert_eq!(actual, expected);
679 }
680
681 #[test]
682 #[allow(non_snake_case)]
683 fn R_and_U_commutes_to_sexy() {
684 let r = Algorithm::from("R").unwrap();
685 let u = Algorithm::from("U").unwrap();
686 let actual = r.commute(&u);
687 let expected = Algorithm::sexy();
688
689 assert_eq!(actual, expected);
690 }
691
692 #[test]
693 #[allow(non_snake_case)]
694 fn F_and_sexy_permute() {
695 let r = Algorithm::from("F").unwrap();
696 let sexy = Algorithm::sexy();
697 let actual = r.permute(&sexy);
698 let expected = Algorithm::from("F R U R' U' F'").unwrap();
699
700 assert_eq!(actual, expected);
701 }
702}
703
704#[cfg(test)]
705mod order_tests {
706 use super::*;
707 #[allow(unused_imports)]
708 use pretty_assertions::{assert_eq, assert_ne, assert_str_eq};
709
710 #[test]
711 #[allow(non_snake_case)]
712 fn order_of_U_is_4() {
713 let m = Algorithm::from("U").unwrap();
714
715 let actual = m.order();
716 let expected = 4;
717 assert_eq!(actual, expected);
718 }
719
720 #[test]
721 #[allow(non_snake_case)]
722 fn order_of_U2_is_2() {
723 let m = Algorithm::from("U2").unwrap();
724
725 let actual = m.order();
726 let expected = 2;
727 assert_eq!(actual, expected);
728 }
729
730 #[test]
731 #[allow(non_snake_case)]
732 fn order_of_sexy_is_6() {
733 let m = Algorithm::sexy();
734
735 let actual = m.order();
736 let expected = 6;
737 assert_eq!(actual, expected);
738 }
739}
740
741#[cfg(test)]
742mod solves_tests {
743 use super::*;
744 #[allow(unused_imports)]
745 use pretty_assertions::{assert_eq, assert_ne, assert_str_eq};
746
747 #[test]
748 #[allow(non_snake_case)]
749 fn U_rev_solves_U() {
750 let scramble = Algorithm::from("U").unwrap();
751 let solution = Algorithm::from("U'").unwrap();
752
753 assert!(solution.solves(&scramble));
754 }
755
756 #[test]
757 #[allow(non_snake_case)]
758 fn F_does_not_solve_U() {
759 let scramble = Algorithm::from("U").unwrap();
760 let solution = Algorithm::from("F").unwrap();
761
762 assert!(!solution.solves(&scramble));
763 }
764}
765
766#[cfg(test)]
767mod tests {
768 use super::*;
769 #[allow(unused_imports)]
770 use pretty_assertions::{assert_eq, assert_ne, assert_str_eq};
771
772 #[test]
773 fn display() {
774 let moves = "U2 F B'";
775 let alg = Algorithm::from(moves).unwrap();
776
777 let actual = format!("{alg}");
778
779 assert_str_eq!(actual, moves);
780 }
781}