Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Speedy category for One line Drawing by _Chico_
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 []
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"
May 10, 2021
