Problem79 パスコードの導出

問題

オンラインバンクで通常使われるsecurity methodは,
パスコードからランダムに選んだ3文字をユーザーに要求するものである.

たとえば, パスコードが531278のとき, 2番目, 3番目, 5番目の文字を要求されるかもしれない.
このとき, 期待される答えは: 317 である.

テキストファイルには,ログインに成功した50回の試行が記録されている.

3つの文字が常に順番通りに要求されるとするとき,
テキストファイルを分析して, 可能なパスコードのなかで最も短いものを見つけよ.

ソース

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

class Program
{
    static List<string> mAcceptStrList = new List<string>();

    static void Main()
    {
        mAcceptStrList.Add("319");
        mAcceptStrList.Add("680");
        mAcceptStrList.Add("180");
        mAcceptStrList.Add("690");
        mAcceptStrList.Add("129");
        mAcceptStrList.Add("620");
        mAcceptStrList.Add("762");
        mAcceptStrList.Add("689");
        mAcceptStrList.Add("762");
        mAcceptStrList.Add("318");
        mAcceptStrList.Add("368");
        mAcceptStrList.Add("710");
        mAcceptStrList.Add("720");
        mAcceptStrList.Add("710");
        mAcceptStrList.Add("629");
        mAcceptStrList.Add("168");
        mAcceptStrList.Add("160");
        mAcceptStrList.Add("689");
        mAcceptStrList.Add("716");
        mAcceptStrList.Add("731");
        mAcceptStrList.Add("736");
        mAcceptStrList.Add("729");
        mAcceptStrList.Add("316");
        mAcceptStrList.Add("729");
        mAcceptStrList.Add("729");
        mAcceptStrList.Add("710");
        mAcceptStrList.Add("769");
        mAcceptStrList.Add("290");
        mAcceptStrList.Add("719");
        mAcceptStrList.Add("680");
        mAcceptStrList.Add("318");
        mAcceptStrList.Add("389");
        mAcceptStrList.Add("162");
        mAcceptStrList.Add("289");
        mAcceptStrList.Add("162");
        mAcceptStrList.Add("718");
        mAcceptStrList.Add("729");
        mAcceptStrList.Add("319");
        mAcceptStrList.Add("790");
        mAcceptStrList.Add("680");
        mAcceptStrList.Add("890");
        mAcceptStrList.Add("362");
        mAcceptStrList.Add("319");
        mAcceptStrList.Add("760");
        mAcceptStrList.Add("316");
        mAcceptStrList.Add("729");
        mAcceptStrList.Add("380");
        mAcceptStrList.Add("319");
        mAcceptStrList.Add("728");
        mAcceptStrList.Add("716");

        var AppearedCharSet = new HashSet<char>();
        mAcceptStrList.ForEach(X => AppearedCharSet.UnionWith(X));
        char[] AppearedCharArr = AppearedCharSet.ToArray();

        Console.WriteLine("登場している数字は、{0}通りです。", AppearedCharArr.Length);
        Console.WriteLine("解の長さ上限を、{0}として深さ優先探索します。", AppearedCharArr.Length);

        var Stk = new Stack<string>();
        foreach (char EachKouho in AppearedCharArr) {
            Stk.Push(EachKouho.ToString());
        }

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

            if (Popped.Length == AppearedCharArr.Length) {
                if (IsOKOrder(Popped)) {
                    Console.WriteLine("解は{0}", Popped);
                    break;
                }
                continue;
            }

            foreach (char EachKouho in AppearedCharArr) {
                Stk.Push(Popped + EachKouho.ToString());
            }
        }
    }

    static bool IsOKOrder(string pStr)
    {
        foreach (string EachAcceptStr in mAcceptStrList) {
            int I = 0;

            bool IsOK = false;
            for (int J = 0; J <= pStr.Length - 1; J++) {
                if (pStr[J] == EachAcceptStr[I]) {
                    if (++I > EachAcceptStr.Length - 1) {
                        IsOK = true;
                        break;
                    }
                }
            }
            if (IsOK == false) return false;
        }
        return true;
    }
}

実行結果

登場している数字は、8通りです。
解の長さ上限を、8として深さ優先探索します。
解は73162890

解説

登場している数字は8通りあり、
解の長さ上限を、8として深さ優先探索して、
見つかった解の長さが8なので題意を満たしてます :-)