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 - Nested

Flatten Hidden

枝狩り一切無し。効率悪いと思ふ。

1
2
3
4
5
6
7
require "mathn"
(5**8).times do |i|
  s=("2".."9").inject("1") do |r,e|
    r+=["","+","-","*","/"][i%5]+e;i/=5;r
  end
  puts s if eval(s)==100
end

とりあえず投稿。括弧は使わない版。結果は101通り出てきます。

(123 - 45 - 67 + 89)
(1 * 2 - 3 + 4 - 5 + 6 + 7 + 89)
(1 + 2 * 3 - 4 - 5 + 6 + 7 + 89)
(1 - 23 + 4 * 5 + 6 + 7 + 89)
(12 - 3 - 4 + 5 - 6 + 7 + 89)
(1 + 2 + 3 * 4 - 5 - 6 + 7 + 89)
(1 - 23 - 4 + 5 * 6 + 7 + 89)
(1 * 2 / 3 + 4 * 5 / 6 + 7 + 89)
(1 / 2 * 34 - 5 + 6 - 7 + 89)
(12 + 3 + 4 + 5 - 6 - 7 + 89)
(1 * 23 - 4 + 5 - 6 - 7 + 89)
(12 / 3 + 4 * 5 - 6 - 7 + 89)
(1 - 23 - 4 - 5 + 6 * 7 + 89)
(1 * 2 - 3 + 4 + 56 / 7 + 89)
(1 + 2 * 3 - 4 + 56 / 7 + 89)
(12 + 3 + 4 - 56 / 7 + 89)
(1 * 23 - 4 - 56 / 7 + 89)
(123 + 4 - 5 + 67 - 89)
(1 + 234 * 5 / 6 - 7 - 89)
(12 + 3 * 45 + 6 * 7 - 89)
(1 + 2 * 34 - 56 + 78 + 9)
(1 + 2 + 3 - 4 + 5 + 6 + 78 + 9)
(1 * 2 * 3 - 4 + 5 + 6 + 78 + 9)
(1 * 2 + 3 * 4 + 5 - 6 + 78 + 9)
(12 + 3 * 4 - 5 - 6 + 78 + 9)
(1 * 2 * 3 * 4 - 5 - 6 + 78 + 9)
(1 * 2 - 3 + 4 * 5 - 6 + 78 + 9)
(1 + 2 + 3 * 4 * 5 / 6 + 78 + 9)
(1 + 234 * 5 * 6 / 78 + 9)
(1 + 2 * 3 + 4 + 5 + 67 + 8 + 9)
(12 + 3 - 4 + 5 + 67 + 8 + 9)
(1 - 2 + 3 * 4 + 5 + 67 + 8 + 9)
(1 - 2 - 3 + 4 * 5 + 67 + 8 + 9)
(12 * 3 - 4 * 5 + 67 + 8 + 9)
(1 / 2 / 3 * 456 + 7 + 8 + 9)
(1 + 23 - 4 + 56 + 7 + 8 + 9)
(12 + 34 + 5 * 6 + 7 + 8 + 9)
(1 - 2 - 3 + 45 + 6 * 7 + 8 + 9)
(1 * 2 + 34 + 5 + 6 * 7 + 8 + 9)
(12 + 34 - 5 + 6 * 7 + 8 + 9)
(1 * 23 + 4 + 5 + 67 - 8 + 9)
(1 + 2 + 34 - 5 + 67 - 8 + 9)
(1 * 2 + 34 + 56 + 7 - 8 + 9)
(1 + 23 * 4 + 5 - 6 + 7 - 8 + 9)
(1 + 2 + 3 * 4 * 56 / 7 - 8 + 9)
(12 + 3 * 4 + 5 + 6 + 7 * 8 + 9)
(1 * 2 * 3 * 4 + 5 + 6 + 7 * 8 + 9)
(12 - 3 + 4 * 5 + 6 + 7 * 8 + 9)
(1 - 2 - 3 + 45 - 6 + 7 * 8 + 9)
(1 * 2 + 34 + 5 - 6 + 7 * 8 + 9)
(12 + 34 - 5 - 6 + 7 * 8 + 9)
(12 - 3 - 4 + 5 * 6 + 7 * 8 + 9)
(1 * 23 + 4 + 56 / 7 * 8 + 9)
(1 * 23 * 4 - 56 / 7 / 8 + 9)
(1 + 23 - 4 + 5 + 6 + 78 - 9)
(1 * 2 + 3 + 4 * 5 + 6 + 78 - 9)
(12 * 3 - 4 + 5 - 6 + 78 - 9)
(1 * 2 + 3 - 4 + 5 * 6 + 78 - 9)
(12 / 3 / 4 + 5 * 6 + 78 - 9)
(123 + 45 - 67 + 8 - 9)
(1 + 23 * 4 - 5 + 6 + 7 + 8 - 9)
(123 - 4 - 5 - 6 - 7 + 8 - 9)
(1 - 2 + 3 * 4 * 5 + 6 * 7 + 8 - 9)
(123 + 4 * 5 - 6 * 7 + 8 - 9)
(1 + 23 * 4 + 56 / 7 + 8 - 9)
(1 * 2 + 3 + 45 + 67 - 8 - 9)
(1 * 2 * 34 + 56 - 7 - 8 - 9)
(12 / 3 + 4 * 5 * 6 - 7 - 8 - 9)
(1 - 2 + 3 + 45 + 6 + 7 * 8 - 9)
(1 - 2 + 3 * 4 * 5 - 6 + 7 * 8 - 9)
(12 / 3 + 4 * 5 * 6 * 7 / 8 - 9)
(1 + 2 + 3 - 45 + 67 + 8 * 9)
(1 * 2 * 3 - 45 + 67 + 8 * 9)
(1 - 2 - 34 + 56 + 7 + 8 * 9)
(1 / 2 * 3 / 4 * 56 + 7 + 8 * 9)
(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9)
(1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9)
(1 + 23 - 4 - 5 + 6 + 7 + 8 * 9)
(1 - 2 * 3 + 4 * 5 + 6 + 7 + 8 * 9)
(12 * 3 - 4 - 5 - 6 + 7 + 8 * 9)
(1 + 2 * 3 + 4 * 5 - 6 + 7 + 8 * 9)
(1 - 2 * 3 - 4 + 5 * 6 + 7 + 8 * 9)
(1 + 2 - 3 * 4 + 5 * 6 + 7 + 8 * 9)
(1 + 2 * 3 * 4 * 5 / 6 + 7 + 8 * 9)
(12 + 3 * 4 + 5 + 6 - 7 + 8 * 9)
(1 * 2 * 3 * 4 + 5 + 6 - 7 + 8 * 9)
(12 - 3 + 4 * 5 + 6 - 7 + 8 * 9)
(1 - 2 - 3 + 45 - 6 - 7 + 8 * 9)
(1 * 2 + 34 + 5 - 6 - 7 + 8 * 9)
(12 + 34 - 5 - 6 - 7 + 8 * 9)
(12 - 3 - 4 + 5 * 6 - 7 + 8 * 9)
(1 - 2 * 3 - 4 - 5 + 6 * 7 + 8 * 9)
(1 + 2 - 3 * 4 - 5 + 6 * 7 + 8 * 9)
(1 + 2 + 3 - 4 * 5 + 6 * 7 + 8 * 9)
(1 * 2 * 3 - 4 * 5 + 6 * 7 + 8 * 9)
(1 + 23 - 4 + 56 / 7 + 8 * 9)
(1 * 2 + 34 - 56 / 7 + 8 * 9)
(1 - 2 - 3 + 4 * 56 / 7 + 8 * 9)
(1 * 234 + 5 - 67 - 8 * 9)
(1 + 234 - 56 - 7 - 8 * 9)
(1 + 2 + 34 * 5 + 6 - 7 - 8 * 9)

  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
(use srfi-1)

(define (atom? x)
  (not (or (null? x) (pair? x))))
(define (atom-list? ls)
  (and (pair? ls) (atom? (car ls))))

(define (my-flatten ls)
  (cond ((null? ls) '())
        ((pair? ls)
         (cond ((atom? (car ls)) (list ls))
               ((atom-list? (car ls))
                (append (list (car ls)) (my-flatten (cdr ls))))
               (else
                (append (my-flatten (car ls)) (my-flatten (cdr ls))))))
        (else (list ls))))

(define (_ a b)
  (cond ((< b 10) (+ (* a 10) b))
        ((< b 100) (+ (* a 100) b))
        ((< b 1000) (+ (* a 1000) b))
        ((< b 10000) (+ (* a 10000) b))
        ((< b 100000) (+ (* a 100000) b))
        ((< b 1000000) (+ (* a 1000000) b))
        ((< b 10000000) (+ (* a 10000000) b))
        ((< b 100000000) (+ (* a 100000000) b))
        ((< b 1000000000) (+ (* a 1000000000) b))
;        (else #f)
        ))

(define ops '(_ + - * /))

(define (apply-op op x y)
  (case op
    ((_) (_ x y))
    ((+) (+ x y))
    ((-) (- x y))
    ((*) (* x y))
    ((/) (/ x y))
    ))

(define (apply-rev-op op x y)
  (case op
;    ((_) (_ x y))
    ((+) (- x y))
    ((-) (+ x y))
    ((*) (/ x y))
    ((/) (* x y))))

(define (komachi n sum)
  (define (append-op-n ls op n) (append ls (list op n)))

  (define (1..k= k p)
; [1..k] = p となる組み合わせ
    (if (= 1 k) ;
      ; 1 = 1   ; p!=1ならアウト
        (if (= p 1) '((1)) '())
    ; [1..k-1] ?? k = p
        (my-flatten (map (lambda (op) (1..k (- k 1) op k p)) ops))
        ))

  (define (eval-exp exp)
    (define (iter rest product)
      (cond ((null? rest) product)
            ((eq? '* (car rest))
             (iter (cddr rest) (* product (cadr rest))))
            ((eq? '/ (car rest))
             (iter (cddr rest) (/ product (cadr rest))))
            ))
    (iter (cdr exp) (car exp)))

  (define (1..k?<..>= k op exp p)
; [1..k] op (exp) = p
    (if (= 1 k)
        (case op
          ((_)
           (let1 exp* (cons (_ 1 (car exp)) (cdr exp))
                 (if (= (eval-exp exp*) p)
                     exp*
                     '())))
          ((+ -) ; 1 +- exp = p
           (if (= (apply-op op 1 (eval-exp exp)) p)
               (append (list 1 op) exp)
               '()))
          ((* /)
           (let1 exp* (append (list 1 op) exp)
                 (if (= (eval-exp exp*) p)
                     exp*
                     '())))
          )
        (case op
          ((_)
           (my-flatten
            (map (lambda (op2) (1..k?<..>= (- k 1) op2 (cons (_ k (car exp)) (cdr exp)) p)) ops)))
          ((+ -)
           (map (lambda (x) (append x (list op) exp))
                (my-flatten (1..k= k (apply-rev-op op p (eval-exp exp))))
                ))
          ((* /)
           (my-flatten
            (map (lambda (op2) (1..k?<..>= (- k 1) op2 (append (list k op) exp) p)) ops)))
          )
        ))

  (define (1..k k op n p)
; [1..k] op n = p となる組み合わせが全部ほしい
    (if (= 1 k)
      ;k=1 : [1] op n = p
        (case op
          ((_)
           (if (= (_ 1 n) p) (list (_ 1 n)) '()))
          ((+ -)
           (if (= (apply-op op 1 n) p) (list 1 op n) '()))
          ((*)
           (if (= n p) (list 1 '* n) '()))
          ((/) '()) ; 1/n (n>1) cannot be p
          )
      ;k>1
        (case op
          ((_); [1..k-1] ?? k_n = p
           (my-flatten (map (lambda (op2) (1..k (- k 1) op2 (_ k n) p)) ops)))
          ((+ -) ; [1..k] ± n = p ;
           (map (lambda (x) (append-op-n x op n))
                (my-flatten (1..k= k (apply-rev-op op p n)))))
          ((* /) ; [1..k] */ n = p :: [1..c] ? ([c+1..k] */ n) = p
           (my-flatten (map (lambda (op2) (1..k?<..>= (- k 1) op2 (list k op n) p)) ops)))
           ; 結合則が加減算とは違う
          )
        ))

  (remove null? (1..k= n sum)))

(map print (komachi 9 100))

秒殺です
% time gosh komachi.scm
(123 - 45 - 67 + 89)
(1 * 2 - 3 + 4 - 5 + 6 + 7 + 89)
中略
(1 + 234 - 56 - 7 - 8 * 9)
(1 + 2 + 34 * 5 + 6 - 7 - 8 * 9)

real	0m0.775s
user	0m0.758s
sys	0m0.015s


pythonでナイーブな実装。
括弧なしで101個でした。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def komachi():
    num = range(1,10)
    ope = ["",".0+",".0-",".0*",".0/"]
    c = 1
    for x in xrange(5**8):
        formula = str(num[0])
        for n in range(1,9):
            formula += ope[x%5] + str(num[n])
            x /= 5
        if eval(formula) == 100:
           print formula,c
           c += 1
           

komachi()
「C# には eval が無いなぁ。動的コンパイルでもしようかな。あ待てよアレがあったな」 ということで C#2.0 + IronPython1.1 です。ところてんさんの #4728 を参考に、Python のコードを片っ端から生成して IronPython で Execute しています。komachi 関数は C# 側で作成。括弧なしで 101 個を、６分程度(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
using System;
using System.Collections.Generic;
using IronPython;
using IronPython.Hosting;
using IronPython.Runtime;
using IronPython.Runtime.Calls;
class Program {
    static void Main() {
        PythonEngine python = new PythonEngine();
        EngineModule module = python.CreateModule();
        Dictionary<string, object> locals = new Dictionary<string, object>();
        int count = 0;
        locals["komachi"] = new CallTarget2(delegate(object obj, object obj2) {
            if (obj2.Equals(100.0)) {
                count++;
                Console.WriteLine(obj + " = " + obj2);
            }
            return null;
        });
        DateTime before = DateTime.Now;
        foreach (string code in GenPythonCode()) {
            python.Execute(code, module, locals);
        }
        Console.WriteLine("time: {0}", DateTime.Now - before);
        Console.WriteLine("total: {0}", count);
    }
    static IEnumerable<string> GenPythonCode()
    {
        string[] ops = { "", ".0+", ".0-", ".0*", ".0/" };
        for (int i = 0; i < Math.Pow(ops.Length, 8); i++) {
            string code = "1";
            int j = i;
            foreach (char num in "23456789") {
                code += ops[j % ops.Length] + num;
                j /= ops.Length;
            }
            yield return string.Format("komachi(\"{0}\", {0})", code + ".0");
        }
    }
}

パーサコンビネータでパーサを作ってナイーブに。 解答は101個です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import scala.util.parsing.combinator.{Parsers, ImplicitConversions, ~, mkTilde}
import scala.util.parsing.combinator.syntactical.StdTokenParsers
import scala.util.parsing.combinator.lexical.StdLexical

object Komachi extends StdTokenParsers with Application{
  type Tokens = StdLexical ; val lexical = new StdLexical
  lexical.delimiters ++= List("+","-", "*", "/")
  def expr = term*("+" ^^ {(x: double, y: double) => x + y}
                 | "-" ^^ {(x: double, y: double) => x - y})
  def term = factor*("*" ^^ {(x: double, y: double) => x * y}
                   | "/" ^^ {(x: double, y: double) => x / y})
  def factor: Parser[double] = numericLit ^^ (_.toDouble)

  ((List(List[String]())) /: List.make(8, List("+", "-", "*", "/", ""))){
    for(i <-_; j <-_) yield j::i
  }.foreach{fs =>
    val s = (new StringBuilder("1") /: (2 to 9)){(s,i) =>
      s.append(fs(i-2)).append(i)
    }.toString
    if(expr(new lexical.Scanner(s)).get == 100.0) println(s)
  }
}
#4725 を参考にしました。printはRhinoのprintで。
重いので、ブラウザでは動かさないように。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function komachi() {
  var list = Array.prototype.slice.apply(arguments, [0]);
  var right = list.pop();
  var operator = ["", "+", "-", "*", "/"];
  var n = Math.pow(operator.length,list.length-1);

  for(var i=0; i<n; i++) {
    var exp = [list[0]];
    var o = (n+i).toString(5);
    for(var j=1, ii=i; j<list.length; j++) {
      exp.push(operator[o.slice(j,j+1)]);
      exp.push(list[j]);
      ii = Math.floor(i/5);
    }
    if(eval(exp.join("")) == right) print(exp.join("") + '=' + right);
  }
}
print("begin");
komachi(1,2,3,4,5,6,7,8,9,100);
print("end");

解答101個で4分弱でした。

ナイーブに全探索。

opparseで演算子順位文法を使って式をRPNに変換し、calcで計算してます。

opsの定義を変えれば演算子を増やしたり優先順位を買えたりできます。同じ優先度の演算子は左結合。 
 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
import Numeric

data Item a b = Value a | Op (a->a->a) b [Char]

cat a b = a*10+b

ops :: [Item Double Integer]
ops = [Op cat 2 "", Op (+) 0 "+", Op (-) 0 "-", Op (*) 1 "*", Op (/) 1 "/"]
 
opparse [] _ vs = reverse vs
opparse (op:ops) (i:is) vs = opparse ops is $ push op (Value i) vs

push op@(Op o p _) v (op'@(Op o' p' _):vs)
  | (p <= p') = (op:v:op':vs)
  | otherwise = (op':push op v vs)
push op v vs = op:v:vs

calc [a] [] = a
calc ns ((Value a):vs) = calc (a:ns) vs
calc (a:b:ns) ((Op op _ _):vs) = calc ((op b a):ns) vs
calc _ _ = error "invalid stack state"

showFormula ops = "1" ++ rec [2..] ops where
   rec _ [] = ""
   rec (i:is) ((Op _ _ n):ops) = n ++ (showInt . round) i (rec is ops)

genops 0 = [[]]
genops n = [o:os | o <- map (ops!!) [0..4], os <- genops (n-1)]

komachi n = [ops | ops <- genops n, test 100 ops] where
   test sum ops = abs (sum - (calc [] $ opparse ops [2..] [Value 1])) <= 1.0e-10

main = putStr $ unlines $ map showFormula $ komachi 8

高階関数と有理数を使って書き直してみました。
一部私好みに書き換えています。

 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
import Ratio

data Item a b c = Value a | Op (b->b->b) c String

cat a b = a*10+b

ops :: [Item Integer Rational Integer]
ops = [Op cat 2 "", Op (+) 0 "+", Op (-) 0 "-", Op (*) 1 "*", Op (/) 1 "/"]

opparse ops = reverse $ foldl push [Value 1] (zip ops $ map Value [2..])

push (op'@(Op o' p' _):vs) opv@(op@(Op o p _), v)
  | p <= p' = op:v:op':vs
  | otherwise = op':push vs opv
push vs (op, v) = op:v:vs

calc vs = head $ foldl g [] vs where
  g ns (Value a) = a%1:ns
  g (a:b:ns) (Op op _ _) = op b a:ns
  g _ _ = error "invalid stack state"

showFormula ops = concat $ ["1"] ++ zipWith (\(Op _ _ n) i -> n ++ show i) ops [2..]

genops n = sequence $ replicate n ops

komachi n = filter (test 100) $ genops n where
   test sum ops = sum == (calc $ opparse ops)

とりあえず適当に全探索。候補を5進8桁の整数と同一視して dotimes で回してます。結果は101 件、CLISP で 16 秒でした。

 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
(defun apply-op (op x y)
  (case op
    (#\+ (+ x y))
    (#\- (- x y))
    (#\* (* x y))
    (#\/ (/ x y))
    (#\SPACE (+ (* 10 x) y))
    (t 't)))

(defun precedence (op) (case op ((#\+ #\-) 1) ((#\* #\/) 2) (t 3)))
(defun precedence< (op1 op2) (< (precedence op1) (precedence op2)))

(defun eval-string (s)
  (loop with vstack and opstack
    for c across s
    if (digit-char-p c) do
    (push (parse-integer (string c)) vstack)
    else if #1=(or (null opstack) (precedence< (car opstack) c)) do
    (push c opstack)
    else do
    (loop until #1# do
      #2=(setf vstack
               (cons (apply-op (pop opstack) (cadr vstack) (car vstack))
                     (cddr vstack))))
    (push c opstack)
    finally
    (loop for op in opstack do  #2#)
    (return (car vstack))))

(defun komachi ()
  (let ((s (copy-seq "1 2 3 4 5 6 7 8 9")))
    (dotimes (x (expt 5 8))
      (dotimes (i 8)
        (setf (elt s (+ i i 1)) (elt " +-*/" (rem (floor x (expt 5 i)) 5))))
      (if (= (eval-string s) 100) (write-line s)))))

順当な遅さです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# -*- coding: utf-8 -*-

from __future__ import division
import re

E = '1%s2%s3%s4%s5%s6%s7%s8%s9==100'
A = ['', '+', '-', '*', '/']
F = lambda n: [[i] + l for i in A for l in F(n-1)] if n > 1 else [[i] for i in A]
R = lambda s: s.replace('+', u'＋').replace('-', u'－').replace('*', u'×').replace('/', u'÷').replace('==', u'＝')

print '\n'.join([R(E % tuple(l)) for l in F(8) if eval(E % tuple(l))])

Javaでは、evalがないので自前でParseを行って計算してみました。

括弧対応なしで、約1秒で 101通りの結果がでました。

  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
import java.util.ArrayList;
import java.util.List;

public class Sample104 {

    public static void komachi(int[] lhs, int rhs) {
        if (lhs.length == 0) return;

        List<Term> expression = new ArrayList<Term>();
        expression.add(new TermValue(lhs[0]));
        for (int index = 1; index < lhs.length; index++) {
            List<Term> work = new ArrayList<Term>(expression);
            expression.clear();
            for (Term term: work) {
                List<Term> list = createTerm(term, lhs[index]);
                expression.addAll(list);
            };
        }

        int counter = 1;
        for (Term term: expression) {
            if (term.getValue() == rhs) {
                System.out.println(counter++ + ": " + term.toString() + " = " + rhs);
            }
        }
    }
    private static List<Term> createTerm(Term lhs, int r) {
        List<Term> result = new ArrayList<Term>();
        Operator[] operators = Operator.values();
        for (int index = 0; index < operators.length; index++) {
            result.add(new TermData(operators[index], lhs, new TermValue(r)));
        }
        return result;
    }


    public enum Operator {
        None {
            public int getPriority() { return 10; }
            public double operate(double lhs, double rhs) { return lhs * 10 + rhs; }
            public String toString() { return ""; }
        },
        Plus {
            public int getPriority() { return 1; }
            public double operate(double lhs, double rhs) { return lhs + rhs; }
            public String toString() { return "+"; }
        },
        Minus {
            public int getPriority() { return 1; }
            public double operate(double lhs, double rhs) { return lhs - rhs; }
            public String toString() { return "-"; }
        },
        Times {
            public int getPriority() { return 2; }
            public double operate(double lhs, double rhs) { return lhs * rhs; }
            public String toString() { return "*"; }
        },
        Divide {
            public int getPriority() { return 2; }
            public double operate(double lhs, double rhs) { return lhs / rhs; }
            public String toString() { return "/"; }
        };

        public abstract int getPriority();
        public abstract double operate(double lhs, double rhs);
    }
    private static interface Term {
        public boolean isOperate();
        public double getValue();
    }
    private static class TermValue implements Term {
        public final int value;

        public TermValue(int val) {
            value = val;
        }
        public boolean isOperate() { return false; }
        public double getValue() {
            return value;
        }
        public String toString() { return String.valueOf(value); }
    }
    private static class TermData implements Term {
        public final Operator op;
        public final Term lhs;
        public final Term rhs;

        /**
         * 右辺は追加分と考えて、演算子の順序に従ってデータを正規化します。
         */
        public TermData(Operator o, Term l, Term r) {
            Operator operator = o;
            Term lterm = l;
            Term rterm = r;

            if (l.isOperate()) {
                TermData data = (TermData) l;
                if (operator.getPriority() > data.op.getPriority()) {
                    rterm = new TermData(operator, data.rhs, rterm);
                    lterm = data.lhs;
                    operator = data.op;
                }
            }
            op = operator;
            lhs = lterm;
            rhs = rterm;
        }
        public boolean isOperate() { return true; }
        public double getValue() {
            return op.operate(lhs.getValue(), rhs.getValue());
        }
        public String toString() {
            return lhs.toString() + op.toString() + rhs.toString();
        }
    }


    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        komachi(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, 100);
        System.out.println();
        long end = System.currentTimeMillis();
        System.out.println("elipse: " + (end - start) + "(ms)");
    }
}

アルゴリズム的には一番月並み。MacBook Pro 2.33GHz で12秒。

＃あ、関数名が微妙に

Dan the Perl Monger

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#!/usr/local/bin/perl
use strict;
use warnings;
use B::Deparse;

sub komanechi {
    for my $i ( 1 .. 5**8 ) {
        my $formula = 1;
        for my $n ( 2 .. 9 ) {
            $formula .= ( '', qw{+ - * /} )[ $i % 5 ] . $n;
            $i /= 5;
        }
        next if  100 != eval $formula;
        print "$formula\n";
    }
}

komanechi;

逆ポーランドへの変換が変だったので修正＋べき乗を。 個数あってても計算結果がちがったらあかんよな...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;
}

101件確認しました．

1
2
3
4
5
komati([X], N, X) :- term_to_atom(T, X), N =:= T.
komati([X1,X2|Xs], N, S) :- member(Op, [+,-,*,/,'']),
    concat_atom([X1,Op,X2], X3), komati([X3|Xs], N, S).

:- forall(komati([1,2,3,4,5,6,7,8,9], 100, S), writeln(S)).
evalとreplaceの合わせ技。cscriptで26秒，Rhinoで17秒。 
1
2
3
4
5
6
7
8
9
function doukaku104(exp, ops){
  var d = new Date, x = /□/g, f = function(t){ t = ops[i % o], i = i / o | 0; return t };
  for(var R = [], r = 0, o = ops.length, n = Math.pow(o, exp.match(x).length), i, e; i = n--;)
    if(eval(e = exp.replace(x, f))) R[r++] = e;
  return R[r] = R.length +' results / '+ (new Date - d) +'[ms]', R.join('\n');
}

(typeof print != 'undefined' ? print : function($){ WSH.echo($) })
(doukaku104('1□2□3□4□5□6□7□8□9==100', ['', '+', '-', '*', '/']));
Squeak Smalltalk で。

eval（Compiler class>>#evaluate:）を使いたかったのですが、Smalltalk には四則演算で乗除の優先がないので断念(^_^;)。Squeak OMeta でパーサー＆インタープリタを書いて、それに eval 相当の仕事を肩代わりさせています。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
!OMeta methodsFor: 'calc'!
num ::= <digit>+:xs => [Integer readFrom: xs readStream]! !

!OMeta methodsFor: 'calc'!
mul ::= <mul>:x ( $* <num>:y => [x * y] | $/ <num>:y => [x / y] ) | <num>! !

!OMeta methodsFor: 'calc'!
add ::= <add>:x ( $+ <mul>:y => [x + y] | $- <mul>:y => [x - y] ) | <mul>! !

!OMeta methodsFor: 'calc'!
exp ::= <add>! !

World findATranscript: nil.
#('' '+' '-' '*' '/') asDigitsToPower: 8 do: [:comb |
    | expStr result |
    expStr := '1{1}2{2}3{3}4{4}5{5}6{6}7{7}8{8}9' format: comb.
    result := (OMeta onTree: nil) apply: #exp withArguments: expStr.
    result = 100 ifTrue: [Transcript cr; show: expStr]]
式をすべて生成して演算する方法。
が、メモリエラーが発生（memory_limit = 32Mの設定）したため、
とりあえず8を追加するときに、9を加減する場合のみ前計算して不要なものを排除。
101件取得（33.56秒） 
 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
$operators = array( '+', '-', '*', '/', '' );

for ( $i = 1; $i <= 9; $i ++ ) {
    $h = 1;
    if ( $i == 1 ) {
        foreach ( $operators as $row ) {
            $temp[$h] = $i . $row;
            $h++;
        }
    } elseif ( $i == 9 ) {
        foreach ( $temp as $row ) {
            $expression = $row . $i;
            eval("\$ans = $expression;");
            if ( $ans == 100 ) {
                $expressions[] = $expression;
            }
            $h++;
        }
    } else {
        if ( $i == 8 ) {
            foreach ( $temp as $row ) {
                foreach ( $operators as $key => $val ) {
                    $expression_temp = $row . $i;
                    eval("\$ans = $expression_temp;");
                    if ( $key === 0 ) {
                        if ( $ans == 91 ) {
                            $temp[$h] = $row . $i . $val;
                            $h++;
                        }
                    } elseif ( $key == 1 ) {
                        if ( $ans == 109 ) {
                            $temp[$h] = $row . $i . $val;
                            $h++;
                        }
                    } else {
                        $temp[$h] = $row . $i . $val;
                        $h++;
                    }
                }
            }
        } else {
            foreach ( $temp as $row ) {
                foreach ( $operators as $row2 ) {
                    $temp[$h] = $row . $i . $row2;
                    $h++;
                }
            }
        }
    }
}
print_r($expressions);

ocamlyaccとかストリームパーサーとか色々な道具を試した結果、LL(1) 再帰下降パーサーを手書きしました。

計算途中の値はint*int型の分数で持っています。

結果は101件で実行時間は0.23秒でした。

 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
type token = Int of int | Mul | Div | Add | Sub

let add (a1, b1) (a2, b2) = (a1 * b2 + a2 * b1), (b1 * b2)
let sub (a1, b1) (a2, b2) = (a1 * b2 - a2 * b1), (b1 * b2)
let mul (a1, b1) n        = (a1 * n), b1
let div (a1, b1) n        = a1, (b1 * n)

let factor list =
  let rec factor' n = function
    | Int x :: tl -> factor' (n * 10 + x) tl
    | x           -> n, x in
  factor' 0 list

let term input =
  let rec term' (f,input)  = match input with
    | Mul :: tl -> let f2, tl2 = factor tl in term' ((mul f f2), tl2)
    | Div :: tl -> let f2, tl2 = factor tl in term' ((div f f2), tl2)
    | x         -> f, x in
  let n, input = factor input in term' ((n,1), input)

let expr input =
  let rec expr' (f,input) = match input with
    | Add :: tl -> let f2, tl2 = term tl in expr' ((add f f2), tl2)
    | Sub :: tl -> let f2, tl2 = term tl in expr' ((sub f f2), tl2)
    | _         -> f in
  expr' (term input)

let op = [| Add; Sub; Mul; Div |]

let rec makeexpr list o n =
  if n = 0 then list else match (o mod 5) with
    | 4 -> makeexpr (Int n           :: list) (o / 5) (n - 1)
    | x -> makeexpr (Int n :: op.(x) :: list) (o / 5) (n - 1)

let rec makestr s = function
  | []       -> s
  | hd :: tl -> makestr (s ^ (match hd with
    | Int x -> string_of_int x | Mul->"*" | Div->"/" | Add->"+" | Sub->"-")) tl

let rec main n = if n >= 0 then
    let ex = makeexpr [ Int 9 ] n 8 in
    let a, b = expr ex in
    let _ = if b * 100 = a then Printf.printf "%s\n" (makestr "" ex) in
    main (n - 1)

let _ = main 390624
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;
}

日記の方に一度書いたソースですが、そのまま載せます。

 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
from __future__ import division
import itertools

def permutation(*args):
    D = dict([(id(L), L) for L in args])
    def permutation_(*args):
        if not args:
            yield []
        elif len(args) == 1:
            D[id(args[0])], g = itertools.tee(D[id(args[0])])
            for x in g:
                yield [x]
        else:
            D[id(args[0])], g = itertools.tee(D[id(args[0])])
            for x in g:
                for y in permutation_(*args[1:]):
                    yield [x] + y
    return permutation_(*args)

c = itertools.count(1)
ops = ['+', '-', '*', '/', '']
L = ['1', ops, '2', ops, '3', ops, '4', ops, '5', ops, '6', ops, '7', ops, '8', ops, '9']
for exp in permutation(*L):
    exp = ''.join(exp)
    if eval(exp) == 100:
        print exp, c.next()

演算子配列の重複順列と数字とを`zip'を利用して交互に配置して`eval'で評価しました. 実行時間はP4 2.4GHzで3分間程度.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
module Enumerable
  def rperm(n=size, out=[], &block) #重複順列生成
    n <= 0 ? (yield out) : each{|x| rperm(n-1, [x,*out], &block)}
  end
end
def komachi(n=9)
  soln = []
  seq = (1..n-1).to_a
  ['+', '-', '*', '/', ''].rperm(n-1){|opr|
    eqn = "#{seq.zip(opr).to_a.join}#{n}"
    eqn.gsub!(/\/(\d+)/){"\/#{$1}.0"} #floatとして計算させるため
    soln << eqn if eval(eqn) == 100}
  soln
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def komachi(n = 2, e = "1")
  if n == 10
    p e if eval(e.gsub(' ','.0')) == 100
  else
    "+-*/".split("").each{|i|
      komachi(n + 1, e + " " + i + n.to_s)
    }
    komachi(n + 1, e + n.to_s)
  end
end

komachi

重たすぎです。

１．java実行形式にコンパイル
２．combi.eachをfor文に書き換える

としたら何とか動くようになりました。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import static groovy.util.GroovyCollections.combinations
import groovy.util.Eval


def operations = ["", "+", "-", "*", "/"]

def combi = combinations((1..8).collect{ operations })

def eval = new Eval()
combi.each{ opes ->
    def text = "1${opes[0]}2${opes[1]}3${opes[2]}4${opes[3]}5${opes[4]}6${opes[5]}7${opes[6]}8${opes[7]}9"
    if( eval.me(text) == 100 ){
        println "${text} = 100"
    }
}

Eval使いました。

 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
using System;
using System.Collections.Generic;
using System.Windows.Forms;
using Microsoft.JScript.Vsa;
using Microsoft.JScript;

static class Program {
    [STAThread]
    static void Main() {
        string[] s1 = new string[] { "2","3","4","5","6","7","8","9" };
        string[] s2 = new string[] { "","+","-","*","/" };
        int max = (int)Math.Pow(5,8);
        for(int i = 0;i <= max;i++) {
            string rslt = "1";
            int iCopy = i;
            foreach(string s in s1) {
                rslt += s2[iCopy % 5] + s;
                iCopy /= 5;
            }
            VsaEngine ve = VsaEngine.CreateEngine();
            double r = System.Convert.ToDouble(Eval.JScriptEvaluate(rslt,ve));
            if(r == 100.0) {
                Console.WriteLine(rslt);
            }
        }
    }
}

 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
※【なでしこ実行モード】cnako

候補[0]に「」を代入する
候補[1]に「+」を代入する
候補[2]に「-」を代入する
候補[3]に「*」を代入する
候補[4]に「/」を代入する

発見数に0を代入する

枠1で0から4まで繰り返す
  枠2で0から4まで繰り返す
    枠3で0から4まで繰り返す
      枠4で0から4まで繰り返す
        枠5で0から4まで繰り返す
          枠6で0から4まで繰り返す
            枠7で0から4まで繰り返す
              枠8で0から4まで繰り返す
                計算式に「1{候補[枠1]}2{候補[枠2]}3{候補[枠3]}4{候補[枠4]}5{候補[枠5]}6{候補[枠6]}7{候補[枠7]}8{候補[枠8]}9」を代入する
                計算式でナデシコする
                もし、それが100ならば
                  発見数に1を直接足す
                  「{発見数}. {計算式} = 100」と表示

「{改行}全部で{発見数}コありました！」と表示

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);
    }
}

演算子の重複順列を5進数00000000から44444444で表現して総当たり。

10進数を"%08d" % i.to_s(5)で8桁の5進数に変換。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
n = (1..9).to_a
op = ["",".0/","+","-","*"]
for i in 0..((5**8)-1)
  a = n.zip(("%08d" % i.to_s(5)).chars.map{|j|op[j.to_i]}).to_s
  puts a.tr("*/+-","×÷＋－").concat("＝#{eval(a)}").gsub(/\.0/,"") if eval(a) == 100.0
end

# => 123＋45－67＋8－9＝100
# => 123＋4－5＋67－89＝100
# => 123＋4×5－6×7＋8－9＝100
# => 123－45－67＋89＝100
# => 123－4－5－6－7＋8－9＝100
# => 12÷3÷4＋5×6＋78－9＝100
# => 12÷3＋4×5－6－7＋89＝100
# => 12÷3＋4×5×6－7－8－9＝100
# => 12÷3＋4×5×6×7÷8－9＝100
# => 12＋34＋5×6＋7＋8＋9＝100
#...101個表示。

小数点以下の計算が必要なのは、割り算のときだけという事を利用して、#6188を倍速化しました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
OP = "+ - * .0/".split(/ /)

def komachi(n = 2, e = '1')
  if n == 10
    p e if eval(e) == 100
  else
    OP.each{|i|
      komachi(n + 1, e + i + n.to_s)
    }
    komachi(n + 1, e + n.to_s)
  end
end

Tcl8.6b からcoroutine が導入されたので練習も兼ねて。

 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
package require Tcl 8.6

proc A {} {
    foreach x {{{}} + - * /} { B [list $x] }
}

proc cat coro {
    while 1 {
        set input [yield]
        foreach x {{{}} + - * /} { $coro [concat $input $x] }
    }
}

coroutine B cat C
coroutine C cat D
coroutine D cat E
coroutine E cat F
coroutine F cat G
coroutine G cat H
coroutine H cat print

coroutine print apply {{} {
    while 1 {
        lassign [yield] a b c d e f g h
        set exp [join "1 $a 2 $b 3 $c 4 $d 5 $e 6 $f 7 $g 8 $h 9" {}]
        set num [expr [string map {/ *1.0/} $exp]]
        if {$num == 100.0} { puts "$exp = 100" }
    }
}}

puts [time A]
初めてのPowerShellスクリプト。というわけでなんの工夫もありません、ごめんなさい。括弧とか対応していません。なお、Invoke-Expressionはいわゆるevalです。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function komachi([int] $i, [string] $expr)
{
    if ($i -gt 10)
    {
        $sum = Invoke-Expression $expr
        if ($sum -eq 100)
        {
            Write-Output ("$expr = $sum")
        }
    }
    else
    {
        komachi ($i + 1) ($expr + " + $i")
        komachi ($i + 1) ($expr + " - $i")
        komachi ($i + 1) ($expr + " * $i")
        komachi ($i + 1) ($expr + " / $i")
    }
}

komachi 2 '1'
はい、ごめんなさい。空白の場合を忘れていました。というわけで投稿し直します。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function komachi([int] $i, [string] $expr)
{
    if ($i -gt 10)
    {
        $sum = Invoke-Expression $expr
        if ($sum -eq 100)
        {
            Write-Output ("$expr = $sum")
        }
    }
    else
    {
        komachi ($i + 1) ($expr + " + $i")
        komachi ($i + 1) ($expr + " - $i")
        komachi ($i + 1) ($expr + " * $i")
        komachi ($i + 1) ($expr + " / $i")
        komachi ($i + 1) ($expr + [string]$i)
    }
}

komachi 2 '1'

PHP勉強中
 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
<?php
print <<< END_DOC
<HTML>
<HEAD><title>doukaku104</title>
</HEAD><BODY>
END_DOC;

function doukaku104()
{
    $num = array("1", "2", "3", "4", "5", "6", "7", "8", "9");
    $ope = array("","+", "-", "*", "/");
    
    $total = 0;
    for($i = 0; $i < pow(5,8); $i++){
        $t =$i;
        $s = "";
        
        for($j = 0; $j < 8; $j++){
            $s .= $num[$j] . $ope[$t % 5];
            $t /= 5;
        }
        $s .= $num[8];
        $n = eval("return (".$s.");");
        if ($n == 100) {
            print "$s = $n<BR>";
            $total++;
        }
    }
    
    print "total=$total";
}

doukaku104();

print <<< END_DOC
</BODY>
</HTML>
END_DOC;
?>

Index

Feed

Other

Link

Pathtraq

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