using System;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Linq;

namespace PLL
{
    // <summary>just to make it easier to print</summary>
    public class Output
    {
        public void print(string s)
        {
            Console.WriteLine(s);
        }
    }

    // <summary>handy routines, in this case swapCharacters</summary>
    public class Util
    {
        // Swaps characters in a string. Must copy the characters and reallocate the string.
        public static string swapCharacters(string value, int position1, int position2)
        {
            char[] array = value.ToCharArray();
            char temp = array[position1];
            array[position1] = array[position2];
            array[position2] = temp;
            return new string(array);
        }
    }

    // <summary>A move consists of a face and a count, like "R2"</summary>
    public class Move
    {
        public string face;
        public int count;

        public Move(string f, int c) {
            face = f;
            count = c;
        }

        // <summary>clone</summary>
        public Move(Move original) {
            face = original.face;
            count = original.count;
        }

        // <summary>return a move as string face+count</summary>
        public override string ToString()
        {
           //return "move: " + face + Environment.NewLine + "count: " + count;
            return face + count.ToString();
        }

        public void print() {
            Console.WriteLine(this);
        }
    }

    // <summary>Algorithm works on strings representing cube algorithms</summary>
    public class Algorithm
    {
        public string alg;

        public Algorithm(string s)
        {
            this.alg=s;
        }

        public string clean(){
            if (alg=="") {
                return alg;
            }

            string tokens = " ()-\'";
            string input_clean = "";
            char prevCh = '\0';

            foreach(char ch in alg)
            {
                if (tokens.IndexOf(ch)==-1) {
                    input_clean += ch;
                }

                // only add prime when not right after a move token, e.g. R'
                // so skip R2' (becomes R2)
                if (ch=='\'' && prevCh!='2') {
                    input_clean += ch;
                }
                prevCh = ch;
            }
            return input_clean;
        }

        public string normalize(){
            char prevCh='\0';
            string temp = this.alg.Replace("\'", "3");
            string alg_normal="";

            if (this.alg=="")
                return "";

            foreach(char ch in temp)
            {
                // when both ch and prev are moves, insert a 1 between them
                // RL becomes R1L
                if (prevCh!='\0' && !char.IsDigit(prevCh) && !char.IsDigit(ch)) {
                    alg_normal += '1';
                }
                alg_normal += ch;
                prevCh = ch;
            }
            if (!char.IsDigit(prevCh)) {
                alg_normal += '1';
            }
            return alg_normal;
        }

        public string denormalize(){
            string alg = this.alg.Replace("3", "'");
            alg = alg.Replace("1", "");
            return alg;
        }

        public string inverse(){
            return "";
        }

        public string compact(){
            string face;
            int count;

            Move prevMove = new Move("",0);

            // clean input leaves only the moves
            alg = this.clean();

            // process to get normalized alg (e.g. R2F1L3)
            alg = this.normalize();

            // convert to array of Move objects {R,2},{F,1},{L,3}
            var moves = new List<Move>();
            var newMoves = new List<Move>();
            for (int i=0; i < alg.Length; i+=2) {
                face = alg.Substring(i,1);
                count = Convert.ToInt32(alg.Substring(i+1,1));
                moves.Add(new Move(face, count));
            }

            // merge Moves to remove duplicates
            // e.g. D2D2 => D4 => D0
            int last;
            foreach(Move move in moves)
            {
                // if a duplicate is found
                if (move.face == prevMove.face) {
                    last = newMoves.Count-1;
                    // add the moves
                    newMoves[last].count += move.count;
                    // mod 4 to remove 360 turns
                    newMoves[last].count %= 4;
                    if (newMoves[last].count == 0)
                        newMoves.RemoveAt(last);
                }
                else
                    newMoves.Add(move);
                prevMove = new Move(move);
            }
            // convert to string again
            string s = "";
            foreach(Move move in newMoves)
                s += move;
            return s;
        }

    }

    public class Cases
    {
        public static string Aa,Ab,E,F,Ga,Gb,Gc,Gd,H,Ja,Jb,Na,Nb,Ra,Rb,T,Ua,Ub,V,Y,Z;

