# Combinations of lego bricks figures in an array of random bricks

I have an assignment where a robot should assemble some lego figures of the simpsons. See the figures here: Simpsons figures!

To start with we have some identical sized, different colored lego bricks on a conveyor belt. See image.

My problem is to find out which combinations of figures to make out of the bricks on the conveyor belt. The bricks on the conveyor belt can vary.

Here is an example:

Conveyor bricks: 5x yellow, 2x red, 3x blue, 1x white, 4x green, 1x orange

From these bricks I can make:

• Homer(Y,W,B), Marge(B,Y,G), Bart(Y,O,B), Lisa(Y,R,Y), Rest(Y,G,G,G), OR
• Marge(B,Y,G), Marge (B,Y,G), Marge(B,Y,G), Lisa(Y,R,Y), Rest(R,W,G,O), OR
• ...

Any way to automate this? Any suggestions to literature or theories? Algorithms I should check out?

• What’s the actual goal? To maximize the number of Simpsons made? To maximize the number of different Simpsons made? To minimize the number of unused bricks? To enumerate all maximal sets of Simpsons that can be made? – Brian M. Scott Apr 10 '12 at 23:23
• Actually, there is not a concrete goal. However I would say that it is preferred to minimize the number of unused bricks. – hansdam Apr 11 '12 at 6:57

You have seven colors of blocks, say colors $1$ through $7$; the input consists of $c_k$ blocks of color $k$ for some constants $c_k\ge 0$. You have five types of output (Simpsons), which I will number $1$ through $5$ in the order in which they appear in this image. If the colors are numbered yellow $(1)$, white $(2)$, light blue $(3)$, dark blue $(4)$, green $(5)$, orange $(6)$, and red $(7)$, the five output types require colors $(1,2,3),(4,1,5),(1,6,4),(1,7,1)$, and $(1,3)$. To make $x_k$ Simpsons of type $k$ for $k=1,\dots,5$ requires \begin{align*} x_1+x_2+x_3+2x_4+x_5&\text{blocks of color }1,\\ x_1&\text{blocks of color }2,\\ x_1+x_5&\text{blocks of color }3,\\ x_2+x_3&\text{blocks of color }4,\\ x_2&\text{blocks of color }5,\\ x_3&\text{blocks of color }6,\text{ and}\\ x_4&\text{blocks of color }7\;. \end{align*}
\left\{\begin{align*} x_1+x_2+x_3+2x_4+x_5&\le c_1\\ x_1&\le c_2\\ x_1+x_5&\le c_3\\ x_2+x_3&\le c_4\\ x_2&\le c_5\\ x_3&\le c_6\\ x_4&\le c_7\;. \end{align*}\right.\tag{1}
Let $b=c_1+c_2+\dots+c_7$, the total number of blocks, and let $$f(x_1,x_2,\dots,x_7)=\sum_{k=1}^7 x_k\;,$$ the number of blocks used. You want to maximize $f(x_1,\dots,x_7)$ subject to the constraints in $(1)$ and the requirement that the $x_k$ be non-negative integers.