Great first question!
I've been taking a crack at helping to reduce the runtime for this. So far, I seem to have been somewhat successful. (I'm averaging a 21% increase in performance)
Here are the changes I've made so far:
1.) Pre-sorting the expansions
By pre-sorting the expansions using a heap, we are making subsequent calls to canonical and it's use of sorted more efficient. This was the most noticeable performance increase. I chose a heap because it's a good option for sorting when appending to an empty list, which you are doing in possible_expansions with the expansions list. This is because heaps have an insertion time complexity of O(log n), which is very good.
Your code:
# Inside of `possible_expansions`
for p in positions:
if p not in piece_set:
expansions.append(piece + [p])
# Inside of `expand_pieces`
for piece in pieces:
for e in possible_expansions(piece):
exp = canonical(e)
My change:
# Inside of `possible_expansions`
for p in positions:
if p not in piece_set:
heappush(expansions, piece + [p])
# Inside of `expand_pieces`
exps = possible_expansions(piece)
for _ in range(len(exps)): # Use _ to show that we aren't using the loop var
e = heappop(exps)
exp = canonical(e)
2.) Reducing loop copies
Originally, canonical effectively re-uses the same list comprehension for getting min_x and min_y:
def canonical(piece):
min_x = min(x for (x, y) in piece)
min_y = min(y for (x, y) in piece)
res = sorted((x - min_x, y - min_y) for (x, y) in piece)
return res
By using a for loop instead of a list comprehension, we can more readably convert this into a single loop, reducing iterations by 50%:
def canonical(piece):
min_x = float('inf')
min_y = min_x
for (x, y) in piece:
if x < min_x:
min_x = x
if y < min_y:
min_y = y
res = sorted((x - min_x, y - min_y) for (x, y) in piece)
return res
Since we got rid of the calls to min, we must keep track of the current minimums for x and y ourselves, and because this code could eventually reach extremely high numbers for x and y, we can set min_x and min_y to float('inf').
2.5) One more loop removal
On line 52 inside of expand_pieces you check if the current piece, exp, contains an x or y greater than or equal to8:
if (max(x for (x, y) in exp) >= 8) or (max(y for (x, y) in exp) >= 8):
We can remove one list comprehension, and replace max in the other with any, further reducing total iterations:
if any([(x > 7 or y > 7) for (x, y) in exp]):
I made another simplification by changing >= 8 to > 7, but this is more of a preference than anything.
3.) Preventing re-initialization of constant variables
neighbor_offsets never changes but is initialized every time possible_expansions is called. You can move the declaration and initialization of neighbor_offsets to the global scope, just above the definition of possible_expansions.
I will edit this if I find anything else!