Roc*_*off 30 image-manipulation image image-processing lego
背景
乐高生产X-Large灰色底板,这是一块大型建筑板材,宽48铆钉,高48铆钉,总面积为2304铆钉.作为一个乐高狂热者,我模仿了一些马赛克风格的设计,可以放在这些基板上,然后挂在墙上或显示器上(参见:Android,Dream Theatre,The Galactic Empire,Pokemon).
挑战
我现在面临的挑战是获得购买这些设计的最低成本.购买2304个单独的1x1板可能会变得昂贵.使用BrickLink,本质上是乐高的eBay,我可以找到数据来确定给定颜色最便宜的部件.例如,0.10美元(或每个螺柱0.025美元)的1x4板块比2.16美元(或每个螺柱0.06美元)的6x6板块便宜.我们还可以确定可用于组装图像的所有可能印版的列表:
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
问题
对于这个问题,让我们假设我们有一个列表,包括所有印版,颜色,以及每个印版的"重量"或成本.为了简单起见,我们甚至可以删除角落部分,但这将是一个有趣的挑战.您如何找到最便宜的组件来创建48x48图像？您如何找到使用最少组件的解决方案(不一定是最便宜的)？如果我们要将角落件添加为允许件,您将如何解释它们？
我们可以假设我们有一些通过查询BrickLink获得的主列表,获得给定颜色的给定砖的平均价格,并将其添加为列表中的元素.因此,没有黑色16x16板只是因为它不是制造或出售.然而,16x16 Bright Green板块的价值为3.74美元,按当前可用的平均价格计算.
我希望我对这个问题的记录足够简单.这是我几天来一直在考虑的事情,我很好奇你们的想法.我将其标记为"面试问题",因为它具有挑战性,不是因为我通过面试得到了它(尽管我认为这是一个有趣的问题!).
编辑
这是2x2角件和4x4角件的链接.答案不一定需要考虑颜色,但它应该可以扩展以涵盖该场景.情况是并非所有的印版都有各种颜色可供选择,所以想象一下,我们有一系列元素可以识别印版,颜色以及该印版的平均成本(下面是一个例子).感谢本杰明提供赏金!
1x1|white|.07
1x1|yellow|.04
[...]
1x2|white|.05
1x2|yellow|.04
[...]
此列表没有条目:
8x8|yellow|imaginarydollaramount
这是因为不存在8x8黄板.列表本身是微不足道的,只应被视为为解决方案提供参考; 它不会影响解决方案本身.
EDIT2
为了清楚起见改变了一些措辞.
卡尔的方法基本上是合理的,但可以使用更多细节.它会找到最优的成本解决方案,但对某些输入来说太慢了.大型开放区域尤其会有太多的天真搜索可能性.
无论如何,我在这里用C++快速实现了:http: //pastebin.com/S6FpuBMc
它解决了填充空白空间(时期),使用4种不同的砖块:
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
因此,算法填充给定区域.它是递归的(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
}
一旦我们找出填充子区域的最便宜的方法,我们将缓存结果.为了非常有效地识别子区域,我们将使用Zobrist散列使用64位整数.警告:哈希冲突可能导致错误的结果.一旦我们的例程返回,我们就可以根据缓存的值重建最优解.
优化: 在该示例中,探索了41936个节点(递归调用)(从上到下搜索空方块).但是,如果我们从左到右搜索空方块,则会探索约900,000个节点.
对于大型开放区域:我建议找到最具成本效益的部件,并将该部件作为预处理步骤填充许多开放区域.另一种技术是将图像划分为几个区域,并分别优化每个区域.
祝好运!我将在3月26日之前无法使用,所以希望我没有错过任何东西!
| 归档时间： |
|
| 查看次数： |
1528 次 |
| 最近记录： |