Problem32 2から9までを1回ずつ使う掛け算

問題

7254は面白い性質を持っている. 39 × 186 = 7254と書け, 掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する.
掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ.

いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

ソース (正規表現もどきを使う方法)

#include <string>
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <numeric>

bool IsOKPattern(std::string pTarget);
int ExtractKou(int pKouNo,std::string pTarget);

void main()
{
    const std::string Kouho = "123456789*=";
    std::stack<std::string> stk;

    for (int I = 0; I <= (int)Kouho.length() - 1; I++) {
        if (Kouho.at(I) != '*' && Kouho.at(I) != '=') {
            stk.push(Kouho.substr(I,1));
        }
    }

    std::vector<int> AnsVect;

    while (stk.empty() == false) {
        std::string Popped = stk.top(); stk.pop();

        if(Popped.length() == Kouho.length()) {
            if(IsOKPattern(Popped)==false) continue;

            int kou1 = ExtractKou(1,Popped);
            int kou2 = ExtractKou(2,Popped);
            int kou3 = ExtractKou(3,Popped);

            if (kou1 < kou2 && kou1 * kou2 == kou3) {
                if(std::find(AnsVect.begin(),AnsVect.end(),kou3)==AnsVect.end()){
                    AnsVect.push_back(kou3);
                    std::cout << Popped.c_str() << std::endl;
                }
            }
            continue;
        }

        for (int I = 0; I <= (int)Kouho.length() - 1; I++) {
            if (Popped.find(Kouho.at(I)) != std::string::npos) continue;

            std::string WillPush = Popped + Kouho.at(I);
            if (WillPush.find("=*") != std::string::npos) continue;
            if (WillPush.find("*=") != std::string::npos) continue;
            if (WillPush.find("=") != std::string::npos
             && WillPush.find("*") == std::string::npos) continue;

            // =がない状態で5桁の数値があったら枝切り
            if (WillPush.find("=") == std::string::npos){
                bool WillEdakiri = false; int NumCnt = 0;
                for(int I=0;I<= (int)WillPush.length()-1;I++){
                    if('1' <= WillPush.at(I) && WillPush.at(I) <= '9') NumCnt++;
                    else NumCnt=0;

                    if(NumCnt == 5) WillEdakiri=true;
                }
                if(WillEdakiri) continue;
            }

            stk.push(WillPush);
        }
    }
    printf("合計=%d\n",std::accumulate(AnsVect.begin(),AnsVect.end(),0));
}

//文字列がマッチパターン^[1-9]+\*[1-9]+=[1-9]+$を満たすかを返す
bool IsOKPattern(std::string pTarget)
{
    int Jyoutai=0;
    //状態1 ^[1-9]+
    //状態2 \*
    //状態3 [1-9]+
    //状態4 =
    //状態5 [1-9]+$

    for(int I=0;I<= (int)pTarget.length()-1;I++){
        if('1' <= pTarget.at(I) && pTarget.at(I) <= '9'){
            if (Jyoutai == 0){
                Jyoutai=1;
                continue;
            }
            else if (Jyoutai == 1 || Jyoutai == 3 || Jyoutai == 5)
                continue;
            else if (Jyoutai == 2 || Jyoutai == 4){
                Jyoutai++;
                continue;
            }
        }
        else if (pTarget.at(I) == '*'){
            if (Jyoutai == 1){
                Jyoutai++;
                continue;
            }
            return false;
        }
        else if (pTarget.at(I) == '='){
            if (Jyoutai == 3){
                Jyoutai++;
                continue;
            }
            return false;
        }
    }
    return Jyoutai==5;
}

//^[1-9]+\*[1-9]+=[1-9]+$ のpKouNo番目の[1-9]+を数値に変換して返す
int ExtractKou(int pKouNo,std::string pTarget)
{
    std::string CapturedStr;
    bool IsCapture = (pKouNo==1);

    for(int I=0;I<= (int)pTarget.length()-1;I++){
        if('1' <= pTarget.at(I) && pTarget.at(I) <= '9'){
            if(IsCapture) CapturedStr += pTarget.at(I);
        }
        else if (pTarget.at(I) == '*'){
            IsCapture = (pKouNo==2);
        }
        else if (pTarget.at(I) == '='){
            IsCapture = (pKouNo==3);
        }
    }
    return atoi(CapturedStr.c_str());
}

実行結果 (正規表現もどきを使う方法)

4*1963=7852
4*1738=6952
48*159=7632
42*138=5796
39*186=7254
28*157=4396
27*198=5346
合計=45228

ソース (正規表現もどきを使わない方法)

#include <vector>
#include <valarray>
#include <algorithm>
#include <stdio.h>
#include <numeric>

bool IsKouho(int pTargetInt);
bool IsOK(std::valarray<int> &pTargetArr);

void main()
{
    std::vector<int> KouhoVect;
    for (int I = 1; I <= 9999; I++) {
        if (IsKouho(I)) KouhoVect.push_back(I);
    }

    std::vector<int> ProdValVect;

    for (int I = 1; I <= (int)KouhoVect.size() - 1; I++) {
        for (int J = I + 1; J <= (int)KouhoVect.size() - 1; J++) {
            int ProdVal = KouhoVect.at(I) * KouhoVect.at(J);
            if(ProdVal >= 9876543) break; //積の値で枝切り

            if(std::find(ProdValVect.begin(),ProdValVect.end(),ProdVal) != ProdValVect.end())
                continue;

            std::valarray<int> WKArr(3);
            WKArr[0] = KouhoVect.at(I); WKArr[1] = KouhoVect.at(J); WKArr[2] = ProdVal;
            if(IsOK(WKArr)) {
                ProdValVect.push_back(ProdVal);
                printf("%d * %d = %d\n",KouhoVect.at(I),KouhoVect.at(J),ProdVal);
            }
        }
    }
    printf("合計=%d\n",std::accumulate(ProdValVect.begin(),ProdValVect.end(),0));
}

bool IsKouho(int pTargetInt)
{
    std::valarray<bool> CheckNumArr(false,10);
    do {
        int wk = pTargetInt % 10;
        if (wk == 0) return false;
        if (CheckNumArr[wk]) return false;
        CheckNumArr[wk] = true;

        pTargetInt /= 10;
    } while (pTargetInt > 0);
    return true;
}

bool IsOK(std::valarray<int> &pTargetArr)
{
    std::valarray<bool> CheckNumArr(false,10);
    for(int I=0;I<=(int)pTargetArr.size()-1;I++){
        int CopiedInt = pTargetArr[I];
        do {
            int wk = CopiedInt % 10;
            if (wk == 0) return false;
            if (CheckNumArr[wk]) return false;
            CheckNumArr[wk] = true;

            CopiedInt /= 10;
        } while (CopiedInt > 0);
    }
    for (int I = 1; I <= 9; I++)
        if (CheckNumArr[I] == false) return false;

    return true;
}

実行結果 (正規表現もどきを使わない方法)

4 * 1738 = 6952
4 * 1963 = 7852
12 * 483 = 5796
18 * 297 = 5346
28 * 157 = 4396
39 * 186 = 7254
48 * 159 = 7632
合計=45228

解説

正規表現もどきを使う方法では、深さ優先探索で組み合わせを列挙しつつ、枝切りも行ってます。

ですが、正規表現もどきを使わない方法のほうが、圧倒的に高速ですね。