We're trying to solve this problem:
Reddit is so successful online, that it has decided to open an offline kiosk for people to get their physical front page of the internet - now we just need to decide where to build it. Fortunately we have already located the perfect city to put our first test kiosk, and like all cities, it happens to be a perfect grid. We also happen to know the locations of all of our happy customers as intersections on the grid. Given this customer data, what is the best place to put our kiosk?
Here is an ascii grid demonstrating this problem. Streets are lines, and locations of customers are smiley faces. The asterisk is an example place for a kiosk on the grid.
0 1 2 3 4 5 6 7 8
0+--+--+--+--+--+--+--+--+
| | | | | | | | |
1+--+--+--+--+--+--+--+--+
| | | | | | | | |
2+--+--☻--+--+--+--+--☻--+
| | | | | | | | |
3+--+--+--+--☻--+--+--+--+
| | | | | | | | |
4+--+--+--+--+-[*]-+--+--+
| | | | | | | | |
5+--+--+--☻--+--+--+--+--+
| | | | | | | | |
6+--+--+--+--+--+--+--+--+
| | | | | | | | |
7+--+--☻--+--+--+--+--+--+
| | | | | | | | |
8+--+--+--+--+--+--+--+--+
Input 1 (locations):
{(2,2), (7,2), (4,3), (3,5), (2,7)}
Output 1 (any optimal location):
(3,3)
Input 2 (locations):
[(2, 2), (7, 2), (3, 4), (3, 5), (2, 7)]
Output 2 (any optimal location):
(4,3)
>Note: there might be more than one optimal solutions, your program can return any one of them.
I solved a similar problem on Leetcode to find the minimum total distance between points: https://www.tutorialcup.com/leetcode-solutions/best-meeting-point-leetcode-solution.htm
let grid = [[1,0,0],
[0,0,1],
[1,0,0]]
print(minTotalDistance(grid)) // -> 4 b/c optimal point is (1,0)
func minTotalDistance(_ grid: [[Int]]) -> Int {
let rowCount = grid.count
let columnCount = grid[0].count
var existRows: [Int] = []
var existCols: [Int] = []
for row in 0..<rowCount { // row
for col in 0..<columnCount { // column
print(row, col)
if grid[row][col] == 1 { // person exists
existRows.append(row)
existCols.append(col)
}
}
}
let row = existRows[existRows.count / 2] // rounds down since it's an int
existCols.sort()
let col = existCols[existCols.count / 2]
var distance = 0
for index in 0..<existRows.count { // loop through points of people -> calculate their distances
distance += abs(existCols[index]-col) + abs(existRows[index]-row)
}
return distance
}
We could manually go through every point and check for the shortest distance but that would inefficient.
Any help on solving the problem would be great!