<p>A delivery company wants to build a new service center in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new center in a position such that <strong>the sum of the euclidean distances to all customers is minimum</strong>.</p>

<p>Given an array <code>positions</code> where <code>positions[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> is the position of the <code>ith</code> customer on the map, return <em>the minimum sum of the euclidean distances</em> to all customers.</p>

<p>In other words, you need to choose the position of the service center <code>[x<sub>centre</sub>, y<sub>centre</sub>]</code> such that the following formula is minimized:</p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/25/q4_edited.jpg" />
<p>Answers within <code>10<sup>-5</sup></code> of the actual value will be accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/25/q4_e1.jpg" style="width: 377px; height: 362px;" />
<pre>
<strong>Input:</strong> positions = [[0,1],[1,0],[1,2],[2,1]]
<strong>Output:</strong> 4.00000
<strong>Explanation:</strong> As shown, you can see that choosing [x<sub>centre</sub>, y<sub>centre</sub>] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/06/25/q4_e3.jpg" style="width: 419px; height: 419px;" />
<pre>
<strong>Input:</strong> positions = [[1,1],[3,3]]
<strong>Output:</strong> 2.82843
<strong>Explanation:</strong> The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= positions.length &lt;= 50</code></li>
	<li><code>positions[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 100</code></li>
</ul>

import sys 
import random



class Solution:
    def getDist(self, pos1, pos2):
        dist = sqrt((pos1[0] - pos2[0])**2 + (pos1[1]-pos2[1])**2)
        # print('dist is: {0}'.format(dist))
        return dist

    def getMinDistSum(self, positions: List[List[int]]) -> float:

        # # Gradient descent: 
        # # 1) Pick a starting point (maybe average of positions?)
        # # 2) Wiggle x and y, choose optimal orientation
        # # 3) Descend by some small step size
        # # 4) Stop once the increments have reduced to a small amount

        # # Parameters
        # delta = 1

        # # 1)
        # sum_x = sum(x for x, y in positions)
        # sum_y = sum(y for x, y in positions)
        
        # prev_lowest_dist = 10000000
        # cur_pos = [sum_x / len(positions), sum_y / len(positions)]
        # wiggles = [[0,delta],[0,-1*delta],[delta,0],[-1*delta,0]]
        # cur_lowest_distance = 100000
        # # 2)
        # while delta > 10e-6:
        #     optimal_wiggle = 1000000
        #     for i,wiggle in enumerate([[0,delta],[0,-1*delta],[delta,0],[-1*delta,0]]):
        #         new_pos = [cur_pos[0] + wiggle[0], cur_pos[1] + wiggle[1]]
        #         # print('pos is {0}'.format(cur_pos))
        #         # print('wiggles pos is {0}'.format(new_pos))
        #         cur_dist = sum([self.getDist(new_pos, customer) for customer in positions])
        #         if cur_dist < optimal_wiggle:
        #             optimal_wiggle = cur_dist
            
        #     prev_lowest_dist = cur_lowest_distance
        #     cur_lowest_distance = optimal_wiggle
        #     cur_pos = new_pos
        #     delta /= 2
        #     print('prev_lowest_dist = {0}, cur_lowest_dist = {1}, optimal_wiggle = {2}'.format(prev_lowest_dist, cur_lowest_distance, optimal_wiggle))
        
        # return optimal_wiggle





        # BELOW IS SAMPLING IMPLEMENTATION, TRYING GRADIENT DESCENT ABOVe
        if len(positions) == 1:
            return 0
        elif all(x == positions[0] for x in positions):
            return 0
        # We want to try and find the minimized distance
        # 1) Get an array of sample points
        # 2) Get sum of eucledian distances for each sample
        # 3) Pick smallest sample point, and "zoom" in
        # 4) Repeat until difference between current and past sample point is < 10^-5

        # Parameters
        one_dimension_sample_points = 57 # The real number is this ^2
        zoom_in_fraction = 0.07 # amount that we scale down at each go, this is a one-way zoom

        # 4)
        prev_sample = [-2,-2]
        cur_sample = [-1,-1]
        x_bounds = [min([p[0] for p in positions]), max([p[0] for p in positions])]
        y_bounds = [min([p[1] for p in positions]), max([p[1] for p in positions])]

        while self.getDist(prev_sample, cur_sample) > 10e-6:
            #1) 
            delta_x = (x_bounds[1] - x_bounds[0]) / one_dimension_sample_points
            delta_y = (y_bounds[1] - y_bounds[0]) / one_dimension_sample_points

            samples = []
            for x in range(one_dimension_sample_points):
                for y in range(one_dimension_sample_points):
                    samples.append([x_bounds[0]+x*delta_x, y_bounds[0]+y*delta_y])

            # 2) 
            closest_sample = [-1, -1]
            smallest_dist = sys.float_info.max
            for sample in samples:
                
                cur_dist = sum([self.getDist(sample, customer) for customer in positions])
                # print('CHECK dist for {0}, sum is {1}'.format(sample, cur_dist))
                if cur_dist < smallest_dist:
                    smallest_dist = cur_dist
                    closest_sample = sample
            print('closest sample is: {0} at dist of {1}'.format(closest_sample, smallest_dist))        


            # 4) Reset the samples
            prev_sample = cur_sample
            cur_sample = closest_sample

            # 2.5) Add in a bit of randomness so as to make the solution more resiliant 
            # 3) zoom in time
            x_spread = zoom_in_fraction*(x_bounds[1] - x_bounds[0])
            y_spread = zoom_in_fraction*(y_bounds[1] - y_bounds[0])
            # Reset the bounds
            x_bounds[0] = closest_sample[0] + (random.random() - 0.5)*10e-5 - x_spread
            x_bounds[1] = closest_sample[0] + (random.random() - 0.5)*10e-5 + x_spread
            y_bounds[0] = closest_sample[1] + (random.random() - 0.5)*10e-5 - y_spread
            y_bounds[1] = closest_sample[1] + (random.random() - 0.5)*10e-5 + y_spread

            


        return smallest_dist



        # # Naive:
        # # - full sweep of all possible locations. Would be O(N*X) where X is all possible locations; X will be very large because of the specificity required.

        # # Slightly better:
        # # - Granular sweep. This will randomly sample points throughout the grid, and will then focus on the areas with the lowest point, zoom in, resample, etc.. until we get to the desired granularity.
        # # - This would probably work, but can fall into local minima and not capure the absolute minima. I dont *think* this is a big concern because the gradianet map is continuous and the number of customers is small, so as long as we choose enough sample sizes, we should be ok.
        # # - This will also be complicated to implement, and may require tuning.

        # # Another idea: gradient descent (similar to ML)
        # # - wiggle the position, and travel into the area with the largest loss gain.
        # # - Pretty similar to the above idea, but probably requires more tuning and is more complicated to implement.

        # # Let's try the sampling idea.

17400