It's possible that @lru_cache could help speed this up in nearly its current form, if we're passing around immutable (hashable!) tuples instead of lists.
You can write five I's, or five L'sL values, into thefive cells of board.
You can write five I's, or five L's, into the board.
It's possible that @lru_cache could help speed this up in nearly its current form, if we're passing around immutable (hashable!) tuples instead of lists.
You can write five I's, or five L values, into five cells of board.
Kudos on tackling such an interesting problem!
design of Public API
print(solve(5, 12, {'F': [[0, 0], [1, 0], [1, -1], [1, 1], [2, 1]],
'W': ... }))
On the one hand, I like the simplicity of representation,
and the very helpful use of standard pentomino names.
On the other hand, I think I'd prefer to see a level of indirection here.
And [x, y] coord lists should definitely become (x, y) tuples.
(Also, trivially, W ×ばつ H might become a size tuple, whatever.)
pentominos = {
'F': [(0, 0), (1, 0), (1, -1), (1, 1), (2, 1)],
'W': ...
}
print(solve((5, 12), 'FWVXNPUZIYTL', pentominos)
or perhaps
print(solve((5, 12), 'FILNPTUVWXYZ', pentominos)
tuple over list
A slightly odd thing about python culture is that choice of Sequence matters. Some concepts are a good semantic fit for a tuple, others for a list, as James Tauber explains.
Think of an (x, y) Point as a C struct or a python tuple.
Or consider an invoice spreadsheet showing the sale
of half a dozen widgets, with columns part_number,
quantity, extended_price.
Each row is a 3-tuple.
And then we have half a dozen list entries,
each of them being a 3-tuple.
With tuples position matters, it changes the meaning of the item. In contrast, a list is a bunch of "same thing", so the initial item and the final one have similar semantics.
Recommend you prefer (x, y) tuples in this code base, rather than the [x, y] lists that are currently implemented.
unit tests
This submission tackles a challenging geometry problem.
Yet it includes no automated unit or integration tests. Which makes me sad. And complicates the life of maintainers, or benchmarkers.
nested functions
The following functions impress me as being "hard to test":
def is_valid_placement(piece, x, y): ...
def place_piece(piece, x, y, char): ...
def remove_piece(piece, x, y): ...
def find_smallest_area(): ...
def bfs(start_x, start_y): ...
def rotateR(piece_coords): ...
def rotateH(piece_coords): ...
def backtrack(piece_index): ...
def try_place(x, y, piece_coords, placed_pieces, piece_index): ...
Why? Because they are nested. Sometimes even doubly-nested!
Occasionally nesting can be helpful, when functions should share the same namespace, should have overlapping access to same variables. My standard advice on nesting is simple: Don't. Usually it's not helpful. (I confess this is the very first time I have ever seen someone use double nesting for purposes other than asking whether the interpreter supports arbitrary nesting.)
Here, we are using some very well thought out nesting to organize the code. But it thwarts the efforts of any maintainer who wants to write a simple unit test or wants to produce benchmark timings of two competing implementations, even something as simple as the use of @njit decorator.
Prefer to use modules or classes to
organize the code.
Alternatively, each of these functions
might appear at top-level, just like solve.
Use an _ underscore prefix to suggest that
a _private helper is not part of the Public API
that you're exporting.
I feel it would make sense to introduce class Solver:
which knows about a collection of class Pentomino: shapes.
lint
def rotateR( ... ): ...
def rotateH( ... ): ...
Pep-8
asks that you name these rotate_r and rotate_h.
And then I ask that you spell these out more fully. At first I thought left / right, cw / ccw (or anti-clockwise for my British friends), links / rechts, gauche / droit, but wasn't finding a match. The OP context suggested your native tongue might possibly be Polish, but lewy / prawidłowy doesn't work, and clockwise had too many Z's and W's for a match.
The (y, -x) and (-x, y) transforms suggest that we are Flipping about a mirror axis, rather than Rotating a shape within the plane. Recommend that you choose more informative function names, or at least add a """docstring""" to each one.
The lambdas appear to be superfluous, as each sequence would work on its own.
tuple unpack
This code base makes extensive use of [0] subscript
to denote x and [1] subscript to denote y.
Prefer to express this as x, y = coords.
Or, much better, define a class:
from collections import namedtuple
Point = namedtuple('Point', 'x y')
rotations
def sort_pieces_by_length(piece_dict):
sorted_pieces = dict(sorted(piece_dict.items(),
key=lambda item: len(item[1]), reverse=True))
I don't understand this function. In two ways.
It's unclear whether "length" should match "width" or "height".
(The [1] subscript tells me "height", but the relationship
isn't obvious to me.)
It's unclear why this is even helpful.
We alternatively might define max_length
as the maximum of a piece's width or height,
and then "sort by max_length", in an effort
to make "hard to fit" pieces bubble up toward the front.
Maybe "height" is special because of how we iterate over shapes,
doing x and y in a certain order?
Maybe it's special because pentominos are conventionally defined
to be "tall", or "squat"?
Maybe there's something else going on here?
Dealing with symmetry is fundamental to solving pentomino-style problems. This codebase should include ReadMe.md or docstrings that describe the approach taken. The L pentomino, for example, has four rotations and then the flipped form has four rotations. It might be worth hanging on to all eight copies, recording them as all part of the same equivalence class, and trying to fit them into the evolving puzzle.
use builtins
def piece_already_placed(new_piece, pieces):
for piece in pieces:
if are_pieces_same(new_piece, piece):
return True
return False
This is:
def piece_already_placed(new_piece, pieces):
return any(are_pieces_same(new_piece, piece))
use array for speed
board = [['' for _ in range(width)] for _ in range(height)]
Lists are nice, but they involve a lot of object pointers. Prefer a python array, or perhaps a numpy ndarray.
A byte array, without all those object pointers, will be smaller and more cache friendly.
If you go the numpy route you will be able to use fast vectorized
operations for adding a piece shape to the board,
for testing whether a proposed placement caused overlap,
and other useful primitives.
define a class
Uggh! Put this within class Solver:, please.
def backtrack( ... ):
nonlocal result, counter
counter += 1
if ... :
result.append( ... )
The declaration for result appears to be spurious.
(While the one for counter is essential.)
The lookup should succeed even without a declaration,
and then we mutate that object, which is quite
different from assigning a new value to counter.
This code appears to be trickier than necessary.
Prefer references to self.counter and self.result.
sameness
def are_pieces_same(piece1, piece2):
# Calculate the biases on x and y axes
piece1 = [coord.copy() for coord in piece1]
piece2 = [coord.copy() for coord in piece2]
for coord1, coord2 in zip(piece1, piece2): # move to the positive quadrant
coord1[0] += 10 ...
Thank you for that helpful comment about the magic number 10 -- we're
just translating to the positive quadrant, and a pentomino's size
will never exceed 5.
The # Calculate ... comment could have been a """docstring""".
Except that it wouldn't be a very informative docstring.
So I'm left with the (very nice!) function name to explain this function's
responsibility.
It leaves me with some questions about what "same" means.
Same w.r.t. translation? rotation? mirror-flipping?
During placement we did some of those transforms. And now it seems we have to undo them to recover the identity of the piece. It makes me sad that we lost track of its identity during placement.
Consider pre-rotating and pre-flipping all pieces at the outset. The "I" pentomino, for example, is quite boring so it will expand to fewer entries than "L" will.
You can write five I's, or five L's, into the board.
You may find it helpful to attach a summary bbox,
a width ×ばつ height bounding box, to each piece variant,
so e.g. a vertical "I" or a horizontal "I" can be
quickly ruled out from certain proposed solutions.
This code appears to achieve a subset of its design goals. Speedup is the principle aim of future development. Changes to how we represent pieces, and the board, hold some promise for that.
There are no automated tests in this submission, and substantial changes would be needed in order to introduce them.
I would not be willing to delegate or accept maintenance tasks on this codebase.