Computing - Tetriling Reassambly
The Module
The aim of this module is to provide students with design concepts, theoretical foundations, and hands-on experience to efficiently construct their own algorithms and data structures for solving general or particular problems.
The Task
To come up with an algorithm to solve a tetriling reassembly as fast as possible and with the best solution that minimized uncovered squares in the target region. The target size could range from 10x10 to 1000x1000. The target could have three different densities; a higher density meant more pieces had to be placed.
The Solution
For sizes smaller than 100x100, the solution was reached through a combination of recursion and an improved greedy algorithm. For targets larger than that, the pieces were placed using only the improved greedy algorithm.
Recursion
The code would begin by placing the first given piece on the target. It would make a deep copy on a global variable and call itself again. When a piece could not be placed, the code would retrace its steps until it could place that piece. Sometimes, backtracking could take too long, so after 40 seconds, the algorithm would end and return the saved global variable.
Improved Greedy Algorithm
To place the pieces on the target, a neighbouring system was used. The best solution was reached by placing pieces where there were the fewest neighbours around one location. All the 1s were changed to the number of 1s it had around it.
This method was used because it improves the greedy algorithm as it would not pick the best immediate output without considering the whole target.
Run Time Analysis
The Recursion algorithm gets the highest results on small-sized targets, however as the size gets bigger, the algorithm increases drastically as seen on the graph on the left. Using just the greedy algorithm for bigger sized targets, the time is below 60 seconds for all densities but 0.8.
Accuracy Analysis
When looking at the accuracy, it is clear that in smaller sized targets, the recursion algorithm gets higher accuracy, in fact, the average accuracy for the recursion algorithm is 95%, and for the greedy algorithm, it is 89%.
The neighbouring method is an improved approach to a simple greedy algorithm because instead of placing a piece where it fits, the algorithm places a piece compared to the other pieces around it, and no matter what size, it will return the same accuracy.
