Tiles Contest - Rules

The Tiles Contest

Rules in Chinese

This contest is inspired by the venerable tradition of edge-matching puzzles, in which polygons edges, distinguished with colors or patterns, are tiled so that edges of adjacent tiles match.

The Problem

Given a box filled with numbered tiles like the tiles below, your job is to fit the tiles together to minimize overall error along edges where two tiles meet.

You begin with a board on which to place all tiles. After you place these tiles, we calculate a cost to determine overall error using all tile adjacencies. The absolute value of the difference of two adjacent numbers contributes to the overall cost. Your goal is to minimize your overall cost.

The Details

Look at this example. Four tiles are placed on a 2-by-2 board.

Internal Cost

First, consider inside edges to calculate internal cost. In the top row, because two 2s appear next to each other, they contribute nothing to internal cost. However, on the second row, 2 and 1 appear next to each other, contributing to an internal cost of 1.

For the left column, 7 appears over 2 at an internal cost of 5. For the right column, 5 appears over 4 at an internal cost of 1.

Cost = |2 - 2| + |2 - 1| + |7 - 2| + |5 - 4|
Cost = 0 + 1 + 5 + 1 = 7

External Cost

Next, consider outside edges to calculate external cost. Zero is implied at every tile's outside edge. The calculation here is based on the difference of the implied 0 and the number of the outside edge.

The external cost along outside edges, working clockwise from the top left, is calculated as follows:

External cost = 1 + 3 + 6 + 3 + 0 + 3 + 8 + 9 = 33

Overall Cost

Overall cost is calculated by adding internal cost and external cost.

Overall cost = Internal + External = 7 + 33 = 40 

Here's a cleaner view of the operation, showing numbers on each tile and corresponding differences along edges.

Low Cost, Best Answer

You can reduce overall cost in several ways.

• You can move tiles wherever you want.
• You can orient tiles however you want.
• You can rotate tiles. For the example, does rotating the lower-left tile clockwise by 90 degrees improve your cost?
• You don’t have to place tiles on your board, although such a play is rather pointless. If you do leave your board empty, overall cost is simply the sum of all numbers on all tiles. This calculation can be helpful if you receive more tiles than you can fit on your board, as you will have to leave some tiles unplayed.



Internal cost = 0 + 1 + 1 + 1 = 3
External cost = 1 + 3 + 6 + 3 + 0 + 2 + 3 + 9 = 27
Overall cost = 3 + 27 = 30

Overall cost has improved significantly by rotating tiles. Can you find ways to reduce overall cost even more?

Other Considerations

• You don't have to use all tiles.
• Tiles you play don't need to fill your board.
• You may receive fewer tiles than your board can contain.
• You may receive more tiles than your board can contain.

Syntax

Here is the syntax to use:

[board, orientation] = solver(tiles, boardSize) 

You receive a set of n tiles in the form of an n-by-4 matrix. Each row corresponds to a single tile, listing the 4 numbers in clockwise order. For example, the vector corresponding to the tile below is [2 2 3 8].

Place tiles on a board with dimensions of boardSize, which is a two-element vector, [nRows nCols].

Specify location and orientation of each tile using the output arguments, board and orientation.

A Worked Example

Using the syntax described above, here's how to spell out the example:

tiles = 
  1 2 7 9
  2 2 3 8
  0 1 4 3
  2 3 6 5

boardSize = [2 2]

Initial Solution

The initial solution appears below, showing the board, syntax, and details about the syntax.

board = 
  1 4
  2 3

• Tile with Index 1 (the first 1 in the variable tiles) appears in the upper left.
• Tile with Index 2 appears in the lower left.
• Tile with Index 3 appears in the lower right.
• Tile with Index 4 appears in the upper right.

orientation = 
  1
  1
  3
  2

• Tile with Index 1 is oriented so the first number (1) is north.
• Tile with Index 2 is oriented so the first number (2) is north.
• Tile with Index 3 is oriented so the third number (4) is north.
• Tile with Index 4 is oriented so the second number (3) is north.

