DouKaku?beta

challenge 小町算

古典的なパズルである小町算を解くプログラムを作成してください。

小町算とは：

1□2□3□4□5□6□7□8□9＝100

四角の中に、空白、＋、－、×、÷のいずれかを一つ入れ、等式が成り立つようにするパズルです。

解答例：

1－2－3＋4×56÷7＋8×9＝100

1＋234×5÷6－7－89＝100

参考：　http://ja.wikipedia.org/wiki/%E5%B0%8F%E7%94%BA%E7%AE%97

  • evalやそれに類するものを使うか否かは自由です。
  • 割り算の際には小数点以下の切捨てが起こらないのが望ましいです。(必須ではない)
    • 切捨てが起こる場合の解答例：1÷2÷3＋4＋5÷6＋7＋89＝100
  • 余裕があれば括弧を含むようにしてもいいかもしれません。

手元で20数行ほどのPythonスクリプトを書いてみたところ、101個の解答が得られました。

post comment

Posted feedbacks - C++

余裕があったら...という要望が、いつの間にか仕様になってるなんてコトはいつものこと。括弧付きも計算できるように実装しとくけど、計算しない方向で。

計算式を、逆ポーランド形式に変換して計算（総当たり）。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <ctype.h>
#include <math.h>
#include <iostream>
#include <queue>
#include <stack>

std::queue<std::string> ToReversePolish(std::string strExp)
{
    std::queue<std::string> result;
    bool bNum = false;
    std::stack<char> buff;
    for (std::string::iterator p = strExp.begin(); p != strExp.end(); p++) {
        if (isspace(*p) != 0)
            continue;
        if ((*p >= '0') && (*p <= '9')) {
            if (bNum) { result.back() += *p; }
            else      { result.push( std::string(1, *p) ); }
        }
        else if ((*p == '*') || (*p == '/') || (*p == '+') || (*p == '-')) {
            while ((buff.empty() == false) && (buff.top() != '(') && (buff.top() != '+') && (buff.top() != '-')) {
                result.push( std::string(1, buff.top()) );
                buff.pop();
            }
            buff.push(*p);
        }
        else if (*p == ')') {
            while (buff.empty() == false) {
                if (buff.top() == '(') { buff.pop(); break; }
                result.push( std::string(1, buff.top()) );
                buff.pop();
            }
        }
        else { buff.push(*p); }
        bNum = ((*p >= '0') && (*p <= '9'));
    }
    while (buff.empty() == false) {
        result.push( std::string(1, buff.top()) );
        buff.pop();
    }
    return result;
}

bool CalcReversePolish(std::queue<std::string> exp, double& ans)
{
    std::stack<double> buff;
    while (exp.empty() == false) {
        if ((exp.front().compare("/") == 0) ||
            (exp.front().compare("*") == 0) ||
            (exp.front().compare("+") == 0) ||
            (exp.front().compare("-") == 0) )
        {
            if (buff.size() < 2)
                return false;
            double b = buff.top(); buff.pop();
            double a = buff.top(); buff.pop();
            if ((exp.front().compare("/") == 0) && (b == 0.0)) { return false; }

            if      (exp.front().compare("/") == 0) { buff.push(a / b); }
            else if    (exp.front().compare("*") == 0) { buff.push(a * b); }
            else if (exp.front().compare("+") == 0) { buff.push(a + b); }
            else if (exp.front().compare("-") == 0) { buff.push(a - b); }
        }
        else { buff.push( atof(exp.front().c_str()) ); }
        exp.pop();
    }
    if (buff.size() != 1)
        return false;
    ans = buff.top();
    return true;
}

void komachi()
{
    int count = 0;

    char szExp[50];
    strcpy(szExp, "1 2 3 4 5 6 7 8 9");

    bool bLast = false;
    while (bLast == false) {
        double ans = 0.0;
        if ((CalcReversePolish( ToReversePolish(szExp), ans) != false) &&
            (ans == 100.0))
        {
            std::cout << szExp << "=" << ans << std::endl;
            count++;
        }

        for (int n = 7; n >= 0; n--)
        {
            if (szExp[n * 2 + 1] == ' ') { szExp[n * 2 + 1] = '*'; break; }
            if (szExp[n * 2 + 1] == '*') { szExp[n * 2 + 1] = '/'; break; }
            if (szExp[n * 2 + 1] == '/') { szExp[n * 2 + 1] = '+'; break; }
            if (szExp[n * 2 + 1] == '+') { szExp[n * 2 + 1] = '-'; break; }
            szExp[n * 2 + 1] = ' ';
            bLast = ((n == 0) && (szExp[n * 2 + 1] == ' '));
        }
    }

    std::cout << "count = " << count << std::endl;
}

