Skip to content

Instantly share code, notes, and snippets.

@orlp
Created August 12, 2021 20:12
Show Gist options
  • Save orlp/b7b62a904f9152acb1363b4a1240f9f8 to your computer and use it in GitHub Desktop.
Save orlp/b7b62a904f9152acb1363b4a1240f9f8 to your computer and use it in GitHub Desktop.
from collections import defaultdict
import sys
import pulp
class keydefaultdict(defaultdict):
def __missing__(self, key):
ret = self[key] = self.default_factory(key)
return ret
def horiz_disjoint(xvals):
xvals = sorted(xvals)
diffs = (b - a for a, b in zip(xvals, xvals[1:]))
return all(d >= 1 for d in diffs)
def overhang(blocks):
n = len(blocks)
xs = [round(x, 6) for x, _y in blocks]
ys = [int(y) for _x, y in blocks]
levels = defaultdict(list)
for i, y in enumerate(ys):
if y < 0: return False, "block below table"
levels[y].append(i)
directly_above = defaultdict(list)
directly_below = defaultdict(list)
for i, (xi, yi) in enumerate(zip(xs, ys)):
if xi < 0 and yi == 0:
directly_below[i].append(-1)
directly_above[-1].append(i)
for j in levels[yi + 1]:
if abs(xs[j] - xi) < 1.0:
directly_above[i].append(j)
directly_below[j].append(i)
if not all(horiz_disjoint(xs[i] for i in level) for level in levels.values()):
return False, "blocks not disjoint"
if not all(directly_below[i] for i in range(n)):
return False, "not all blocks supported"
# Algorithm from "Overhang" by Mike Paterson and Uri Zwick.
prob = pulp.LpProblem("balanced")
f = keydefaultdict(lambda t: pulp.LpVariable("f" + ",".join(map(str, t))))
a = lambda i, j: max(xs[i] if i >= 0 else -float('inf'),
xs[j] if j >= 0 else -float('inf'))
b = lambda i, j: min(1 + xs[i] if i >= 0 else 0,
1 + xs[j] if j >= 0 else 0)
for i, xi in enumerate(xs):
force = (pulp.lpSum((f[0,i,j] + f[1,i,j] for j in directly_below[i]))
- pulp.lpSum((f[0,k,i] + f[1,k,i] for k in directly_above[i])))
moment = (pulp.lpSum((a(i,j)*f[0,i,j] + b(i,j)*f[1,i,j] for j in directly_below[i]))
- pulp.lpSum((a(k,i)*f[0,k,i] + b(k,i)*f[1,k,i] for k in directly_above[i])))
prob += force == 1.0
prob += moment == xi + 0.5
for var in f.values():
prob += var >= 0
if not prob.solve(pulp.PULP_CBC_CMD(msg=0)) == pulp.LpStatusOptimal:
return False, "blocks not balanced"
return True, 1 + max(xs)
if __name__ == "__main__":
coords = []
for line in sys.stdin:
line = line.strip()
if not line: continue
x, y = line.split()
coords.append((float(x), int(y)))
valid, ret = overhang(coords)
if valid:
print("Overhang:", ret)
else:
print("Invalid input:", ret)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment