Advertisement
Guest User

aoc day whatever

a guest
Dec 6th, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.54 KB | None | 0 0
  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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement