1 import copy
  2 from cmath import inf, log
  3 import numpy as np
  4 
  5 class Solution:
  6     suffix_list = None
  7     tree_list = None
  8     shuffle_list = None
  9     op_list = None
 10     num_list = None
 11     flag = False
 12 
 13     gen_combine_peer_layer = None
 14     def which_to_gen(self, parent:[], i, res):
 15         if i < len(parent):
 16             self.which_to_gen(parent, i+1, res)
 17             res.append(parent[i])
 18             self.which_to_gen(parent, i+1, res)
 19             res.pop()
 20         elif len(res) > 0 and res not in self.gen_combine_peer_layer:
 21             self.gen_combine_peer_layer.append(copy.deepcopy(res))
 22 
 23 
 24     def generator(self, n, cnt, layer, tree):
 25         if cnt < n and pow(2, layer) < len(tree):
 26             parent = []
 27             for k in range(pow(2, layer), pow(2, layer+1)):
 28                 if 2*k+1 < len(tree) and tree[k] == 1:
 29                     parent.append(k)
 30             self.gen_combine_peer_layer = []
 31             self.which_to_gen(parent, 0, [])
 32             for gen in self.gen_combine_peer_layer:
 33                 for p in gen:
 34                     tree[2*p], tree[2*p+1] = 1, 1
 35                 self.generator(n, cnt+2*len(gen), layer+1, tree)
 36                 for p in gen:
 37                     tree[2*p], tree[2*p+1] = 0, 0
 38         elif cnt == n and tree not in self.tree_list:
 39             self.tree_list.append(copy.deepcopy(tree))
 40 
 41 
 42     def generate_suffix(self, nums: [], ops: [],  tree:[], i, j, k, suffix):
 43         if k < len(tree) and (len(nums) > 0 or len(ops) > 0):
 44             if tree[k] == 1:
 45                 if 2*k+1 < len(tree) and tree[2*k] == 1 and tree[2*k+1] == 1 and len(ops) > 0:
 46                     suffix[k] = ops.pop()
 47                     self.generate_suffix(nums, ops, tree, i, j, 2*k, suffix)
 48                     self.generate_suffix(nums, ops, tree, i, j, 2*k+1, suffix)
 49                 elif len(nums) > 0:
 50                     suffix[k] = nums.pop()
 51                     self.generate_suffix(nums, ops, tree, i, j, 2*k, suffix)
 52                     self.generate_suffix(nums, ops, tree, i, j, 2*k+1, suffix)
 53         elif  len(nums) == 0 and len(ops) == 0 and suffix not in self.suffix_list:
 54             self.suffix_list.append(copy.deepcopy(suffix))
 55 
 56     def select_combine(self, ops: []):
 57         for i, ei in enumerate(ops):
 58             for j, ej in enumerate(ops):
 59                 for k, ek in enumerate(ops):
 60                     if [ei, ej, ek] not in self.op_list:
 61                         self.op_list.append([ei, ej, ek])
 62 
 63     def shuffle(self, nums: [], i=0) -> []:
 64         if i < len(nums):
 65             for k in range(len(nums)):
 66                 self.shuffle(nums, i + 1)
 67                 nums[i], nums[k] = nums[k], nums[i]
 68                 self.shuffle(nums, i + 1)
 69         elif nums not in self.shuffle_list:
 70             self.shuffle_list.append(copy.deepcopy(nums))
 71 
 72     def calcu(self, suffix:[], i):
 73         if not self.flag and i < len(suffix):
 74             if suffix[i] != '#':
 75                 if suffix[i] in ['+', '-', '*', '/']:
 76                     self.calcu(suffix, 2*i)
 77                     self.calcu(suffix, 2*i+1)
 78                     if 2*i+1 < len(suffix) and suffix[2*i] not in ['+', '-', '*', '/', '#'] and suffix[2*i+1] not in ['+', '-', '*', '/', '#']:
 79                         if suffix[i] == '+':
 80                             suffix[i] = suffix[2*i] + suffix[2*i+1]
 81                         elif suffix[i] == '-':
 82                             suffix[i] = suffix[2 * i] - suffix[2 * i + 1]
 83                         elif suffix[i] == '*':
 84                             suffix[i] = suffix[2 * i] * suffix[2 * i + 1]
 85                         else:
 86                             if suffix[2 * i + 1] != 0:
 87                                 suffix[i] = suffix[2 * i] / suffix[2 * i + 1]
 88                             else:
 89                                 suffix[i] = inf
 90                         suffix[2 * i], suffix[2 * i + 1] = '#', '#'
 91                     if i == 1 and suffix[1] == 24:
 92                         self.flag = True
 93 
 94 
 95 
 96 
 97 
 98     def judgePoint24(self, nums: [int]) -> bool:
 99         self.shuffle_list = []
100         self.op_list = []
101         self.shuffle(nums)
102         self.num_list = copy.deepcopy(self.shuffle_list)
103         self.select_combine(['+', '-', '*', '/'])
104         self.shuffle_list = []
105         while len(self.op_list) > 0:
106             ol = self.op_list.pop()
107             self.shuffle(ol)
108         self.op_list = self.shuffle_list
109 
110         n = 7
111         length = int((n+1)/2)
112         length = int(pow(2, length)) + 1
113         tree = [0] * length
114         tree[1] = 1
115         self.tree_list = []
116         #self.generate_tree(7, 1, 1, tree)
117         self.generator(7,1,0,tree)
118         self.suffix_list = []
119         for tree in self.tree_list:
120             for nl in self.num_list:
121                 for ol in self.op_list:
122                     suffix = ['#'] * length
123                     dnl = copy.deepcopy(nl)
124                     dol = copy.deepcopy(ol)
125                     self.generate_suffix(dnl, dol, tree, 0, 0, 1, suffix)
126 
127 
128         self.flag = False
129         for suffix in self.suffix_list:
130             self.calcu(suffix, 1)
131 
132         return self.flag
133 
134 ['#', 2, 1, '+', 9, 1, '-', '*', '#', '#', '#', '#', '#', '#', '#', '#', '#']
135 nums = [1,9,1,2]
136 
137 nums = [1,3,4,6]
138 nums = [4, 1, 8, 7]
139 sol = Solution()
140 res = sol.judgePoint24(nums)
141 print(res)