Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Dec 6th, 2018 59 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. import numpy as np
  2.  
  3. # 2-D points implemented using (x, y) tuples
  4. def X(point): return point[0]
  5. def Y(point): return point[1]
  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[0]-minx, c[1]-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]==0 or it.multi_index[0]==sh[0]-1 or it.multi_index[1]==0 or it.multi_index[1]==sh[1]-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. OK, I Understand
 
Top