Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
BFS solution in Clear category for Stacking Cubes by Sim0000
from typing import List, Tuple
from collections import Counter, deque
def stacking_cubes(cubes: List[Tuple[int, int, int]]) -> int:
def cross(c1, c2):
x1, y1, d1, _ = c1
x2, y2, d2, _ = c2
return (x1 <= x2 < x1 + d1 or x2 <= x1 < x2 + d2) and (y1 <= y2 < y1 + d1 or y2 <= y1 < y2 + d2)
C = Counter(cubes)
C = [c + (C[c] * c[2],) for c in C] # (x, y, edge length, height)
Q = deque([({c}, c, c[3]) for c in C])
max_height = 0
while Q:
used, last, height = Q.popleft()
max_height = max(max_height, height)
for c in C:
if c not in used and cross(last, c):
Q.append((used | {c}, c, height + c[3]))
return max_height
if __name__ == '__main__':
assert stacking_cubes([(0, 0, 2), (1, 1, 2), (3, 2, 2)]) == 4, 'basic'
assert stacking_cubes([(0, 0, 2), (1, 1, 2), (1, 2, 1), (2, 2, 2)]) == 6, 'basic 2'
assert stacking_cubes([(0, 0, 2), (2, 0, 2), (2, 0, 2), (0, 2, 2), (0, 2, 2), (0, 2, 2), (0, 2, 2)]) == 8, 'towers'
assert stacking_cubes([(0, 0, 2), (0, 3, 2), (3, 0, 2)]) == 2, 'no stacking'
assert stacking_cubes([(-1, -1, 2), (0, 0, 2), (-2, -2, 2)]) == 6, 'negative coordinates'
print("Coding complete? Click 'Check' to earn cool rewards!")
April 22, 2020
Comments:
