MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn moreOpportunities for recent engineering grads.

Apply TodayThis Challenge is derived from GJam 2014 China Party. Small Case.

The Goal is determine the optimal Party House. Given a set of people to attend a party, select the home from this set that minimizes the total travel of people. People travel only NSEW, no diagonals, to reach the host's home. If multiple homes have equal distance then select the home with minimum X. If there are more than one with Min distance and equal Min X then choose the house with Min Y.

The input is an array that defines rectangles of partiers. One line of the array is [xmin,ymin,xmax,ymax]. Blocks do not overlap.

**Input:** [M], Bx4 matrix (B<=100). Total B area of <=1000

**Output:** [x,y,d] where [x,y] is Party House and d is everyone's total distance

**Examples:**

M [x y d] [0 0 2 2] [1 1 12] [-1 2 -1 2;0 0 0 0;1 3 1 3] [-1 2 6]

**Contest Performance:** Best Delta Time of 16 minutes with 496 of 2010 able to process the small data set. The large data set was only achieved by 47 in the 3 hrs of contest duration.

**Commentary:**

1) The small can be solved by brute force since fewer than 1000 points require evaluation. 2) The large case, which is giving me fits, has up to 1,000,000 points to evaluate. 3) Graphing the small case with surf gives some unexpected asymmetric results relative to the simple centroid.

12 correct solutions
1 incorrect solutions

Last solution submitted on Oct 20, 2013

1 Comment

Tim
on 18 Oct 2013

This one seems to work for the large test case, too, although it is not a general solution [for size(p,1)>100 it only tests corner points].

1 Comment