summaryrefslogtreecommitdiff
path: root/25_2023.py
diff options
context:
space:
mode:
Diffstat (limited to '25_2023.py')
-rw-r--r--25_2023.py31
1 files changed, 31 insertions, 0 deletions
diff --git a/25_2023.py b/25_2023.py
new file mode 100644
index 0000000..0b44a86
--- /dev/null
+++ b/25_2023.py
@@ -0,0 +1,31 @@
+import sys
+import re
+from copy import deepcopy
+import math
+from collections import defaultdict, Counter, deque
+import networkx as nx
+import heapq
+
+D = open(sys.argv[1]).read().strip()
+L = D.split("\n")
+G = [[c for c in row] for row in L]
+R = len(G)
+C = len(G[0])
+E = defaultdict(set)
+for line in L:
+ s, e = line.split(":")
+ for y in e.split():
+ E[s].add(y)
+ E[y].add(s)
+n = len(E)
+G = nx.DiGraph()
+for k, vs in E.items():
+ for v in vs:
+ G.add_edge(k, v, capacity=1.0)
+ G.add_edge(v, k, capacity=1.0)
+for x in [list(E.keys())[0]]:
+ for y in E.keys():
+ if x != y:
+ cut_val, (L, R) = nx.minimum_cut(G, x, y)
+ if cut_val == 3:
+ print(len(L) * len(R))