adventofcode_2024/day_12.py at main · Stephan-Kok/adventofcode_2024 · GitHub

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
from datetime import datetime

time_start = datetime.now()

with open('day_12.input', 'r') as file:
    lines = file.readlines()

# This class defines a side for part2
class Side:
    start: tuple[int,int]
    end: tuple[int,int]

    def __init__(self, start_x, start_y, end_x, end_y):
        self.start = (start_x, start_y)
        self.end = (end_x, end_y)
        if start_x - end_x == 0:
            self.direction = "v"
        elif start_y - end_y == 0:
            self.direction = "h"
        else:
            raise ValueError("Cannot happen")

    def add_side(self, new_side):
        if self.direction == new_side.direction:
            if self.start == new_side.end:
                self.start = new_side.start
                return True
            if self.end == new_side.start:
                self.end = new_side.end
                return True
        return False

    def __repr__(self):
        return self.direction + ":" + str(self.start) + ":" + str(self.end)

class GardenGroup:
    garden: [[tuple[str, bool]]]
    height: int
    width: int

    def __init__(self):
        self.garden = []
        for line in lines:
            self.garden.append([(plant, False) for plant in line[:-1]])
        self.height = len(self.garden)
        self.width = len(self.garden[0])

    def find_plant(self, plant: str, x: int, y: int):
        if 0 <= x < self.width and 0 <= y < self.height:
            tmp_plant, is_found = self.garden[y][x]
            if tmp_plant == plant:
                return x, y, is_found
        return None

    def get_plants_near(self, plant: str, x: int, y: int):
        found = [
            (self.find_plant(plant, x + 1, y), "r"),
            (self.find_plant(plant, x, y + 1), "d"),
            (self.find_plant(plant, x - 1, y), "l"),
            (self.find_plant(plant, x, y - 1), "u")
        ]
        return [(item, direction) for item, direction in found if item is not None]


    def find_plant_area(self, plant: str, x: int, y: int):
        if self.garden[y][x][1]:
            return 0, 0
        self.garden[y][x] = (plant, True)
        plants = self.get_plants_near(plant, x, y)
        area = 4 - len(plants)
        count = 1
        for (xpos, ypos, is_found), direction in plants:
            if not is_found:
                new_area, new_count = self.find_plant_area(plant, xpos, ypos)
                area += new_area
                count += new_count
        return area, count

    def find_garden_area(self):
        plants_area = []
        for y in range(self.height):
            for x in range(self.width):
                plant, is_found = self.garden[y][x]
                if not is_found:
                    plants_area.append(((plant, x,y), self.find_plant_area(plant, x, y)))
        # print(plants_area)
        return sum([area * occurrence for (plant, (area, occurrence)) in plants_area])

    def find_plant_side(self, plant: str, x: int, y: int):
        # Skip if plant already done
        if self.garden[y][x][1]:
            return [], 0

        # Set plant done
        self.garden[y][x] = (plant, True)

        # Get plants near
        plants_near = self.get_plants_near(plant, x, y)
        plants, direction = [plant for plant, _ in plants_near], [direction for _, direction in plants_near]

        # Only add sides where no plant is near
        sides = []
        if "r" not in direction:
            sides.append(Side(x + 1, y, x + 1, y + 1))
        if "d" not in direction:
            sides.append(Side(x + 1, y + 1, x, y + 1))
        if "l" not in direction:
            sides.append(Side(x, y + 1, x, y))
        if "u" not in direction:
            sides.append(Side(x, y, x + 1, y))

        # Recursive do all near plants to find total space
        count = 1
        for xpos, ypos, is_found in plants:
            if not is_found:
                new_sides, new_count = self.find_plant_side(plant, xpos, ypos)
                for new_side in new_sides:
                    if not self.add_side_if_already_exists(sides, new_side):
                        sides.append(new_side)
                count += new_count
        return sides, count

    def add_side_if_already_exists(self, sides: [Side], new_side: Side):
        for side in sides:
            if side.add_side(new_side):
                return True
        return False

    def find_garden_sides(self):
        plant_sides = []
        for y in range(self.height):
            for x in range(self.width):
                plant, is_found = self.garden[y][x]
                if not is_found:
                    plant_sides.append(((plant, x,y), self.find_plant_side(plant, x, y)))
        # print(plant_sides)
        return sum([len(sides) * occurrence for (plant, (sides, occurrence)) in plant_sides])


garden_group = GardenGroup()
print("Part1", garden_group.find_garden_area())
garden_group = GardenGroup()
print("Part2", garden_group.find_garden_sides())

print("Total time: ", datetime.now() - time_start)