Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Step by Step solution in Speedy category for The Square Chest by Renelvon
def checkio(edges):
# Assume graph is N x N mesh with E edges
# Total Complexity: O(E * N) + set building time
N = 4
# Phase 0: Partition edges into horizontal and vertical.
# Set them pointing from left to right and from top to bottom
# Complexity: Theta(E)
sedges = set(map(lambda e: tuple(sorted(e)), edges))
horizontal = set(filter(lambda e: e[1] == e[0] + 1, sedges))
vertical = sedges - horizontal
# Phase 1: Detect horizontal and vertical segments of length <= N
# Complexity: O(number_of_segments) <= O(E * N)
horiz_segs, vert_segs = set(), set()
for (start, end) in horizontal:
for l in range(N + 1):
if (start + l, end + l) in horizontal:
horiz_segs.add((start, l + 1))
else:
break
for (start, end) in vertical:
for l in range(N + 1):
if (start + N*l, end + N*l) in vertical:
vert_segs.add((start, l + 1))
else:
break
# Phase 2: Detect L-shaped segments
# __
# | -> Lup | -> Ldown
# | |__
#
# Complexity: O(number_of_segments) <= O(E * N)
Lup, Ldown = set(), set()
for (start, l) in horiz_segs:
if (start + l, l) in vert_segs:
Lup.add((start, l))
if (start - N*l, l) in vert_segs:
Ldown.add((start - N*l, l))
# Phase 3: Return the number of matched L-shaped segment pairs.
# Complexity: O(number_of_L-shapes) <= O(E * N)
return sum(s in Ldown for s in Lup)
May 19, 2014
Comments:
