Team name: Frictionless Bananas
Team members: Jeremy Sawicki, Mieszko Lis
Lightning submission:
lightning.tar.gz
Final submission:
submission.tar.gz
Final leaderboard solutions:
solutions.json
The Frictionless Bananas had two team members this year, after being a single-person team in recent years. This page describes our 2015 ICFP Programming Contest entry.
This year's task had two main parts: placing pieces on the board (playing Tetris) and encoding "phrases of power" in the sequence of commands used to move and rotate the pieces. We chose to solve the two parts separately. First we decide where each piece should be placed, and then we choose a sequence of commands to put the pieces into the chosen locations while encoding phrases of power.
For piece placement, we process pieces one at a time without any lookahead. We calculate all possible locations for a piece, score them according to a few heuristics, and choose the best location. If several locations are equally good, we choose randomly. By varying the seed for the random number generator, we are able to generate multiple solutions to a problem and choose the best one.
Our program uses the following heuristics:
We were unable to decide between placing pieces as low as possible and placing pieces in the rows with the most filled cells. On boards with some initially filled cells, it seems better to take advantage of those cells to complete more rows, but that risks filling the board more quickly and becoming unable to play more pieces. Playing pieces as low as possible creates more opportunities to encode phrases of power.
Our final submission contains two different scoring systems. One tries to place pieces as low as possible (heuristic 1), and the other tries to favor rows with filled cells while also giving some weight to placing pieces lower (the sum of heuristics 1 and 2). In both cases, heuristic 3 is used as a tie breaker, resulting in some fairly decent looking moves.
For phrases of power, our program contains two algorithms: a greedy algorithm that is relatively fast and a dynamic programming algorithm that is quite a bit slower.
The greedy algorithm processes each piece independently, without considering phrases that are split among multiple pieces. It first performs a search backwards from the destination location to determine which locations can reach the destination and the commands needed to get there. It then creates a path beginning from the spawn location. The algorithm repeatedly tries to insert a phrase at the current position in the path. If the phrase ends at a location that can reach the destination, the phrase is inserted. If no phrase can be inserted, the algorithm follows the path determined by the inital search until a new row is reached, and then it resumes trying to insert phrases. Phrases are only inserted when the path has just entered a new row to avoid problems with repeated states.
Phrases are tried in priority order according to the following rules:
The main limiting factor in playing phrases is the number of times that a piece can descend (move southwest or southeast), so the goal is to maximize the number of phrase characters that can be played per descending command. Thus the priority of a phrase is based on the number of characters in the phrase divided by the number of descending commands in the phrase. Because the algorithm always starts phrases on a new row, phrases that don't end with a descending command have their priorities calculated using a descending command count that is one higher than the true count.
The dynamic programming algorithm attempts to optimize the sequence of commands for the entire problem by playing as many phrase characters as possible, including phrases that are split among multiple pieces. It works by building up a table containing the highest number of played phrase characters achievable in a given state, as well as the commands needed to reach that state. For a given piece, the table has the following dimensions:
The table is built one Y coordinate at a time. Each row of the table can be completed by referring only to the previous row, so it is only necessary to store two rows at a time. (The entire history of commands must be stored, which we did not have time to optimize.)
Like the greedy algorithm, the dynamic programming algorithm only starts a phrase when the path has just entered a new row. That means for example that the algorithm cannot play "Ei!" once per row, even though it is theoretically possible if the current piece can be rotated. It would require playing the final "!" of one "Ei!", followed by a rotation, followed by the initial "E" of another "Ei!" all within a single row, which our algorithm will not do.
We did not implement any logic to handle overlapping phrases.
In the first stage, our program uses both piece scoring systems with the greedy phrase algorithm, trying various random number generator seeds until the score stops showing much improvement. When a given <problem, seed> pair has 30 consecutive solutions that show no score improvement (15 for each piece scoring system), we stop working on that <problem, seed> pair. When all <problem, seed> pairs are finished, our program proceeds to the second stage.
In the second stage, our program uses the dynamic programming phrase algorithm. It first tries the best piece scoring system and random number generator seed found for each <problem, seed> pair in the first stage. Then it continues trying both scoring systems and various random number generator seeds.
When our program is run on multiple problems simultaneously, it sorts them in increasing order of difficulty, calculated as width × height × piece count, so that for example we may have time to run the dynamic programming algorithm on some easier problems even if it would take too long for the harder problems.
Our program does not use multiple cores, and it does not track memory usage. It does keep track of the time and abort when close to the time limit.
Our program is written in C++. We used the Jansson library for JSON manipulation.
In addition to the main program that computes solutions, we have a few other utilities: a program to play the game manually, a program to compute the scores for a set of solutions, and a program to visualize a solution.
Our utilities display the game board using a simple text-mode rendering with ANSI escape sequences for color:
We ranked 17th on the Final Qualifying Leaderboard.