Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
One line Drawing solution in Uncategorized category for One line Drawing by capback250
# migrated from python 2.7
from collections import defaultdict
from copy import deepcopy
class Graph(object):
def __init__(self, edges):
self.adjacent = defaultdict(list) # connections in graph
self.vertices = set() # vershini
for a in edges:
self.vertices.add(a[0:2])
self.vertices.add(a[2:4])
self.adjacent[a[0:2]].append(a[2:4])
self.adjacent[a[2:4]].append(a[0:2])
class CyclesFinder(object):
def __init__(self, graph, start, cords):
self.graph = graph
self.start = start
self.cords = cords
self.way = self.finder()
def finder(self):
queue = []
queue.append((self.graph, self.start, self.cords, []))
while queue:
graf, current, cors, path = queue.pop()
check = path + [current]
if self.validator(check):
return check
for nextHope in graf[current]:
copycords = deepcopy(cors)
copycords -= {current + nextHope}
copycords -= {nextHope + current}
cpath = deepcopy(path)
cpath.append(current)
queue.append((Graph(copycords).adjacent, nextHope, copycords, cpath))
return None
def validator(self, pretendent):
valid = deepcopy(self.cords)
for i in range(len(pretendent)-1):
valid -= {pretendent[i] + pretendent[i+1]}
valid -= {pretendent[i+1] + pretendent[i]}
if not valid and i == len(self.cords) - 1:
return True
return False
def draw(data):
d = defaultdict(set)
chet, nechet, nodes = [], [], []
for line in data:
nodes.append(line[:2])
nodes.append(line[2:])
for n in nodes:
d[n] = nodes.count(n)
[nechet.append(ind) if ind % 2 else chet.append(ind) for ind in list(d.values())]
if len(nechet) == 2 or not nechet:
initialState = Graph(data)
for node in initialState.vertices:
if CyclesFinder(initialState.adjacent, node, data).way:
return CyclesFinder(initialState.adjacent, node, data).way
return []
return []
March 2, 2016