Desafío: tome una imagen de 48x48, encuentre áreas contiguas que resulten en la solución LEGO más barata para crear esa imagen. [cerrado

Question

Fondo

LEGO produce el Placa base gris de larga duración, que es una gran placa de construcción que tiene 48 espárragos de ancho y 48 tachuelas de alto, lo que resulta en un área total de 2304 tachuelas. Al ser un fanático de LEGO, modelé algunos diseños de estilo mosaico que se pueden poner en estas placas de base y luego quizás colgar en las paredes o en una pantalla (ver: Androide, Teatro de ensueño, El imperio galáctico, Pokemon).

El reto

Mi desafío ahora es obtener el menor costo para comprar estos diseños. La compra de 2304 placas individuales 1x1 puede ser costosa. Usando Ladrillo, esencialmente un eBay para LEGO, puedo encontrar datos para determinar cuáles son las partes más baratas para los colores dados. Por ejemplo, una placa 1x4 a $ 0.10 (o $ 0.025 por perno) sería más barata que una placa de 6x6 a $ 2.16 (o $ 0.06 por perno). También podemos determinar una lista de todas las placas posibles que se pueden usar para ensamblar una imagen:

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

El problema

Para este problema, supongamos que tenemos una lista de todas las placas, sus color (s) y un "peso" o un costo para cada plato. En aras de la simplicidad, incluso podemos eliminar las piezas de la esquina, pero ese sería un desafío interesante de abordar. ¿Cómo encontrarías los componentes más baratos para crear la imagen 48x48? ¿Cómo encontrarías la solución que usa la menor cantidad de componentes (no necesariamente los más baratos)? Si tuviéramos que agregar piezas de esquina como piezas permitidas, ¿cómo explicaría ellas?

Podemos suponer que tenemos una lista maestra que se obtiene consultando Bricklink, obteniendo el precio promedio de un ladrillo determinado en un color determinado y lo agregó como un elemento en la lista. Por lo tanto, no habría una placa negra de 16x16 simplemente porque no está hecha ni a la venta. La placa verde brillante de 16x16, sin embargo, tendría un valor de $ 3.74, pasando por el precio promedio actual disponible.

Espero que mi redacción del problema sea suficiente. Es algo en lo que he estado pensando durante unos días, y tengo curiosidad sobre lo que piensan ustedes. Lo etiqueté como "preguntas de entrevista" porque es desafiante, no porque lo obtuve a través de una entrevista (¡aunque creo que sería una pregunta divertida!).

EDITAR

Aquí hay un enlace al Pieza de esquina 2x2 y al Pieza de esquina 4x4. La respuesta no necesariamente necesita tener en cuenta el color, pero debe ser expandible cubrir ese escenario. El escenario sería que no todas las placas están disponibles en todos los colores, así que imagine que tenemos una variedad de elementos que identifican una placa, su color y el costo promedio de esa placa (un ejemplo está debajo). ¡Gracias a Benjamin por proporcionar una recompensa!

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

Esta lista no tendría la entrada:

8x8|yellow|imaginarydollaramount

Esto se debe a que no existe una placa amarilla de 8x8. La lista en sí es trivial y solo debe considerarse como proporcionar referencias para la solución; No afecta la solución en sí.

Edición2

Cambió algunas redacción para claridad.

Answer 1

El enfoque de Karl es básicamente sólido, pero podría usar más detalles. Encontrará la solución de costo óptima, pero será demasiado lenta para ciertas entradas. Las grandes áreas abiertas especialmente tendrán demasiadas posibilidades para buscar ingenuamente.

De todos modos, hice una implementación rápida en C ++ aquí: http://pastebin.com/s6fpubmc

Resuelve el relleno del espacio vacío (períodos), con 4 tipos diferentes de ladrillos:

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

Entonces, el algoritmo llena un área determinada. Es recursivo (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
}

Una vez que descubramos la forma más barata de llenar un subárea, almacenamos en caché el resultado. Para identificar de manera muy eficiente un subárea, usaremos un entero de 64 bits usando Zobrista hash. Advertencia: las colisiones hash pueden causar resultados incorrectos. Una vez que nuestra rutina regresa, podemos reconstruir la solución óptima basada en nuestros valores en caché.

Optimización:En el ejemplo, se exploran 41936 nodos (llamadas recursivas) (buscando un cuadrado vacío de arriba a abajo). Sin embargo, si buscamos cuadrados vacíos de izquierda a derecha, se exploran ~ 900,000 nodos.

Para grandes áreas abiertas: Sugeriría encontrar la pieza más rentable y completar una gran cantidad de área abierta con esa pieza como un paso previo al proceso. Otra técnica es dividir su imagen en algunas regiones y optimizar cada región por separado.

¡Buena suerte! No estaré disponible hasta el 26 de marzo, ¡así que espero que no me pierda nada!

Answer 2

Pasos

Paso 1: iterar a través de todas las soluciones.

Paso 2: Encuentra la solución más barata.

Crear inventario de piezas

Para una variedad de piezas posibles (incluya piezas individuales de cada color), haga al menos n duplicados de cada pieza, donde n = max (tablero#/pieza# de cada color). Por lo tanto, a lo sumo, N de esa pieza puede cubrir todos los colores de toda la tabla por área.

Ahora tenemos una gran colección de posibles piezas, limitadas porque se garantiza que un subconjunto de esta colección llenará por completo el tablero.

Luego se convierte en un problema de subconjunto, que es NP-complete.

Resolver el problema del subconjunto

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)

Optimizaciones

Obviamente, ser un algoritmo O (2^n), la poda del árbol de búsqueda temprano es de suma importancia. Las optimizaciones deben hacerse temprano para evitar la larga duración. n es un número muy grande; Solo considere una placa de 48x48: tiene 48x48xc (donde C = número de colores) solo para piezas individuales solas.

Por lo tanto, el 99% del árbol de búsqueda debe ser podado de los primeros cientos de capas para que este algoritmo se complete en cualquier momento. Por ejemplo, mantenga un recuento de la solución de menor costo que se encuentra hasta ahora, y simplemente deje de buscar todas las capas inferiores y retroceda siempre que el costo actual (el número de posiciones vacías de la placa x costo promedio más bajo para cada color)> Solución actual de menor costo.

Por ejemplo, optimice aún más al favorecer siempre las piezas más grandes (o las piezas de costo promedio más bajo) primero, para reducir la solución de bajo costo de base lo más rápido posible y podar tantos casos futuros como sea posible.

Encontrar el más barato

Calcule el costo de cada solución, ¡encuentre el más barato!

Comentario

Este algoritmo es genérico. No asume que una pieza es del mismo color (¡puedes tener piezas multicolores!). No supone que una pieza grande es más barata que la suma de piezas más pequeñas. Realmente no asume nada.

Si se pueden hacer algunos supuestos, esta información se puede usar para podar más el árbol de búsqueda lo antes posible. Por ejemplo, cuando usa solo piezas de un solo color, puede podar grandes secciones del tablero (con los colores incorrectos) y podar una gran cantidad de piezas en el conjunto (del color incorrecto).

Sugerencia

No intente hacer 48x48 a la vez. Pruébelo en algo pequeño, digamos, 8x8, con un conjunto de piezas razonablemente pequeño. Luego aumente el número de piezas y el tamaño de la tabla progresivamente. Realmente no tengo idea de cuánto tiempo llevará el programa, ¡pero me encantaría que alguien me lo diga!

Answer 3

Primero usa el relleno de inundación para romper el problema en llenar regiones continuas de ladrillos LEGO. Luego, para cada uno de ellos, puede usar un DFS con memoización que desee. El relleno de inundación es trivial, por lo que no lo describiré más lejos.

Asegúrese de seguir una regla de la derecha mientras se expande el árbol de búsqueda para no repetir los estados.

Answer 4

Mi solución será:

1. Ordena todas las piezas por costo del semental.
2. Para cada pieza en la lista ordenada, intente colocar tantos como pueda en el plato:
   • Raster Una imagen 2D de su diseño en busca de regiones de la imagen con color uniforme, la forma de la pieza actual y los pernos gratuitos para cada perno que la pieza usará.
   • Si el color de la región que se encuentra no existe para esa pieza en particular, ignore una búsqueda de continuar.
   • Si el color existe: etiquete los espárragos utilizados por esas piezas e incrementa un mostrador para ese tipo de pieza y ese color.
   • El paso 2 se realizará una vez para piezas cuadradas, dos veces para piezas rectangulares (una vez verticales y una vez horizontales) y 4 veces para piezas de esquina.
3. Itera a 2 hasta que la placa esté llena o no hay más tipo de piezas disponibles.

Una vez llegando al final, tendrá la cantidad de piezas de cada tipo y cada color que necesitaba con un costo mínimo.

Si el costo de los trozos puede cambiar por color, entonces la lista ordenada original debe incluir no solo el tipo de pieza por el color.