Défi: Prenez une image 48x48, trouver des zones contigus qui se traduisent par la solution Lego la moins chère pour créer cette image!

Question

Arrière-plan

Lego produit de la X-Large Gris plaque de base, qui est un grand bâtiment de la plaque qui est de 48 crampons de large et 48 crampons de haut, résultant en une surface total de 2304 crampons. Être un Lego fanatique, j'ai modélisé un peu de mosaïque de style des dessins qui peuvent être mis sur ces plaques de base et puis peut-être accroché sur les murs ou dans un affichage (voir: Android, Dream Theater, L'Empire Galactique, Pokemon).

Le Défi

Mon défi, c'est maintenant pour obtenir le plus bas coût d'achat de ces modèles. Achat 2304 personne 1x1 plaques peuvent coûter cher. À l'aide de BrickLink, essentiellement, une boutique pour les Lego, je peux trouver des données pour déterminer ce que le moins cher des pièces pour les couleurs. Par exemple, un 1x4 plaque à 0,10 $(ou 0,025 $par stud) serait moins cher qu'un 6x6 plaque à $2.16 (ou 0,06 $par stud). Nous pouvons également déterminer une liste de toutes les plaques qui peuvent être utilisés pour assembler une 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

Le Problème

Pour résoudre ce problème, supposons que nous avons une liste de toutes les plaques, leur couleur(s), et un "poids" ou le coût pour chaque plaque. Par souci de simplicité, on peut même supprimer les pièces de coin, mais ce serait un défi intéressant à relever. Comment voulez-vous trouver le moins cher des composants pour créer le 48x48 image? Comment voulez-vous trouver la solution qui utilise le moins de composants (pas nécessairement le moins cher)? Si nous devions ajouter les pièces de coin, comme admissibles morceaux, comment voulez-vous de les prendre en compte?

Nous pouvons supposer que nous avons une certaine maîtrise liste qui est obtenu en interrogeant BrickLink, l'obtention de la moyenne des prix d'une brique dans une couleur donnée, et en ajoutant que comme un élément dans la liste. Donc, il n'y aurait pas noir 16 x 16 plaque simplement parce qu'il n'est pas fait ou pour la vente. Le 16x16 Vert Vif de la plaque, cependant, aurait une valeur de $3.74, en passant par le courant disponible prix moyen.

J'espère que mon écriture-up du problème est assez succinct. C'est quelque chose que j'ai pensé depuis quelques jours maintenant, et je suis curieux de savoir ce que vous en pensez. J'ai marqué comme "interview-questions" parce que c'est difficile, non pas parce que je l'ai eu grâce à une interview (même si je pense que ce serait un plaisir question!).

MODIFIER

Voici un lien vers la 2x2 coin de la pièce et à l' 4x4 coin de la pièce. La réponse n'a pas nécessairement besoin de prendre en compte la couleur, mais il doit être extensible pour couvrir ce scénario. Le scénario serait que pas toutes les plaques sont disponibles dans toutes les couleurs, imaginez donc que nous avons un tableau d'éléments qui permettent d'identifier une plaque, sa couleur, et le coût moyen de la plaque (un exemple ci-dessous). Merci à Benjamin pour fournir un bounty!

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

Cette liste n'aurait PAS l'entrée:

8x8|yellow|imaginarydollaramount

C'est parce qu'un 8x8 plaque jaune n'existe pas. La liste elle-même est trivial et ne doit être pensé comme fournissant des références pour la solution; il n'a pas d'incidence sur la solution elle-même.

EDIT2

Modifié le texte pour plus de clarté.

Answer 1

Karl approche est fondamentalement bonne, mais pourrait utiliser un peu plus de détails. Il va trouver le coût optimal de la solution, mais sera trop lent pour certaines entrées. Les grands espaces, en particulier aura aussi de nombreuses possibilités de recherche par le biais de la naïveté.

De toute façon, j'ai fait une rapide mise en œuvre en C++ ici: http://pastebin.com/S6FpuBMc

Il résout de remplissage dans l'espace vide (périodes), avec 4 différents types de briques:

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

Ainsi, l'algorithme remplit dans une zone donnée. Elle est récursive (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
}

Une fois que nous trouvions le moyen le moins cher pour remplir une sous-zone, nous allons mettre en cache le résultat. De façon très efficace d'identifier une sous-zone, nous allons utiliser un entier de 64 bits à l'aide de Zobrist de hachage. Avertissement: les collisions de hachage peut entraîner des résultats incorrects. Une fois notre routine renvoie, nous pouvons reconstruire la solution optimale basée sur nos valeurs mises en cache.

Optimisation: Dans l'exemple, 41936 nœuds (appels récursifs) sont explorées (recherche de la place vide, de haut en bas). Toutefois, si l'on recherche pour les cases vides de gauche à droite, ~de 900 000 nœuds sont explorées.

Pour les grands espaces ouverts: je vous suggère de trouver la plus coût-efficace de la pièce et de remplissage dans un lot de la zone ouverte avec ce morceau comme une pré-étape de processus. Une autre technique consiste à diviser votre image dans quelques régions, et d'optimiser chaque région séparément.

Bonne chance! Je vais être indisponible jusqu'au 26 Mars, donc j'espère que je n'ai pas manqué de rien!

Answer 2

Étapes

Étape 1: Itérer sur toutes les solutions.

Étape 2: Trouver la solution la moins chère.

Créer des pièces de l'inventaire

Pour un tableau de possibles morceaux (inclure les pièces uniques de chaque couleur), faire au moins n des doubles de chaque pièce, où n = max(conseil#/pièce# de chaque couleur). Donc, à la n de cette pièce peut couvrir la totalité de l'ensemble du conseil d'administration de couleurs par région.

Maintenant, nous avons une énorme collection de possibles morceaux, limité car il est garanti qu'un sous-ensemble de la collection de remplir complètement le conseil d'administration.

Puis il devient un sous-ensemble du problème, qui est NP-Complet.

Résoudre le problème sous-ensemble

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)

Optimisations

De toute évidence être un O(2^n) de l'algorithme, l'élagage de l'arbre de recherche précoce est de la plus haute importance. Optimisations doit être fait tôt pour éviter de longues. n est un nombre très grand; il suffit de considérer un 48x48 conseil -- vous avez 48x48xc (où c = nombre de couleurs) juste pour une seule pièce à lui seul.

Par conséquent, 99% de l'arbre de recherche doit être taillé à partir de la première quelques centaines de plis pour que cet algorithme afin de compléter en tout temps. Par exemple, de conserver un contrôle des coûts les plus bas de solution trouvée jusqu'à présent, et tout simplement arrêter la recherche à tous les plis et revenir en arrière à chaque fois que le coût actuel de plus (le nombre de vider les positions x les plus bas coût moyen pour chaque couleur) > actuel le plus bas coût de la solution.

Par exemple, optimiser encore, toujours en privilégiant les plus gros morceaux (ou le plus bas coût moyen de pièces) tout d'abord, afin de réduire le niveau de référence le plus bas coût de la solution le plus rapidement possible et de le tailler comme beaucoup de futurs cas possible.

Trouver le moins cher

Calculer le coût de chaque solution, trouver le moins cher!

Commentaires

Cet algorithme est générique. Il ne suppose pas une pièce est de la même couleur (vous pouvez avoir plusieurs couleur des pièces!). Il ne suppose pas qu'un grand morceau est moins cher que la somme de petites pièces. Il n'a pas vraiment d'assumer quoi que ce soit.

Si certaines hypothèses peuvent être faites, alors cette information peut être utilisée pour plus d'élaguer l'arbre de recherche le plus tôt possible. Par exemple, lors de l'utilisation d'une seule couleur des pièces, vous pouvez tailler de grandes sections du conseil d'administration (avec les mauvaises couleurs) et le pruneau grand nombre de pièces dans le set (de la bonne couleur).

Suggestion

Ne pas essayer de faire 48x48 à la fois. Essayez-le sur un petit quelque chose, disons, 8x8, avec un certain nombre réduit de pièces. Puis augmentez le nombre de pièces et la taille du conseil progressivement. Je n'ai vraiment aucune idée de combien de temps le programme prendra -- mais que serait l'amour pour quelqu'un de me le dire!

Answer 3

Tout d'abord, vous utilisez le remplissage des inondations pour briser le problème en remplissant les régions continues de briques lego. Ensuite, pour chacun de ceux que vous pouvez utiliser un dfs avec mémorisation que vous souhaitez. Le remplissage des inondations est trivial, donc je ne vais pas le décrire plus loin.

Assurez-vous de suivre une règle de la main droite tout en élargissant l'arbre de recherche pour ne pas répéter les états.

Answer 4

Ma solution:

1. Trier les pièces par goujon coût.
2. Pour chaque morceau dans la liste triée, essayez de placer autant que vous le pouvez dans l'assiette:
   • Raster 2D de l'image de votre conception, à la recherche pour les régions de l'image avec une couleur uniforme, la forme de la pièce courante et libre crampons pour chaque goujon que la pièce d'utilisation.
   • Si la couleur de la région n'existent pas pour cette pièce en particulier, ignorer un poursuivre la recherche.
   • Si la couleur n'existe: tag les clous utilisés par les pièces et incrémenter un compteur pour ce genre de pièce, et que la couleur.
   • Étape 2 sera effectué une fois par carré de pièces, deux pièces rectangulaires (une fois verticale et une fois à l'horizontale) et 4 fois pour les pièces de coin.
3. Itérer à 2 jusqu'à ce que la plaque est pleine ou pas plus de type de pièces sont disponibles.

Une fois arrivé à la fin vous aurez le nombre de pièces de chaque type et de chaque couleur que vous avez besoin, avec un coût minimum.

Si le coût par stubs pouvez changer la couleur, l'original de la liste triée doit comprendre non seulement le type de pièce, par la aussi la couleur.