Skip to content

Instantly share code, notes, and snippets.

@fmayer
Created February 14, 2013 16:45
Show Gist options
  • Save fmayer/4954141 to your computer and use it in GitHub Desktop.
Save fmayer/4954141 to your computer and use it in GitHub Desktop.
class Mine(object):
def __init__(self, id_, x, y, r):
self.neighbours = set()
self.id_ = id_
self.x = x
self.y = y
self.r = r
self.dead = False
def find_neighbours(self, mines):
for mine in mines:
if mine is self:
continue
if (self.x - mine.x)**2 + (self.y - mine.y)**2 <= self.r**2:
self.neighbours.add(mine)
def merge(self, mines):
if self.dead:
return
c = False
neighbours = set(self.neighbours)
for neigh in self.neighbours:
if self in neigh.neighbours:
neighbours |= neigh.neighbours
mines.replace(neigh, self)
neighbours.remove(neigh)
c = True
if self in neighbours:
neighbours.remove(self)
self.neighbours = neighbours
return c
class Minefield(object):
def __init__(self, mines):
self.mines = mines
def __iter__(self):
return iter(self.mines)
def replace(self, one, other):
self.mines.remove(one)
# self.mines.append(other)
for mine in mines:
if mine is other:
continue
if one in mine.neighbours:
mine.neighbours.remove(one)
mine.neighbours.add(other)
one.dead = True
def loaddata(fname):
mines = []
with open(fname) as fd:
fd.next()
for id_, line in enumerate(fd):
x, y, r = map(int, line.strip().split(" "))
mines.append(Mine(id_, x, y, r))
return Minefield(mines)
if __name__ == "__main__":
mines = loaddata("Downloads/PROBLEMSET/input/B/8.in")
for mine in mines:
mine.find_neighbours(mines)
while any(d.merge(mines) for d in mines):
pass
for mine in mines:
for mine2 in mines:
if mine in mine2.neighbours:
break
else:
print mine.id_
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment