Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for One line Drawing by jcg
#one-line-drawing
# the problem has solutions iff :
# - all the nodes are connected
# - all nodes have an even number of adjacent nodes (the path will be a cycle starting and ending on any node)
# or
# exactly two nodes have an odd number of adjacent nodes (the path will start and end on these nodes)
# Récréations mathématiques (2ème éd.), Édouard Lucas, A. Blanchard (Paris), 1891
def setOfConnectedNodes(myNode, myGraph, visited=None):
# returns the set of nodes connected with myNode (including myNode) in myGraph
# myNode + connected(x, myGraph, visited) for each not visited x adjacent to myNode
if visited == None: # first call
visited = {myNode}
else:
visited.add(myNode)
for node in setOfAdjacentNodes(myNode, myGraph):
if node not in visited:
visited = setOfConnectedNodes(node, myGraph, visited)
return visited
def setOfVertices(edge):
return {(edge[0], edge[1]), (edge[2], edge[3])}
def setOfAdjacentNodes(myNode, myGraph):
# returns the set of adjacent vertices of myNode in myGraph
adjacentNodes = set()
for edge in setOfEdges(myNode, myGraph):
adjacentNodes |= setOfVertices(edge)
adjacentNodes -= {myNode}
return adjacentNodes
def setOfEdges(myNode, myGraph):
# returns the set of edges starting or ending in myNode in myGraph
edges = set()
for edge in myGraph:
vertices = setOfVertices(edge)
if myNode in vertices:
edges.add(edge)
return edges
def setOfNodes(myGraph):
return set(node for edge in myGraph for node in setOfVertices(edge))
def anyElement(mySet):
return next(iter(mySet))
def otherVertice(myVertice, myEdge):
return anyElement(setOfVertices(myEdge)-{myVertice})
def getOneEdge(myGraph):
return anyElement(myGraph)
def getOneVertice(myEdge):
return anyElement(setOfVertices(myEdge))
def getOneNode(myGraph):
return anyElement(setOfNodes(myGraph))
def isConnex(myGraph):
oneEdge = getOneEdge(myGraph)
oneNode = getOneVertice(oneEdge)
return setOfConnectedNodes(oneNode, myGraph) == setOfNodes(myGraph)
def computePath(myGraph):
if not isConnex(myGraph):
return []
oddNodes = {node for node in setOfNodes(myGraph) if len(setOfAdjacentNodes(node, myGraph)) % 2 == 1}
if len(oddNodes)>2:
return []
elif len(oddNodes)==2:
start = anyElement(oddNodes)
else :
start = getOneNode(myGraph)
path = [start]
auxGraph = myGraph.copy()
node = start
while auxGraph:
s = setOfEdges(node, auxGraph)
for edge in s:
if len(s) == 1 or isConnex(auxGraph-{edge}):
auxGraph.discard(edge)
node = otherVertice(node, edge)
path.append(node)
break
return path
draw = computePath
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
def checker(func, in_data, is_possible=True):
user_result = func(in_data)
if not is_possible:
if user_result:
print("How did you draw this?")
return False
else:
return True
if len(user_result) < 2:
print("More points please.")
return False
data = list(in_data)
for i in range(len(user_result) - 1):
f, s = user_result[i], user_result[i + 1]
if (f + s) in data:
data.remove(f + s)
elif (s + f) in data:
data.remove(s + f)
else:
print("The wrong segment {}.".format(f + s))
return False
if data:
print("You forgot about {}.".format(data[0]))
return False
return True
assert checker(draw,
{(1, 2, 1, 5), (1, 2, 7, 2), (1, 5, 4, 7), (4, 7, 7, 5)}), "Example 1"
assert checker(draw,
{(1, 2, 1, 5), (1, 2, 7, 2), (1, 5, 4, 7),
(4, 7, 7, 5), (7, 5, 7, 2), (1, 5, 7, 2), (7, 5, 1, 2)},
False), "Example 2"
assert checker(draw,
{(1, 2, 1, 5), (1, 2, 7, 2), (1, 5, 4, 7), (4, 7, 7, 5),
(7, 5, 7, 2), (1, 5, 7, 2), (7, 5, 1, 2), (1, 5, 7, 5)}), "Example 3"
Oct. 3, 2014