Pythonでテンパズルのn個の数字で好きな数字を作りたい

やること

• n個の数字から2つを選んで +-x÷をすべて並べ替えて出力
  [1,2] -> ['(1+2)', '(1-2)', '(1*2)', '(1/2)'] みたいに
• 繰り返す

[1,2,3] ->
[['(1+2)', 3], ['(1-2)', 3], ['(1*2)', 3], ['(1/2)', 3]] -> 
['((1+2)+3)', '((1+2)-3)', '((1+2)*3)', '((1+2)/3)' ... ]

みたいに

コード

import

import math
from tqdm import tqdm

permutation

2個選ぶ用の関数
https://docs.python.org/3/library/itertools.html#itertools.permutations を改変。

def permutations(iterable, r=None):
    pool = list(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    x=[]
    x.append(list(pool[i] for i in indices[:r]))
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                x.append(list(pool[i] for i in indices[:r]))
                break
        else:
            return x

itertools.permutations()でもよかったが、Cythonで高速化したかったのでリストが返ってきてほしかったため。

+-*/の並べ替え

def insert(nums):
    if not isinstance(nums,list):
        return nums
    ret=[]
    for i in ["+","-","*","/"]:
        num=nums.copy()
        num.insert(1,i)
        ret.append("("+"".join([str(i) for i in num])+")")
    return ret


print(insert([1,2]))
#['(1+2)', '(1-2)', '(1*2)', '(1/2)']

listを並べ替えて結合

def combine(x,y):
    x=x if isinstance(x,list) else [x]
    y=y if isinstance(y,list) else [y]
    x=[i if isinstance(i,list) else [i] for i in x]
    y=[i if isinstance(i,list) else [i] for i in y]
    ret=[]
    for i in x:
        for j in y:
            ret.append(i+j)
    return ret

def combine_all(x):
    if len(x)==1:
        return x[0]
    if len(x)==2:
        return combine(x[0],x[1])
    else:
        y=combine(x[0],x[1])
        for i in x[2:]:
            y=combine(y,i)
        return y

print(combine_all([[1,2],[3,4],5]))
#[[1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5]]

例外処理

実行時にZeroDivisionError が出る可能性があるため。

def execute(i,t):
    try:
        if eval(i)==t:
            return i
        else:
            return False
    except:
        return False

実行部

whileでretにできたものを、noretにまだできていないやつを追加して実行。
最終的にやっていることは、

[1,2,3] ->
["(1+2)",3],[3,"(1+2)"] ... ->
"((1+2)+3)","((1+2)*3)" ... "(3+(1+2))","(3*(1+2))", ...

みたいな感じ。

def get(nums,a):
    nums=[nums]
    ret=[]
    while True:
        noret=[]
        for num in nums:
            perms=permutations(num,2)
            for perm in perms:
                inserted=insert(perm)
                if len(num)==2:
                    ret+=inserted
                    continue
                x=num.copy()
                for i in perm:
                    x.remove(i)
                x.append(inserted)
                noret+=combine_all(x)
        if noret:
            nums=noret
        else:
            val=[]
            for i in tqdm(set(ret)):
                if x:=execute(i,a):
                    val.append(i)
            return val

実行

print(get([1,1,9,9],10))
#['(9*((1/9)+1))', '((1+(1/9))*9)', '(((1/9)+1)*9)', '(9*(1+(1/9)))']

5個の数字の場合、平均10秒ほど。

import math
from tqdm import tqdm

cdef list permutations(list iterable,int r):
    cdef:
        list pool=iterable
        int n = len(pool)
    if r > n:
        return
    cdef:
        list indices = list(range(n))
        list cycles = list(range(n, n-r, -1))
        list x=[]
        int i,j,k,l
    x.append(list(pool[k] for k in indices[:r]))
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                x.append(list(pool[l] for l in indices[:r]))
                break
        else:
            return x

cdef insert(nums):
    if not isinstance(nums,list):
        return nums
    cdef:
        list ret=[]
        list f=["+","-","*","/"]
        list j,num
        str x=""
        str i
    for i in f:
        num=nums.copy()
        num.insert(1,i)
        ret.append("("+"".join([str(k) for k in num])+")")
    return ret

cdef combine(d,f):
    cdef:
        list a=d if isinstance(d,list) else [d]
        list b=f if isinstance(f,list) else [f]
        list x=[p if isinstance(p,list) else [p] for p in a]
        list y=[q if isinstance(q,list) else [q] for q in b]
        list ret=[]
        list i,j
    for i in x:
        for j in y:
            ret.append(i+j)
    return ret

cdef list combine_all(list x):
    cdef list y
    if len(x)==1:
        return x[0]
    if len(x)==2:
        return combine(x[0],x[1])
    else:
        y=combine(x[0],x[1])
        for i in x[2:]:
            y=combine(y,i)
        return y

cdef execute(str i,t):
    try:
        if eval(i)==t:
            return i
        else:
            return False
    except:
        return False

def get(list numbers,int a):
    cdef:
        list nums=[numbers]
        list ret=[]
        list noret=[]
        list val=[]
        list perms,num,x,inserted
        str k
    while True:
        noret=[]
        for num in nums:
            perms=permutations(num,2)
            for perm in perms:
                inserted=insert(perm)
                if len(num)==2:
                    ret+=inserted
                    continue
                x=num.copy()
                for i in perm:
                    x.remove(i)
                x.append(inserted)
                noret+=combine_all(x)
        if noret:
            nums=noret
        else:
            val=[]
            for k in tqdm(set(ret)):
                if execute(k,a):
                    val.append(k)
            return val

Cythonでもやってみたが、１秒ほどしか変わらなかった。

後日短くした

import os
os.environ["OPENBLAS_NUM_THREADS"] = "16"
os.environ["MKL_NUM_THREADS"] = "16"
os.environ["VECLIB_NUM_THREADS"] = "16"
from tqdm import tqdm
import numpy as np
from multiprocessing import Pool
import sys
import time
import threading
import itertools

def products(x):
    for i in x[-1]:
        yield x[:-1]+[i]
        
def insert(nums):
    s1,s2=nums[0],nums[1]
    n1,n2=convert(s1),convert(s2)
    return [f"{s1}+{s2}", f"{s1}-{s2}", f"{s2}-{s1}", f"{n1}*{n2}", f"{n1}/{n2}", f"{n2}/{n1}"]

def numpy_combinations(x):
    idx = np.stack(np.triu_indices(len(x), k=1), axis=-1)
    return x[idx]

def convert(i):
    return f"({i})" if ("+" in i or "-" in i) else i

def execute(i,targetn):
    try:
        if eval(i)==targetn:
            return i
        else:
            return False
    except ZeroDivisionError:
        return False

def get1(x):
    if len(x)>2:
        for comb in numpy_combinations(np.array(x)):
            y=sorted(x,key=(list(comb)+x).index)[2:]
            y.append(insert(comb))
            for i in products(y):
                yield from get1(i)
    else:
        for i in insert(x):
            yield i

done=False
    
def animate():
    for c in itertools.cycle(['|', '/', '-', '\\']):
        if done:
            break
        sys.stdout.write('\rGenerating all expressions  ' + c)
        sys.stdout.flush()
        time.sleep(0.1)
    sys.stdout.write('\rDone!')
    
def task():
    global done
    p2=Pool(16)
    x=input("input numbers with space like '1 2 3 4' > ").split(" ")
    targetn=int(input("input target number. > "))
    t = threading.Thread(target=animate)
    t.start()
    s=time.time()
    done=True
    print(list(filter(lambda i:i,p2.starmap(execute,tqdm(list(map(lambda i:(i,targetn),set(get1(x)))))))))
    e=time.time()
    print(f"Took {e-s}s")

if __name__=="__main__":
    task()

treadingにより並列処理を導入。