The “Rules of the new game” puzzler was the most difficult one yet. Puzzlers are MATLAB programming challenges that I post from time to time. They lead to interesting discussions of MATLAB coding styles. There were two very interesting submissions which I would like to highlight from T and Darren. They both made some very clever optimizations that give speed improvements over my original solution. I wrote my solution with the objectives of guaranteeing a solution and keeping the code simple.

One major thing that all solutions needed to do for this problem was to find all of the pixels that would be touched in a flood operation. I used the method developed by the community in my last puzzler. Darren’s entry used a method that padded the board around the edges, making his operations easier. It was very similar to a two dimensional convolution. It very quickly would find the “fringe” of the existing block.

T’s entry used a different technique that was more heavily reliant on the Image Processing Toolbox. Using IMDILATE and other functions, he was really able to make a good algorithm for finding the neighbors to the ever growing blob.

I used a greedy algorithm, simply choosing the color that that would cause the greatest number of squares to change color. Since this was a recursive algorithm, I would order the possible choices by greatest to least change and hopefully find an acceptable solution simply by always taking the first ranked choice. Recursion would (eventually) find a solution in the exhaustive search, so I did not look ahead any moves. I was doing a depth first search.

T and Darren would actually look ahead a few moves, choosing color that appeared best in a couple of moves (exhaustive search, since it was a more limited set). Not only this, but T wired his solution up with many configurable parameters, such as depth of search and metric to decide which is the best choice.

If you are interested, I would recommend looking at the code from T and Darren on the File Exchange.