Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Broken Window by tokiojapan55
from typing import List, Tuple
def add_queue(path, pieces, shapes, stack, walked):
new_shapes = tuple([shapes.index(tuple(pieces[p[0]])) for p in list(path)])
if new_shapes not in walked:
stack.append(path)
walked.append(new_shapes)
def broken_window2(pieces: List[List[int]], height: int) -> Tuple[List[int], List[int]]:
shapes = list(set([tuple(piece) for piece in pieces]))
stack = []
for p,piece in enumerate(pieces):
if piece[0] > 0:
stack.append(((p,0,0),))
if piece[-1] == height:
stack.append(((p,1,0),))
walked = []
for path in stack:
walked.append(tuple([shapes.index(tuple(pieces[p[0]])) for p in list(path)]))
uppers,lowers = [],[]
while stack:
path = stack.pop()
length = 0
for (p,f,i) in path:
if length < i + len(pieces[p]):
length = i + len(pieces[p])
upper = [-1] * length
lower = [-1] * length
for idx,(p,f,i) in enumerate(path):
for ii in range(len(pieces[p]) - 1):
if f == 0:
lower[i + ii] = idx
else:
upper[i + ii] = idx
lack = []
start = length - 1
for idx,lo,up in zip(range(length), lower, upper):
if lo < 0 and up < 0:
break
if len(lack) > 0:
h = 0
if lo >= 0:
h += pieces[path[lo][0]][idx - path[lo][2] + 1]
if up >= 0:
h += pieces[path[up][0]][::-1][idx - path[up][2] + 1]
if h >= height:
break
elif up < 0:
pth = path[lo]
piece = pieces[pth[0]]
if piece[idx - pth[2]] < height or piece[idx - pth[2] + 1] < height:
if len(lack) <= 0:
start = idx
lack.append(piece[idx - pth[2]] - height)
lack.append(piece[idx - pth[2] + 1] - height)
elif lo < 0:
pth = path[up]
piece = pieces[pth[0]]
if piece[::-1][idx - pth[2]] < height or piece[::-1][idx - pth[2] + 1] < height:
if len(lack) <= 0:
start = idx
lack.append(height - piece[::-1][idx - pth[2]])
lack.append(height - piece[::-1][idx - pth[2] + 1])
if len(path) == len(pieces) and len(lack) == 0:
uppers = [p for p,f,i in path if f==1]
lowers = [p for p,f,i in path if f==0]
break
for idx,piece in enumerate(pieces):
if idx not in [p[0] for p in list(path)]:
if len(lack) == 0:
if path[-1][1] == 0 and piece[-1] == height:
add_queue(path + ((idx,1,start),), pieces, shapes, stack, walked)
if path[-1][1] == 1 and piece[0] > 0:
add_queue(path + ((idx,0,start),), pieces, shapes, stack, walked)
elif sum(lack) >= 0:
chk_len = min(len(lack), len(piece))
if piece[:chk_len] == lack[:chk_len]:
add_queue(path + ((idx,0,start),), pieces, shapes, stack, walked)
else:
chk_len = min(len(lack), len(piece))
if piece[::-1][:chk_len] == [-v for v in lack[:chk_len]]:
add_queue(path + ((idx,1,start),), pieces, shapes, stack, walked)
return [uppers, lowers]
def broken_window(pieces: List[List[int]]) -> Tuple[List[int], List[int]]:
height = max([max(p) for p in pieces])
for h in range(height, height*2 + 1):
result = broken_window2(pieces, h)
if result != [[],[]]:
return result
return [[],[]]
June 2, 2020
