# pixel fill - problem statement at the end
# I think this problem is from old gild.com
# essentially the problem boils down to one to find the
# number of the trees of black pixels in the graph
# an image is modelled as a graph
class Node(object):
"""
Representation of a Node in graph
"""
def __init__(self, value):
self.value = value
self.children =[]
def getValue(self):
return self.value
def __str__(self):
return str(self.value)
def__lt__(self, node):
return self.value < node.value
def __gt__(self, node):
return self.value > node.value
class Edge(object):
"""
Indicates an edge from a source node to end node
"""
def __init__(self,src, end):
self.src = src
self.end = end
def getSource(self):
return self.src
def getEnd(self):
return self.end
def __str__(self):
return str(self.src.getValue()) + ' -> ' +str(self.end.getValue())
class Graph(object):
"""
Implements a graph as a collection of nodes and edges
"""
def __init__(self):
self.nodes = {}
self.edges = []
def addEdge(self, edge = None):
assert type(edge) ==Edge
# make sure we have both source and end nodes in graph
assert self.hasNode(edge.getSource())
assertself.hasNode(edge.getEnd())
self.edges.append(edge)
# add end node as child of source node
self.addChild(edge.getSource(), edge.getEnd())
def addNode(self, node = None):
assert type(node) == Node
if notself.hasNode(node):
self.nodes[node] = []
def getNode(self, value):
for node, children inself.nodes.items():
if node.getValue() == value:
return node
raise ValueError('No node with value ' +str(value))
def getNodes(self):
"""
Returns the adjacency list of Graph
"""
returnself.nodes.keys()
def hasNode(self, node):
assert type(node) == Node
try:
n =self.getNode(node.getValue())
return True
except ValueError:
return False
def hasEdge(self,edge):
assert type(edge) == Edge
for e in self.edges:
if (e.getSource().getValue() ==edge.getSource().getValue() \
and e.getEnd().getValue() == edge.getEnd().getValue()) or \
(e.getSource().getValue()== edge.getEnd().getValue() \
and e.getEnd().getValue() == edge.getSource().getValue()):
return True
return False
def getChildren(self, node):
try:
returnself.nodes[self.getNode(node.getValue())]
except KeyError:
return []
def addChild(self, p, c):
assert type(p) == Node
assert type(c) == Node
n = self.getNode(p.getValue())
if c not inself.nodes[n]:
self.nodes[n].append(c)
def __str__(self):
print 'Nodes'
nodes =self.getNodes()
nodes.sort()
for node in nodes:
print node, 'Children: ',
for child inself.nodes[node]:
print child, ' ',
print ''
##
## print 'Edges'
## for edge inself.edges:
## print edge
return ''
def test():
a = Node(1)
b = Node(2)
c =Node(3)
g = Graph()
g.addNode(a)
g.addNode(b)
g.addNode(c)
g.addEdge(Edge(a, b))
g.addEdge(Edge(b, c))
g.addEdge(Edge(b, a))
print g
## assert g.hasEdge(Edge(b, a)) == True
## assertg.hasEdge(Edge(a,b)) == True
## assert g.hasEdge(Edge(c, b)) == True
def buildGraph():
r = 8
c = 6
## a=[[1,0,0,0,1],
## [1,0,1,0,0],
## [0,0,0,0,0],
## [0,0,0,0,0],
## [0,0,1,1,1],
## [0,0,1,0,0],
## [0,0,1,0,0]]
a = [[1,0,1,1,1,0],
[0,1,0,0,0,1],
[1,0,0,0,1,0],
[0,0,0,1,1,1],
[0,0,0,0,0,0],
[1,1,1,1,0,1],
[0,0,1,1,1,0],
[1,0,1,1,0,1]]
g = Graph()
for x in xrange(r):
for y in xrange(c):
if not a[x][y]:
p =Node(str(x) + str(y))
try:
g.addNode(p)
exceptAssertionError:
pass
# TEST - May not work
# Optimization to make the graph kind ofdirectional
# This cuts the space by half
# upper left diagonal
if x > 0 and y >0:
if not a[x-1][y-1] and not a[x][y]: # we have an edge
p = Node(str(x) + str(y))
q= Node(str(x-1) + str(y-1))
try:
g.addNode(p)
exceptAssertionError:
pass
try:
g.addNode(q)
except AssertionError:
pass
# add to graph
g.addEdge(Edge(p, q))
# top
if x > 0:
if not a[x-1][y] and not a[x][y]: # we have an edge
p= Node(str(x) + str(y))
q = Node(str(x-1) + str(y))
try:
g.addNode(p)
except AssertionError:
pass
try:
g.addNode(q)
except AssertionError:
pass
# add tograph
g.addEdge(Edge(p, q))
# upper right diagonal
if x > 0 and y if not a[x-1][y+1] and not a[x][y]: # we have an edge
p = Node(str(x) +str(y))
q = Node(str(x-1) + str(y+1))
try:
g.addNode(p)
exceptAssertionError:
pass
try:
g.addNode(q)
except AssertionError:
pass
# add to graph
g.addEdge(Edge(p, q))
# left
if y > 0:
if not a[x][y-1] and not a[x][y]: # we have an edge
p = Node(str(x) + str(y))
q = Node(str(x) + str(y-1))
try:
g.addNode(p)
except AssertionError:
pass
try:
g.addNode(q)
except AssertionError:
pass
# add tograph
g.addEdge(Edge(p, q))
# right
if y < c-1:
if not a[x][y+1] andnot a[x][y]: # we have an edge
p = Node(str(x) + str(y))
q = Node(str(x) +str(y+1))
try:
g.addNode(p)
exceptAssertionError:
pass
try:
g.addNode(q)
except AssertionError:
pass
# add to graph
g.addEdge(Edge(p, q))
# lower left diagonal
if x < r-1 and y > 0:
if not a[x+1][y-1] and not a[x][y]: # we have anedge
p = Node(str(x) + str(y))
q = Node(str(x+1) + str(y-1))
try:
g.addNode(p)
except AssertionError:
pass
try:
g.addNode(q)
except AssertionError:
pass
# add to graph
g.addEdge(Edge(p, q))
# bottom
if x if not a[x+1][y] and not a[x][y]: # we have an edge
p = Node(str(x) + str(y))
q= Node(str(x+1) + str(y))
try:
g.addNode(p)
exceptAssertionError:
pass
try:
g.addNode(q)
except AssertionError:
pass
# add to graph
g.addEdge(Edge(p, q))
# lower right diagonal
if x < r-1 and y < c-1:
if not a[x+1][y+1] and not a[x][y]: # we have anedge
p = Node(str(x) + str(y))
q = Node(str(x+1) + str(y+1))
try:
g.addNode(p)
except AssertionError:
pass
try:
g.addNode(q)
except AssertionError:
pass
# add to graph
g.addEdge(Edge(p, q))
return g
def printSet(s, n):
# sshould have its elements implementing __str__
print n, ':',
for e in s:
print e,
print ''
defdfs(count=0):
# build and test
g = buildGraph()
#print g
# unvisited nodes
unodes =g.getNodes()
# visited nodes
vnodes = {}
while True:
# Take the set difference btw unvisited and visitednodes
a = set(unodes)
#printSet(a, 'a')
b = set(vnodes.keys())
#printSet(b,'b')
c = a-b
#printSet(c, 'c')
l = list(c)
#l.sort()
if len(l) ==0:
break
count = count+1
# dfs stack
stack = [l[0]]
whileTrue:
if len(stack) == 0: break
# Always consult graph for the proper address of a node
x =g.getNode(stack.pop().getValue())
try:
if vnodes[x] == 1:
continue
except KeyError:
vnodes[x] = 1
for e in g.getChildren(x):
y =g.getNode(e.getValue())
if y not in vnodes.keys():
stack = stack + [y]
return count
printdfs()
# unit test
#test()
##
##During the day you work at a high flying design company but at nightyou
##troll the internet as a hacker. No one knows your dual identify and
##once in awhile a coworker will challenge you to solve a randomproblem.
##
##As you chat at lunch, a coworker mentions he found a large number of
##digital black and white photos. He then asks you how many clicks it
##would take to turn all these photos black by only using the pixel
##fill tool in your image manipulation program. The pixel fill tool is a
##neat feature as it can turn an area of black pixels into white pixels
##with just a click of a mouse.
##
##The hacker in you starts to think and you determine you can
##programmatically figure out the answer...
##
##For the sake of simplicity, a black and white image is a matrix composed of
##X * Y values.
##A 0 represents a black pixel and a 1 represents a white pixel.
##
##The following is a 7x5 image with some whites and some blacks pixel:
##
##10001
##10100
##00000
##00000
##00111
##00100
##00100
##
##With one click, the pixel fill tool turns each black pixel into a white
##one until there isn't a black pixel that can be reached from the
##previous pixel. A pixel is connected with another one in up to eight ways:
##north, south, east, west and the four diagonals.
##
##The image above can be filled of whites pixel with just two clicks:
##First click:
##
##11111
##11111
##11111
##11111
##11111
##11100
##11100
##
##Second click:
##
##11111
##11111
##11111
##11111
##11111
##11111
##11111
##
##Given a black and white image of dimension X * Y, can you determine how many
##clicks it would take to turn the whole image into a white one?
##
##Input specifications
##The input file starts with a two integers, H and W, separated by a whitespace
##The H and W are the height and the width of the image.
##The subsequent lines of the file is the image data:
##
##7 5
##10001
##10100
##00000
##00000
##00111
##00100
##00100
##
##Output specifications
##Your program should output the number,followed by a newline, of required
##clicks to transform the whole image into a white image.
##
##Sample output:
##
##2
November 26, 2012
pixel fill
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment