Skip to content

Instantly share code, notes, and snippets.

@chrisc24
Created April 24, 2012 13:57
Show Gist options
  • Save chrisc24/2479853 to your computer and use it in GitHub Desktop.
Save chrisc24/2479853 to your computer and use it in GitHub Desktop.
Find the Island From Edges
edges = [( 0,22),( 0,39),( 0,47),( 1, 5),( 2,38),( 2,39),( 2,44),( 4,23),( 4,33),
( 5,19),( 6,17),( 6,35),( 6,45),( 7,49),( 8,24),( 8,40),( 9,25),( 7,10),
(10,11),(10,21),(11,30),(12,32),(13,27),(14,33),(14,36),(15,49),(16,48),
(18,37),(18,45),(19,24),(19,40),(20,39),(21,34),(25,36),(26,27),(26,31),
(26,32),(28,48),(29,36),(29,41),(35,43),(38,42),(39,44),(43,46),(48,49)]
class PointCollection:
members = set([])
masterDictionary = {}
distinctList = []
def __init__(self, x, y, dictionaryIn, listIn):
self.distinctList = listIn
self.distinctList.append(self)
self.masterDictionary = dictionaryIn
self.addElements(x, y)
def mergeWithOther(self, other):
if other != self:
for member in other.members:
self.masterDictionary[member] = self
self.members = self.members | other.members
distinctList.remove(other)
def addElements(self, x, y):
self.members = self.members | set([x, y])
self.masterDictionary[x] = self
self.masterDictionary[y] = self
def compare(self, other):
return (self.members >= other.members and other.members >= self.members)
edgeDictionary = {}
distinctList = []
for edgeTuple in edges:
if edgeTuple[0] in edgeDictionary.keys() and edgeTuple[1] in edgeDictionary.keys():
edgeDictionary[edgeTuple[0]].mergeWithOther(edgeDictionary[edgeTuple[1]])
elif edgeTuple[0] in edgeDictionary.keys():
edgeDictionary[edgeTuple[0]].addElements(edgeTuple[0], edgeTuple[1])
elif edgeTuple[1] in edgeDictionary.keys():
edgeDictionary[edgeTuple[1]].addElements(edgeTuple[0], edgeTuple[1])
else:
PointCollection(edgeTuple[0], edgeTuple[1], edgeDictionary, distinctList)
for point in range(0, 49):
if not point in edgeDictionary.keys():
PointCollection(point, point, edgeDictionary, distinctList)
for value in distinctList:
print(value.members)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment