Blackbox is the 14th MATLAB Online Programming Contest.
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.
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.
[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.
actual = [ . . . . 7 ] [ . . . . . ] [ . 15 . . . ] [ . . . . . ] [ . 2 . . . ] guess = [ . . . . 7 ] [ . . . . . ] [ . 6 . . . ] [ . . . . 2 ] [ . 12 . . . ] guess - actual = [ . . . . 0 ] [ . . . . . ] [ . -9 . . . ] [ . . . . 2 ] [ . 10 . . . ] >> error = sum(sum(abs(guess - actual))) ans = 21your 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).
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.
All times are Eastern Standard Time, US.
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.
The following are prohibited:
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: