Winner Alan Chalker (End of it all)
Blackbox - Rules
Blackbox is the 14th MATLAB Online Programming Contest.
The Problem
For this contest, imagine you're looking down at a black box. You can't see what's in the box, but you can shine a special laser in through the sides of the box to help you learn what's inside.
You know that the box contains one or more objects, each associated with a point value. The box is square and divided into compartments. Each compartment can be empty or have one object in it. If we could pry off the top of the box, it might look like this.
Your goal is to determine, using your laser, the exact location and point value of each object in the box as efficiently as possible. Laser light can be absorbed, deflected, or reflected back where it came from.
- If the laser hits an object directly, it is absorbed.
- If the laser passes right next to an object, it is deflected 90 degrees as shown above.
- If the laser is directed through the empty square directly between two nearby objects, it is reflected.
- If the laser enters the box adjacent to an object on the edge of the box, it is reflected.
- When laser light is deflected or reflected, it returns information about the score of the objects it encounters.
By carefully shining your laser into the black box, you can deduce the location and point value of the objects inside. Every time you use your laser, you increase your beam count by one. A lower beam count is rewarded by a better score.
How it works
Use the BEAM function to query the black box. Here is the syntax:[rowOut, columnOut, score] = beam(rowIn,columnIn,beamIntensity)Columns and rows are numbered as shown below. Beam intensity is either 'low' or 'high'. The score associated with a beam is what lets you deduce the value of the hidden objects. If a beam is absorbed, it returns no information about the value of the object it has encountered. If, however, it is deflected or reflected, then the return value is the sum of all the objects it has encountered along its path.
The next diagram shows what the input and output arguments would look like for this example.
In some circumstances, you may find it useful or even necessary to remove certain objects before you can solve the puzzle. For this purpose, your laser is equipped with a special (though expensive) "high beam" option that destroys any object that absorbs it. Note that if the beam is not absorbed, then no objects are removed from the puzzle. No information is returned to you as a result of this call. If you ask for return values, you will always get [0 0 0]. Don't use it unless you really need to: the high beam operation increases your beam count by the point value of the object you destroy.
Some Examples
- beam(1,0) or beam(1,0,'low') shines the light into the first row from the left.
- beam(1,0,'high') destroys any object that absorbs it.
Scoring
The overall score for your entry is a combination of three things:- Error: How well your answers match the actual test suite
- Beam count: How many times you called the BEAM command (remembering that high beams add to your beam count by the amount of the objects they destroy)
- Speed: How fast your code runs
actual = [ . . . . 7 ]
[ . . . . . ]
[ . 15 . . . ]
[ . . . . . ]
[ . 2 . . . ]
guess = [ . . . . 7 ]
[ . . . . . ]
[ . 6 . . . ]
[ . . . . 2 ]
[ . 12 . . . ]
guess - actual = [ . . . . 0 ]
[ . . . . . ]
[ . -9 . . . ]
[ . . . . 2 ]
[ . 10 . . . ]
>> error = sum(sum(abs(guess - actual)))
ans =
21
your error would be 21. Beam counts are then added to this error to provide a single number for each black box like so:
result = error + kbc*beam_count
where kbc is 0.1.
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 (the "result") depends on how low your final score is.
The total 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
score = k1*result + k2*e(k3*runtime)
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 three minutes (180 seconds).
Developing Your Entry
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 main routine is solver.m.
solution = solver(n)where n determines the size of the n-by-n square matrix. The return value solution should contain your best guess for the n-by-n game board. In order to formulate your solution, you will want to use the virtual laser beam function shown below.
[rowID, columnID, score] = beam(rowID, columnID, level)The variables rowID and columnID correspond to the row or column index of the box matrix. A positive index number means the left or top side of the matrix, and a negative index number means the right or bottom side of the matrix. The third input argument "level" is a string which is either "low" or "high". If no third argument is provided, the default level of "low" is assumed. If level is set to "high", there are no return arguments.
Keep in mind that these functions must have the right signature. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m.
>> runcontest
Size limitations
The code is limited in size by the database architecture. The column in our MySQL database that stores the M-code is of type text, which is limited of 65535 characters. Submissions longer than this limit will fail.About the Contest
The contest is divided into three segments. The first two days of the contest hide some of the information about each entry. After that, code is freely shared.- Darkness. (Wed. 9 AM to Thurs. 12 PM) During the first day of the contest, you can't see the code or scores for any of the entries.
- Twilight. (Thurs. 12 PM to Fri. 12 PM) During the second day of the contest, you can see scores but no code.
- Daylight. (Fri. 12 PM to Wed. 5 PM) For the remainder of the contest you can see scores and code for all entries.
All times are Eastern Standard Time, US.
Collaboration and Editing Existing Entries
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 newsgroup thread that we've started from our newsreader.
Fine Print
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.3 (R2006b).The following are prohibited:
- MEX-files
- Java commands or object creation
- eval, feval, inline, function handles, etc.
- Shell escape such as !, dos, unix
- Handle Graphics commands
- ActiveX commands
- File I/O commands
- Debugging commands
- Printing commands
- Simulink commands
- Benchmark commands such as tic, toc, flops, clock, pause
- error, lasterr
- clear, persistent, mlock
FAQ
Check our FAQ for answers to frequently asked questions about the contest.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 - You can't see the code or scores for any of the entries.
- Twilight - You can see scores but no code.
- Daylight - You can see scores and code for all entries.
- Finish - Contest end time.