逆ポーランド法を用いた10パズル

逆ポーランド記法を用いた計算

• 数字がスタックに積まれ、演算子が出てくるとスタックのトップ2つの数字を取り出し計算する
• ゼロ除算を避けるため、分母がゼロの場合は大きな数（1e5）をスタックに積む

calc.py

def calc(re_polish_lists):
    stack = []
    for i in range(7):
        if re_polish_lists[i] < 10:
            stack.append(re_polish_lists[i])
        else:
            v1 = stack.pop(-1)
            v2 = stack.pop(-1)
            if re_polish_lists[i] == ADD:
                stack.append(v2 + v1)
            elif re_polish_lists[i] == SUB:
                stack.append(v2 - v1)
            elif re_polish_lists[i] == MUL:
                stack.append(v2 * v1)
            elif re_polish_lists[i] == DIV:
                if v1 != 0:
                    stack.append(v2 / v1)
                else:
                    stack.append(1e5)
    return stack.pop(-1)

演算パターン

演算子と数字の並び方は5パターン
演算子 = o
数字 = d
とすると

[d, d, d, d, o, o, o]
[d, d, d, o, d, o, o]
[d, d, d, o, o, d, o]
[d, d, o, d, d, o, o]
[d, d, o, d, o, d, o]

許容範囲内のチェック

is_within_tolerance.py

def is_within_tolerance(target, result, threshold):
    if math.fabs(target - result) < threshold: return True  
    return  False

10になる組み合わせかチェック

is10.py

def is10(l, ops):
    arrays = [
        [l[0], l[1], l[2], l[3], ops[0], ops[1], ops[2]],
        [l[0], l[1], l[2], ops[0], l[3], ops[1], ops[2]],
        [l[0], l[1], l[2], ops[0], ops[1], l[3], ops[2]],
        [l[0], l[1], ops[0], l[2], l[3], ops[1], ops[2]],
        [l[0], l[1], ops[0], l[2], ops[1], l[3], ops[2]]
    ]
    for array in arrays:
        if is_within_tolerance(10.0, calc(array), 1.0e-7):
            print_fomula(array)
            return True  
    return False

メイン部分

• permutations_list : 数字4つの順列
• operators : [ADD, SUB, MUL, DIV]

最初の for 文3つで演算子３種類を取り出し、4つ目の for 文で
permutations_list から数字の演算パターンを取り出す。

main.py

print("四つの数字を入力してください")
a, b, c, d = map(int, input().split())

isBeing_10 = False
permutations_list = list(itertools.permutations([a, b, c, d], 4))
for opr1 in operators:
    for opr2 in operators:
        for opr3 in operators: 
            opr_list = [opr1, opr2, opr3]
            for list_for_calc in permutations_list:
                isBeing_10 = is10(list_for_calc, opr_list)
                if isBeing_10:
                    break
            if isBeing_10:
                break
        if isBeing_10:
            break
    if isBeing_10:
        break
if not isBeing_10:
    print("\n10になりません\n")

まとめ

make10.py

import math
import itertools
ADD = 101
SUB = 102
MUL = 103
DIV = 104
operators = [ADD, SUB, MUL, DIV]

def calc(re_polish_lists):
    stack = []
    for i in range(7):
        if re_polish_lists[i] < 10:
            stack.append(re_polish_lists[i])
        else:
            v1 = stack.pop(-1)
            v2 = stack.pop(-1)
            if re_polish_lists[i] == ADD:
                stack.append(v2 + v1)
            elif re_polish_lists[i] == SUB:
                stack.append(v2 - v1)
            elif re_polish_lists[i] == MUL:
                stack.append(v2 * v1)
            elif re_polish_lists[i] == DIV:
                if v1 != 0:
                    stack.append(v2 / v1)
                else:
                    stack.append(1e5)
    return stack.pop(-1)

def is_within_tolerance(target, result, threshold):
    if math.fabs(target - result) < threshold: return True  
    return  False

def print_fomula(array):
    print("\n逆ポーランド法表示")
    for i in range(7):
        if array[i] == 101:
            print("+", end = " ")
        elif array[i] == 102:
            print("-", end = " ")
        elif array[i] == 103:
            print("*", end = " ")
        elif array[i] == 104:
            print("/", end = " ")
        else:
            print(array[i], end = " ")
    print("\n")
        
def is10(l,ops):
    arrays = [
        [l[0],l[1],l[2],l[3],ops[0],ops[1],ops[2]],
        [l[0],l[1],l[2],ops[0],l[3],ops[1],ops[2]],
        [l[0],l[1],l[2],ops[0],ops[1],l[3],ops[2]],
        [l[0],l[1],ops[0],l[2],l[3],ops[1],ops[2]],
        [l[0],l[1],ops[0],l[2],ops[1],l[3],ops[2]]
    ]
    for array in arrays:
        if is_within_tolerance(10.0, calc(array), 1.0e-7):
            print_fomula(array)
            return True  
    return False

print("四つの数字を入力してください")
a, b, c, d = map(int,input().split())

isBeing_10 = False
permutations_list = list(itertools.permutations([a, b, c, d], 4))
for opr1 in operators:
    for opr2 in operators:
        for opr3 in operators: 
            opr_list = [opr1, opr2, opr3]
            for list_for_calc in permutations_list:
                isBeing_10 = is10(list_for_calc, opr_list)
                if isBeing_10:
                    break
            if isBeing_10:
                break
        if isBeing_10:
            break
    if isBeing_10:
        break
if not isBeing_10:
    print("\n10になりません\n")

実行結果

$ python3 make10.py
四つの数字を入力してください
3 4 7 8

逆ポーランド法表示
3 7 4 / - 8 * 

解けないパターン

四つの数字を入力してください
7 7 8 9

10になりません