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?

Thank you in advance for any help you can provide.

  • $\begingroup$ 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? $\endgroup$ – Brian M. Scott Apr 10 '12 at 23:23
  • $\begingroup$ Actually, there is not a concrete goal. However I would say that it is preferred to minimize the number of unused bricks. $\endgroup$ – hansdam Apr 11 '12 at 6:57

The problem of minimizing the number of unused blocks is an integer linear programming problem, equivalent to maximizing the number of blocks that you do use. Integer programming problems are in general hard, and I don’t know much about them or the methods used to solve them. In case it turns out to be at all useful to you, though, here’s a more formal description of the problem of minimizing the number of unused blocks.

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*}$$

This yields the following system of inequalities:

$$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.