ExtraTaker stage V solver

solver.py

h = 6
w = 9

bo = """
#####G###
#G #   ##
 X     X 
     X X 
##     X 
###### S 
""".split('\n')[1:-1]

pbo = """
#####G###
#G #   ##
         
         
##       
######   
"""

def isin(y,x):
	return 0 <= y and y < h and 0 <= x and x < w and bo[y][x] != '#'

def isinbox(y,x):
	return 0 <= y and y < h and 0 <= x and x < w and bo[y][x] != '#' and bo[y][x] != 'G'

def isbeam(y,x,vs):
	if x == 6:
		# print((y,x),vs)
		for ty in range(1,y):
			if (ty,x) in vs:
				return False
		return True
	if y == 1:
		if ((1,4) in vs and (y,x) == (1,5)) or x == 1:
			return False
		else:
			return True
	if x == 3:
		for ty in range(2,y):
			if (ty,x) in vs:
				return False
		return True
	if x == 2:
		for ty in range(1,y):
			if (ty,x) in vs:
				return False
		return True
	return False

def p2v(p):
	return p[0] * w + p[1]

def p2pbop(p):
	return p[0] * (w+1) + p[1] + 1
	
def reprs(s,p,c):
	return s[:p] + c + s[p+1:]

class State:
	def __init__(self,p,vs,ison,nidx,bidx):
		self.vs = sorted(vs)
		self.p = p
		self.ison = ison
		self.nidx = nidx
		self.bidx = bidx
	
	def __hash__(self):
		res = p2v(self.p)
		for p in self.vs:
			res = res * h * w + p2v(p)
		res = res * h * w + self.ison
		# print(res)
		return res
	
	def __str__(self):
		res = pbo
		for y in range(h):
			for x in range(w):
				if isinbox(y,x) and isbeam(y,x,self.vs):
					res = reprs(res,p2pbop((y,x)),'B')
		res = reprs(res,p2pbop(self.p),'S')
		for p in self.vs:
			res = reprs(res,p2pbop(p),'X')
		return res
		

p = None
vs = []
for y in range(h):
	for x in range(w):
		if bo[y][x] == 'X':
			vs.append((y,x))
		elif bo[y][x] == 'S':
			p = (y,x)

inst = State(p,vs,0,0,-1)

dy = [0,1,0,-1]
dx = [1,0,-1,0]

def copy(v):
	return [i for i in v]



dp = set()
dp.add(inst.__hash__())

import queue
que = queue.Queue()
que.put((0,inst))

mem = []
mem.append(inst)

bd = -1
while not que.empty():
	d,st = que.get()
	if d != bd:
		bd = d
		print(d,len(dp))
	
	if st.ison == 3 or d == 107:
		print(d,st.p,st.vs,st.ison)
		for dep in range(d)[::-1]:
			print(st.__str__())
			st = mem[st.bidx]
		break
	
	for i in range(4):
		ty,tx = st.p[0] + dy[i], st.p[1] + dx[i]
		if not isin(ty,tx):
			continue
		has = False
		tp = st.p
		tvs = copy(st.vs)
		tison = st.ison
		bidx = st.nidx
		for j,(vy,vx) in enumerate(tvs):
			if vy == ty and vx == tx:
				has = True
				tvy,tvx = vy + dy[i], vx + dx[i]
				if (not (tvy,tvx) in tvs) and isinbox(tvy,tvx):
					tvs[j] = (tvy,tvx)
				else:
					tvs = None
				break
		
		if not has:
			if isbeam(ty,tx,tvs):
				tvs = None
			else:
				tp = (ty,tx)
				if bo[ty][tx] == 'G':
					if tx == 1:
						tison = tison | 1
					else:
						tison = tison | 2
					tp = st.p
		
		if tvs is not None:
			tst = State(tp,tvs,tison,len(mem),bidx)
			ha = tst.__hash__()
			if not ha in dp:
				dp.add(ha)
				mem.append(tst)
				que.put((d+1,tst))