daily pastebin goal
7%
SHARE
TWEET

aoc day whatever

a guest Dec 6th, 2018 42 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import collections as c
  2.  
  3. def bfs(row, col, grid, owner, pointId):
  4.     dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
  5.    
  6.     queue = c.deque([((row, col), 0)])
  7.     seen = set([(row, col)])
  8.     while queue:
  9.         currPos, dist = queue.popleft()
  10.         grid[currPos[0]][currPos[1]] += dist
  11.         for dir in dirs:
  12.             nextPos = (currPos[0] + dir[0], currPos[1] + dir[1])
  13.             if (nextPos[0] >= 0 and nextPos[0] < len(grid) and nextPos[1] >= 0 and nextPos[1] < len(grid[0])) and nextPos not in seen:
  14.                 seen.add(nextPos)
  15.                 queue.append((nextPos, dist + 1))
  16.                 owner[nextPos[0]][nextPos[1]] = pointId
  17.  
  18. #for part 1, starting from a point and get the area of points it owns
  19. def bfsThroughPointsArea(row, col, grid, owner, pointId):
  20.     dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
  21.     area = 0
  22.     queue = c.deque([(row, col)])
  23.     seen = set([(row, col)])
  24.     while queue:
  25.  
  26.         currPos = queue.popleft()
  27.         area += 1
  28.         for dir in dirs:
  29.             nextPos = (currPos[0] + dir[0], currPos[1] + dir[1])
  30.             if (nextPos[0] >= 0 and nextPos[0] < len(grid) and nextPos[1] >= 0 and nextPos[1] < len(grid[0])) and nextPos not in seen and owner[nextPos[0]][nextPos[1]] == pointId:
  31.                 seen.add(nextPos)
  32.                 queue.append(nextPos)
  33.             #if you hit the edge, return 0
  34.             elif nextPos[0] < 0 or nextPos[0] >= len(grid) or nextPos[1] < 0 or nextPos[1] >= len(grid[0]):
  35.                 print((row, col))
  36.                 return 0
  37.     return area
  38.        
  39.  
  40. with open('input.txt') as f:
  41.  
  42.     distancesSoFar = [[]]
  43.  
  44.     allPoints = f.readlines()
  45.    
  46.     #go through points, get largest row and col
  47.     rowSize = 0
  48.     colSize = 0
  49.     for p in allPoints:
  50.         row, col = map(int, p.split(','))
  51.  
  52.         rowSize = max(rowSize, row)
  53.         colSize = max(colSize, col)
  54.  
  55.     grid = [[0 for _ in range(colSize + 1)] for _ in range(rowSize + 1)]
  56.     owners = [[-1 for _ in range(colSize + 1)] for _ in range(rowSize + 1)]
  57.  
  58.     largestArea = 0
  59.    
  60.     pId = 0
  61.     for p in allPoints:
  62.         row, col = map(int, p.split(','))
  63.         bfs(row, col, grid, owners, pId)
  64.         pId += 1
  65.     pId = 0
  66.     #for p in allPoints:
  67.         #row, col = map(int, p.split(','))
  68.         #largestArea = max(largestArea, bfsThroughPointsArea(row, col, grid, owners, pId))
  69.         #pId += 1
  70.     ans = 0
  71.     for r in grid:
  72.         s = ''
  73.         for c in r:
  74.             if c < 10000:
  75.                 ans += 1
  76.  
  77.  
  78.  
  79.  
  80.     print(largestArea)
  81.     print(ans)
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