Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BruteForce without any special optimizations solution in Clear category for Broken Window by swagg010164
from typing import List, Tuple
from itertools import zip_longest
from copy import deepcopy, copy
from collections import defaultdict
from functools import lru_cache
def answer_checker(tops, bottoms):
return len({sum(z) for z in zip(tops, bottoms)}) == 1
def recur(tops, bottoms, stat, pieces, top_pieces, bottom_pieces, max_):
if len(tops) == len(bottoms) and len(top_pieces) + len(bottom_pieces) == len(pieces) and answer_checker(tops,
bottoms):
yield top_pieces, bottom_pieces
return
if len(top_pieces) + len(bottom_pieces) == len(pieces):
return
for piece in pieces:
if stat[tuple(piece)] > 0:
stat[tuple(piece)] -= 1
to_top = copy(piece[::-1])
top_pieces.append(copy(piece))
top_carry = None
if tops and to_top[0] == tops[-1]:
top_carry = tops.pop()
tops += to_top
if (len(tops) != len(bottoms) or len(top_pieces) + len(bottom_pieces) <= len(pieces)) and max({sum(z) for z in zip(tops, bottoms)}, default=0) <= max_:
yield from recur(tops, bottoms, stat, pieces, top_pieces, bottom_pieces, max_)
for _ in range(len(top_pieces[-1])):
tops.pop()
if top_carry is not None:
tops += [top_carry]
to_bottom = copy(top_pieces.pop())
bottom_pieces.append(copy(piece))
bottom_carry = None
if bottoms and to_bottom[0] == bottoms[-1]:
bottom_carry = bottoms.pop()
bottoms += to_bottom
if (len(tops) != len(bottoms) or len(top_pieces) + len(bottom_pieces) <= len(pieces)) and max({sum(z) for z in zip(tops, bottoms)}, default=0) <= max_:
yield from recur(tops, bottoms, stat, pieces, top_pieces, bottom_pieces, max_)
for _ in range(len(bottom_pieces[-1])):
bottoms.pop()
if bottom_carry is not None:
bottoms += [bottom_carry]
if bottom_pieces:
bottom_pieces.pop()
stat[tuple(piece)] += 1
else:
for _ in range(len(bottom_pieces[-1])):
bottoms.pop()
if bottom_carry is not None:
bottoms += [bottom_carry]
if bottom_pieces:
bottom_pieces.pop()
stat[tuple(piece)] += 1
else:
for _ in range(len(top_pieces[-1])):
tops.pop()
if top_carry is not None:
tops += [top_carry]
top_pieces.pop()
stat[tuple(piece)] += 1
def broken_window(pieces: List[List[int]]) -> Tuple[List[int], List[int]]:
if len(set(tuple(k) for k in pieces)) == 1:
return [i for i in range(len(pieces)//2)], [i for i in range(len(pieces)//2, len(pieces))]
stat = defaultdict(int)
indexes = defaultdict(list)
for ind, k in enumerate(pieces):
stat[tuple(k)] += 1
indexes[tuple(k)].append(ind)
tops, bottoms = [], []
global_max = 0
for k in pieces:
global_max = max(max(k), global_max)
for res in recur([], [], stat, pieces, [], [], global_max):
if res:
tops, bottoms = res
break
return [indexes[tuple(k)].pop(0) for k in tops], [indexes[tuple(k)].pop(0) for k in bottoms]
May 5, 2020
