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 andrea.manno1
def next_step(segments,path,point,points):
"""Look for a way to complete the path starting from a given point"""
if len(segments) == 0:
return path + (point,)
else:
for segment in points[point]:
if segment in segments:
for point0, point1 in ((segment[:2], segment[2:]), (segment[2:], segment[:2])):
if point0 == point:
whole_path = next_step(segments-{segment}, path+(point0,), point1, points)
if whole_path is not None:
return whole_path
def draw(segments):
points, odd_points = dict(), list()
#odd points: points having an odd number of segments.
for segment in segments:
for point in (segment[:2], segment[2:]):
if point not in points:
points[point] = []
points[point].append(segment)
for point in points:
if len(points[point])%2 != 0:
odd_points.append(point)
#My reasoning: only figures with at most two odd points can be drawn
#because every line entering a given point, except the starting
#and the ending points, must exit as well.
if len(odd_points) > 2:
return []
# if the figure has two odd points, one must be the starting one, and the other
# the ending one. If it only has even points, any point can be both start and end.
point = next(iter(points.keys())) if len(odd_points) == 0 else odd_points.pop()
path=next_step(set(segments), tuple(), point, points)
if path is not None:
return path
return []
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"
Dec. 27, 2014