Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Generate big stacks with a bit of OOP solution in Clear category for Stacking Cubes by Phil15
from typing import List, Tuple
def stacking_cubes(cubes: List[Tuple[int, int, int]]) -> int:
"""Return the largest in stacking height of the cubes."""
_cubes = [_Cube(x, y, dim) for x, y, dim in cubes]
graph = {cube: {c for c in _cubes if c is not cube and cube.touch(c)}
for cube in _cubes}
# Basic upper bound to stop the search.
# May be unefficient in some cases. It could be more efficient if computed
# for each connected component. But it is unnecessary here to pass tests.
max_height = sum(cube.height for cube in _cubes)
def big_stacks():
stacks = [([cube], set()) for cube in _cubes]
while stacks:
stack, visited = stacks.pop()
last = stack[-1]
next_cubes = graph[last] - visited
if not next_cubes:
height = sum(cube.height for cube in stack)
yield stack, height
if height == max_height:
break
else:
stacks.extend((stack + [cube], visited | {last})
for cube in next_cubes)
best_stack, best_height = max(big_stacks(), key=lambda x: x[1])
print([cube.args for cube in best_stack])
return best_height
class _Cube:
"""
Easier to handle cubes this way than with tuples.
They are still hashable (usable as dict key and in sets).
It has a simple method to determine if it can touch an another cube.
And most important, they are unique (not like tuples):
>>> {(0, 0, 1), (0, 0, 1)}
{(0, 0, 1)}
>>> {_Cube(0, 0, 1), _Cube(0, 0, 1)}
{_Cube(0, 0, 1), _Cube(0, 0, 1)}
"""
def __init__(self, x: int, y: int, dim: int):
self.args = x, y, dim
self.ranges = (x, x + dim), (y, y + dim)
self.height = dim
def __repr__(self): return f'_Cube{self.args}'
def touch(self, other: '_Cube') -> bool:
return all(maxi1 > mini2 and maxi2 > mini1
for (mini1, maxi1), (mini2, maxi2) in zip(self.ranges, other.ranges))
March 11, 2020
Comments:
