Databases
StackOverflow2013
Postsdbo
POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
    primarykey
    data
    text
    <p><strong>Background</strong></p> <p>Lego produces the <a href="http://shop.lego.com/Product/?p=628" rel="noreferrer">X-Large Gray Baseplate</a>, which is a large building plate that is 48 studs wide and 48 studs tall, resulting in a total area of 2304 studs. Being a Lego fanatic, I've modeled a few mosaic-style designs that can be put onto these baseplates and then perhaps hung on walls or in a display (see: <a href="https://i.stack.imgur.com/Uj786.png" rel="noreferrer">Android</a>, <a href="https://i.stack.imgur.com/DbnAE.png" rel="noreferrer">Dream Theater</a>, <a href="https://i.stack.imgur.com/DX8jO.png" rel="noreferrer">The Galactic Empire</a>, <a href="https://i.stack.imgur.com/HVWNw.png" rel="noreferrer">Pokemon</a>).</p> <p><strong>The Challenge</strong></p> <p>My challenge is now to get the lowest cost to purchase these designs. Purchasing 2304 individual 1x1 plates can get expensive. Using <a href="http://www.bricklink.com/browseList.asp?itemType=P&amp;catString=26" rel="noreferrer">BrickLink</a>, essentially an eBay for Lego, I can find data to determine what the cheapest parts are for given colors. For example, a 1x4 plate at $0.10 (or $0.025 per stud) would be cheaper than a 6x6 plate at $2.16 (or $0.06 per stud). We can also determine a list of all possible plates that can be used to assemble an image:</p> <pre><code>1x1 1x2 1x3 1x4 1x6 1x8 1x10 1x12 2x2 corner! 2x2 2x3 2x4 2x6 2x8 2x10 2x12 2x16 4x4 corner! 4x4 4x6 4x8 4x10 4x12 6x6 6x8 6x10 6x12 6x14 6x16 6x24 8x8 8x11 8x16 16x16 </code></pre> <p><strong>The Problem</strong></p> <p>For this problem, let's assume that we have a list of all plates, their color(s), and a "weight" or cost for each plate. For the sake of simplicity, we can even remove the corner pieces, but that would be an interesting challenge to tackle. How would you find the cheapest components to create the 48x48 image? How would you find the solution that uses the fewest components (not necessarily the cheapest)? If we were to add corner pieces as allowable pieces, how would you account for them?</p> <p>We can assume we have some master list that is obtained by querying BrickLink, getting the average price for a given brick in a given color, and adding that as an element in the list. So, there would be no black 16x16 plate simply because it is not made or for sale. The 16x16 Bright Green plate, however, would have a value of $3.74, going by the <a href="http://www.bricklink.com/catalogPG.asp?itemType=P&amp;itemNo=91405&amp;itemSeq=1&amp;colorID=36&amp;v=P&amp;priceGroup=Y&amp;prDec=2" rel="noreferrer">current available average price</a>.</p> <p>I hope that my write-up of the problem is succint enough. It's something I've been thinking about for a few days now, and I'm curious as to what you guys think. I tagged it as "interview-questions" because it's challenging, not because I got it through an interview (though I think it'd be a fun question!).</p> <p><strong>EDIT</strong></p> <p>Here's a link to the <a href="http://www.bricklink.com/catalogItem.asp?P=2420" rel="noreferrer">2x2 corner piece</a> and to the <a href="http://www.bricklink.com/catalogItem.asp?P=2639" rel="noreferrer">4x4 corner piece</a>. The answer doesn't necessarily need to take into account color, but it should be expandable to cover that scenario. The scenario would be that not all plates are available in all colors, so imagine that we've got a array of elements that identify a plate, its color, and the average cost of that plate (an example is below). Thanks to Benjamin for providing a bounty!</p> <pre><code>1x1|white|.07 1x1|yellow|.04 [...] 1x2|white|.05 1x2|yellow|.04 [...] </code></pre> <p>This list would NOT have the entry:</p> <pre><code>8x8|yellow|imaginarydollaramount </code></pre> <p>This is because an 8x8 yellow plate does not exist. The list itself is trivial and should only be thought about as providing references for the solution; it does not impact the solution itself.</p> <p><strong>EDIT2</strong></p> <p>Changed some wording for clarity.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USRockmaninoff
    1. USRockmaninoff
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
      1. USMufaka
      1. VTFavorite
    2. VO
      singulars
      1. POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
      1. UStemplatetypedef
      1. VTFavorite
    3. VO
      singulars
      1. POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
      1. This table or related slice is empty.
      1. VTUpMod
    1. CODon't accept an answer too fast. I will put up a bounty when it becomes possible...
      singulars
      1. POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
      1. USBenjamin
    2. COThanks! I could definitely use a solid answer, perhaps with pseudo-code. Or at least a good explanation.
      singulars
      1. POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
      1. USRockmaninoff
    3. COCan you explain what a "corner" piece looks like? Should answers consider colour?
      singulars
      1. POChallenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image!
      1. USBenjamin
 

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