逆ポーランドへの変換が変だったので修正＋べき乗を。 個数あってても計算結果がちがったらあかんよな...orz

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <ctype.h>
#include <math.h>
#include <iostream>
#include <queue>
#include <stack>
#include <complex>

bool ToReversePolish(std::string strExp, std::queue<std::string>& ans)
{
    std::queue<std::string> result;
    bool bNum = false;
    std::stack<char> buff;
    for (std::string::iterator p = strExp.begin(); p != strExp.end(); p++) {
        if (isspace(*p) != 0)
            continue;
        if ((*p >= '0') && (*p <= '9')) {
            if (bNum) { result.back() += *p;               }
            else      { result.push( std::string(1, *p) ); }
        }
        else if (*p == '^') {
            while ((buff.empty() == false) && (buff.top() != '(') &&
                    (buff.top() != '*') && (buff.top() != '/') &&
                    (buff.top() != '+') && (buff.top() != '-')) {
                result.push( std::string(1, buff.top()) );
                buff.pop();
            }
            buff.push(*p);
        }
        else if ((*p == '*') || (*p == '/')) {
            while ((buff.empty() == false) && (buff.top() != '(') &&
                    (buff.top() != '+') && (buff.top() != '-'))    {
                result.push( std::string(1, buff.top()) );
                buff.pop();
            }
            buff.push(*p);
        }
        else if ((*p == '+') || (*p == '-')) {
            while ((buff.empty() == false) && (buff.top() != '(')) {
                result.push( std::string(1, buff.top()) );
                buff.pop();
            }
            buff.push(*p);
        }
        else if (*p == ')') {
            bool bPair = false;
            while ((buff.empty() == false) && (bPair == false)) {
                bPair = (buff.top() == '(');
                if (bPair == false)
                    result.push( std::string(1, buff.top()) );
                buff.pop();
            }
            if (bPair == false)
                return false;
        }
        else if (*p == '(') {
            buff.push(*p);
        }
        else {
            return false;
        }
        bNum = ((*p >= '0') && (*p <= '9'));
    }
    while (buff.empty() == false) {
        if (buff.top() == '(')
            return false;
        result.push( std::string(1, buff.top()) );
        buff.pop();
    }
    ans = result;
    return true;
}

bool CalcReversePolish(std::string strExp, double& ans)
{
    std::queue<std::string> exp;
    if (ToReversePolish(strExp, exp) == false)
        return false;
    std::stack<double> buff;
    while (exp.empty() == false) {
        if ((exp.front().compare("^") == 0) ||
            (exp.front().compare("/") == 0) ||
            (exp.front().compare("*") == 0) ||
            (exp.front().compare("+") == 0) ||
            (exp.front().compare("-") == 0) ) {
            if (buff.size() < 2)
                return false;
            double b = buff.top(); buff.pop();
            double a = buff.top(); buff.pop();
            if ((exp.front().compare("/") == 0) && (b == 0.0))
                return false;
            if      (exp.front().compare("^") == 0) { buff.push(std::pow(a, b)); }
            else if (exp.front().compare("/") == 0) { buff.push(a / b); }
            else if    (exp.front().compare("*") == 0) { buff.push(a * b); }
            else if (exp.front().compare("+") == 0) { buff.push(a + b); }
            else if (exp.front().compare("-") == 0) { buff.push(a - b); }
        }
        else {
            buff.push( atof(exp.front().c_str()) );
        }
        exp.pop();
    }
    if (buff.size() != 1)
        return false;
    ans = buff.top();
    return true;
}

void komachi()
{
    int nCount = 0;
    int nError = 0;

    char szExp[50];
    strcpy(szExp, "1 2 3 4 5 6 7 8 9");

    bool bLast = false;
    while (bLast == false) {
        double ans = 0.0;
        if (CalcReversePolish(szExp, ans) != false) {
            if (ans == 100.0) {
                std::cout << szExp << "=" << ans << std::endl;
                nCount++;
            }
        }
        else {
            nError++;
        }

        for (int n = 7; n >= 0; n--) {
            if (szExp[n * 2 + 1] == ' ') { szExp[n * 2 + 1] = '*'; break; }
            if (szExp[n * 2 + 1] == '*') { szExp[n * 2 + 1] = '/'; break; }
            if (szExp[n * 2 + 1] == '/') { szExp[n * 2 + 1] = '+'; break; }
            if (szExp[n * 2 + 1] == '+') { szExp[n * 2 + 1] = '-'; break; }
            szExp[n * 2 + 1] = ' ';
            bLast = ((n == 0) && (szExp[n * 2 + 1] == ' '));
        }
    }

    std::cout << "count = " << nCount << std::endl;
    std::cout << "error = " << nError << std::endl;
}

C++ですがCみたいなコードになってしまいました

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <cmath>

const int EXPRSIZ = 17;
enum { _ = -5, ADD, SUB, MUL, DIV };
const int operators[] = { _, ADD, SUB, MUL, DIV };

