Blackbox, mid-contest Analysis

Contents

Introduction

Today (finally) I have had a great day playing around with the contest entries, this is really fun. Before getting into the matter, let me apologize for not having a better visualization before, this contest got the Mathwork-ers into the middle of very critical days for the next MATLAB release, therefore our participation has been somehow decimated. Anyways, with the exception of some obvious hacks that got us unprepared, the contest has gone smoothly and most importantly I see a lot of room for further improvement into our current leader.

For this mid-analysis I will be using four different entries. First, the darkness phase winner code “on its head” (entry number 32137) by Cobus Potgieter, I will denote this entry as [A] thereafter. During the darkness phase other people were also working on good ideas, one of those led to the twilight phase first place, “Aargh :-)” (entry number 33328) by Per Rutquist is our second entry [B] to analyze. One of the most active participants today and yesterday (when does this guy sleeps?) is David Jones, he won the midnight madness challenge with “Coding in the dark 60” (entry number 32537), we will use [C] to represent his solver. Our fourth entry to analyze [D] is top entry (at the time of this writing) “Not done” (entry number 33517) by the old known The Cyclist.

Raster algorithm

What seems to be the core strategy in most of the entries is to create a raster algorithm which cleans the black box orderly, either row by row or column by column. First it looks at deflections and then it destroys any particle that is in the current row. A good example of this approach can be observed with solvers [A] and [C] using the problem 100 of the sample testsuite. However, Per seems to have introduced a clever way to start the rasterization from different edges in [C], and more interesting, the last two particles are guesses without having to blow them away. [D] uses the same approach as [C].

load testsuite_sample
drawpuzzle(testsuite{100},'Sample testsuite, problem 100')

Problems starting the rastering

While I was working on the visualization board I created a working example to test that beams that are reflected are correctly plotted. To my surprise this turned out to be a very difficult example, the four solvers seem to have a problem to start the rasterization. This seems to be due to those particles placed at the corners of the box, luckily it seems that the testsuite does not have many of these cases.

puzzle = [ 0 0 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0;
           4 0 0 0 0 0 5 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0;
           0 0 0 0 7 0 6 0 0 0; 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0;
           3 0 0 0 0 0 0 0 0 2;];
drawpuzzle(puzzle,'Lucio''s example')

Memoryless solvers

Another curious fact that I observed while working on the visualization is that the solvers seem not to have memory. I am not sure if it could be possible to remember the results of the low beams that we use in the solver approach, but I noticed, at least for visualization, that it is feasible to keep them in memory and remove them from memory when we blow out a particle that we know affects the trajectory of a previously stored low intensity beam. In the example taken from the problem 6 of the sample testsuite we can observe that all the solvers repeat low intensity beams that have already been used, especially solvers [B] and [D] have this characteristic.

drawpuzzle(testsuite{6},'Sample testsuite, problem 6')

Are there problems that can be solved without blasting particles?

Problem 35 of the sample testsuite seems to be spare enough to create a table of all the possible low intensity beams and deduce the result from it. This would give a significant benefit, specially in this problem where the particles seem to be quite heavy. [A] zaps all the particles, [B], [C] and [D] leave alive the second heaviest particle.

drawpuzzle(testsuite{35},'Sample testsuite, problem 35')

Ned’s example

The example posted in the rules may give another hint to the contestants; so far it seems that the solvers can leave generally one particle without blasting it. How difficult would be to design a strategy that leaves more particles on the board, or at least when we are approaching to the end of the board we could make a decision to blast the lighter particles and not the heavy ones.

puzzle =  [0 0 0 0 7;0 0 0 0 0;0 15 0 0 0;0 0 0 0 0;0 2 0 0 0];
drawpuzzle(puzzle,'Ned''s example')

Are sparse problems optimizable?

Problem 41 in the sample testsuite seems to be sparse enough to send some low beams in the middle of the board that will not have any deflection or reflection, and I know you may be hating me because we know that the fact that a beam appears exactly on the opposite side of the box does not mean it did not hit any particle. Though the rasterization technique seems to work fast and appropriately (but not inexpensively) in this problem I believe there is the possibility to leave a good quantity of particles without having to disintegrate them.

drawpuzzle(testsuite{41},'Sample testsuite, problem 41')

I hope this analysis have been insightful and give you some ideas to try on, but to be honest I believe that some of you are already working on them. We will update the submission in Matlab Central with the visualization routines, I apologize for those running earlier Matlab versions, if you have too many troubles let me know and I’ll try to update it soon. Happy tweaking.

Published with MATLAB® 7.4