kociemba 0.5.1

use rand::prelude::*;
use std::fmt;
use std::ops::Mul;

use self::{Corner::*, Edge::*, Move::*};
use crate::constants::*;
use crate::error::Error;
use crate::symmetries;
use crate::{facelet::*, moves::*};

/// Represents the 8 corners on the cube, described by the layer they are on.
/// 
/// Example: `ULB` (Up, Left, Bottom).
#[rustfmt::skip]
#[allow(clippy::upper_case_acronyms)]
#[derive(Debug, PartialEq, PartialOrd, Clone, Copy)]
pub enum Corner {
    URF, UFL, ULB, UBR, DFR, DLF, DBL, DRB,
}

impl fmt::Display for Corner {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}

impl TryFrom<u8> for Corner {
    type Error = Error;

    fn try_from(value: u8) -> Result<Self, Self::Error> {
        match value {
            0 => Ok(URF),
            1 => Ok(UFL),
            2 => Ok(ULB),
            3 => Ok(UBR),
            4 => Ok(DFR),
            5 => Ok(DLF),
            6 => Ok(DBL),
            7 => Ok(DRB),
            _ => Err(Error::InvalidCorner),
        }
    }
}

/// Represents the 12 edges on the cube, described by the layer they are on.
/// 
/// Example: `BL` (Bottom, Left).
#[rustfmt::skip]
#[allow(clippy::upper_case_acronyms)]
#[derive(Debug, PartialEq, PartialOrd, Clone, Copy)]
pub enum Edge {
    UR, UF, UL, UB, DR, DF, DL, DB, FR, FL, BL, BR,
}

impl fmt::Display for Edge {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}

impl TryFrom<u8> for Edge {
    type Error = Error;

    fn try_from(value: u8) -> Result<Self, Self::Error> {
        match value {
            0 => Ok(UR),
            1 => Ok(UF),
            2 => Ok(UL),
            3 => Ok(UB),
            4 => Ok(DR),
            5 => Ok(DF),
            6 => Ok(DL),
            7 => Ok(DB),
            8 => Ok(FR),
            9 => Ok(FL),
            10 => Ok(BL),
            11 => Ok(BR),
            _ => Err(Error::InvalidEdge),
        }
    }
}

/// Cube on the cubie level.
#[derive(Debug, PartialEq, Clone, Copy)]
pub struct CubieCube {
    /// Corner permutation, relative to SOLVED_STATE.
    pub cp: [Corner; 8],
    /// Corner orientation, 3 possible values: 0 (correctly oriented), 1 (twisted clockwise), 2 (twisted counter-clockwise).
    pub co: [u8; 8],
    /// Edge permutation, relative to SOLVED_STATE.
    pub ep: [Edge; 12],
    /// Edge orientation, 2 possible values: 0 (correctly oriented), 1 (flipped).
    pub eo: [u8; 12],
}

/// Solved cube on the Cubie level.
pub const SOLVED_CUBIE_CUBE: CubieCube = CubieCube {
    cp: [URF, UFL, ULB, UBR, DFR, DLF, DBL, DRB],
    co: [0, 0, 0, 0, 0, 0, 0, 0],
    ep: [UR, UF, UL, UB, DR, DF, DL, DB, FR, FL, BL, BR],
    eo: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
};

impl Default for CubieCube {
    fn default() -> Self {
        SOLVED_CUBIE_CUBE
    }
}

impl Mul for CubieCube {
    type Output = Self;

    fn mul(self, rhs: CubieCube) -> Self::Output {
        let mut res = CubieCube::default();
        // (A * B).c = A(B(x).c).c
        // (A * B).o = A(B(x).c).o + B(x).o

        for i in 0..8 {
            res.cp[i] = self.cp[rhs.cp[i] as usize];
            res.co[i] = (self.co[rhs.cp[i] as usize] + rhs.co[i]) % 3;
        }

        for i in 0..12 {
            res.ep[i] = self.ep[rhs.ep[i] as usize];
            res.eo[i] = (self.eo[rhs.ep[i] as usize] + rhs.eo[i]) % 2;
        }

        res
    }
}

impl fmt::Display for CubieCube {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // Print string for a cubie cube.
        let mut s = String::new();
        for i in 0..8 {
            let cs: String = format!("({},{})", self.cp[i], self.co[i]);
            s.push_str(&cs);
        }
        for i in 0..12 {
            let es: String = format!("({},{})", self.ep[i], self.eo[i]);
            s.push_str(&es);
        }
        write!(f, "{s}")
    }
}


impl From<&Vec<Move>> for CubieCube {
    fn from(moves: &Vec<Move>) -> Self {
        CubieCube::default().apply_moves(moves)
    }
}

/// Gives cubie representation of a face cube (facelet).
impl TryFrom<&FaceCube> for CubieCube {
    type Error = Error;
    fn try_from(face_cube: &FaceCube) -> Result<Self, Self::Error> {
        let mut state = CubieCube::default();
        let mut ori: usize = 0;
        let mut col1;
        let mut col2;

        for i in 0..8 {
            let i = Corner::try_from(i)?;
            // get the colors of the cubie at corner i, starting with U/D
            for index in 0..3 {
                ori = index;
                if face_cube.f[CORNER_FACELET[i as usize][ori] as usize] == Color::U
                    || face_cube.f[CORNER_FACELET[i as usize][ori] as usize] == Color::D
                {
                    break;
                }
            }

            col1 = face_cube.f[CORNER_FACELET[i as usize][(ori + 1) % 3] as usize];
            col2 = face_cube.f[CORNER_FACELET[i as usize][(ori + 2) % 3] as usize];

            for j in 0..8 {
                let j = Corner::try_from(j)?;
                if col1 == CORNER_COLOR[j as usize][1] && col2 == CORNER_COLOR[j as usize][2] {
                    // in cornerposition i we have cornercubie j
                    state.cp[i as usize] = j;
                    state.co[i as usize] = ori as u8 % 3;
                    break;
                }
            }
        }

        for i in 0..12 {
            let i = Edge::try_from(i)?;
            for j in 0..12 {
                let j = Edge::try_from(j)?;
                if face_cube.f[EDGE_FACELET[i as usize][0] as usize] == EDGE_COLOR[j as usize][0]
                    && face_cube.f[EDGE_FACELET[i as usize][1] as usize]
                        == EDGE_COLOR[j as usize][1]
                {
                    state.ep[i as usize] = j;
                    state.eo[i as usize] = 0;
                    break;
                }
                if face_cube.f[EDGE_FACELET[i as usize][0] as usize] == EDGE_COLOR[j as usize][1]
                    && face_cube.f[EDGE_FACELET[i as usize][1] as usize]
                        == EDGE_COLOR[j as usize][0]
                {
                    state.ep[i as usize] = j;
                    state.eo[i as usize] = 1;
                    break;
                }
            }
        }

        if !state.is_solvable() {
            Err(Error::InvalidFaceletValue)
        } else {
            Ok(state)
        }
    }
}

impl CubieCube {
    /// Applies a move to the current state.
    pub fn apply_move(self, move_name: Move) -> Self {
        let move_state = match move_name {
            U => U_MOVE,
            U2 => U_MOVE * U_MOVE,
            U3 => U_MOVE * U_MOVE * U_MOVE,
            D => D_MOVE,
            D2 => D_MOVE * D_MOVE,
            D3 => D_MOVE * D_MOVE * D_MOVE,
            R => R_MOVE,
            R2 => R_MOVE * R_MOVE,
            R3 => R_MOVE * R_MOVE * R_MOVE,
            L => L_MOVE,
            L2 => L_MOVE * L_MOVE,
            L3 => L_MOVE * L_MOVE * L_MOVE,
            F => F_MOVE,
            F2 => F_MOVE * F_MOVE,
            F3 => F_MOVE * F_MOVE * F_MOVE,
            B => B_MOVE,
            B2 => B_MOVE * B_MOVE,
            B3 => B_MOVE * B_MOVE * B_MOVE,
        };

        self * move_state
    }

    /// Applies the sequence of moves to the current state.
    pub fn apply_moves(&self, moves: &[Move]) -> Self {
        moves.iter().fold(*self, |acc, &m| acc.apply_move(m))
    }

    /// Returns the number of corner twist needed to orient the corners.
    pub fn count_corner_twist(&self) -> u8 {
        self.co.iter().fold(0, |acc, co| acc + ((3 - co) % 3))
    }

    /// Returns the number of edge twist needed to orient the edges.
    pub fn count_edge_twist(&self) -> u8 {
        self.eo.iter().sum()
    }

    /// Returns the number of corner permutations needed to solve the corners.
    pub fn count_corner_perm(&self) -> u8 {
        let mut count = 0;
        let mut cp = self.cp;

        for i in 0..8 {
            if cp[i] as usize != i {
                if let Some(j) = (i + 1..8).find(|&j| cp[j] as usize == i) {
                    cp.swap(i, j);
                    count += 1;
                }
            }
        }

        count
    }

    /// Returns the number of edge permutations needed to solve the edges.
    pub fn count_edge_perm(&self) -> u8 {
        let mut count = 0;
        let mut ep = self.ep;

        for i in 0..12 {
            if ep[i] as usize != i {
                if let Some(j) = (i + 1..12).find(|&j| ep[j] as usize == i) {
                    ep.swap(i, j);
                    count += 1;
                }
            }
        }

        count
    }

    /// Checks if CubieCube is a valid cubie representation.
    pub fn is_solvable(&self) -> bool {
        let c_perm = self.count_corner_perm();
        let e_perm = self.count_edge_perm();
        let c_twist = self.count_corner_twist();
        let e_twist = self.count_edge_twist();
        let has_even_permutation = c_perm % 2 == e_perm % 2;
        let has_valid_twist = c_twist % 3 == 0 && e_twist % 2 == 0;

        has_even_permutation && has_valid_twist
    }

    /// Multiply this cubie cube with another cubie cube b, restricted to the corners.
    pub fn corner_multiply(&mut self, b: CubieCube) {
        let mut c_perm = [URF; 8];
        let mut c_ori = [0; 8];
        let mut ori = 0;
        for ci in ALL_CORNERS {
            let c = ci as usize;
            c_perm[c] = self.cp[b.cp[c] as usize];
            let ori_a = self.co[b.cp[c] as usize];
            let ori_b = b.co[c];
            if ori_a < 3 && ori_b < 3 {
                // two regular cubes
                ori = ori_a + ori_b;
                if ori >= 3 {
                    ori -= 3;
                }
            } else if ori_a < 3 && 3 <= ori_b {
                // cube b is in a mirrored state
                ori = ori_a + ori_b;
                if ori >= 6 {
                    ori -= 3; // the composition also is in a mirrored state
                }
            } else if ori_a >= 3 && 3 > ori_b {
                // cube a is in a mirrored state
                ori = ori_a - ori_b;
                if ori < 3 {
                    ori += 3; // the composition is a mirrored cube
                }
            } else if ori_a >= 3 && ori_b >= 3 {
                // if both cubes are in mirrored states
                if ori_a >= ori_b {
                    ori = ori_a - ori_b;
                } else {
                    ori = ori_b - ori_a;
                    ori = 3 - ori; // the composition is a regular cube
                }
            }
            c_ori[c] = ori;
        }
        for c in ALL_CORNERS {
            let ci = c as usize;
            self.cp[ci] = c_perm[ci];
            self.co[ci] = c_ori[ci];
        }
    }

    /// Multiply this cubie cube with another cubie cube b, restricted to the edges.
    pub fn edge_multiply(&mut self, b: CubieCube) {
        let mut e_perm: [Edge; 12] = [UR; 12];
        let mut e_ori = [0; 12];
        for ei in ALL_EDGES {
            let e = ei as usize;
            e_perm[e] = self.ep[b.ep[e] as usize];
            e_ori[e] = (b.eo[e] + self.eo[b.ep[e] as usize]) % 2;
        }
        for ei in ALL_EDGES {
            let e = ei as usize;
            self.ep[e] = e_perm[e];
            self.eo[e] = e_ori[e];
        }
    }

    /// Multiply this cubie cube with another cubie cube b.
    pub fn multiply(&mut self, b: CubieCube) {
        self.corner_multiply(b);
        self.edge_multiply(b);
    }

    /// Return the inverse of this cubiecube.
    pub fn inverse_cubie_cube(&self) -> Self {
        let mut d = CubieCube::default();
        for ei in ALL_EDGES {
            let e: usize = ei as usize;
            d.ep[self.ep[e] as usize] = ei;
        }
        for ei in ALL_EDGES {
            let e: usize = ei as usize;
            d.eo[e] = self.eo[d.ep[e] as usize];
        }

        for ci in ALL_CORNERS {
            let c = ci as usize;
            d.cp[self.cp[c] as usize] = ci;
        }
        for ci in ALL_CORNERS {
            let c = ci as usize;
            let ori = self.co[d.cp[c] as usize];
            if ori >= 3 {
                d.co[c] = ori;
            } else {
                d.co[c] = 3 - ori;
                if d.co[c] == 3 {
                    d.co[c] = 0;
                }
            }
        }
        d
    }

    /// Give the parity of the corner permutation.
    pub fn corner_parity(&self) -> bool {
        let mut s = 0;
        for i in ((URF as usize + 1)..=(DRB as usize)).rev() {
            for j in ((URF as usize)..=(i - 1)).rev() {
                if self.cp[j] > self.cp[i] {
                    s += 1
                }
            }
        }
        (s % 2) == 0
    }

    /// Give the parity of the edge permutation. A solvable cube has the same corner and edge parity.
    pub fn edge_parity(&self) -> bool {
        let mut s = 0;
        for i in ((UR as usize + 1)..=(BR as usize)).rev() {
            for j in ((UR as usize)..=(i - 1)).rev() {
                if self.ep[j] > self.ep[i] {
                    s += 1;
                }
            }
        }
        (s % 2) == 0
    }

    /// Generate a list of the symmetries and antisymmetries of the cubie cube.
    pub fn symmetries(&self) -> Vec<usize> {
        let sc = symmetries::sc();
        let inv_idx = symmetries::inv_idx();
        let mut s = Vec::new();
        for j in 0..N_SYM {
            let mut c = CubieCube {
                cp: sc[j].cp,
                co: sc[j].co,
                ep: sc[j].ep,
                eo: sc[j].eo,
            };
            c.multiply(*self);
            c.multiply(sc[inv_idx[j] as usize]);
            if *self == c {
                s.push(j);
            }
            let d = c.inverse_cubie_cube();
            if *self == d {
                // then we have antisymmetry
                s.push(j + N_SYM);
            }
        }
        s
    }

    /// Get the twist of the 8 corners. 0 <= twist < 2187 in phase 1, twist = 0 in phase 2.
    pub fn get_twist(&self) -> u16 {
        let mut twist: u16 = 0;
        for i in (URF as usize)..(DRB as usize) {
            twist = 3 * twist + self.co[i] as u16;
        }
        twist
    }

    /// Set the twist of the 8 corners. 0 <= twist < 2187 in phase 1, twist = 0 in phase 2.
    pub fn set_twist(&mut self, twist: u16) {
        let mut twistparity = 0;
        let mut twist = twist;
        for i in ((URF as usize)..(DRB as usize)).rev() {
            self.co[i] = (twist % 3) as u8;
            twistparity += self.co[i];
            twist /= 3;
        }
        self.co[DRB as usize] = (3 - twistparity % 3) % 3;
    }

    /// Get the flip of the 12 edges. 0 <= flip < 2048 in phase 1, flip = 0 in phase 2.
    pub fn get_flip(&self) -> u16 {
        let mut ret: u16 = 0;
        for i in (UR as usize)..(BR as usize) {
            ret = 2 * ret + self.eo[i] as u16;
        }
        ret
    }

    /// Set the flip of the 12 edges. 0 <= flip < 2048 in phase 1, flip = 0 in phase 2.
    pub fn set_flip(&mut self, flip: u16) {
        let mut flipparity = 0;
        let mut flip = flip;
        for i in ((UR as usize)..(BR as usize)).rev() {
            self.eo[i] = (flip % 2) as u8;
            flipparity += self.eo[i];
            flip /= 2;
        }
        self.eo[BR as usize] = (2 - flipparity % 2) % 2;
    }

    /// Get the location of the UD-slice edges FR,FL,BL and BR ignoring their permutation.
    /// 
    /// 0<= slice < 495 in phase 1, slice = 0 in phase 2.
    pub fn get_slice(&self) -> u16 {
        let mut a = 0;
        let mut x = 0;
        // Compute the index a < (12 choose 4)
        for j in ((UR as usize)..=(BR as usize)).rev() {
            if FR <= self.ep[j] && self.ep[j] <= BR {
                a += c_nk((11 - j) as u32, x + 1);
                x += 1;
            }
        }
        a as u16
    }

    /// Set the location of the UD-slice edges FR,FL,BL and BR ignoring their permutation.
    /// 
    /// 0<= slice < 495 in phase 1, slice = 0 in phase 2.
    pub fn set_slice(&mut self, idx: u16) {
        let slice_edge = [FR, FL, BL, BR];
        let other_edge = [UR, UF, UL, UB, DR, DF, DL, DB];
        let mut a = idx; // Location
        let mut ep = [-1; 12];

        let mut x: i32 = 4; // set slice edges
        for j in ALL_EDGES {
            if a >= c_nk((11 - j as u32) as u32, x as u32) as u16 {
                self.ep[j as usize] = slice_edge[(4 - x) as usize];
                ep[j as usize] = slice_edge[(4 - x) as usize] as i32;
                a -= c_nk(11 - j as u32, x as u32) as u16;
                x -= 1;
            }
        }
        let mut x = 0; // set the remaining edges UR..DB
        for j in ALL_EDGES {
            if ep[j as usize] == -1 {
                self.ep[j as usize] = other_edge[x];
                x += 1;
            }
        }
    }

    /// Get the permutation and location of the UD-slice edges FR,FL,BL and BR.
    /// 
    /// 0 <= slice_sorted < 11880 in phase 1, 0 <= slice_sorted < 24 in phase 2, slice_sorted = 0 for solved cube.
    pub fn get_slice_sorted(&self) -> u16 {
        let mut a = 0;
        let mut x = 0;
        let mut edge4 = [UR; 4];
        // First compute the index a < (12 choose 4) and the permutation array perm.
        for j in ((UR as usize)..=(BR as usize)).rev() {
            if FR <= self.ep[j] && self.ep[j] <= BR {
                a += c_nk((11 - j) as u32, x + 1);
                edge4[(3 - x) as usize] = self.ep[j as usize];
                x += 1;
            }
        }
        // Then compute the index b < 4! for the permutation in edge4
        let mut b = 0;
        for j in (1..=3).rev() {
            let mut k = 0;
            while edge4[j] != ALL_EDGES[j + 8] {
                rotate_left(&mut edge4, 0, j);
                k += 1
            }
            b = (j + 1) * b + k;
        }
        24 * a as u16 + b as u16
    }

    /// Set the permutation and location of the UD-slice edges FR,FL,BL and BR.
    /// 
    /// 0 <= slice_sorted < 11880 in phase 1, 0 <= slice_sorted < 24 in phase 2, slice_sorted = 0 for solved cube.
    pub fn set_slice_sorted(&mut self, idx: u16) {
        let mut slice_edge = [FR, FL, BL, BR];
        let other_edge = [UR, UF, UL, UB, DR, DF, DL, DB];
        let mut b = idx % 24; // Permutation
        let mut a = idx / 24; // Location
        let mut ep = [-1; 12]; // Invalidate all edge positions

        let mut j = 1; // generate permutation from index b
        while j < 4 {
            let mut k = b % (j + 1);
            b /= j + 1;
            while k > 0 {
                rotate_right(&mut slice_edge, 0, j as usize);
                k -= 1;
            }
            j += 1;
        }

        let mut x = 4; // set slice edges
        for j in ALL_EDGES {
            if a >= c_nk(11 - j as u32, x) as u16 {
                self.ep[j as usize] = slice_edge[4 - x as usize];
                ep[j as usize] = slice_edge[4 - x as usize] as i32;
                a -= c_nk(11 - j as u32, x) as u16;
                x -= 1;
            }
        }

        let mut x = 0; // set the remaining edges UR..DB
        for j in ALL_EDGES {
            if ep[j as usize] == -1 {
                self.ep[j as usize] = other_edge[x];
                x += 1;
            }
        }
    }

    /// Get the permutation and location of edges UR, UF, UL and UB.
    /// 
    /// 0 <= u_edges < 11880 in phase 1, 0 <= u_edges < 1680 in phase 2, u_edges = 1656 for solved cube.
    pub fn get_u_edges(&self) -> u16 {
        let mut a = 0;
        let mut x = 0;
        let mut edge4 = [UR; 4];
        let mut ep_mod = self.ep.clone();
        for _j in 0..4 {
            rotate_right(&mut ep_mod, 0, 11);
        }
        // First compute the index a < (12 choose 4) and the permutation array perm.
        for j in ((UR as usize)..=(BR as usize)).rev() {
            if UR <= ep_mod[j] && ep_mod[j] <= UB {
                a += c_nk(11 - j as u32, x + 1);
                edge4[3 - x as usize] = ep_mod[j];
                x += 1;
            }
        }
        // Then compute the index b < 4! for the permutation in edge4
        let mut b = 0;
        for j in (1..=3).rev() {
            let mut k = 0;
            while edge4[j] != ALL_EDGES[j] {
                rotate_left(&mut edge4, 0, j);
                k += 1;
            }
            b = (j + 1) * b + k;
        }
        24 * a as u16 + b as u16
    }

