AOJトライに関する知識知見の記録共有 （Volume0-0041）

概要

Expression

コード

TIPS：再帰処理により可変長引数に対応

import itertools

def apply_op(op, args):
    a, b = args[:2]
    if op == "+":
        return a + b
    elif op == "-":
        return a - b
    elif op == "*":
        return a * b

def gen_list_histresult(hist, args):
    if len(args) == 1:
        return [[hist, args]]
    else:
        ret = []
        for v in itertools.permutations(args):
            for op in ["+", "-", "*"]:
                new_valuelist = [apply_op(op, v[:2])] + list(v[2:])
                ret.extend(gen_list_histresult(hist + [op, v[:2]], new_valuelist))
        return ret

def ret_readable_exp(v):
    return v

def core(args, cond_res=10):
    list_hist_valuelist = gen_list_histresult([], args)
    print(len(list_hist_valuelist), list_hist_valuelist[0])
    return [[ret_readable_exp(v[0]), v[1]] for v in list_hist_valuelist if v[1] == [cond_res]][:1]

def app(*args):
    return [[arg, core(arg)] for arg in args]

print(app(
[8, 7, 9, 9],
[4, 4, 4, 4],
[5, 5, 7, 5],
[1, 2, 7],
))

実行結果

デバッグログ出力部含む

7776 [['+', (8, 7), '+', (15, 9), '+', (24, 9)], [33]]
7776 [['+', (4, 4), '+', (8, 4), '+', (12, 4)], [16]]
7776 [['+', (5, 5), '+', (10, 7), '+', (17, 5)], [22]]
108 [['+', (1, 2), '+', (3, 7)], [10]]
[[[8, 7, 9, 9], [[['-', (9, 7), '*', (2, 9), '-', (18, 8)], [10]]]], [[4, 4, 4, 4], []], [[5, 5, 7, 5], [[['*', (5, 5), '*', (7, 5), '-', (35, 25)], [10]]]], [[1, 2, 7], [[['+', (1, 2), '+', (3, 7)], [10]]]]]