Blockbuster, mid-contest Analysis

Contents

Introduction

Diving into this contest has been somehow difficult due to the obfuscated code practice. Still, when it is possible to see the un-obfuscated version of it, it is surprising the well structured and compactness of code that we are developing. Something that keep my attention from other past contests is that the current solver only has one general approach to solve the problem. In the past, the leading entry usually contained several strategies all grouped by a final comparison which selected the best solution.

warning('off')

Popping or swapping?

I have been following some of the entries in the queue and I have noticed that most of our participants, prefer mostly pop than swap. This is something that we were expecting. Swapping apparently does not add value, since every swap costs as much as one pop, one move. While designing the contest we knew about this, still we feel that a good swapping strategy will give someone the small edge that might make him/her win the contest.

Even though the preference for swapping, we feel that the only-pops strategy has not been exhausted yet, observe the following example in which my brain can still beat the current winning entry.

blockBusterGUI2(repmat(ceil(magic(7)/10),2,1),20)

This is the solution of our best entry so far (April 10), the solver can't clear the board in 20 moves:

open('p1_2.fig')

It is not difficult at all to find an only-pops solution that outperforms our best solver, here is a solution that clears the board in 14 moves:

open('p1_3.fig')

Swap to join high valued blocks

I have this example in which I placed intentionally some blocks that you need to swap in order to remove them, I am not sure if the test suite has an example like this, but I believe this could hint an improvement to our current algorithm:

A= [1 2 3 4 4 1 9 3 9 5; 5 4 9 2 1 5 4 3 2 1; 9 9 3 9 9 1 2 3 4 5
    2 1 2 4 2 2 1 2 2 1; 3 4 1 2 3 1 4 4 4 3; 3 1 4 2 4 1 4 4 1 3
    4 2 3 2 5 3 1 3 2 1; 3 3 4 1 4 3 4 4 4 2; 1 4 1 4 2 1 4 4 4 2
    3 1 4 2 4 1 4 4 4 2; 2 3 2 1 2 2 2 1 2 4; 2 4 4 4 4 4 4 4 4 3
    9 4 9 2 3 4 4 4 4 3; 1 2 2 2 2 2 2 2 2 1; 1 4 4 4 1 4 4 4 4 2
    3 4 4 4 2 4 9 4 9 1; 1 1 1 1 4 2 2 2 2 1; 1 2 3 4 5 1 2 3 4 5
    5 4 3 2 1 5 4 3 2 1; 1 2 3 4 5 1 2 3 4 5];

blockBusterGUI2(A,20)

Our current solver, somehow does not remove any:

open('p2_2.fig')

If we swap in order to get those blocks closer, we can achieve better scoring:

open('p2_3.fig')

The checkerboard

Imre Polik wondered about how the current leading entry would do it with a checkerboard. Here it is:

A = repmat([2 1;1 2],10,5);
blockBusterGUI2(A,20)

Our best solver leaves a good deal of blocks without popping !

open('p3_3.fig')

I could clear the board in 20 moves, can someone beat me?

open('p3_2.fig')

Published with MATLAB® 7.2