The Challenge

For a university computing project, we were tasked to write an algorithm in python that would fill a given polyomino region using only tetrominoes. The project would be marked based not only on accuracy but also time efficiency

6x6.png

My solution to a 6x6 target area with 100% accuracy running in 0.00038s.

SKILLS

Algorithm
Logic
Python

Harder and Harder...

15x15.png
15 x 15
Time = 0.00184s
Accuracy = 86.4%
100x100.png
100 x 100
Time = 0.125s
Accuracy = 89.0%
500x500.png
500 x 500
Time = 2.32s
Accuracy = 91.6%

The Algorithm

I designed a greedy algorithm, it uses only the immediate information around it to find local optimum solutions and joins these together. This is achieved by creating a tree of possible 4-step paths from a given root which is, in turn, traversed using depth-first search to find all possible shapes. Each node is assigned with a value based on how many neighbours it has, and the shape with the least total neighbours is selected and placed. The neighbourhood matrix is updated and the algorithm repeats this process until it runs out of shapes.

dfs.png

Example of my DFS algorithm starting from root node A

The Implementation

Going from a conceptual algorithm to a written and working python code was a big challenge. My largest function, FindShape is shown below. Starting from a root node, it searches in all 4 directions and appends the neighbourhood values to a list called RLUD (in order right, left, up, down). It then moves to the node with the lowest non-zero value (in this case left) and updates the searcher coordinates (x=-1), the movement_log is also updated to store the path to allow backtracking. The shape coordinates are updated, and this process continues until 4 coordinated are found and a Tetris piece is formed. 

dfs2.png

FindShape deciding to move the the left node.

The Results

Tetriling Reassembly Report-page-004.jpg

My Algorithm was one of the fastest in the class, earning me an A grade for this project. Below you can see my time and accuracy performance across varying target sizes and densities. One interesting correlation was that as size increases, accuracy also increases (as seen on the graph below) which is unexpected. The occurred due to my 'Booster' function that essentially cleans up any shapes missed from find shape and uses a brute force method which is very time inefficient. This function is far more effective if there are more available shapes. 

FindShape deciding to move the the left node.

Tetriling Reassembly Report-page-0042.jp

The relationship between size and accuracy. different colours represtn different densities

Continue Exploring...