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.
My solution to a 6x6 target area with 100% accuracy running in 0.00038s.
SKILLS
Harder and Harder...
15 x 15
Time = 0.00184s
Accuracy = 86.4%
100 x 100
Time = 0.125s
Accuracy = 89.0%
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.
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.
FindShape deciding to move the the left node.
The Results
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.
The relationship between size and accuracy. different colours represtn different densities
Continue Exploring...