        public static void Init() {
            Aa = "(y) R2 F2 (R' B' R) F2 (R' B R')";
            Ab = "R B' R F2 R' B R F2 R2";
            E  = "(x) U R' U' L U R U' r2 U' R U L U' R' U x";
            F  = "R' U R U' R2 y' R' U' R U y x R U R' U' R2 x' U'";
            Ga = "(y) R2' u R' U R' U' R u' R2 y' R' U R y'";
            Gb = "L' U' L F2 z' R U' L U L' U R' F2 z";
            Gc = "(y) R2' u' R U' R U R' u R2 y R U' R'";
            Gd = "(y2) R U R' F2 D' L U' L' U L' D F2";
            H  = "M2 U M2 U2 M2 U M2";
            Ja = "(y2) x U2 r' U' r U2 l' U R' U' R2 x2 y2";
            Jb = "(y2) F2 R U R' F2 L D' L D L2";
            Na = "z U R' D R2 U' R (D' U) R' D R2 U' R D' R z'";
            Nb = "R' U L' U2 R U' L R' U L' U2 R U' L";
            Ra = "(y2) z U R2 U' R2 U F' U' R' U R U F U2 R z' y2";
            Rb = "R' U2 R U' y' R' F R B' R' F' R z x' R' U R' z' y2";
            T  = "R U R' U' R' F R2 U' R' U' R U R' F'";
            Ua = "(y2) R U' R U R U R U' R' U' R2";
            Ub = "R' U R' U' R' U' R' U R U R2";
            V  = "y L' U R U' L U L' U R' U' L U2 R U2 R'";
            Y  = "F R U' R' U' R U R' F' R U R' U' R' F R F'";
            Z  = "y U R' U' R U' R U R U' R' U R U R2 U' R' U";
        }

        public static Dictionary<string,string> All() {
            var algs = new Dictionary<string,string>() {};
            algs.Add("Aa", Aa);
            algs.Add("Ab", Ab);
            algs.Add("E", E);
            algs.Add("F", F);
            algs.Add("Ga", Ga);
            algs.Add("Gb", Gb);
            algs.Add("Gc", Gc);
            algs.Add("Gd", Gd);
            algs.Add("H", H);
            algs.Add("Ja", Ja);
            algs.Add("Jb", Jb);
            algs.Add("Na", Na);
            algs.Add("Nb", Nb);
            algs.Add("Ra", Ra);
            algs.Add("Rb", Rb);
            algs.Add("T", T);
            algs.Add("Ua", Ua);
            algs.Add("Ub", Ub);
            algs.Add("V", V);
            algs.Add("Y", Y);
            algs.Add("Z", Z);
            return algs;
        }

        public static Dictionary<string,string> NonSym() {
            var algs = new Dictionary<string,string>();
            algs.Add("E", E);
            algs.Add("F", F);
            algs.Add("H", H);
            algs.Add("Ja", Ja);
            algs.Add("Jb", Jb);
            algs.Add("Na", Na);
            algs.Add("Nb", Nb);
            algs.Add("Ra", Ra);
            algs.Add("Rb", Rb);
            algs.Add("T", T);
            algs.Add("V", V);
            algs.Add("Y", Y);
            algs.Add("Z", Z);
            return algs;        }

        public static string[] Rotations() {
            return new string[] { "", "y", "y'", "y2", "U", "U'", "U2", "yU", "yU'", "yU2", "y'U", "y'U'", "y'U2", "y2U", "y2U'", "y2U2" };
        }
    }

    public class Cube
    {
        const string defaultStickers = "rrrrrrrrrgggggggggwwwwwwwwwooooooooobbbbbbbbbyyyyyyyyy";
        string stickers;

        // constructor
        public Cube()
        {
            // initialize stickers
            stickers = defaultStickers;
        }

        public void executePermutation(int a, int b, int c, int d){
            stickers = Util.swapCharacters(stickers, a, b);
            stickers = Util.swapCharacters(stickers, a, c);
            stickers = Util.swapCharacters(stickers, a, d);
        }

        public void move(string token){
            var moveTransforms = new Dictionary<string, string>
            {
                {"u","UEEE"}, {"d","DE"}, {"f","FS"}, {"b","BSSS"}, {"l","LM"}, {"r","RMMM"}, {"x","rLLL"}, {"y","uDDD"}, {"z","fBBB"}
            };

            // recursive calls to walk through the translated lowercase moves
            //Console.WriteLine(token.Length);
            if (token.Length > 1) {
                foreach (char ch in token)
                    this.move(ch.ToString());
                    return;
            }
            try {
                switch (token) {
                    case "U":
                        //one of the elementary move functions. Uses the executePermutation function
                        //five times to make five 4-cycles of stickers:
                        this.executePermutation(53, 51, 45, 47);
                        // top layer
                        this.executePermutation(50, 52, 48, 46);
                        this.executePermutation(2, 38, 29, 11);
                        this.executePermutation(1, 37, 28, 10);
                        this.executePermutation(0, 36, 27, 9);
                        break;
                    case "D":
                        this.executePermutation(20, 26, 24, 18);
                        this.executePermutation(23, 25, 21, 19);
                        this.executePermutation(8, 17, 35, 44);
                        this.executePermutation(7, 16, 34, 43);
                        this.executePermutation(6, 15, 33, 42);
                        break;
                    case "F":
                        this.executePermutation(2, 8, 6, 0);
                        this.executePermutation(5, 7, 3, 1);
                        this.executePermutation(9, 20, 44, 51);
                        this.executePermutation(12, 19, 41, 52);
                        this.executePermutation(15, 18, 38, 53);
                        break;
                    case "B":
                        this.executePermutation(29, 35, 33, 27);
                        this.executePermutation(32, 34, 30, 28);
                        this.executePermutation(47, 36, 24, 17);
                        this.executePermutation(46, 39, 25, 14);
                        this.executePermutation(45, 42, 26, 11);
                        break;
                    case "R":
                        this.executePermutation(11, 17, 15, 9);
                        this.executePermutation(14, 16, 12, 10);
                        this.executePermutation(2, 47, 33, 20);
                        this.executePermutation(5, 50, 30, 23);
                        this.executePermutation(8, 53, 27, 26);
                        break;
                    case "L":
                        this.executePermutation(38, 44, 42, 36);
                        this.executePermutation(41, 43, 39, 37);
                        this.executePermutation(0, 18, 35, 45);
                        this.executePermutation(3, 21, 32, 48);
                        this.executePermutation(6, 24, 29, 51);
                        break;
                    case "M":
                        this.executePermutation(4, 22, 31, 49 );
                        this.executePermutation(1, 19, 34, 46 );
                        this.executePermutation(7, 25, 28, 52 );
                        break;
                    case"E":
                        this.executePermutation(4, 13, 31, 40);
                        this.executePermutation(5, 14, 32, 41);
                        this.executePermutation(3, 12, 30, 39);
                        break;
                    case "S":
                        this.executePermutation(49, 13, 22, 40);
                        this.executePermutation(50, 16, 21, 37);
                        this.executePermutation(48, 10, 23, 43);
                        break;
                    default:
                        // u,d,f,b,l,r,x,y,z
                        this.move(moveTransforms[token]);
                        break;
                    }
                }
                catch (Exception e){
                    Console.WriteLine("{0} Exception caught.", e);
                }
            }

        public void setMode(string mode){
        }

        public string execute(string alg, string mode){
            string face;
            int count;

            // prepare with a certain mode if given
            if (mode!="") {
                this.setMode(mode);
            }

            if (alg=="")
                return this.stickers;

            // walk through all moves in a normalized alg
            for (int i=0; i < alg.Length; i+=2) {
                // define Move (move) and quantifier
                face = alg[i].ToString();
                count = Convert.ToInt16(alg[i+1].ToString());
                // move a face n times
                foreach (int j in Enumerable.Range(1,count))
                    this.move(face);
            }
            return this.stickers;
        }

        public string execute(string alg) {
            this.execute(alg, "");
            return this.stickers;
        }

        public string toAppletStickers(bool delta, string separator, bool outputAsPositions){
            return "";
        }

        public string toImageCubeStickers(){
            string[] faces;
            string up, front, right;

            faces = new string[6];
            foreach (int i in Enumerable.Range(0,5))
                faces[i]=stickers.Substring(i*9, 9);
            up = faces[5];
            front = faces[0];
            right = faces[1];

            return up + front + right;
        }

        public string getSticker(string position){
            return "";
        }

        public bool stickersMatch(string s1, string s2){
            return false;
        }

        public string[] getPieceOrientations(string piece){
            return null;
        }

        public bool isPieceSolved(string piece){
            return false;
        }

        public string[] getStickers(string position){
            return null;
        }

        public string locatePiece(string piece){
            return "";
        }

        public void performAlg(string input, bool inverse){

            // clean input leaves only the moves
            Algorithm a = new Algorithm(input);
            a.alg = a.compact();

            // process inverse of alg
            if (inverse) {
                a.alg = a.inverse();
            }

            // perform inverse on the stickers
            this.stickers = this.execute(a.alg);
        }

        public void performAlg(string input)
        {
            this.performAlg(input, false);
        }

        public bool findMatches()
        {
            int n;
            string tab;
            string[] auf, rotations;
            var o = new Output();
            string alg, def;

            tab = "\t";
            Cases.Init();
            Dictionary<string,string> algs = Cases.All();
            n = algs.Count;
            long sentinel = 2000000;
            auf = Cases.Rotations();
            rotations = new string[] {"","y","y'","y2"};
            foreach (KeyValuePair<string, string>alg1 in algs)
                foreach (KeyValuePair<string, string>alg2 in algs)
                    foreach (string adjust in auf)
                        foreach(KeyValuePair<string, string>alg4 in algs)
                            foreach (string rotation in rotations)
                            {
                                Cube c = new Cube();
                                //if (alg1.Value==alg2.Value || alg1.Value==alg4.Value || alg2.Value==alg4.Value )
                                //  continue;
                                alg = alg1.Value + " " + alg2.Value + " " + adjust + " " + alg4.Value + " " + rotation;
                                def = alg1.Key + tab + alg2.Key + tab + adjust + tab + alg4.Key + tab + rotation
                                c.performAlg(alg);
                                if (c.stickers == Cube.defaultStickers)
                                    o.print(def);
                                if (sentinel % 1000 == 0 && false)
                                    o.print("n:" + s.ToString());
                                if (sentinel-- < 1)
                                    return false;
                            }
                        return false;
        }

        // search for a sequence of PLLs that end in a solved state
        public string findPath()
        {

        }

        public static void Main()
        {
            Cube c = new Cube();
            c.findMatches();
        }

    }
}