Desafío: tome una imagen de 48x48, encuentre áreas contiguas que resulten en la solución de Lego más económica para crear esa imagen.
image-processing image-manipulation (4)
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 posibles piezas (incluir 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 la placa por área.
Ahora tenemos una enorme colección de piezas posibles, limitadas porque se garantiza que un subconjunto de esta colección llenará por completo la pizarra.
Luego se convierte en un problema de subconjunto, que es NP-Completo.
Resolviendo 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, al ser un algoritmo O (2 ^ n), la poda temprana del árbol de búsqueda es de suma importancia. Las optimizaciones deben hacerse temprano para evitar carreras de 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 sueltas.
Por lo tanto, el 99% del árbol de búsqueda debe ser podado de los primeros cientos pliegues para que este algoritmo se complete en cualquier momento. Por ejemplo, mantenga un recuento de la solución de menor costo encontrada hasta ahora, y simplemente deje de buscar todas las capas inferiores y retroceda siempre que el costo actual más (el número de posiciones de la placa vacía x el costo promedio más bajo para cada color)> solución actual de menor costo.
Por ejemplo, optimice aún más privilegiando siempre las piezas más grandes (o las piezas de costo promedio más bajas) en primer lugar, a fin de reducir la solución de menor costo inicial lo más rápido posible y podar la mayor cantidad posible de casos futuros.
Encontrar el más barato
Calcule el costo de cada solución, ¡encuentre la más barata!
Comentarios
Este algoritmo es genérico. No supone que una pieza sea del mismo color (¡puede tener piezas multicolores!). No supone que una pieza grande sea más barata que la suma de piezas más pequeñas. Realmente no asume nada.
Si se pueden hacer algunas suposiciones, esta información se puede usar para podar aún más el árbol de búsqueda lo antes posible. Por ejemplo, cuando se usan piezas de un solo color, puede podar grandes secciones del tablero (con los colores incorrectos) y podar gran cantidad de piezas en el conjunto (del color incorrecto).
Sugerencia
No intente hacer 48x48 a la vez. Pruébalo en algo pequeño, por ejemplo, 8x8, con un conjunto razonablemente pequeño de piezas. A continuación, aumente progresivamente el número de piezas y el tamaño de la tabla. Realmente no tengo idea de cuánto durará el programa, ¡pero me encantaría que alguien me lo dijera!
Fondo
Lego produce la placa de base gris X-Large , que es una placa de construcción grande que tiene 48 pernos de ancho y 48 pernos de altura, lo que da como resultado un área total de 2304 pernos. Siendo un fanático de Lego, he modelado algunos diseños de estilo mosaico que pueden colocarse en estas bases y luego colgarse en las paredes o en una pantalla (ver: Android , Dream Theater , The Galactic Empire , Pokemon ).
El reto
Mi desafío ahora es obtener el costo más bajo para comprar estos diseños. Comprar 2304 placas individuales de 1x1 puede ser costoso. Usando BrickLink , esencialmente un eBay para Lego, puedo encontrar datos para determinar cuáles son las piezas más baratas para colores dados. Por ejemplo, una placa de 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, su color (es) y un "peso" o costo para cada plato. En aras de la simplicidad, incluso podemos eliminar las piezas de la esquina, pero sería un desafío interesante de abordar. ¿Cómo encontraría los componentes más baratos para crear la imagen 48x48? ¿Cómo encontraría la solución que utiliza la menor cantidad de componentes (no necesariamente el más barato)? Si tuviéramos que agregar piezas de esquina como piezas permitidas, ¿cómo las contabilizarías?
Podemos suponer que tenemos una lista maestra que se obtiene al consultar BrickLink, obtener el precio promedio de un ladrillo dado en un color determinado y agregarlo como un elemento en la lista. Por lo tanto, no habría una placa negra de 16x16 simplemente porque no está hecha o en venta. Sin embargo, la placa de color verde brillante de 16x16 tendría un valor de $ 3.74, según el precio promedio actual disponible .
Espero que mi redacción del problema sea lo suficientemente sucinta. Es algo en lo que he estado pensando durante algunos días, y siento curiosidad por lo que ustedes piensan. Lo etiqueté como "preguntas de la entrevista" porque es un desafío, no porque lo obtuve en una entrevista (¡aunque creo que sería una pregunta divertida!).
EDITAR
Aquí hay un enlace a la esquina de 2x2 y a la pieza de esquina 4x4 . La respuesta no necesita necesariamente tener en cuenta el color, pero debe ser ampliable para cubrir ese escenario. El escenario sería que no todas las placas están disponibles en todos los colores, así que imaginemos que tenemos una serie de elementos que identifican una placa, su color y el costo promedio de esa placa (un ejemplo es más abajo). ¡Gracias a Benjamin por proporcionarnos 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 una placa amarilla de 8x8 no existe. La lista en sí es trivial y solo debe considerarse como una referencia para la solución; no impacta la solución en sí misma.
EDIT2
Cambió algunas palabras para mayor claridad.
El enfoque de Karl es básicamente el sonido, pero podría usar algunos detalles más. Encontrará la solución de costo óptimo, pero será demasiado lenta para ciertas entradas. 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 llenar el 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 dada. 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 económica de llenar un subárea, guardaremos el resultado en caché. Para identificar de manera muy eficiente una subárea, usaremos un entero de 64 bits usando hash de Zobrist . Advertencia: las colisiones hash pueden causar resultados incorrectos. Una vez que nuestra rutina regrese, podemos reconstruir la solución óptima en base a nuestros valores en caché.
Optimización: en el ejemplo, se exploran 41936 nodos (llamadas recursivas) (buscando el 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: sugiero encontrar la pieza más rentable y rellenar gran parte del área abierta con esa pieza como 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 no haberme perdido nada!
Mi solución será:
- Clasifica todas las piezas por costo de perno.
- Para cada pieza de la lista ordenada, intente colocar tantas como pueda en el plato:
- Cree una imagen bidimensional de su diseño en busca de regiones de la imagen con un color uniforme, la forma de la pieza actual y pernos libres para cada perno que la pieza utilizará.
- Si el color de la región encontrada no existe para esa pieza en particular, ignore una búsqueda continua.
- Si el color existe: etiquete los postes utilizados por esas piezas e incremente un contador para ese tipo de pieza y ese color.
- El paso 2 se realizará una vez para piezas cuadradas, dos para piezas rectangulares (una vez verticales y una vez horizontales) y 4 veces para piezas de esquina.
- Itere a 2 hasta que el plato esté lleno o no haya más tipos de piezas disponibles.
Una vez que llegue al final, tendrá la cantidad de piezas de cada tipo y color que necesita con un costo mínimo.
Si el costo por talones puede cambiar por color, entonces la lista ordenada original debe incluir no solo el tipo de pieza por el color.
Primero usa el relleno de inundación para dividir el problema en el llenado de regiones continuas de ladrillos lego. Luego, para cada uno de ellos, puede usar un archivo dfs con memoria que desee. El relleno de inundación es trivial, así que no lo describiré más.
Asegúrese de seguir una regla de la mano derecha mientras expande el árbol de búsqueda para no repetir estados.