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

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <stdio.h>
#include <math.h>

#define PART_MULT '*'
#define PART_DIV '/'
#define PART_PLUS '+'
#define PART_MINUS '-'
#define PART_DIGIT ' '
#define PART_EQ '='
#define NPART 9

typedef struct {
    int num;
    char csim;
} exppart_t;

void display_exp(exppart_t *epart)
{
    int i;
    for (i = 0; i < NPART; i++) {
        printf("%d %c ", epart[i].num, epart[i].csim);
        if (epart[i].csim == '=') {
            printf("\n");
            return;
        }
    }
    printf("\n");
}

void shift_exp(exppart_t *epart, int offset, int n)
{
    int i;
    for (i = offset; i < NPART; i++) {
        if (i + n < NPART) {
            epart[i] = epart[i + n];
        } else {
            epart[i].csim = '=';
            epart[i].num = 0;
        }
    }
}

int adigit_exp(exppart_t *epart) {return (epart->num * 10 + (epart+1)->num);}
int aplus_exp(exppart_t *epart) {return (epart->num + (epart+1)->num);}
int aminus_exp(exppart_t *epart) {return (epart->num - (epart+1)->num);}
int amult_exp(exppart_t *epart) {return (epart->num * (epart+1)->num);}
int adiv_exp(exppart_t *epart) {return (epart->num / (epart+1)->num);}

void acalc_exp(exppart_t *epart, char cparts, int (*acalc)(exppart_t*))
{
    int i;
    for (i = 0; i < NPART-1; i++) {
        if (epart[i].csim == cparts) {
            epart[i].num = acalc(epart+i);
            epart[i].csim = epart[i+1].csim;
            shift_exp(epart, i + 1, 1);
            break;
        }
    }
}

void proc_calc_exp(exppart_t *epart, char cparts, int (*acalc)(exppart_t*))
{
    int i;
    for (i = 0; i < NPART-1; i++) {
        acalc_exp(epart, cparts, acalc);
    }
}

int isdivable(exppart_t *epart) {
    int i, vmem = epart[0].num;
    for (i = 0; i < NPART-1; i++) {
        if (epart[i].csim == PART_DIV) {
            if (vmem % epart[i+1].num != 0) {
                return 0;
            }
        } else {
            vmem = epart[i+1].num;
        }
    }
    return 1;
}

void komachi() {
    exppart_t epart[NPART], epart_def[NPART];
    char simpart[] = {PART_MULT, PART_DIV, PART_PLUS, PART_MINUS, PART_DIGIT};
    int i, cnt;
    long li, limax;

    cnt = 0;
    limax = (long)pow(5.0, NPART-1.0);
    for (li = 0; li < limax; li++) {
        for (i = 0; i < NPART; i++) {
            epart[i].csim = simpart[(li / (long)pow(5.0, i)) % 5];
        }
        epart[NPART-1].csim = PART_EQ;
        for (i = 0; i < NPART; i++) {
            epart[i].num =i + 1;
            epart_def[i] = epart[i];
        }

        proc_calc_exp(epart, PART_DIGIT, adigit_exp);
        proc_calc_exp(epart, PART_MULT, amult_exp);
        if (!isdivable(epart)) {
            continue;
        }
        proc_calc_exp(epart, PART_DIV, adiv_exp);
        proc_calc_exp(epart, PART_PLUS, aplus_exp);
        proc_calc_exp(epart, PART_MINUS, aminus_exp);

        if (epart[0].num == 100) {
            cnt++;
            display_exp(epart_def);
        }
    }
    printf("count : %d\n", cnt);
}

int main()
{
    komachi();
    return 0;
}

Index

Feed

Other

Link

Pathtraq

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