    /// Set the permutation and location of edges UR, UF, UL and UB.
    /// 
    /// 0 <= u_edges < 11880 in phase 1, 0 <= u_edges < 1680 in phase 2, u_edges = 1656 for solved cube.
    pub fn set_u_edges(&mut self, idx: u16) {
        let mut slice_edge = [UR, UF, UL, UB];
        let other_edge = [DR, DF, DL, DB, FR, FL, BL, BR];
        let mut b = idx % 24; // Permutation
        let mut a = idx / 24; // Location
        let mut ep = [-1; 12];

        let mut j = 1; // generate permutation from index b
        while j < 4 {
            let mut k = b % (j + 1);
            b /= j + 1;
            while k > 0 {
                rotate_right(&mut slice_edge, 0, j as usize);
                k -= 1;
            }
            j += 1;
        }

        let mut x = 4; // set slice edges
        for j in ALL_EDGES {
            if a >= c_nk(11 - j as u32, x) as u16 {
                self.ep[j as usize] = slice_edge[4 - x as usize];
                ep[j as usize] = slice_edge[4 - x as usize] as i32;
                a -= c_nk(11 - j as u32, x) as u16;
                x -= 1;
            }
        }

        let mut x = 0; // set the remaining edges UR..DB
        for j in ALL_EDGES {
            if ep[j as usize] == -1 {
                self.ep[j as usize] = other_edge[x];
                x += 1;
            }
        }
        for _j in 0..4 {
            rotate_left(&mut self.ep, 0, 11);
        }
    }

    /// Get the permutation and location of the edges DR, DF, DL and DB.
    /// 
    /// 0 <= d_edges < 11880 in phase 1, 0 <= d_edges < 1680 in phase 2, d_edges = 0 for solved cube.
    pub fn get_d_edges(&self) -> u16 {
        let mut a = 0;
        let mut x = 0;
        let mut edge4 = [UR; 4];
        let mut ep_mod = self.ep.clone();
        for _j in 0..4 {
            rotate_right(&mut ep_mod, 0, 11);
        }
        // First compute the index a < (12 choose 4) and the permutation array perm.
        for j in ((UR as usize)..=(BR as usize)).rev() {
            if DR <= ep_mod[j] && ep_mod[j] <= DB {
                a += c_nk(11 - j as u32, x + 1);
                edge4[3 - x as usize] = ep_mod[j];
                x += 1;
            }
        }
        // Then compute the index b < 4! for the permutation in edge4
        let mut b = 0;
        for j in (1..=3).rev() {
            let mut k = 0;
            while edge4[j] != ALL_EDGES[j + 4] {
                rotate_left(&mut edge4, 0, j);
                k += 1;
            }
            b = (j + 1) * b + k;
        }
        24 * a as u16 + b as u16
    }

    /// Set the permutation and location of the edges DR, DF, DL and DB.
    /// 
    /// 0 <= d_edges < 11880 in phase 1, 0 <= d_edges < 1680 in phase 2, d_edges = 0 for solved cube.
    pub fn set_d_edges(&mut self, idx: u16) {
        let mut slice_edge = [DR, DF, DL, DB];
        let other_edge = [FR, FL, BL, BR, UR, UF, UL, UB];
        let mut b = idx % 24; // Permutation
        let mut a = idx / 24; // Location
        let mut ep = [-1; 12]; // Invalidate all edge positions

        let mut j = 1; // generate permutation from index b
        while j < 4 {
            let mut k = b % (j + 1);
            b /= j + 1;
            while k > 0 {
                rotate_right(&mut slice_edge, 0, j as usize);
                k -= 1;
            }
            j += 1;
        }

        let mut x = 4; // set slice edges
        for j in ALL_EDGES {
            if a >= c_nk(11 - j as u32, x as u32) as u16 {
                self.ep[j as usize] = slice_edge[4 - x];
                ep[j as usize] = slice_edge[4 - x] as i32;
                a -= c_nk(11 - j as u32, x as u32) as u16;
                x -= 1;
            }
        }

        let mut x = 0; // set the remaining edges UR..DB
        for j in ALL_EDGES {
            if ep[j as usize] == -1 {
                self.ep[j as usize] = other_edge[x];
                x += 1;
            }
        }
        for _j in 0..4 {
            rotate_left(&mut self.ep, 0, 11);
        }
    }

    /// Get the permutation of the 8 corners.
    /// 
    /// 0 <= corners < 40320 defined but unused in phase 1, 0 <= corners < 40320 in phase 2,
    /// 
    /// corners = 0 for solved cube
    pub fn get_corners(&self) -> u16 {
        let mut perm = self.cp.clone(); // duplicate cp
        let mut b = 0;
        for j in ((URF as usize + 1)..=(DRB as usize)).rev() {
            let mut k = 0;
            while perm[j] != ALL_CORNERS[j] {
                rotate_left(&mut perm, 0, j);
                k += 1;
            }
            b = (j + 1) * b + k;
        }
        b as u16
    }

    /// Set the permutation of the 8 corners.
    /// 
    /// 0 <= corners < 40320 defined but unused in phase 1, 0 <= corners < 40320 in phase 2,
    /// 
    /// corners = 0 for solved cube
    pub fn set_corners(&mut self, idx: u16) {
        self.cp = ALL_CORNERS.clone();
        let mut x = idx;
        for j in ALL_CORNERS {
            let mut k = x % (j as u16 + 1);
            x /= j as u16 + 1;
            while k > 0 {
                rotate_right(&mut self.cp, 0, j as usize);
                k -= 1;
            }
        }
    }

    /// Get the permutation of the 8 U and D edges.
    /// 
    /// ud_edges undefined in phase 1, 0 <= ud_edges < 40320 in phase 2, ud_edges = 0 for solved cube.
    pub fn get_ud_edges(&self) -> u16 {
        let mut perm = [UR; 8];
        for i in 0..8 {
            perm[i] = self.ep[i]; // duplicate first 8 elements of ep
        }
        let mut b = 0;
        for j in ((UR as usize + 1)..=(DB as usize)).rev() {
            let mut k = 0;
            while perm[j] != ALL_EDGES[j] {
                rotate_left(&mut perm, 0, j);
                k += 1;
            }
            b = (j + 1) * b + k;
        }
        b as u16
    }

