Skip to content

Instantly share code, notes, and snippets.

@josejuan
Created October 22, 2023 09:49
Show Gist options
  • Save josejuan/3fd5a21eb16fe79dd3c735c53046727a to your computer and use it in GitHub Desktop.
Save josejuan/3fd5a21eb16fe79dd3c735c53046727a to your computer and use it in GitHub Desktop.
xs = [
[0, 0, 1, 0, []],
[0, 2, 2, 0, []],
[0, 5, 1, 0, []],
[1, 3, 2, 0, []],
[1, 6, 2, 0, []],
[2, 0, 3, 0, []],
[2, 2, 2, 0, []],
[2, 4, 2, 0, []],
[3, 1, 1, 0, []],
[3, 3, 3, 0, []],
[4, 4, 5, 0, []],
[4, 6, 2, 0, []],
[5, 0, 2, 0, []],
[5, 3, 2, 0, []],
[6, 1, 1, 0, []],
[6, 4, 4, 0, []],
[6, 6, 1, 0, []]
]
def find_pairs(xs):
n = len(xs)
for i in range(n):
xi, yi, _, _, ni = xs[i]
for j in range(i + 1, n):
xj, yj, _, _, nj = xs[j]
if xi == xj:
ya = min(yi, yj)
yb = max(yi, yj)
if all(x != xi or y < ya or yb < y for k, (x, y, _, _, _) in enumerate(xs) if k != i and k != j):
ni.append(j)
nj.append(i)
elif yi == yj:
xa = min(xi, xj)
xb = max(xi, xj)
if all(y != yi or x < xa or xb < x for k, (x, y, _, _, _) in enumerate(xs) if k != i and k != j):
ni.append(j)
nj.append(i)
_edges = {}
def edges(i, j, n):
k = (min(i, j), max(i, j))
_edges[k] = _edges.get(k, 0) + n
def is_fully_connected(edges, Z):
visited = set()
pending = {edges[0][0]}
while pending:
z = pending.pop()
if z not in visited:
visited.add(z)
for a, b in edges:
if a == z:
pending.add(b)
elif b == z:
pending.add(a)
return len(visited) == Z
def find_solution(xs, k):
if k == len(xs):
if all(a == b for (_, _, a, b, _) in xs):
graph = [k for k, v in _edges.items() if v > 0]
if is_fully_connected(graph, len(xs)):
print("== solution found ==")
for n in [(k, v) for k, v in _edges.items() if v > 0]:
print(n)
else:
pendingEdges = xs[k][2] - xs[k][3]
find_solution_distribute(xs, k, xs[k][4], 0, pendingEdges)
def find_solution_distribute(xs, k, v, j, n):
J = xs[v[j]]
if j == len(v) - 1:
if J[2] - J[3] >= n:
J[3] += n
xs[k][3] += n
edges(k, v[j], n)
find_solution(xs, k + 1)
J[3] -= n
xs[k][3] -= n
edges(k, v[j], -n)
else:
for t in range(min(n, J[2] - J[3]) + 1):
J[3] += t
xs[k][3] += t
edges(k, v[j], t)
find_solution_distribute(xs, k, v, j + 1, n - t)
J[3] -= t
xs[k][3] -= t
edges(k, v[j], -t)
find_pairs(xs)
find_solution(xs, 0)
# == solution found ==
# ((0, 5), 1)
# ((1, 2), 1)
# ((1, 6), 1)
# ((3, 4), 1)
# ((3, 9), 1)
# ((4, 11), 1)
# ((5, 6), 1)
# ((5, 12), 1)
# ((7, 10), 2)
# ((8, 9), 1)
# ((9, 13), 1)
# ((10, 11), 1)
# ((10, 15), 2)
# ((12, 13), 1)
# ((14, 15), 1)
# ((15, 16), 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment