67 lines
1.8 KiB
Python
67 lines
1.8 KiB
Python
from itertools import combinations
|
|
import sys
|
|
|
|
sys.setrecursionlimit(5000)
|
|
cell_size = 3
|
|
truthTable = [
|
|
[0b000,0b000],[0b001,0b000],
|
|
[0b010,0b000],[0b011,0b000],
|
|
[0b100,0b110],[0b101,0b110],
|
|
[0b110,0b110],[0b111,0b110],
|
|
]
|
|
|
|
|
|
inp = [index for index,_ in truthTable]
|
|
ans = [index for _,index in truthTable]
|
|
|
|
def generate_ins(size,exception):
|
|
lst = [index for index in range(0,size+1) if index != exception+1]
|
|
ans = []
|
|
for i in range(1,len(lst)+1):
|
|
for com in combinations(lst,i):
|
|
tmp = 0
|
|
for j in com:
|
|
tmp += 1<<j
|
|
ans.append(tmp)
|
|
return(ans)
|
|
|
|
def operate(operand,ins):
|
|
if((ins & 1) == 0):
|
|
return(operand | (ins>>1))
|
|
else:
|
|
return(operand ^ (ins>>1))
|
|
|
|
|
|
def bfs(present = [[inp,[]]]):
|
|
next_present = []
|
|
for stat,proc in present:
|
|
if(stat == ans):
|
|
return proc
|
|
else:
|
|
for i in range(0,cell_size):
|
|
ins_list = generate_ins(cell_size,i)
|
|
tmp_present = [(x & (~(1<<i))) for x in stat]
|
|
operable = [(True if ((x & (1<<i)) > 0) else False) for x in stat]
|
|
for j in ins_list:
|
|
tmp_proc = proc.copy()
|
|
tmp_proc.append([i,j])
|
|
next_present.append([[(operate(tmp_present[k],j) if(operable[k] == True) else tmp_present[k]) for k in range(0,len(stat))],tmp_proc])
|
|
#print(next_present)
|
|
return bfs(next_present)
|
|
|
|
for i in bfs():
|
|
operand = []
|
|
tmp = i[1]
|
|
count = 0
|
|
while(tmp != 0):
|
|
tmp >>= 1
|
|
if((tmp&1) == 1):
|
|
operand.append(count)
|
|
count += 1
|
|
if(i[1] == 0 or i[1] == 1):
|
|
print("ERASE ",i[0])
|
|
else:
|
|
if(i[1] &1 == 1):
|
|
print("ERASE ",i[0]," SET1 ",operand)
|
|
else:
|
|
print("ERASE ",i[0]," FLIP ",operand) |