    /// Set the permutation of the 8 U and D edges.
    /// 
    /// ud_edges undefined in phase 1, 0 <= ud_edges < 40320 in phase 2, ud_edges = 0 for solved cube.
    pub fn set_ud_edges(&mut self, idx: usize) {
        let mut x: usize = idx;
        // positions of FR FL BL BR edges are not affected
        for i in 0..8 {
            self.ep[i] = ALL_EDGES[i];
        }
        for j in 0..8 {
            let mut k = x % (j + 1);
            x /= j + 1;
            while k > 0 {
                rotate_right(&mut self.ep, 0, j);
                k -= 1;
            }
        }
    }

    /// Generate a random cube. The probability is the same for all possible states.
    pub fn randomize(&mut self) {
        // The permutation of the 12 edges. 0 <= idx < 12!."""
        let mut idx = random::<usize>() % 479001600; // 12!
        self.cp = ALL_CORNERS.clone();
        for j in ALL_EDGES {
            let mut k = idx % (j as usize + 1);
            idx /= j as usize + 1;
            while k > 0 {
                rotate_right(&mut self.ep, 0, j as usize);
                k -= 1;
            }
        }
        let p = self.edge_parity();
        loop {
            self.set_corners(random::<u16>() % 40320); // 8!
            if p == self.corner_parity() {
                // parities of edge and corner permutations must be the same
                break;
            }
        }
        self.set_flip(random::<u16>() % 2048); // 2^11
        self.set_twist(random::<u16>() % 2187); // 3^7
    }

    /// Check if cubiecube is valid.
    pub fn verify(&self) -> Result<bool, Error> {
        let mut edge_count = [0; 12];
        for i in ALL_EDGES {
            edge_count[self.ep[i as usize] as usize] += 1;
        }
        for i in ALL_EDGES {
            if edge_count[i as usize] != 1 {
                return Err(Error::InvalidEdge);
            }
        }
        let mut s = 0;
        for i in ALL_EDGES {
            s += self.eo[i as usize];
        }
        if s % 2 != 0 {
            return Err(Error::InvalidEdge);
        }

        let mut corner_count = [0; 8];
        for i in ALL_CORNERS {
            corner_count[self.cp[i as usize] as usize] += 1;
        }
        for i in ALL_CORNERS {
            if corner_count[i as usize] != 1 {
                return Err(Error::InvalidCorner);
            }
        }
        let mut s = 0;
        for i in ALL_CORNERS {
            s += self.co[i as usize];
        }
        if s % 3 != 0 {
            return Err(Error::InvalidCorner);
        }

        if self.edge_parity() != self.corner_parity() {
            return Err(Error::InvalidCubieValue);
        }
        Ok(true)
    }
}

/// these cubes represent the basic cube moves.
pub fn basic_move_cubes() -> [CubieCube; 6] {
    let mut basic_move_cube = [CubieCube::default(); 6];
    basic_move_cube[Color::U as usize] = U_MOVE;
    basic_move_cube[Color::R as usize] = R_MOVE;
    basic_move_cube[Color::F as usize] = F_MOVE;
    basic_move_cube[Color::D as usize] = D_MOVE;
    basic_move_cube[Color::L as usize] = L_MOVE;
    basic_move_cube[Color::B as usize] = B_MOVE;
    basic_move_cube
}

/// these cubes represent the all 18 cube moves
pub fn move_cubes() -> [CubieCube; 18] {
    let basic_move_cube = basic_move_cubes();
    let mut move_cube = [CubieCube::default(); 18];
    for c1 in ALL_COLORS {
        let mut cc = CubieCube::default();
        for k1 in 0..3 {
            cc.multiply(basic_move_cube[c1 as usize]);
            move_cube[3 * c1 as usize + k1] = CubieCube {
                cp: cc.cp,
                co: cc.co,
                ep: cc.ep,
                eo: cc.eo,
            };
        }
    }
    move_cube
}

/// Rotate array arr right between left and right. right is includ
pub fn rotate_right<T: Copy>(arr: &mut [T], left: usize, right: usize) {
    let temp = arr[right];
    for i in (left + 1..=right).rev() {
        arr[i] = arr[i - 1];
    }
    arr[left] = temp;
}

/// Rotate array arr left between left and right. right is includ
pub fn rotate_left<T: Copy>(arr: &mut [T], left: usize, right: usize) {
    let temp = arr[left];
    for i in left..right {
        arr[i] = arr[i + 1];
    }
    arr[right] = temp;
}

/// Binomial coefficient [n choose k].
pub fn c_nk(n: u32, k: u32) -> u32 {
    let mut k = k;
    if n < k {
        return 0;
    }
    if k > (n / 2) {
        k = n - k;
    }
    let mut s = 1;
    let mut i = n;
    let mut j = 1;
    while i != n - k {
        s *= i;
        s /= j;
        i -= 1;
        j += 1;
    }
    s
}

#[cfg(test)]
mod test {
    use crate::cubie::*;

    #[test]
    fn test_eq() {
        let state = CubieCube::default();
        let state2 = CubieCube::default();
        assert_eq!(state, state2);
    }

    #[test]
    fn test_multiply() {
        let mut state = CubieCube::default().apply_move(F);
        let s2 = CubieCube::default().apply_move(R);
        state.multiply(s2);

        let fr_state = CubieCube {
            //URF, UFL, ULB, UBR, DFR, DLF, DBL, DRB,
            cp: [URF, DLF, ULB, UFL, DRB, DFR, DBL, UBR],
            co: [1, 2, 0, 2, 1, 1, 0, 2],
            ep: [UF, FL, UL, UB, BR, FR, DL, DB, DR, DF, BL, UR],
            eo: [1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],
        };
        assert_eq!(state, fr_state);
    }

    #[test]
    fn test_inverse() {
        let state = CubieCube {
            cp: [DLF, ULB, DBL, DRB, UBR, UFL, DFR, URF],
            co: [2, 1, 2, 1, 2, 2, 0, 2],
            ep: [BR, BL, UB, UR, DR, FR, FL, UF, DF, DL, DB, UL],
            eo: [1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1],
        };
        let twist = state.get_twist();
        assert_eq!(twist, 1914);
        let ic = state.inverse_cubie_cube();
        let d = CubieCube {
            cp: [DRB, DLF, UFL, DFR, DBL, URF, ULB, UBR],
            co: [1, 1, 2, 1, 0, 1, 1, 2],
            ep: [UB, DB, BR, UL, DR, FR, FL, BL, DF, DL, UF, UR],
            eo: [0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1],
        };
        assert_eq!(ic, d);
        let d2 = ic.inverse_cubie_cube();
        assert_eq!(state, d2);
    }

    #[test]
    fn test_parity() {
        let state = CubieCube::default();

        assert_eq!(state.corner_parity(), true);
        assert_eq!(state.edge_parity(), true);

        let state = CubieCube::from(&vec![R, U, R3, U3, R3, F, R, F3]);

        assert_eq!(state.corner_parity(), true);
        assert_eq!(state.edge_parity(), true);
    }

