Challenge: Take a 48x48 image, find contiguous areas that result in the cheapest Lego solution to create that image! [closed]

Question

Background

Lego produces the X-Large Gray Baseplate, 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: Android, Dream Theater, The Galactic Empire, Pokemon).

The Challenge

My challenge is now to get the lowest cost to purchase these designs. Purchasing 2304 individual 1x1 plates can get expensive. Using BrickLink, 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:

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

The Problem

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?

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 current available average price.

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!).

EDIT

Here's a link to the 2x2 corner piece and to the 4x4 corner piece. 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!

1x1|white|.07
1x1|yellow|.04
[...]
1x2|white|.05
1x2|yellow|.04
[...]

This list would NOT have the entry:

8x8|yellow|imaginarydollaramount

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.

EDIT2

Changed some wording for clarity.

Answer 1

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.

Anyways, I made a quick implementation in C++ here: http://pastebin.com/S6FpuBMc

It solves filling in the empty space (periods), with 4 different kinds of bricks:

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 

So, the algorithm fills in a given area. It is recursive (DFS):

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 } 

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 Zobrist hashing. Warning: hash collisions may cause incorrect results. Once our routine returns, we can reconstruct the optimal solution based on our cached values.

Optimizing: 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.

For large open areas: 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.

Good luck! I'll be unavailable until March 26th, so hopefully I didn't miss anything!

Answer 2

Steps

Step 1: Iterate through all solutions.

Step 2: Find the cheapest solution.

Create pieces inventory

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.

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.

Then it becomes a subset problem, which is NP-Complete.

Solving the subset problem

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)

Optimizations

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.

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.

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.

Finding the cheapest

Calculate cost of each solution, find the cheapest!

Comments

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.

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).

Suggestion

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!