Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS revised solution in Clear category for One line Drawing by Sim0000
def draw(segments):
# recursive search
def search(last, route, seg):
if not seg: return route
for edge in seg:
v0, v1 = (edge[0], edge[1]), (edge[2], edge[3])
if last in (v0, v1):
v = v1 if last == v0 else v0
rc = search(v, route + [v], seg - {edge})
if rc: return rc
return []
# find start point
vertex = [(e[0], e[1]) for e in segments] + [(e[2],e[3]) for e in segments]
oddlist = [v for v in set(vertex) if vertex.count(v) % 2 == 1]
# search route
if len(oddlist) == 0: # no odd degree vertex, any vertex can be start point
return search(vertex[0], [vertex[0]], segments);
if len(oddlist) == 2: # there is two odd degree vertex
return search(oddlist[0], [oddlist[0]], segments);
return []
# revised version. first version has some bugs and removed by recheck.
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"
Aug. 14, 2014
Comments: