{"id":385,"date":"2009-08-14T20:33:41","date_gmt":"2009-08-14T20:33:41","guid":{"rendered":"https:\/\/blogs.mathworks.com\/videos\/2009\/08\/14\/puzzler-results-of-most-difficult-puzzler-yet\/"},"modified":"2009-08-14T20:33:41","modified_gmt":"2009-08-14T20:33:41","slug":"puzzler-results-of-most-difficult-puzzler-yet","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/videos\/2009\/08\/14\/puzzler-results-of-most-difficult-puzzler-yet\/","title":{"rendered":"Puzzler: Results of most difficult puzzler yet"},"content":{"rendered":"The “Rules of the new game” puzzler<\/a> 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.\r\n

\r\nOne 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<\/a>. Darren’s entry<\/a> 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.\r\n

\r\nT’s entry<\/a> 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.\r\n

\r\nI 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<\/a>.\r\n

\r\nT 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.\r\n

\r\nIf you are interested, I would recommend looking at the code from T and Darren on the File Exchange.\r\n\r\n","protected":false},"excerpt":{"rendered":"

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… read more >><\/a><\/p>","protected":false},"author":68,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[4,12,10],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/posts\/385"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/users\/68"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/comments?post=385"}],"version-history":[{"count":0,"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/posts\/385\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/media?parent=385"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/categories?post=385"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/tags?post=385"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}