int priority(double op)
{
    switch (static_cast<int>(op)) {
        case _: return 3;
        case ADD: case SUB: return 1;
        default: return 2;
    }
}
void torpn(const double *expr, double *rpn)
{
    double stack[EXPRSIZ];
    int sp = 0;
    for (const double *endp = expr + EXPRSIZ; expr != endp; ++expr) {
        if (*expr > 0) *rpn++ = *expr;
        else {
            int pri = priority(*expr);
            if (!sp || pri > priority(stack[sp-1])) stack[sp++] = *expr;
            else {
                do *rpn++ = stack[--sp];
                while (sp > 0 && pri <= priority(stack[sp-1]));
                stack[sp++] = *expr;
            }
        }
    }
    while (sp > 0) *rpn++ = stack[--sp];
}
double eval(const double *rpn)
{
    double stack[EXPRSIZ];
    int sp = 0;
    for (const double *endp = rpn + EXPRSIZ; rpn < endp; ++rpn) {
        if (*rpn > 0) stack[sp++] = *rpn;
        else {
            double y = stack[--sp], x = stack[--sp];
            switch (static_cast<int>(*rpn)) {
                case _: stack[sp++] = x * 10 + y; break;
                case ADD: stack[sp++] = x + y; break;
                case SUB: stack[sp++] = x - y; break;
                case MUL: stack[sp++] = x * y; break;
                case DIV: stack[sp++] = x / y; break;
            }
        }
    }
    return stack[sp-1];
}
void print(double *expr)
{
    for (int i = 0; i < EXPRSIZ; ++i)
        if (expr[i] > 0)
            std::printf("%g", expr[i]);
        else if (expr[i] != _)
            std::printf(" %c ", "+-*/"[static_cast<int>(expr[i]) + 4]);
    std::putchar('\n');
}
int main()
{
    double expr[] = { 1., 0., 2., 0., 3., 0., 4., 0., 5.,
                        0., 6., 0., 7., 0., 8., 0., 9. };
    double rpn[EXPRSIZ], stack[EXPRSIZ];
    for (int i = 0, limit = static_cast<int>(std::pow(5., 8.)); i < limit; ++i) {
        for (int n = i, j = 0; j < 8; ++j, n /= 5)
            expr[2 * j + 1] = operators[n % 5];
        torpn(expr, rpn);
        if (eval(rpn) == 100.0) print(expr);
    }
}

別にintでいいところまでdoubleにしてました。やりなおし。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <cmath>

const int EXPRSIZ = 17;
enum { _ = -5, ADD, SUB, MUL, DIV };
const int operators[] = { _, ADD, SUB, MUL, DIV };

int priority(int op)
{
    switch (op) {
        case _: return 3;
        case ADD: case SUB: return 1;
        default: return 2;
    }
}
void torpn(const int *expr, int *rpn)
{
    int stack[EXPRSIZ];
    int sp = 0;
    for (int i = 0; i < EXPRSIZ; ++i) {
        if (expr[i] > 0) *rpn++ = expr[i];
        else {
            int pri = priority(expr[i]);
            if (!sp || pri > priority(stack[sp-1]))
                stack[sp++] = expr[i];
            else {
                do *rpn++ = stack[--sp];
                while (sp > 0 && pri <= priority(stack[sp-1]));
                stack[sp++] = expr[i];
            }
        }
    }
    while (sp > 0) *rpn++ = stack[--sp];
}
double eval(const int *rpn)
{
    double stack[EXPRSIZ];
    int sp = 0;
    for (int i = 0; i < EXPRSIZ; ++i) {
        if (rpn[i] > 0) stack[sp++] = static_cast<double>(rpn[i]);
        else {
            double y = stack[--sp], x = stack[--sp];
            switch (rpn[i]) {
                case _: stack[sp++] = x * 10 + y; break;
                case ADD: stack[sp++] = x + y; break;
                case SUB: stack[sp++] = x - y; break;
                case MUL: stack[sp++] = x * y; break;
                case DIV: stack[sp++] = x / y; break;
            }
        }
    }
    return stack[sp-1];
}
void print(const int *expr)
{
    for (int i = 0; i < EXPRSIZ; ++i)
        if (expr[i] > 0)
            std::printf("%d", expr[i]);
        else if (expr[i] != _)
            std::printf(" %c ", "+-*/"[expr[i] + 4]);
    std::putchar('\n');
}
int main()
{
    int expr[] = { 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9 };
    int rpn[EXPRSIZ], limit = static_cast<int>(std::pow(5.,8.));
    for (int i = 0; i < limit; ++i) {
        for (int n = i, j = 0; j < 8; ++j, n /= 5)
            expr[2 * j + 1] = operators[n % 5];
        torpn(expr, rpn);
        if (eval(rpn) == 100.) print(expr);
    }
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]