StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Karl's approach is basically sound, but could use some more details. It will find the optimal cost solution, but will be too slow for certain inputs. Large open areas especially will have too many possibilities to search through naively.</p> <p>Anyways, I made a quick implementation in C++ here: <a href="http://pastebin.com/S6FpuBMc">http://pastebin.com/S6FpuBMc</a></p> <p>It solves filling in the empty space (periods), with 4 different kinds of bricks:</p> <pre><code>0: 1x1 cost = 1000 1: 1x2 cost = 150 2: 2x1 cost = 150 3: 1x3 cost = 250 4: 3x1 cost = 250 5: 3x3 cost = 1 .......... 1112222221 ...#####.. 111#####11 ..#....#.. 11#2222#13 ..####.#.. 11####1#13 ..#....#.. 22#1221#13 .......... 1221122555 ..##..#... --> 11##11#555 ..#.#.#... 11#1#1#555 ..#..##... 11#11##221 .......... 1122112211 ......#..# 122221#11# ...####.#. 555####1#0 ...#..##.. 555#22##22 ...####... 555####444 total cost = 7352 </code></pre> <p>So, the algorithm fills in a given area. It is recursive (DFS):</p> <pre><code>FindBestCostToFillInRemainingArea() { - find next empty square - if no empty square, return 0 - for each piece type available - if it's legal to place the piece with upper-left corner on the empty square - place the piece - total cost = cost to place this piece + FindBestCostToFillInRemainingArea() - remove the piece return the cheapest "total cost" found } </code></pre> <p>Once we figure out the cheapest way to fill a sub-area, we'll cache the result. To very efficiently identify a sub-area, we'll use a 64-bit integer using <a href="http://en.wikipedia.org/wiki/Zobrist_hashing">Zobrist</a> hashing. Warning: hash collisions may cause incorrect results. Once our routine returns, we can reconstruct the optimal solution based on our cached values.</p> <p><strong>Optimizing:</strong> In the example, 41936 nodes (recursive calls) are explored (searching for empty square top-to-bottom). However, if we search for empty squares left-to-right, ~900,000 nodes are explored. </p> <p><strong>For large open areas:</strong> I'd suggest finding the most cost-efficient piece and filling in a lot of the open area with that piece as a pre-process step. Another technique is to divide your image into a few regions, and optimize each region separately.</p> <p>Good luck! I'll be unavailable until March 26th, so hopefully I didn't miss anything!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload