Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h2>Steps</h2> <p>Step 1: Iterate through all solutions.</p> <p>Step 2: Find the cheapest solution.</p> <h2>Create pieces inventory</h2> <p>For an array of possible pieces (include single pieces of each color), make at least n duplicates of each piece, where n = max(board#/piece# of each color). Therefore, at most n of that piece can cover all of the entire board's colors by area.</p> <p>Now we have a huge collection of possible pieces, bounded because it is guaranteed that a subset of this collection will completely fill the board.</p> <p>Then it becomes a subset problem, which is NP-Complete.</p> <h2>Solving the subset problem</h2> <pre><code>For each unused piece in the set For each possible rotation (e.g. for a square only 1, for a rectangle piece 2, for an elbow piece 4) For each possible position in the *remaining* open places on board matching the color and rotation of the piece - Put down the piece - Mark the piece as used from the set - Recursively decent on the board (with already some pieces filled) </code></pre> <h2>Optimizations</h2> <p>Obviously being an O(2^n) algorithm, pruning of the search tree early is of utmost importance. Optimizations must be done early to avoid long-running. n is a very large number; just consider a 48x48 board -- you have 48x48xc (where c = number of colors) just for single pieces alone. </p> <p>Therefore, 99% of the search tree must be pruned from the first few hundred plies in order for this algorithm to complete in any time. For example, keep a tally of the lowest cost solution found so far, and just stop searching all lower plies and backtrack whenever the current cost plus (the number of empty board positions x lowest average cost for each color) > current lowest cost solution.</p> <p>For example, further optimize by always favoring the largest pieces (or the lowest average-cost pieces) first, so as to reduce the baseline lowest cost solution as quickly as possible and to prune as many future cases as possible.</p> <h2>Finding the cheapest</h2> <p>Calculate cost of each solution, find the cheapest!</p> <h2>Comments</h2> <p>This algorithm is generic. It does not assume a piece is of the same color (you can have multi-colored pieces!). It does not assume that a large piece is cheaper than the sum of smaller pieces. It doesn't really assume anything.</p> <p>If some assumptions can be made, then this information can be used to further prune the search tree as early as possible. For example, when using only single-colored pieces, you can prune large sections of the board (with the wrong colors) and prune large number of pieces in the set (of the wrong color).</p> <h2>Suggestion</h2> <p>Do not try to do 48x48 at once. Try it on something small, say, 8x8, with a reasonably small set of pieces. Then increase number of pieces and board size progressively. I really have no idea how long the program will take -- but would love for somebody to tell me!</p>
    singulars
    1. This table or related slice is empty.
    1. POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USStephen Chung
    1. USStephen Chung
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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