def add_vecs(vec1, vec2):
    return (vec1[0] + vec2[0], vec1[1] + vec2[1])

class Walker:
    destinations_found = {}
    walkers = []
    def __init__(self, start: tuple, themap: list[str], current_location: tuple = None) -> None:
        self._start = start
        self._current_location = current_location
        if not self._current_location:
            self._current_location = self._start
        self._themap = themap
        self._map_height = len(themap)
        self._map_width = len(themap[0])
        self._done = False
        self._found_peak = False
        self._peak_location = None

        if self._start not in Walker.destinations_found:
            Walker.destinations_found[self._start] = set()

        Walker.walkers.append(self) # add self to list

    def step(self) -> None:
        if self._done:
            return
        # at each step I look at the numbers around me and if any are
        # 1 step higher then that's a direction I can go. If there are
        # more than one possibility, I choose one and create new
        # Walkers for the other choices
        current_elevation = int(self._themap[self._current_location[1]][self._current_location[0]])
        if current_elevation == 9: # This walker is done
            self._done = True
            self._found_peak = True
            self._peak_location = self._current_location
            Walker.destinations_found[self._start].add(self._current_location)
            return
        new_locations = self._get_possible_next_locations(current_elevation)
        if len(new_locations) == 0: # this walker is done, it hit a dead end
            self._done = True
            self._found_peak = False
            return
        self._current_location = new_locations[0]
        if len(new_locations) > 1:
            for location in new_locations[1:]:
                Walker(self._start, self._themap, location) # create new Walker for each remaining location

    def _get_from_map(self, loc):
        if loc[0] < 0 or loc[0] >= self._map_width:
            return None
        if loc[1] < 0 or loc[1] >= self._map_height:
            return None
        return int(self._themap[loc[1]][loc[0]])

    def _get_possible_next_locations(self, current_elevation):
        possible_locations = []
        for direction in [(0,-1), (1,0), (0,1), (-1,0)]:
            new_loc = add_vecs(self._current_location, direction)
            elevation = self._get_from_map(new_loc)
            if elevation and elevation == current_elevation + 1:
                possible_locations.append(new_loc)
        return possible_locations

    def __repr__(self):
        return f"Walker at {self._current_location} done: {self._done}"

    @property
    def done(self) -> bool:
        return self._done

    @property
    def found_peak(self) -> bool:
        return self._found_peak


with open('data.txt', 'r') as f:
    input = f.read()

lines = input.split('\n')

starting_locations = []
for j in range(len(lines)):
    line = lines[j]
    for i in range(len(line)):
        if line[i] == '0':
            starting_locations.append((i, j))

for loc in starting_locations:
    Walker(loc, lines)

while not all([w.done for w in Walker.walkers]): # while not all walkers done
    for w in Walker.walkers:
        w.step()

sum = 0
for k in Walker.destinations_found.keys():
    sum += len(Walker.destinations_found[k])

print(f"Part 1: {sum}")

count = 0
for w in Walker.walkers:
    if w._found_peak:
        count += 1

print(f"Part 2: {count}")