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.
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.
Look at this example. Four tiles are placed on a 2-by-2 board.
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
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 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.
You can reduce overall cost in several ways.
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?
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,
Specify location and orientation of each tile using the output arguments,
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]
The initial solution appears below, showing the board, syntax, and details about the syntax.
board = 1 4 2 3
tiles) appears in the upper left.
orientation = 1 1 3 2
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
To become a player in the contest, follow this setup:
solver.musing the signature described above Syntax.
runcontest.mto test this function with the test suite in the zip file.
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.
Because the goal is to minimize each of these factors, the lowest overall score at the end of the contest wins.
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
cyc switch for
checkcode, for example:
>> checkcode -cyc magic.m
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)
To keep the queue moving smoothly, we limit your code in the following ways:
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.)
Allowable functions are those contained in the basic MATLAB package available in
$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:
In consideration of all players, we ask that you do not abuse the system and follow these rules:
Check out these helpful resources:
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: