from collections import deque

from tools.aoc import AOCDay
from typing import Any

from tools.coordinate import Coordinate
from tools.grid import Grid


class Day(AOCDay):
    inputs = [
        [
            (11, "input13_test"),
            (92, "input13"),
        ],
        [
            (124, "input13"),
        ],
    ]

    def get_grid(self) -> Grid:
        grid = Grid()
        fav_number = self.getIntsFromInput()[0]
        for x in range(50):
            for y in range(50):
                room_number = x * x + 3 * x + 2 * x * y + y + y * y + fav_number
                set_bits = list(bin(room_number)[2:]).count("1")
                if set_bits % 2 == 0:
                    grid.set(Coordinate(x, y))

        return grid

    def run_maze(self) -> tuple[int, int] | None:
        if self.is_test():
            target = Coordinate(7, 4)
        else:
            target = Coordinate(31, 39)

        grid = self.get_grid()
        pos = Coordinate(1, 1)
        q = deque([(0, pos)])
        seen = set()
        rooms_reached = 0
        while q:
            dist, pos = q.popleft()
            if pos == target:
                return dist, rooms_reached
            if pos in seen:
                continue
            seen.add(pos)
            if dist <= 50:
                rooms_reached += 1
            for n in grid.getNeighboursOf(pos, includeDiagonal=False):
                q.append((dist + 1, n))

        return None

    def part1(self) -> Any:
        return self.run_maze()[0]

    def part2(self) -> Any:
        return self.run_maze()[1]


if __name__ == "__main__":
    day = Day(2016, 13)
    day.run(verbose=True)