<
Back home
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
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
Work
Alchemilka
A colourful pharmacy
The Mouse
Hardware / software game
Lend a Hand
Crowd sourcing electricity
C!ean
Sustainable laundry detergent
Kelvin
Hand-powered hand warmer
Crash Defender
Smart football shoe
Yulife app
Atomic UI design system
Driver Interface
In an autonomous vehicle
See all projects...
See all projects...