Problem Statement
In the design of integrated circuits, we frequently have to connect several points with wires. All wires travel either horizontally (the X direction) or vertically (the Y direction). Write a method to determine the minimum total length of wire needed to connect a group of points; note that we can sometimes reduce the connection length by adding additional points.
For two points at (3, 0) and (5, 7), we would need a total of 9 units of wire to connect them. A wire could travel horizontally for 2 units, turn, and then travel vertically for another 7 units. There are actually many different ways to connect these points using 9 units of wire; an alternate connection could go vertically first.
For three points at (0, 0), (3, -8), and (5, 7), we would need a total of 20 units: a wire from (0, 0) to (3, 0), a wire from (3, 0) to (3, -8), and a wire from (3, 0) to (5, 7). These wires have lengths of 3, 8, and 9, respectively. Note that the point (3, 0) is not one of the three original points. As with the example above, there are several ways for the wire from (3, 0) to (5, 7) to travel, each with a length of 9.
Create a class ChipWire that has a method length that takes a
Definition
- Class:
- ChipWire
- Method:
- length
- Parameters:
- int[], int[]
- Returns:
- int
- Method signature:
- int length(int[] x, int[] y)
- (be sure your method is public)
Constraints
- x will contain between 0 and 5 elements inclusive
- y will contain between 0 and 5 elements inclusive
- x and y will contain the same number of elements
- each element of x will be between -10000 and 10000 inclusive
- each element of y will be between -10000 and 10000 inclusive
Examples
{3, 5}
{0,7}
Returns: 9
This is the first example described above; there are many ways to connect these two points, all with a length of 9 units.
{0,3,5}
{0, -8, 7}
Returns: 20
This is the second example; an additional point at (3, 0) is added.
{0}
{4}
Returns: 0
Total length is zero; one point is trivially connected.
{0,3,6,7,8}
{0,-3,10,0,8}
Returns: 22
{0,5000,9000,10000}
{0,-5000, 1000, 1}
Returns: 16000
{10,20,30,40,50}
{10,20,30,40,50}
Returns: 80
{523,409,9943,1029,5594}
{303,-2000,4059,5599,3021}
Returns: 18171
{3929,2222,1030,9944,2329}
{9329,1029,-9992,1098,5402}
Returns: 29835
{3392,1194,-4944,10000,2933}
{-9999,4030,-444,1929,9333}
Returns: 36474
{9933,-232,1023,4429,111}
{53,999,-43,1021,-988}
Returns: 13216
{10,20,30,40,40}
{20,20,20,20,20}
Returns: 30
The points need not be unique.
{}
{}
Returns: 0
It takes no wire to connect an empty set of points.
{-9608,2480,-8641,1859,4358}
{-1592,-5855,2114,952,9153}
Returns: 32680
{2,1,5,1,4}
{4,0,8,7,0}
Returns: 15
{0,5,9,10}
{0,-5, 1, 0}
Returns: 16
{0,0,5,10,10}
{0,10,5,0,10}
Returns: 30
{10000,10000,-10000,-10000,0}
{10000,-10000,10000,-10000,0}
Returns: 60000
{ 0, 3, 6, 7, 8 }
{ 0, -3, 10, 0, 8 }
Returns: 22
{ -9999, 3050, 6343, -7553, 8000 }
{ 5345, 3234, 6555, 9999, -9999 }
Returns: 41318
{ 5816, 2976, -8, 1986, 1345 }
{ -10000, 1112, -1111, 5, 1345 }
Returns: 18800
{ -10000, -10000, 9999, 10000, 10000 }
{ 9999, 10000, -10000, -10000, 10000 }
Returns: 40002
{ -3, 0, 2, 3, -1 }
{ 0, 0, 2, 0, -1 }
Returns: 9
{ 0, 3, 6, 7, 8 }
{ 0, -3, 10, 0, 8 }
Returns: 22
{ -9999, 3050, 6343, -7553, 8000 }
{ 5345, 3234, 6555, 9999, -9999 }
Returns: 41318
{ 5816, 2976, -8, 1986, 1345 }
{ -10000, 1112, -1111, 5, 1345 }
Returns: 18800
{ -10000, -10000, 9999, 10000, 10000 }
{ 9999, 10000, -10000, -10000, 10000 }
Returns: 40002
{ -3, 0, 2, 3, -1 }
{ 0, 0, 2, 0, -1 }
Returns: 9
{ 0, 3, 6, 7, 8 }
{ 0, -3, 10, 0, 8 }
Returns: 22
{ -9999, 3050, 6343, -7553, 8000 }
{ 5345, 3234, 6555, 9999, -9999 }
Returns: 41318
{ 5816, 2976, -8, 1986, 1345 }
{ -10000, 1112, -1111, 5, 1345 }
Returns: 18800
{ -10000, -10000, 9999, 10000, 10000 }
{ 9999, 10000, -10000, -10000, 10000 }
Returns: 40002
{ -3, 0, 2, 3, -1 }
{ 0, 0, 2, 0, -1 }
Returns: 9