Cマガ電脳クラブ(第147回) リバース・スーバリ

問題

Fig.1の例のように、「CHAR」という文字列を逆順の「RAHC」にしたい。
移動のしかたは「左側から2文字以上をそのまま裏返す」である。
例では、下線部を6回ひっくり返して完成している。
使うアルファベットの文字の左右対称性を利用してかまわないことにする。

では、この移動を使って何回で「CMAGAZINE」を「ENIZAGAMC」にできるだろうか？
最低回数をお答えいただきたい。

Fig.1 文字列

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

    static void Main()
    {
        Solve("CHAR");
        Solve("CMAGAZINE");
    }

    struct JyoutaiDef
    {
        internal string CurrStr;
        internal int Level;
        internal List<string> Log;
    }

    static void Solve(string pFirstStr)
    {
        for (int I = 1; I < int.MaxValue; I++) {
            int LevelLimitSei = I / 2;
            int LevelLimitRev = I - LevelLimitSei;

            JyoutaiDef[] SeiArr = ExecDFS(LevelLimitSei, pFirstStr);

            string RevStr = new string(pFirstStr.Reverse().ToArray());
            JyoutaiDef[] RevArr = ExecDFS(LevelLimitRev, RevStr);

            var IndDict = new Dictionary<string, int>();
            for (int J = 0; J <= RevArr.GetUpperBound(0); J++)
                IndDict.Add(RevArr[J].CurrStr, J);

            for (int J = 0; J <= SeiArr.GetUpperBound(0); J++) {
                if (IndDict.ContainsKey(SeiArr[J].CurrStr) == false) continue;
                int wkInd = IndDict[SeiArr[J].CurrStr];

                Console.WriteLine("{0}手の解を発見。経過時間={1}", I, sw.Elapsed);
                var AnswerList = new List<string>(SeiArr[J].Log);
                AnswerList.AddRange(RevArr[wkInd].Log.AsEnumerable().Reverse().Skip(1));
                for (int K = 0; K <= AnswerList.Count - 1; K++) {
                    Console.WriteLine("{0,2}手目 {1}", K, AnswerList[K]);
                }
                return;
            }
        }
    }

    //深さ制限を引数として、深さ優先探索を行う
    static JyoutaiDef[] ExecDFS(int pLevelLimit, string pFirstStr)
    {
        var WillReturn = new List<JyoutaiDef>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrStr = pFirstStr;
        WillPush.Level = 0;
        WillPush.Log = new List<string>() { pFirstStr };
        Stk.Push(WillPush);

        var MinTesuuDict = new Dictionary<string, int>();
        MinTesuuDict.Add(pFirstStr, 0);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.Level == pLevelLimit) {
                WillReturn.Add(Popped);
                continue;
            }

            int UB = pFirstStr.Length - 1;
            for (int I = 1; I <= UB; I++) {
                char[] wkCharArr = Popped.CurrStr.ToCharArray();
                for (int J = 0; J <= I; J++) {
                    wkCharArr[J] = DeriveConvChar(Popped.CurrStr[I - J]);
                }

                WillPush.CurrStr = new string(wkCharArr.ToArray());
                WillPush.Level = Popped.Level + 1;

                //メモ化探索
                int MinTesuu;
                if (MinTesuuDict.TryGetValue(WillPush.CurrStr, out MinTesuu)) {
                    if (MinTesuu <= WillPush.Level) continue;
                }
                MinTesuuDict[WillPush.CurrStr] = WillPush.Level;

                WillPush.Log = new List<string>(Popped.Log) { WillPush.CurrStr };
                Stk.Push(WillPush);
            }
        }
        WillReturn.RemoveAll(X => MinTesuuDict[X.CurrStr] < X.Level);
        return WillReturn.ToArray();
    }

    //変換前の文字を引数とし、変換後の文字を返す
    static char DeriveConvChar(char pPrevChar)
    {
        char WillReturn = pPrevChar;

        Action<char, char> wkAct = (p1, p2) =>
        {
            if (WillReturn == p1) WillReturn = p2;
            else if (WillReturn == p2) WillReturn = p1;
        };

        wkAct('c', 'C');
        wkAct('r', 'R');

        wkAct('g', 'G');
        wkAct('z', 'Z');
        wkAct('n', 'N');
        wkAct('e', 'E');

        return WillReturn;
    }
}

実行結果

6手の解を発見。経過時間=00:00:00.0203551
 0手目 CHAR
 1手目 AHcR
 2手目 rCHA
 3手目 cRHA
 4手目 AHrC
 5手目 HArC
 6手目 RAHC
12手の解を発見。経過時間=00:00:02.0898605
 0手目 CMAGAZINE
 1手目 nIzAgAMcE
 2手目 eCMAGAZIN
 3手目 IzAgAMcEN
 4手目 ZIAgAMcEN
 5手目 neCMAGAIz
 6手目 AgAMcENIz
 7手目 AGAMcENIz
 8手目 IneCMAgAz
 9手目 cENIMAgAz
10手目 ZAGAMIneC
11手目 MAgAzIneC
12手目 ENIZAGAMC

解説

計算量を減らすために、
双方向に、反復深化深さ優先探索してます。