Overview
Date
December 2019 - January 2020
Skills
Python
Software
Visual Studio Code, Thonny
'The Tetrimino solution I came up with, was able to find an accurate and fast solution to a randomly generated pattern of tetriminoes. It took a matrix of unsolved pieces, and categorised it into 17 different pieces and selected the optimum piece for the solution, so that no block were left unmatched.'
Summary
The algorithm that I had implemented, had an average accuracy of 95% for target surfaces of up to 1000 by 1000 in under 8 seconds. I was placed in the Top 30 for the fastest codes.
Methodology
The code works by using a ranked greedy system, which starts in the top left corner and finishes in the bottom right corner. It uses several different functions:
1) WEIGHT - Creates a matrix with its score being the number of neighbours
2) VALIDITY - Checks if the piece is valid and scores each of the pieces
3) UPDATE - Takes the best piece coordinates and edits matrix around it
4) MOVING - Allows the function to progress through the matrix
5) LAST CHECK - Fills in remaining unsolved values
6) TETRIS - Called in the performance file
Code breakdown
WEIGHT
This weight function makes an empty set in order to create a weighted matrix, in which blocks are given a score based on how many neighbours they contain.
If the square to its left, right, above, or below contains a 1 it adds one to its score.
VALIDITY
The validity function bases its choice on a greedy algorirthm. It uses a scoring system, in which the valid pieces are accepted and then compared to one another.
The piece with the lowest score is chosen as the desired piece and it is changed into the desired tuple.
UPDATE
The update function takes the co-ordinates found in the previous best solution and assigns the tuple to the co-ordinates within the weighted matrix.
It then proceeds to take 1 away from neighbouring squares based on certain conditions in order to change and edit the matrix again.
MOVING
The moving function allows progression to be made within the matrix. It uses a count as the position in which the block is placed and its shape ID
as a tuple. it acts as the main calling function, ensuring that squares that contain integers are used and those containing tuples are not.
LAST CHECK
The last check function, does a last sweep of the weighted matrix, in case any numbers slip through processing, changing them into tuples of (0,0)
otherwise the performance file will not accept any of the numbers.
TETRIS
The Tetris function calls the other elements within the function, returning a value M which is to be used as the solution matrix.
To see the full code, click here:
