将硅片切割成模具

Question

在制造芯片时，圆形硅片被切割成所需尺寸的模具：

这一挑战的目标是最大限度地提高从给定直径的晶圆中切割出的整个模具的数量。

这台机器把晶片放入一个有角的隔间：

_____________________
|     xxxxxx
|  xxxxxxxxxxxx
| xxxxxxxxxxxxxx
|xxxxxxxxxxxxxxxx
|xxxxxxxxxxxxxxxx
| xxxxxxxxxxxxxx
|  xxxxxxxxxxxx
|     xxxxxx     (this ascii art is meant to be a perfect circle)

它测量距离dx从左边缘，并作出垂直切割。然后，使用所需的width间距，进行所需的额外垂直切割。它以同样的方式进行水平切割:首先在距离dy，然后用height的间距。

材料在切割过程中保持完全静止:在进行垂直切割之前，不允许移动一些材料片。

该机器有一个步进电机，工作在绝对精确，但只能走整数大小的距离。

制作一个获得(或读取)下列参数的程序或子程序：

• 晶圆diameter
• 模具width
• 模具height

和输出(或打印)

• dx -水平起始位置
• dy -垂直起始位置

使得矩形模具的数量是最大的。

一些要点：

• 如果模具的角正好位于圆周上，则认为模具是可用的(矩形)。
• 没有边缘情况:你可以假设晶片的直径是均匀的；至少可以切出一个模具；也可以做其他合理的假设
• 所有尺寸均为毫米整数，最大晶片直径为450。

最短代码获胜！

代码必须在合理的时间内完成运行，例如在周末(2天)--晶片直径等于300。

如果有几个不同的输出值是最优的，代码必须输出其中的一个--不需要全部输出！

测试用例：

Wafer diameter 8, die size 2 x 2 => dx = 0, dy = 1 (6 dies)
Wafer diameter 20, die size 5 x 4 => dx = 1, dy = 2 (10 dies)
Wafer diameter 100, die size 12 x 12 => dx = 9, dy = 3 (41 dies)
Wafer diameter 300, die size 11 x 11 => dx = 7, dy = 7 (540 dies) - a realistic example
Wafer diameter 340, die size 15 x 8 => dx = 5, dy = 2 (700 dies) - a Pythagorean triple
Wafer diameter 300, die size 36 x 24 => dx = 2, dy = 6 (66 dies) - full-frame sensors

下面是最后一个测试用例的可视化：

Answer 1

Java，242

这是一个接受三个输入参数并返回包含dx和dy的最优值的字符串的方法。

String k(int d,int w,int h){int m=0,f=0,g=0,r=d/2,s=r*r+1,a,b,p=-1;while(++p<w)for(int q=-1;++q<h;)for(int x=p-r,c=0;(a=x+w)<r;x=a)for(int y=q-r;(b=y+h)<r;y=b)if(x*x+y*y<s&&a*a+b*b<s&&x*x+b*b<s&&a*a+y*y<s&&++c>m){m=c;f=p;g=q;}return f+" "+g;}

未高尔夫球：

String k(int diameter, int width, int height) {
    int
        maxDieCount = 0,
        bestDx = 0,
        bestDy = 0,
        radius = diameter / 2,
        radiusSquared = radius * radius;
    for (int dx = 0; dx < width; ++dx) {
        for (int dy = 0; dy < height; ++dy) {
            int dieCount = 0;
            for (int x1 = dx - radius; x1 + width < radius; x1 += width) {
                int x2 = x1 + width;
                for (int y1 = dy - radius; y1 + height < radius; y1 += height) {
                    int y2 = y1 + height;
                    if (    x1 * x1 + y1 * y1 <= radiusSquared &&
                            x2 * x2 + y2 * y2 <= radiusSquared &&
                            x1 * x1 + y2 * y2 <= radiusSquared &&
                            x2 * x2 + y1 * y1 <= radiusSquared )
                        ++dieCount;
                }
            }
            if (dieCount > maxDieCount) {
                maxDieCount = dieCount;
                bestDx = dx;
                bestDy = dy;
            }
        }
    }
    return bestDx + " " + bestDy;
}

非常简单的蛮力方法--尝试[0，宽度)中的每个dx和[0，高度]中的每个dy，然后循环遍历生成的网格中的每个矩形，检查所有四个角是否都在圆圈内(使用基本的pythagorean关系)，计算这些矩形的数量，并返回第一个dx和dy，为给定的配置生成最高的计数。

使用：(假设这两个方法都放在一个名为CG52148的类中)

public static void main(String[] args) {

    CG52148 o = new CG52148();
    System.out.println("8\t2\t2\t=> " + o.k(8, 2, 2));
    System.out.println("20\t5\t4\t=> " + o.k(20, 5, 4));
    System.out.println("100\t12\t12\t=> " + o.k(100, 12, 12));
    System.out.println("300\t11\t11\t=> " + o.k(300, 11, 11));
    System.out.println("340\t15\t8\t=> " + o.k(340, 15, 8));
    System.out.println("300\t36\t24\t=> " + o.k(300, 36, 24));

}

第三个测试用例生成0 8而不是9 3，但是它们都是有效的、同样最优的，并且都是由我的算法找到的。

Answer 2

Python2.7,317

这是我的解决办法。我想可以打得更高一点，但我更喜欢解决问题而不是打高尔夫。欢迎提出建议。

我用蛮力解决它，迭代所有的dx和dy，然后逐列计数。它运行得非常快(<0,05秒)。在我的Mac上)。

代码：

import math as m
def D(d,w,h):
 r=d/2
 s=[0,0,0]
 for dx in range(0,w):
  for dy in range(0,h):
   t=0
   for c in range(1,int(d/w)+1):
    l=r-dx-(c-1)*w
    if l<w/2:
     l-=w
    if abs(l)<=r:
     f=r*m.sin(m.acos(1.0*l/r));t+=int((2.0*f-(dy+m.ceil((r-dy-f)/h)*h+f-r))/h)
   if t>s[0]:
    s=[t,dx,dy]
 return s

A主要用于测试和描述给定的案例：

def runTestcases():
    for d,w,h in [[8,2,2],[20,5,4],[100,12,12],[300,11,11],[340,15,8],[300,36,24]]:
        S=D(d,w,h)
        print "Wafer diameter {}, die size {} x {} => dx = {}, dy = {} ({} dies)".format(d,w,h,S[1],S[2],S[0])

def main():
    import cProfile
    cProfile.run("runTestcases()")

if __name__ == "__main__":
    main()

及其产出：

Wafer diameter 8, die size 2 x 2 => dx = 0, dy = 1 (6 dies)
Wafer diameter 20, die size 5 x 4 => dx = 1, dy = 2 (10 dies)
Wafer diameter 100, die size 12 x 12 => dx = 0, dy = 8 (41 dies)
Wafer diameter 300, die size 11 x 11 => dx = 7, dy = 7 (540 dies)
Wafer diameter 340, die size 15 x 8 => dx = 5, dy = 2 (700 dies)
Wafer diameter 300, die size 36 x 24 => dx = 2, dy = 6 (66 dies)
         55354 function calls in 0.049 seconds