Improved Cost

After the adjustment to improve overall cost for the example, the answer looks like this.

board = 
  1 4
  2 3
 
orientation = 
  1
  4
  3
  2

Entry Setup

To become a player in the contest, follow this setup:

• Locate the contest-related zip file by visiting File Exchange. (See Resources.)
• Download and uncompress this zip file.
• Write the file solver.m using the signature described above Syntax.
• Use runcontest.m to test this function with the test suite in the zip file.

   >> runcontest

Scoring

The overall score for your entry is a combination of several factors. Items 1 and 2 below are the most important factors. Items 3 and 4 have a milder effect.

1. Your average result across all problems
2. How fast your code runs
3. Cyclomatic complexity of your code (below)
4. Node count of your code (below)

Because the goal is to minimize each of these factors, the lowest overall score at the end of the contest wins.

Cyclomatic Complexity

Cyclomatic complexity, also known as McCabe complexity, is a measure of the number of independent paths through a program's source code. Typically, as this number increases, understanding what's happening in a program becomes more difficult. This difficulty makes it harder to test, modify, and refactor.

Because a file can contain multiple functions, the complexity for any given file is defined as the maximum complexity of any functions contained within the file. A good practice is to keep the complexity for each function below 10. For the contest, your overall score increases according to complexity in excess of 10. No complexity penalty applies to submissions in which all functions have a complexity of 10 or less.

You can measure the cyclomatic (or McCabe) complexity of any function in MATLAB using the cyc switch for checkcode, for example:

>> checkcode -cyc magic.m

Node Count

Node count is a rough measure of the length of your code. Note that you are not penalized for comments and variable name length.

t = mtree(filename,'-file');
length(t.nodesize)

Time and Size Limitations

To keep the queue moving smoothly, we limit your code in the following ways:

• Number of entries
  You may submit no more than 5 files every 15 minutes for an average of 3 minutes per file. If you create multiple accounts to work around this limit, we may disqualify all of your entries for the duration of the contest.


• Run time
  If your entry requires more than 180 seconds (3 minutes) to run, it will time out and be disqualified.


• Size
  If your submission exceeds 65535 characters, it will fail.

Entry Changes and Collaboration

After you submit an entry, you cannot change it. However, any player can view, edit, and resubmit an existing entry as a new entry. This rule means that you can view and copy any entry in the queue.

If you change an existing entry and improve its score, then you are considered the author of that entry when we determine contest winners. We encourage you to examine and optimize existing entries.

We also encourage you to discuss your solutions and strategies with others by posting to the contest thread on MATLAB Newsgroup. (See Resources.)

Helpful Hints

Allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the MATLAB root directory. Functions from other toolboxes are not available. All entries are tested against the latest version of MATLAB. (See Resources.)

The following items are prohibited:

• MEX-files
• Java commands or object creation
• eval, feval, inline, and function handles
• Shell escapes such as !, dos, unix, and system
• Handle Graphics commands
• ActiveX commands
• File I/O commands
• Debugging commands
• Printing commands
• Simulink commands
• Benchmark commands such as tic, toc, flops, clock, and pause
• error, clear, and persistent functions

About Hacking

In consideration of all players, we ask that you do not abuse the system and follow these rules:

• Entries compromising contest machinery are disallowed.
• Extraction of puzzles in the test suite by manipulating the score, runtime, or error conditions is also disallowed.
• While tuning the entry to the contest test suite using multiple entries is permitted, overwhelming the queue is discouraged.

Resources

Check out these helpful resources:

• Zip file for Tiles Contest on MATLAB Central File Exchange
• FAQ for answers to frequently asked questions about the contest
• Contest Thread in a newsreader on MATLAB Newsgroup
• Latest version of MATLAB

About named visibility periods

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

• Darkness - During the first day of the contest, you cannot see code or scores for any entry.
• Twilight - During the second day of the contest, you see scores but cannot see code.
• Daylight - For the remainder of the contest, you see both scores and code for all entries.
• Finish - Contest end time.


Download Sample Code