Project Info

The challenge was to make a Python algorithm to find the most accurate solution to a target pattern of tetrominoes as quickly as possible.

Completion date

2018

To begin with, I’ve drawn out the target grid and tried to fill it with tetrominoes manually, on paper. By doing so I identified the possible approaches to solving the problem. I then identified the steps I took to achieve the solution and translated them first into pseudo code and then into Python code.

The code was then tested on target matrices of varying sizes from 10x10 up to 1000x1000 and densities from 0.2 to 0.8. Iterations to previously written code were highlighted alongside with dates of the edit for future reference and easier debugging.

Weighting

Firstly, a new matrix is created with the number of neighbours of a tile as the value of that tile. The code is scanned row by row and each neighbours of each coordinate are checked. The neighbour value is then added to a variable. After this, the coordinates with zeros in the target are reset to zeros in the weighted matrix. This is done to prevent placement of shapes onto empty tiles. The weighted matrix is then padded with three rows of zeroes to prevent Index errors when placing shapes and calculating weighting.

Tetriling Shape

Representation In Code

Representation In Code

The shapes are defined as a list with a shape number, shape type number and a list of its co- ordinates. There is 19 shape types and 47 shape numbers. This is because one shapes is defined from more origins, making it possible to be identified when any tile of the shape is checked first.

Problem Representation In The Form Of a Tree

The shapes are defined in a multiway tree to reduce the number of checks needed to find whether a shape fits into a position. Implementing a tree reduced the number of checks from 19 when going through all the shapes one by one to a maximum of 6 checks. The root node is 0,0 - the origin. It has 4 children, [0,1], [1,0], [0,-1] [-1,0] so that shapes can be checked in all directions from the origin.

Placing Shapes

Weighting of each of the shapes is calculated - by summing the weightings of the tile values on which it would be placed. The weightings are then sorted from lowest to highest and stored in a two dimensional list.

Depth First Tree Traversal Using Recursion

The algorithm starts by scanning the weighted and padded matrix for tiles with weighting of one. This essentially allows the algorithm start from the edge as a tile with a weighting of one has only one neigbour and is protruding from its connected component. When a tile with weighting of one is found, recursion and depth first search is used to traverse down the tree and output a list of shape numbers of shapes that would fit if placed from the origin that is being currently checked. If there is no tile placed at a coordinate defined in a node of the tree, the whole subtree of that node is removed. Weighting of each of the shapes is calculated - by summing the weightings of the tile values on which it would be placed. The weightings are then sorted from lowest to highest and stored in a two dimensional list.

Runtimes and Accuracy

All of the functions used in the algorithm are linear with respect to the area of the target grid. The overall running time of the algorithm is estimated to be O(n), where n is the area of the target matrix.

The accuracy of the algorithm ranges from 93% for smaller targets to 98% for larger sized targets.

Algorithm Diagram

1. weighted_matrix = weighting of target

2. padding the waighted matrix with 3 rows and columns of zeros

3. Loop 1:

for coordinates in weighted_matrix:

if [y,x] == 1:

fitting shapes = traverse the shape tree

calculate weighting of fitting shapes

sort fitting shapes according to their weighting

Loop 1.1

iterate through sorted fitting shapes:

if shape with lowest weighting is available:

place shape with lowest weighting

zero out its coordinates

lower weigting of neighbouring shapes

break

else: run Loop 1.1 again, try for 2nd lower weighting

4. if there is a one in weighted_matrix and hasn’t run 5 times:

Loop 1

else:

5. Loop 2:

for coordinates in weighted_matrix:

fitting shapes = traverse the shape tree

calculate weighting of fitting shapes

sort fitting shapes according to their weighting

Loop 2.1

iterate through sorted fitting shapes

if shape with lowest weighting is available:

place shape with lowest weighting

zero out its coordinates

lower weigting of neighbouring shapes

break

else: run Loop 2.1 again, try for 2nd lower weighting

2. padding the waighted matrix with 3 rows and columns of zeros

3. Loop 1:

for coordinates in weighted_matrix:

if [y,x] == 1:

fitting shapes = traverse the shape tree

calculate weighting of fitting shapes

sort fitting shapes according to their weighting

Loop 1.1

iterate through sorted fitting shapes:

if shape with lowest weighting is available:

place shape with lowest weighting

zero out its coordinates

lower weigting of neighbouring shapes

break

else: run Loop 1.1 again, try for 2nd lower weighting

4. if there is a one in weighted_matrix and hasn’t run 5 times:

Loop 1

else:

5. Loop 2:

for coordinates in weighted_matrix:

fitting shapes = traverse the shape tree

calculate weighting of fitting shapes

sort fitting shapes according to their weighting

Loop 2.1

iterate through sorted fitting shapes

if shape with lowest weighting is available:

place shape with lowest weighting

zero out its coordinates

lower weigting of neighbouring shapes

break

else: run Loop 2.1 again, try for 2nd lower weighting