지도에서 단계를 추적하는 방법, Advent of Code 6-파이썬 튜토리얼-php.cn

지도에서 단계를 추적하는 방법, Advent of Code 6

DDD

풀어 주다： 2024-12-29 07:05:10

원래의

162명이 탐색했습니다.

Advent of Code 챌린지로 돌아가서, 예측할 수 없는 문제로 인해 챌린지를 제 시간에 완료할 수 없으며 현재 약 5~6일 정도 늦어지고 있습니다. 그러나 나는 올해에도 퍼즐을 완성하겠다고 결심했습니다. 오늘은 여섯 번째 퍼즐에 대해 이야기해보겠습니다.

How to trace steps in a map, Advent of Code ay 6
테마에 다소 어울리는 코파일럿 생성 이미지

2D 평면에서 물건을 찾는 것이 올해 반복되는 주제인 것 같습니다. 오늘은 명확하고 정의된 움직임 논리를 지닌 가드의 발걸음을 추적해보겠습니다. 가드는 직선으로 이동하다가 방해를 받으면 우회전합니다.

경비원이 취하는 각 단계를 2D 평면의 한 점으로 표현한다고 가정하면 다른 방향의 각 단계를 벡터로 표현할 수 있습니다.

LEFT = (1, 0)
RIGHT = (-1, 0)
UP = (0, -1)
DOWN = (0, 1)

로그인 후 복사

아래와 같이 몇 가지 계산을 수행하여 오른쪽 회전을 나타내는 행렬을 얻습니다

How to trace steps in a map, Advent of Code ay 6
회전행렬 도출

원래는 수많은 계산에 크게 의존하게 되므로 사전으로 표시되었습니다. 그러나 적절한 유형 주석을 보장하고 싶었으므로 지금은 이 구현을 사용합니다.

class Rotation:
    c0r0: int
    c1r0: int
    c0r1: int
    c1r1: int

@dataclass(frozen=True)
class RotateRight(Rotation):
    c0r0: int = 0
    c1r0: int = 1
    c0r1: int = -1
    c1r1: int = 0

로그인 후 복사

위치를 조작하고 회전을 실행하는 방법과 함께 위치와 움직임을 나타내는 수단도 필요합니다.

from __future__ import annotations

@dataclass(frozen=True)
class Point:
    x: int
    y: int

    def __add__ (self, direction: Direction) -> Point:
        return Point(self.x + direction.x, self.y + direction.y)

@dataclass
class Direction:
    x: int
    y: int

    def __mul__ (self, rotation: Rotation) -> Direction:
        return Direction(
            self.x * rotation.c0r0 + self.y * rotation.c0r1,
            self.x * rotation.c1r0 + self.y * rotation.c1r1,
        )

로그인 후 복사

dunder/magic 메소드 __add__ 및 __mul__을 정의하면 Point 및 Direction 객체를 모두 코드 내에서 표준 산술 연산인 것처럼 조작할 수 있습니다. 또한 이 스니펫은 Rotation 클래스에 효과적으로 유형 주석을 추가하는 방법을 보여줍니다.

마지막으로 입력 모델을 정의합니다.

class Symbol(Enum):
    Guard = "^"
    Obstruction = "#"

@dataclass
class Space:
    pass

@dataclass
class Guard:
    pass

@dataclass
class Obstruction:
    pass

@dataclass
class Board:
    tiles: dict[Point, Space | Guard | Obstruction]
    width: int
    height: int

로그인 후 복사

Symbol은 입력 내 다양한 기호의 의미를 캡슐화하는 표준 Enum입니다. Space, Guard 및 Obstruction은 자명한 의미를 갖습니다. 보드는 지도를 표현한 것입니다. 나의 초기 접근 방식은 보다 객체 지향적인 디자인을 포함했지만 궁극적으로 각 클래스가 쉽게 검사할 수 있는 상태를 유지하는 이 구현을 선택했습니다.

입력 구문 분석부터 시작하겠습니다.

def finder(board: tuple[str, ...], symbol: Symbol) -> Generator[Point, None, None]:
    return (
        Point(x, y)
        for y, row in enumerate(board)
        for x, item in enumerate(tuple(row))
        if item == symbol.value
    )

def parse(input: str) -> tuple[Board, Point]:
    board = tuple(input.strip().splitlines())

    return (
        Board(
            {point: Obstruction() for point in finder(board, Symbol.Obstruction)},
            len(board[0]),
            len(board),
        ),
        next(finder(board, Symbol.Guard)),
    )

로그인 후 복사

경비원은 Point 개체로 표현됩니다. 파인더 기능은 입력을 스캔하고 원하는 기호의 위치를 식별하는 역할을 합니다. 2D 지도 분석을 위한 유사한 솔루션은 후속 게시물에서 계속해서 탐구될 것입니다.

제 1부 솔루션은 비교적 간단합니다. 경비원의 다음 단계를 계산하려면:

현재 방향 벡터를 바탕으로 경비원 바로 앞에서 원하는 목적지를 결정합니다.
원하는 목적지가 가려져 있는지 확인하세요.
원하는 목적지가 방해를 받는 경우: 원하는 목적지와 현재 방향 벡터를 반환합니다.
원하는 목적지가 방해받지 않는 경우: 현재 위치와 회전된 방향 벡터를 반환합니다.

LEFT = (1, 0)
RIGHT = (-1, 0)
UP = (0, -1)
DOWN = (0, 1)

로그인 후 복사

마지막으로 경비원이 방문한 고유 타일의 수를 결정해야 하는 챌린지의 1부에 대해 설명합니다.

class Rotation:
    c0r0: int
    c1r0: int
    c0r1: int
    c1r1: int

@dataclass(frozen=True)
class RotateRight(Rotation):
    c0r0: int = 0
    c1r0: int = 1
    c0r1: int = -1
    c1r1: int = 0

로그인 후 복사

2부는 우리에게 변화구를 던집니다! 우리는 로봇이 영원히 순찰할 수 있도록 지도에서 새로운 개체를 배치할 완벽한 지점을 찾는 임무를 맡고 있습니다.

좋은 소식은 올바른 장소를 찾는 것이 엄청난 과학이 아니라는 것입니다. 우리는 1부에서 로봇의 초기 경로를 알고 있으므로 해당 경로를 따라 어딘가에 물체를 배치하기만 하면 됩니다.

이제 까다로운 부분입니다. 루프가 성공적으로 생성되었는지 어떻게 알 수 있나요?

내 접근 방식은 다음과 같습니다.

로봇의 움직임 추적: 로봇의 정확한 위치를 추적하는 대신 로봇이 취하는 각 "걸음"을 기록하는 데 집중했습니다. 각 단계는 기본적으로 한 타일에서 다음 타일로 이동하는 것입니다.
반복 패턴 찾기: 로봇이 동일한 단계 순서를 반복하기 시작하면 루프가 발생합니다!
지도에 있는지 확인: 결정적으로 로봇이 지도에서 벗어나지 않도록 해야 합니다.

from __future__ import annotations

@dataclass(frozen=True)
class Point:
    x: int
    y: int

    def __add__ (self, direction: Direction) -> Point:
        return Point(self.x + direction.x, self.y + direction.y)

@dataclass
class Direction:
    x: int
    y: int

    def __mul__ (self, rotation: Rotation) -> Direction:
        return Direction(
            self.x * rotation.c0r0 + self.y * rotation.c0r1,
            self.x * rotation.c1r0 + self.y * rotation.c1r1,
        )

로그인 후 복사

내가 단계를 사전에 저장하기로 선택한 이유는 문제의 이 부분에서는 단계의 순서가 중요하지 않기 때문입니다(이는 이후 퍼즐에서 비슷한 개념을 암시합니다).

특정 단계가 이미 발생했는지 자주 확인해야 했기 때문에 해당 단계를 사전에 저장하면 성능이 크게 향상되었습니다. Python의 사전은 조회 속도가 놀라울 정도로 빠르므로 목록이나 튜플을 사용하는 것에 비해 이러한 검사가 훨씬 빠릅니다.

다른 데이터 구조를 사용한 초기 시도는 내 컴퓨터의 8개 코어 모두에서 실행하는 데 약 70초가 걸렸습니다. 사전으로 전환함으로써 런타임을 단 몇 초로 크게 줄일 수 있었습니다. 이는 당면한 작업에 적합한 데이터 구조를 선택하는 것이 얼마나 강력한지 보여줍니다!

오늘은 여기까지입니다. 모든 코어의 70초에서 단일 코어의 단 몇 초로 향상된 런타임을 고려하면 추가 개선이 가능하다는 것을 알고 있지만(이상적으로는 1초 미만 실행을 목표로 함) 최적화에 매우 만족합니다.

보상 없이 추가 과제/시험 요청을 거부했기 때문에 이전에 취업 점수를 얻으려는 시도가 잘 끝나지 않았습니다(예, 여전히 #OpenToWork, 저에게 핑을 보내주세요!). 내년에는 상황이 크게 개선되길 바라면서 다음 주에 다시 글을 쓰겠습니다.

위 내용은 지도에서 단계를 추적하는 방법, Advent of Code 6의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!