• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Dec 6th, 2018 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import numpy as np
2.
3. # 2-D points implemented using (x, y) tuples
4. def X(point): return point
5. def Y(point): return point
6.
7. def manhattan_distance(p, q=(0, 0)):
8.     "City block distance between two points."
9.     return abs(X(p) - X(q)) + abs(Y(p) - Y(q))
10. #day6 part1
11. #Given a list of coordinates, find largest "area" of coordinates that are only closest to one point.
12.
13. #If I draw a grid, the area defined by any point on the edge of the grid will be infinite, and therefore, doesn't count
14. #step 1:  Create a grid.  Grid boundaries will be the min/max of the x and y values
15. coordinates = input_lines(6)
16.
17. def nearest_point(point, coords):
18.     #This function will compute the nearest coord in coords to point by MD
19.     min_dist, min_coord = 9999999, 0
20.     for i,coord in enumerate(coords):
21.         dist = manhattan_distance(point, coord)
22.         if dist<min_dist:
23.             min_dist, min_coord = dist, i+1
24.         elif dist == min_dist:
25.             min_coord = 0
26.     return min_coord
27.
28. def create_matrix(input_lines):
29.     #Matrix will be filled with the index of the nearest point
30.     #fortran indexed.  0 means two or more coordinates are equidistant
31.     coords = [tuple(map(int, line.strip().split(','))) for line in input_lines]
32.     xs, ys = list(zip(*coords))
33.     #make the matrix smaller by subtracting off minx, miny
34.     minx, maxx, miny, maxy = min(xs), max(xs), min(ys), max(ys)
35.     newcoords = [(c-minx, c-miny) for c in coords]
36.     matrix = np.zeros((maxx-minx+1,maxy-miny+1), dtype=int)
37.     it = np.nditer(matrix, flags=['multi_index'], op_flags=['readwrite'])
38.     for x in it:
39.         x[...] = nearest_point(it.multi_index, newcoords)
40.     return matrix
41.
42. def find_largest_area(matrix):
43.     #Find the largest finite area containing one number that isn't zero
44.     #eliminate any area touching the edges...those are infinite and don't count
45.     infs = set()
46.     sh = matrix.shape
47.     it = np.nditer(matrix, flags=['multi_index'])
48.     for x in it:
49.         if it.multi_index==0 or it.multi_index==sh-1 or it.multi_index==0 or it.multi_index==sh-1:
50.             infs.add(int(x))
51.     max_area = 0
52.     for i in range(np.max(matrix)):
53.         if i+1 in infs:
54.             continue
55.         area = np.sum(matrix==i+1)
56.         if area >= max_area:
57.             max_area = area
58.     return max_area
59.
60. mtx = create_matrix(coordinates)
61. find_largest_area(mtx)  #Answer to part 1
62.
63. #-----------------------------------
64. #Day6 part2
65. #Find size of area with sum of all manhattan distances less than 10000
66.
67. def total_distance_lt_thresh(point, coords, thresh=10000):
68.     #compute total MD to point from all coords, return True if total < thresh
69.     total_dist = 0
70.     for i,coord in enumerate(coords):
71.         total_dist += manhattan_distance(point, coord)
72.     return total_dist <thresh
73.
74. def create_matrix2(input_lines):
75.     #Similar to above, but instead of closest point, just give result of total_distance_lt_thresh
76.     #as values of the matrix.  I left out the bit about subtracting off the minima, because in principle
77.     #this area could go further than the edges of our matrix, depending on the size of thresh
78.     coords = [tuple(map(int, line.strip().split(','))) for line in input_lines]
79.     xs,ys = list(zip(*coords))
80.     maxx, maxy = max(xs), max(ys)
81.     matrix = np.zeros((maxx+1, maxy+1), dtype=bool)
82.     it = np.nditer(matrix, flags=['multi_index'], op_flags=['readwrite'])
83.     for x in it:
84.         x[...] = total_distance_lt_thresh(it.multi_index, coords)
85.     return matrix
86. #To compute the answer, just sum the entire matrix
87. np.sum(create_matrix2(coordinates))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top