    #[test]
    fn test_symmetries() {
        let state = CubieCube::default();
        let syms = state.symmetries();
        let d = CubieCube {
            cp: [URF, UBR, DRB, DFR, UFL, ULB, DBL, DLF],
            co: [2, 1, 2, 1, 1, 2, 1, 2],
            ep: [FR, UR, BR, DR, FL, UL, BL, DL, UF, UB, DB, DF],
            eo: [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        };
        let syms32 = d.symmetries();

        assert_eq!(syms.len(), 96);
        assert_eq!(syms32.len(), 12);
        // println!("{:?}", syms32);

        // assert_eq!(syms.sort(), [0..96].into());
        // assert_eq!(state.edge_parity(), true);

        // let state = CubieCube::from(&vec![R, U, R3, U3, R3, F, R, F3]);

        // assert_eq!(state.corner_parity(), true);
        // assert_eq!(state.edge_parity(), true);
    }

    #[test]
    fn test_twist() {
        let mut state = CubieCube::default();
        let d = CubieCube {
            cp: [UFL, URF, UBR, ULB, DLF, DFR, DRB, DBL],
            co: [3, 3, 3, 3, 3, 3, 3, 3],
            ep: [UL, UF, UR, UB, DL, DF, DR, DB, FL, FR, BR, BL],
            eo: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        };
        assert_eq!(state.get_twist(), 0);
        assert_eq!(d.get_twist(), 3279);
        state.set_twist(3279);
        assert_eq!(state.cp[0], URF);
        assert_eq!(state.get_twist(), 1092);
    }

    #[test]
    fn test_flip() {
        let mut state = CubieCube::default();
        let d = CubieCube {
            cp: [UBR, URF, UFL, ULB, DRB, DFR, DLF, DBL],
            co: [0; 8],
            ep: [UB, UR, UF, UL, DB, DR, DF, DL, BR, FR, FL, BL],
            eo: [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
        };
        assert_eq!(state.get_flip(), 0);
        assert_eq!(d.get_flip(), 7);
        state.set_flip(7);
        assert_eq!(state.eo[8], 1);
        assert_eq!(state.get_flip(), 7);
    }

    #[test]
    fn test_slice() {
        let mut state = CubieCube::default();
        let d = CubieCube {
            cp: [URF, UBR, DRB, DFR, UFL, ULB, DBL, DLF],
            co: [2, 1, 2, 1, 1, 2, 1, 2],
            ep: [FR, UR, BR, DR, FL, UL, BL, DL, UF, UB, DB, DF],
            eo: [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        };
        assert_eq!(state.get_slice(), 0);
        assert_eq!(d.get_slice(), 440);
        state.set_slice(440);
        assert_eq!(state.ep[11], DB);
        assert_eq!(state.ep[0], FR);
        assert_eq!(state.get_slice(), 440);
    }

    #[test]
    fn test_slice_sorted() {
        let mut state = CubieCube::default();
        let d = CubieCube {
            cp: [URF, UBR, DRB, DFR, UFL, ULB, DBL, DLF],
            co: [2, 1, 2, 1, 1, 2, 1, 2],
            ep: [FR, UR, BR, DR, FL, UL, BL, DL, UF, UB, DB, DF],
            eo: [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        };
        assert_eq!(state.get_slice_sorted(), 0);
        assert_eq!(d.get_slice_sorted(), 10576);
        state.set_slice_sorted(11576);
        assert_eq!(state.ep[11], DB);
        assert_eq!(state.ep[0], BR);
        assert_eq!(state.get_slice_sorted(), 11576);
    }

    #[test]
    fn test_u_edges() {
        let mut state = CubieCube::default();
        let d = CubieCube {
            cp: [URF, UBR, DRB, DFR, UFL, ULB, DBL, DLF],
            co: [2, 1, 2, 1, 1, 2, 1, 2],
            ep: [FR, UR, BR, DR, FL, UL, BL, DL, UF, UB, DB, DF],
            eo: [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        };
        assert_eq!(state.get_u_edges(), 1656);
        assert_eq!(d.get_u_edges(), 11225);
        state.set_u_edges(11576);
        assert_eq!(state.ep[11], UR);
        assert_eq!(state.ep[0], DF);
        assert_eq!(state.get_u_edges(), 11576);
    }

    #[test]
    fn test_d_edges() {
        let mut state = CubieCube::default();
        let d = CubieCube {
            cp: [URF, UBR, DRB, DFR, UFL, ULB, DBL, DLF],
            co: [2, 1, 2, 1, 1, 2, 1, 2],
            ep: [FR, UR, BR, DR, FL, UL, BL, DL, UF, UB, DB, DF],
            eo: [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        };
        assert_eq!(state.get_d_edges(), 0);
        assert_eq!(d.get_d_edges(), 4519);
        state.set_d_edges(11576);
        assert_eq!(state.ep[11], DR);
        assert_eq!(state.ep[0], FL);
        assert_eq!(state.get_d_edges(), 11576);
    }

    #[test]
    fn test_corners() {
        let mut state = CubieCube::default();
        let d = CubieCube {
            cp: [URF, UBR, DRB, DFR, UFL, ULB, DBL, DLF],
            co: [2, 1, 2, 1, 1, 2, 1, 2],
            ep: [FR, UR, BR, DR, FL, UL, BL, DL, UF, UB, DB, DF],
            eo: [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
        };
        assert_eq!(state.get_corners(), 0);
        assert_eq!(d.get_corners(), 18196);
        state.set_corners(11576);
        assert_eq!(state.cp[1], DRB);
        assert_eq!(state.cp[2], DLF);
        assert_eq!(state.get_corners(), 11576);
    }

    #[test]
    fn test_ud_edges() {
        let mut state = CubieCube::default();
        let d = CubieCube {
            cp: [UFL, URF, UBR, ULB, DLF, DFR, DRB, DBL],
            co: [3, 3, 3, 3, 3, 3, 3, 3],
            ep: [UL, UF, UR, UB, DL, DF, DR, DB, FL, FR, BR, BL],
            eo: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        };
        assert_eq!(state.get_ud_edges(), 0);
        assert_eq!(d.get_ud_edges(), 3747);
        state.set_ud_edges(11576);
        assert_eq!(state.ep[11], BR);
        assert_eq!(state.ep[0], UR);
        assert_eq!(state.get_ud_edges(), 11576);
    }

    #[test]
    fn test_randomize() {
        let mut state = CubieCube::default();
        state.randomize();
        assert_eq!(state.verify().unwrap(), true);
        // println!("{}", state);
    }

    #[test]
    fn test_mult() {
        let state = CubieCube::default().apply_move(R);
        assert_eq!(state, R_MOVE);

        let r2_state = CubieCube::default().apply_move(R).apply_move(R);
        assert_eq!(r2_state, R_MOVE * R_MOVE);

        let r3_state = r2_state.apply_move(R);
        assert_eq!(r3_state, r2_state * R_MOVE);

        let fr_state = CubieCube {
            //URF, UFL, ULB, UBR, DFR, DLF, DBL, DRB,
            cp: [URF, DLF, ULB, UFL, DRB, DFR, DBL, UBR],
            co: [1, 2, 0, 2, 1, 1, 0, 2],
            ep: [UF, FL, UL, UB, BR, FR, DL, DB, DR, DF, BL, UR],
            eo: [1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],
        };

        assert_eq!(F_MOVE * R_MOVE, fr_state);
    }

    #[test]
    fn test_move_sequence() {
        // (R U R' U') * 6
        let moves = vec![
            R, U, R3, U3, R, U, R3, U3, R, U, R3, U3, R, U, R3, U3, R, U, R3, U3, R, U, R3, U3,
        ];
        let state = CubieCube::default().apply_moves(&moves);

        assert_eq!(state, SOLVED_CUBIE_CUBE);
    }

    #[test]
    fn test_scramble() {
        // U F' D' F2 D B2 D' R2 U' F2 R2 D2 R2 U' L B L R F' D B'
        let scramble = vec![
            U, F3, D3, F2, D, B2, D3, R2, U3, F2, R2, D2, R2, U3, L, B, L, R, F3, D, B3,
        ];
        let state = CubieCube::default().apply_moves(&scramble);

        let expected = CubieCube {
            cp: [DFR, UBR, DLF, ULB, DRB, UFL, URF, DBL],
            co: [2, 0, 1, 2, 0, 0, 2, 2],
            ep: [DF, UB, FL, BL, BR, UL, DR, FR, DL, DB, UF, UR],
            eo: [1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1],
        };

        assert_eq!(state, expected);
    }

    #[test]
    fn test_perm_count() {
        let state = CubieCube::default();

        assert_eq!(state.count_corner_perm(), 0);
        assert_eq!(state.count_edge_perm(), 0);

        let state = CubieCube::from(&vec![R, U, R3, U3]);

        assert_eq!(state.count_corner_perm(), 2);
        assert_eq!(state.count_edge_perm(), 2);

        let state = CubieCube::from(&vec![
            R, U3, R3, U3, R, U, R, D, R3, U3, R, D3, R3, U2, R3, U3,
        ]);

        assert_eq!(state.count_corner_perm(), 1);
        assert_eq!(state.count_edge_perm(), 1);
    }

    #[test]
    fn test_twist_count() {
        let state = CubieCube::default();

        assert_eq!(state.count_corner_twist(), 0);
        assert_eq!(state.count_edge_twist(), 0);

        let state = CubieCube::from(&vec![R, U, R3, U3, R3, F, R, F3]);

        assert_eq!(state.count_corner_twist(), 3);
        assert_eq!(state.count_edge_twist(), 2);
    }
}