Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- Anthony Theocharis' Example Solution to Floor Tiling
- """
- import numpy
- class Floor(object):
- def __init__(self, width, height):
- self.width = int(width)
- self.height = int(height)
- class TileSize(object):
- def __init__(self, width, height):
- self.width = int(width)
- self.height = int(height)
- def can_be_tiled(floor, tile_sizes):
- """
- Given a floor of a size (N, M) [width, height] and a list of tile sizes,
- each with a unique width/height, determine if it is possible to cover the
- entire floor using some inter number of each type of tile.
- This implementation assumes that the tiles can be rotated.
- Approach:
- M = floor.height
- N = floor.width
- Any section is tileable if it can be broken into two subsections that
- are themselves tileable. For each subsection size (i,j) determine if it
- is tileable by finding two subsections that are tileable. Store the
- results in the array R, and build R up from (0, 0) to (N, M).
- A classic bottom-up dynamic programming / divide and conquer approach.
- Complexity:
- O(N * M) memory
- O(N * M * max(N, M)) steps
- """
- # Store a byte-array representing the tile-ability of all sub-section sizes
- # (really just needs to be a bit array, but that's hard in python)
- R = numpy.zeros((floor.width+1, floor.height+1), dtype=numpy.int8)
- # Any section with width=0 or height=0 is already 'tiled'
- R[:,0] = 1
- R[0,:] = 1
- # Any section that is identical to a single tile is tileable by definition
- for t in tile_sizes:
- if t.width <= floor.width and t.height <= floor.height:
- R[t.width][t.height] = 1
- if t.height <= floor.width and t.width <= floor.height:
- R[t.height][t.width] = 1
- # Syntax Note:
- # "for X in range(Y, Z+1):" is equivalent to
- # "for (int X=Y; X<=Z; X++)" in C style languates.
- # For each size of floor (i, j), determine if it's tileable.
- for i in range(1, floor.width+1):
- for j in range(1, floor.height+1):
- # Try to find a horizontal split such that each section is tileable
- if R[i][j] == 0:
- for a in range(0, (i/2)+1):
- if R[a][j] == R[i-a][j] == 1:
- R[i][j] = 1
- break
- # Try to find a vertical split such that each section is tileable
- if R[i][j] == 0:
- for a in range(0, (j/2)+1):
- if R[i][a] == R[i][j-a] == 1:
- R[i][j] = 1
- break
- # Mark the rotation of this section as tileable, if appropriate
- if R[i][j] == 1 and i <= floor.height and j <= floor.width:
- R[j][i] = 1
- if R[floor.width][floor.height] == 1:
- return 'yes'
- else:
- return 'no'
- if __name__ == '__main__':
- print can_be_tiled(
- Floor(5, 7),
- [
- TileSize(2, 3),
- TileSize(3, 3),
- TileSize(2, 4),
- TileSize(5, 5),
- ]
- )
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement