Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Broken Window by mortonfox
from typing import List, Tuple
import itertools
# Decompose a piece into a list of heights.
def heights(piece):
return list(itertools.chain.from_iterable(zip(piece, piece[1:])))
# Window checker. Check that the sum of the bottom height and top height at
# every interval is the same.
def check_window(pieces, btmlist, toplist):
bottom_heights = sum((heights(pieces[indx]) for indx in btmlist), [])
top_heights = sum((heights(list(reversed(pieces[indx]))) for indx in toplist), [])
return len(set(a + b for a, b in zip(bottom_heights, top_heights))) == 1
def build_bottom(pieces, btmlist, btmlistlen, remlist, width):
if btmlistlen == width:
# Once we have a bottom list that equals the window width,
# check to see if the bottom list plus any permutation
# of the remaining pieces form a window.
for toplist in itertools.permutations(remlist):
if check_window(pieces, btmlist, list(toplist)):
return [list(toplist), btmlist]
return False
# Build the bottom list recursively. Find all permutations of pieces that
# equal the window width.
for indx in remlist:
if btmlistlen + len(pieces[indx]) - 1 <= width:
result = build_bottom(
pieces,
btmlist + [indx],
btmlistlen + len(pieces[indx]) - 1,
[x for x in remlist if x != indx],
width)
if result:
return result
return False
def broken_window(pieces: List[List[int]]) -> Tuple[List[int], List[int]]:
width = sum(len(piece) - 1 for piece in pieces) // 2
return build_bottom(pieces, [], 0, list(range(len(pieces))), width)
if __name__ == '__main__':
def checker(func, pieces):
answer = func(pieces)
if not (isinstance(answer, (tuple, list))
and len(answer) == 2
and isinstance(answer[0], list) and isinstance(answer[1], list)):
print('wrong type:', answer)
return False
if set(answer[0]+answer[1]) != set(range(len(pieces))):
print('wrong value:', answer)
return False
def concatenate_pieces(indices, top):
heights_list = []
for i in indices:
heights = pieces[i]
if top:
heights = list(reversed(heights))
if heights_list and heights[0] == heights_list[-1]:
heights_list.pop()
heights_list += heights
return heights_list
tops = concatenate_pieces(answer[0], True)
bottoms = concatenate_pieces(answer[1], False)
if len(tops) != len(bottoms):
return False
return len({sum(z) for z in zip(tops, bottoms)}) == 1
print("Example:")
print(broken_window([[0, 1], [0, 1]]))
assert checker(broken_window, [[0, 3, 4, 1], [4, 0], [3, 0], [0, 1, 4, 0]])
assert checker(broken_window, [[0, 1], [0, 1]])
print("Coding complete? Click 'Check' to earn cool rewards!")
April 5, 2019
