数式の演算子配置問題

数式の演算子配置問題#

次の式に対して、? に +, -, * のいずれかを入れ、括弧を適切に配置して式の値が 99 になるようにしてください。

1 ? 2 ? 3 ? 4 ? 5 ? 6 ? 7 ? 8 ? 9 = 99

from z3 import *
from helper.z3 import all_solutions

解き方#

24を求める問題では、数式中の数値の順番は自由に選べますが、この問題では数値の順番が固定されています。ただし、括弧を用いることで計算の順序を変えることが可能です。そのため、次のグラフのように計算を進めます。

        graph
a1[1]
a2[2]
a3[3+4]
a4[5]
b1[1*2]
b2[3+4]
b3[5]
c1[1*2]
c2[3+4-5]
d1[1*2+3+4-5]
1 --> a1
2 --> a2
3 --> a3
4 --> a3
5 --> a4
a1 --> b1
a2 --> b1
a3 --> b2
a4 --> b3
b1 --> c1
b2 --> c2
b3 --> c2
c1 --> d1
c2 --> d1

この例では、1～5の数値があり、まず演算子を挿入する位置と種類を決定し、その演算を実行します。演算を行うたびに数値の個数が1つ減り、この操作を繰り返すことで、最終的に1つの数値だけが残ります。

この処理は、以下のようにプログラムで実装できます。

def calc_op(x1, x2, op):
    return If(op == 0, x1 + x2, If(op == 1, x1 - x2, x1 * x2))

def calc_tree(f, locs, ops):
    exprs = []
    for l, fn in enumerate(f[1:], 1):
        fp = f[l - 1]
        for i in range(len(f[l])):
            exprs.extend([
                Implies(i  < locs[l - 1], fn[i] == fp[i]),
                Implies(i == locs[l - 1], fn[i] == calc_op(fp[i], fp[i + 1], ops[l - 1])),
                Implies(i  > locs[l - 1], fn[i] == fp[i + 1])
            ])
    return exprs

次に、演算子の位置と種類を固定し、動作を確認します。

n = 5
f = [[Int(f'f{l}_{i}') for i in range(n - l)] for l in range(n)]
init = [f[0][i] == i + 1 for i in range(n)]
locs = [2, 0, 1, 0]
ops = [0, 2, 1, 0]
solve(init + calc_tree(f, locs, ops))

[f2_2 = 5,
 f0_4 = 5,
 f1_3 = 5,
 f0_1 = 2,
 f3_0 = 2,
 f1_0 = 1,
 f2_0 = 2,
 f0_2 = 3,
 f3_1 = 2,
 f1_1 = 2,
 f2_1 = 7,
 f0_3 = 4,
 f4_0 = 4,
 f1_2 = 7,
 f0_0 = 1]

If 関数#

上のコードでは、If 関数を使って、数値で表された演算子に応じた演算結果を計算しています。
If 関数は If(condition, true_value, false_value) の形式で条件分岐を行い、条件が真の場合と偽の場合で異なる値を返します。

次のコードでは、If 関数を使って op の値に応じた異なる演算（+, -, *）を選択しています：

If(op == 0, x1 + x2, If(op == 1, x1 - x2, x1 * x2))

これは、op の値に応じて以下のように動作します：

  • op == 0 の場合：x1 + x2

  • op == 1 の場合：x1 - x2

  • op == 2 の場合：x1 * x2

このように、If を入れ子にすることで、複数の条件分岐を扱うことができます。

コード#

以下のコードでは、上のcalc_op()とcalc_tree()を使用して演算子と計算の組み合わせを探索し、1 から 9 までの数値 を使って 99 を作る組み合わせを求めます。

solver = Solver()

n = 9
f = [[Int(f'f{l}_{i}') for i in range(n - l)] for l in range(n)]

for i in range(n):
    solver.add(f[0][i] == i + 1)

locs = IntVector('loc', n - 1)
ops = IntVector('op', n - 1)

for i, loc in enumerate(locs):
    solver.add(0 <= loc, loc < n - i - 1)

for op in ops:
    solver.add(0 <= op, op <= 2)

solver.add(calc_tree(f, locs, ops))

solver.add(f[-1][0] == 99)

print(solver.check())
m = solver.model()
print("levels")
for level in range(n):
    print([m[f[level][i]] for i in range(n - level)])

print("locations")
print([m[x] for x in locs])
print("ops")
print(['+-*'[m[x].as_long()] for x in ops])

sat
levels
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 7, 5, 6, 7, 8, 9]
[1, 2, 7, 5, 6, -1, 9]
[1, 2, 7, 5, 7, 9]
[1, 9, 5, 7, 9]
[1, 4, 7, 9]
[1, 11, 9]
[11, 9]
[99]
locations
[2, 5, 4, 1, 1, 1, 0, 0]
ops
['+', '-', '-', '+', '-', '+', '*', '*']

数式に出力#

以下のコードでは、演算子の位置と種類を用いて数式を出力します。

class Expr:
    def __init__(self, expr_l, op, expr_r):
        self.expr_l = expr_l
        self.op = op
        self.expr_r = expr_r

    def __str__(self):
        if isinstance(self.expr_l, Expr) and self.op in '*' and self.expr_l.op in '+-':
            left = f'({self.expr_l})'
        else:
            left = f'{self.expr_l}'

        if isinstance(self.expr_r, Expr) and self.op in '*-' and self.expr_r.op in '+-':
            right = f'({self.expr_r})'
        else:
            right = f'{self.expr_r}'

        return f'{left} {self.op} {right}'

def output(numbers, locs, ops):
    numbers = [str(x) for x in numbers]
    for i, op in zip(locs, ops):
        op = '+-*'[op]
        n1, n2 = numbers[i], numbers[i + 1]
        numbers[i] = Expr(n1, op, n2)
        del numbers[i + 1]
    return str(numbers[0])

expr = output(
    [m[x].as_long() for x in f[0]],
    [m[x].as_long() for x in locs],
    [m[x].as_long() for x in ops]
)
print(expr, eval(expr))

1 * (2 + 3 + 4 - 5 + 6 - (7 - 8)) * 9 99
Contents