This is the tenth MATLAB Online Programming Contest.
Imagine a sandbox in which there are ants, sugar cubes, anthills, and rocks. Ants like sugar: collectively they want to bring as many sugar cubes as possible back to their anthills before sunset.
For this contest, you will write the control program used by each ant. Ants, being so small, have some limitations. Each ant can carry no more than one sugar cube at a time. Further, each ant can only see her local vicinity. Your program, which is run sequentially for each ant, knows only what that ant knows. Thus you must bring about the best possible global outcome based only on local conditions. The ants don't have any memory as such, but they can leave behind a chemical trail to guide themselves and others across the sandbox landscape.
Your score is determined by how much progress you make moving food towards and into the anthills. Ideally your ants will move all the sugar cubes into anthills. Practically this may not be possible; do the best you can. You receive credit even when you move a single sugar cube one step closer to an anthill.
Here is a sample map that an ant might face.
The full 9x10 map is shown, but the ant only "sees" the 5x5 subset of the map indicated by the red outline. In this case, food is available on this map in two locations, but the ant has no knowledge of the food in the upper right corner. It is simply beyond her current horizon.
The ant controller code is called with four input arguments and must return four output arguments.
[dy,dx,mark,carry] = ant(mainMap,foodMap,antMap,scentMap)
The inputs are all 5x5 matrices of integers with the ant at the (3,3) center location.
The outputs are all scalars.
If we step through this example, we get the following problem inputs (for the sake of readability, zeros in the following matrices are shown as dots).
mainMap = [ . . . . . ] foodMap = [ . . . . . ] [ . . . . 1 ] [ . . . . . ] [ . . . . . ] [ 2 . . . . ] [ . . . . . ] [ . . . . . ] [-1 . . . . ] [ . . . . . ] antMap = [ . . . . . ] scentMap = [ . . . . . ] [ . . . . . ] [ . . . . . ] [ . . 1 . . ] [ . . . 10 9 ] [ . . . . . ] [ . . . . . ] [ . . . . . ] [ . . . . . ]
Based on the information available to the ant, we want to move west, towards the two nearby sugar cubes. Accordingly we issue the following commands.
dy = 0 dx = -1 mark = 10 carry = 0
We are leaving a scent trail marker of ten to show where we've been. Since we're not in a square with any sugar cubes, there is no need to set the carry bit.
You're not allowed to explicitly pass information from one ant to the next through the use of programming techniques, like persistent variables, global variables, or similar. The challenge in this contest is to find ways to externalize information using smell or the like.
The overall score for your entry is a combination of how well your algorithm does and how fast it runs on a multi-problem test suite. How well your algorithm does (which we call the "result") is determined by how thoroughly you move all the sugar cubes to the anthills. At the end of the total available simulated time, your result will be determined by calculating the aggregate improvement in the total Euclidean distance of all sugar cubes to the nearest holes.
In the example above, there are two sugar cubes at location (r=5,c=2), one sugar cube at location (r=1,c=8), and an anthill at location (r=4,c=6). The result is currently
2 * sqrt((6-2)^2 + (4-5)^2) + sqrt((6-8)^2 + (4-1)^2) = 11.85
If the ant in the diagram picks up one of the two sugar cubes to the left of the anthill and moves it one column closer to the anthill (east), the overall result would be improved (lowered) to
sqrt((6-3)^2 + (4-5)^2) + sqrt((6-2)^2 + (4-5)^2) + sqrt((6-8)^2 + (4-1)^2) = 10.89
The best possible result is zero.
The average result for the entire test suite, along with the associated runtime of your entry, gets passed to our scoring algorithm before returning a final score, according to the equation
We don't publish the values k1, k2, and k3, but they aren't hard to figure out. Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).
The files you need to get started on the contest are included in a ZIP-file available on the MATLAB Central File Exchange. If you download and uncompress this ZIP-file, you will have the files described below.
The ant control routine is solver.m.
[dy,dx,mark,carry] = solver(mainMap,foodMap,antMap,scentMap)
Keep in mind that this function must have the right signature: four input arguments, four scalar output arguments. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m.
The column in our MySQL database that stores the M-code is of type text, which is limited of 65535 characters. It will truncate code above that limit.
Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and copy any entry in the queue. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.
We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the comp.soft-sys.matlab thread that we've started from our newsreader.
The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against MATLAB version 7.0.4 (R14sp2).
The following are prohibited:
Check our FAQ for answers to frequently asked questions about the contest.
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: