BRIEF:

Design an algorithm to solve the tetriling with missing pieces problem. This problem consists of finding a tiling of an arbitrary finite polyomino region by using Tetris pieces, with the exception of the O tetris piece and the I tetris pieces. The objective is to perform the tiling as fast as possible while minimizing the sum of uncovered and added squares in the target region.

OUTCOME:

The challenge was to design an asymptotically efficient algorithm that could place tetriling pieces onto an input grid of shapes. The code was written in python using VS Studio code, and utilised well-known algorithms such as ‘the greedy algorithm’ and quicksort. The input to the algorithm was a matrix of ‘1s’ and ‘0s’ - the ideal solution would cover all the ‘1’s on the input grid, and not cover any ‘0s’. First, the algorithm scanned through the matrix to find a ‘1’. Once it had completed that, it created a smaller 3 x3 matrix around that ‘1’ and sorted through all the possible tetris shapes that could fit. Once each piece had received a ranking, a quicksort algorithm selected the highest scoring piece, and placed it on the output matrix. My code ran within 92% accuracy with consistently fast times, on a varying input grid size of 1000 x 1000.