Tutorial

Simulator Operation

Here's how the simulator works, and what your algorithm must do:

1. The simulator presents problems in the forms of "boards". Each board is a grid of amino acids. The final boards used to score your algorithm will be 32x32 in size. For testing and debugging, you can choose from 8x8, 16x16, and 32x32 boards.
2. There are four types of amino acids: Red, Blue, Green, and Orange. Your protein starts out as the four amino acids in the center of the board, which will always consist of one of each type of amino acid in the following configuration:

 

The rest of the amino acids on the board have been randomly chosen from the four types.

3. To finish a board, your protein must bond with all amino acids. To bond, an entire edge of your protein must be complementary to the amino acids which are adjacent to it. Red is complementary to Blue; Green is complementary to Orange. Once an entire edge is complementary to the amino acids just outside, a bond is formed and this set of outside amino acids becomes part of the protein.
4. To make edges complementary, you perform transformations on rectangles of amino acids within the protein. The transformations you can perform are as follows:

• FlipH, FlipV: Flips the rectangle horizontally or vertically.
• Invert: Inverts the amino acids within the rectangle (Red becomes Blue, Blue become Red, Green becomes Orange, and Orange becomes Green).
• Rotate90, Rotate180, Rotate270: can only be used on squares; this rotates the square clockwise by 90, 180, or 270 degrees.

5. Each such transformation is a move. Your goal is to complete the board (bond with all amino acids) in the fewest moves, and with the least running time. A combination of moves and time will be used to select the final algorithms; for details, see the Scoring page.
6. It is important that your algorithm work on any board configuration. A number of randomly-generated practice boards have been provided; however, the final test will use a different set of randomly-generated boards (which will not be known in advance). Any algorithm which fails to work on any board will be eliminated from consideration.
7. Your algorithm must be supplied in the form of a .NET 2.0 assembly which exposes a "Move" method. The Move method will be given the current board configuration as an input and must return a move to make. The simulator will call your assembly's Move method repeatedly until your protein binds with all amino acids on the board (or until you give up, perform an illegal move, or your time limit expires). See the SDK documentation for more information on creating your submission.

Visual Overview

Here is a visual overview of the simulator:

 

The picture above shows an 8x8 board of amino acids. The current protein is shown in gray; the rectangle for the next move is shown in yellow.

Example Move Sequences

Please refer to the board above for these examples.

Amino acids are addressed using (X,Y) coordinates where (0,0) is the top left, X increases as you move right, and Y increases as you down. Rectangles are specified using (Left, Top, Width, and Height). Since the coordinate system is centered on the amino acids themselves, a width of zero and height of zero means the single amino acid which is at (Left, Top). A Width and Height of 1 would be four amino acids.

In the board shown above the protein rectangle is (3, 2, 2, 2).

One possible move sequence to bond with more amino acids and increase the size of your protein would be as follows:

 

1. Invert(5, 3, 0, 0)

 

 

2. FlipV(3, 2, 0, 2)

 

 

3. FlipH(3, 4, 2, 0)

 

 

Note that the last move caused three new amino acids to bond with the protein, because the amino acids just outside the right edge of the protein (Blue, Orange, Red) were complementary to those just inside the edge (Red, Green, Blue).

Consider, however, the following move sequence:

 

1. FlipV(3, 3, 1, 1)

 

 

2. Rotate180(3, 2, 2, 2)

 

 

This sequence bonds with the same three amino acids, but it does it in two moves instead of three. Note also that with an additional move you could bond with four more amino acids: Invert(4, 4, 0, 0).

Special Considerations

There are a few special cases to consider:

1. It is possible that bonding can "chain"; that is, that one occurrence of bonding can lead directly to another without an intervening move. In fact, bonding can even happen before the first move - so be sure not to assume your initial protein is only the center four amino acids, or that subsequent growth will only be only one row or column at a time.
2. If a single move causes more than one edge to bond, the edges bond "simultaneously". If the two edges share a corner then the amino acid which is diagonally outside of that corner is included in the bond. After all the current protein's edges are checked for bonding, if the protein size has increased, an additional check is made along the new borders. This continues until the protein stops growing or encompasses the whole board.
3. All of your moves must be fully within the protein. Any attempt to make a move outside of the protein, or an attempt to make an invalid move (ie, a negative width or height, a rect outside of the bounds of the board, or a rotate on a non-square rect) will cause the simulator to terminate. If this occurs during the final run of the contest then your entry will be removed from consideration.
4. For debugging purposes, if your algorithm can not find a move to make, it can "give up" and stop working on the board. In the final run, this will remove your entry from consideration.
5. All supplied boards (practice and final) will be solvable without looking beyond the protein's immediately adjacent amino acids, regardless of protein growth sequence (no "lookahead" required).