Changeset 793

Timestamp:

07/20/10 22:33:48 (7 weeks ago)

Author:

hodgestar

Message:

Add level validation using networkx.

Files:

• confluence/randombubble.py (modified) (2 diffs)

confluence/randombubble.py

@@ -1 +1 @@
 #!/usr/bin/python
 
+import warnings
+warnings.simplefilter("ignore", DeprecationWarning)
+
 import random
+from networkx import Graph, connected_components, draw
 
 class Ball(object):
@@ -52 +56 @@
 
     def valid(self):
-        # THIS IS HARD. D:
-        return True
+        g = Graph()
+
+        def add_edge(b1, b2):
+            if b1.ball is not None and b2.ball is not None:
+                g.add_edge(b1, b2)
+
+        # add all balls and horizontal edges
+        for row in self.rows:
+            for ball in row.balls:
+                if ball.ball is not None:
+                    g.add_node(ball)
+            for b1, b2 in zip(row.balls[:-1], row.balls[1:]):
+                add_edge(b1, b2)
+
+        # add inter-row connections
+        for row, above, below in zip(self.rows[1::2], self.rows[::2], self.rows[2::2] + [BlankRow(0)]):
+            for ball, above_left, above_right, below_left, below_right in zip(row.balls, above.balls[:-1], above.balls[1:], below.balls[:-1], below.balls[1:]):
+                add_edge(ball, above_left)
+                add_edge(ball, above_right)
+                add_edge(ball, below_left)
+                add_edge(ball, below_right)
+
+        top_row = set(self.rows[0].balls)
+        valid = True
+        for comp in connected_components(g):
+            if set(comp).isdisjoint(top_row):
+                valid = False
+                break
+
+        return valid
 
     def __str__(self):