Spaces:
Running
Running
File size: 2,619 Bytes
a4da721 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
def find_regions(grid):
height = len(grid)
width = len(grid[0])
visited = set()
regions = []
def flood_fill(x, y, char):
if (x, y) in visited or x < 0 or y < 0 or x >= height or y >= width or grid[x][y] != char:
return set()
region = {(x, y)}
visited.add((x, y))
# Check all four directions
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_x, new_y = x + dx, y + dy
region.update(flood_fill(new_x, new_y, char))
return region
for i in range(height):
for j in range(width):
if (i, j) not in visited:
region = flood_fill(i, j, grid[i][j])
if region:
regions.append((grid[i][j], region))
return regions
def calculate_perimeter(region_cells, grid_height, grid_width):
perimeter = 0
for x, y in region_cells:
# Check all four sides
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_x, new_y = x + dx, y + dy
if (new_x, new_y) not in region_cells:
if new_x < 0 or new_y < 0 or new_x >= grid_height or new_y >= grid_width:
perimeter += 1
elif (new_x, new_y) not in region_cells:
perimeter += 1
return perimeter
def count_sides(region_cells, grid_height, grid_width):
edges = set()
for x, y in region_cells:
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_x, new_y = x + dx, y + dy
if (new_x, new_y) not in region_cells:
# Store the edge as a tuple of two points to make it unique
edge = tuple(sorted([(x, y), (x + dx/2, y + dy/2)]))
edges.add(edge)
return len(edges)
def solve_part1(grid):
regions = find_regions(grid)
total_price = 0
height, width = len(grid), len(grid[0])
for char, region in regions:
area = len(region)
perimeter = calculate_perimeter(region, height, width)
total_price += area * perimeter
return str(total_price)
def solve_part2(grid):
regions = find_regions(grid)
total_price = 0
height, width = len(grid), len(grid[0])
for char, region in regions:
area = len(region)
sides = count_sides(region, height, width)
total_price += area * sides
return str(total_price)
# Read input
with open('./input.txt', 'r') as file:
grid = [list(line.strip()) for line in file]
# Print results
print(solve_part1(grid))
print(solve_part2(grid)) |