{"id":375,"date":"2009-06-17T16:24:50","date_gmt":"2009-06-17T16:24:50","guid":{"rendered":"https:\/\/blogs.mathworks.com\/videos\/2009\/06\/17\/puzzler-find-four-connected-component-to-element-1-of-2-d-matrix\/"},"modified":"2009-06-17T16:24:50","modified_gmt":"2009-06-17T16:24:50","slug":"puzzler-find-four-connected-component-to-element-1-of-2-d-matrix","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/videos\/2009\/06\/17\/puzzler-find-four-connected-component-to-element-1-of-2-d-matrix\/","title":{"rendered":"Puzzler: Find four-connected component to element 1 of 2-d matrix"},"content":{"rendered":"This week, I was going to make a great video on recursion to solve a fun little puzzle.  However, my code runs too slow.  Before my recursive solution to the larger puzzle is practical, I need to clean out this bottleneck in the solver.\r\n<p><p>\r\nI have found the bottleneck to be here (taken out of context for clarity):\r\n\r\n<pre class=\"code\">\r\nsizeBoardEdge = 6;\r\nnumColors      = 6;\r\ntic\r\nfor i = 1:15000\r\n    %optimize contents of loop\r\n    %currently this take 3 seconds, would like to do significantly better\r\n    board = round(rand(sizeBoardEdge)*numColors);\r\n    oldColor = board(1,1);\r\n    %\r\n    connectedComponents = bwconncomp((board == oldColor),4);\r\n    vi = connectedComponents.PixelIdxList{1};\r\nend\r\ntoc\r\n<\/pre>\r\n\r\nNotice that I only want the indices of the pixels that are in the &#8216;four connected pool&#8217; of pixels of the same value as the pixel in the upper left corner.\r\n<p><p>\r\nThe benchmark to beat is 15000 calls in 3 seconds.\r\n<p><p>\r\nHere is a graphical example of what this should do.\r\n<p><p>\r\n<img src='https:\/\/blogs.mathworks.com\/videos\/..\/images\/videos\/2009\/06\/connected.jpg' alt='connected.jpg' \/>\r\n<p><p>\r\nMy code uses the <a href=\"https:\/\/www.mathworks.com\/products\/image\/\">Image Processing Toolbox<\/a>.  I am hoping a dedicated function could be optimized to run faster than BWCONNCOMP since I am only using a small amount of the information that this function calculates.\r\n<p><p>\r\n\r\nThe best solution to this by next week will get a MATLAB t-shirt, if it can cut the time on my machine by at least one half.\r\n\r\n\r\n\r\n\r\n","protected":false},"excerpt":{"rendered":"<p>This week, I was going to make a great video on recursion to solve a fun little puzzle.  However, my code runs too slow.  Before my recursive solution to the larger puzzle is practical, I need to&#8230; <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/videos\/2009\/06\/17\/puzzler-find-four-connected-component-to-element-1-of-2-d-matrix\/\">read more >><\/a><\/p>","protected":false},"author":68,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[12,10],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/posts\/375"}],"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=375"}],"version-history":[{"count":0,"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/posts\/375\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/media?parent=375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/categories?post=375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/videos\/wp-json\/wp\/v2\/tags?post=375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}