When manufacturing chips, circular silicon wafers are cut into dies of needed size:
The goal of this challenge is maximizing the number of whole dies that can be cut from a wafer of a given diameter.
The machine puts the wafer into an angular compartment:
_____________________ | xxxxxx | xxxxxxxxxxxx | xxxxxxxxxxxxxx |xxxxxxxxxxxxxxxx |xxxxxxxxxxxxxxxx | xxxxxxxxxxxxxx | xxxxxxxxxxxx | xxxxxx (this ascii art is meant to be a perfect circle)
It measures a distance
dx from the left edge, and makes a vertical cut. Then it makes the needed number of additional vertical cuts, with spacing of the needed
width. It makes the horizontal cuts in the same way: first one at a distance
dy, and then with spacing of
The material remains perfectly still during the cutting: it's not allowed to move some slices of material before making the perpendicular cuts.
The machine has a stepper motor that works at absolute accuracy but can only go integer-sized distances.
Make a program or a subroutine that gets (or reads) the following parameters:
and outputs (or prints)
dx- horizontal starting position
dy- vertical starting position
such that the number of rectangular dies is maximal.
Some fine points:
- If a corner of a die lies exactly on the circumference of the circle, the die is considered usable (rectangular)
- No edge cases: you can assume that the wafer's diameter is even; at least one die can be cut out; also make other reasonable assumptions
- All sizes are integer numbers of millimeters; maximum wafer diameter is 450
Shortest code wins!
P.S. The code must finish running in a reasonable amount of time, e.g. over a weekend (2 days) - for wafer diameter equal to 300.
P.P.S. If there are several different output values that are optimal, the code must output one of them - no need to output all of them!
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
Here is a visualization of the last test case: