Bagaimana untuk mengesan langkah dalam peta, Kedatangan Kod ay 6

Berbalik kepada cabaran Advent of Code saya, disebabkan beberapa isu yang tidak diduga, saya tidak dapat menyelesaikan cabaran dalam masa dan kini ketinggalan kira-kira 5–6 hari. Walau bagaimanapun, saya masih berazam untuk menyelesaikan teka-teki pada tahun ini. Hari ini, mari kita bincangkan teka-teki ke-6.

Imej janaan salinan yang agak sesuai dengan tema

Mencari perkara dalam pesawat 2D nampaknya menjadi tema berulang untuk tahun ini. Hari ini, kita sedang mengesan langkah pengawal yang mempunyai logik pergerakan yang jelas dan jelas. Pengawal itu bergerak dalam garisan lurus dan membelok ke kanan apabila ia terhalang.

Dengan mengandaikan kami mewakili setiap langkah yang diambil pengawal sebagai titik dalam satah 2D, kami kemudian boleh mewakili setiap langkah dalam arah yang berbeza sebagai vektor:

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

Dengan melakukan beberapa pengiraan seperti yang ditunjukkan di bawah, kami memperoleh matriks yang mewakili putaran yang betul

Menerbitkan matriks putaran

Pada asalnya, ini diwakili sebagai kamus, kerana kami akan sangat bergantung padanya untuk banyak pengiraan. Walau bagaimanapun, saya ingin memastikan anotasi jenis yang betul, justeru pelaksanaan ini buat masa ini.

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

Kami juga memerlukan cara untuk mewakili kedudukan dan pergerakan, bersama-sama dengan kaedah untuk memanipulasi kedudukan dan melaksanakan putaran:

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,
        )

Mentakrifkan kaedah dunder/magik __add__ dan __mul__ membolehkan kedua-dua objek Titik dan Arah dimanipulasi seolah-olah ia adalah operasi aritmetik standard dalam kod. Coretan juga menunjukkan cara menaip-anotasi kelas Putaran dengan berkesan.

Akhir sekali, kami mentakrifkan model untuk input kami:

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

Simbol ialah Enum standard yang merangkumi makna pelbagai simbol dalam input. Angkasa, Pengawal dan Halangan mempunyai maksud yang jelas. Papan ialah perwakilan peta. Pendekatan awal saya melibatkan reka bentuk yang lebih berorientasikan objek, tetapi akhirnya saya memilih pelaksanaan ini di mana setiap kelas hanya mengekalkan keadaan yang boleh diperiksa dengan mudah.

Mari mulakan dengan menghuraikan input:

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)),
    )

Pengawal diwakili oleh objek Titik. Fungsi pencari bertanggungjawab untuk mengimbas input dan mengenal pasti kedudukan simbol yang dikehendaki. Penyelesaian serupa untuk penghuraian peta 2D akan terus diterokai dalam siaran seterusnya.

Penyelesaian saya untuk bahagian 1 agak mudah. Untuk mengira langkah pengawal seterusnya:

1. Tentukan destinasi yang diingini terus di hadapan pengawal, berdasarkan vektor arah semasa.
2. Periksa sama ada destinasi yang diingini terhalang.
3. Jika destinasi yang diingini terhalang: Kami mengembalikan destinasi yang diingini dan vektor arah semasa.
4. Jika destinasi yang diingini tidak terhalang: Kami mengembalikan kedudukan semasa dan vektor arah yang diputar.

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

Akhir sekali, kami menangani bahagian 1 cabaran, yang memerlukan penentuan bilangan jubin unik yang dilawati oleh pengawal.

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

Bahagian 2 membaling bebola lengkung kepada kami! Kami ditugaskan untuk mencari tempat yang sesuai untuk meletakkan objek baharu pada peta untuk membuat rondaan robot kami dalam gelung selama-lamanya.

Berita baiknya, mencari tempat yang betul bukanlah sains roket. Kami tahu laluan awal robot dari Bahagian 1, jadi kami hanya perlu meletakkan objek di suatu tempat di sepanjang laluan itu.

Sekarang, bahagian yang sukar: bagaimana kita tahu jika kita berjaya membuat gelung?

Ini pendekatan saya:

1. Jejaki pergerakan robot: Daripada menjejaki kedudukan tepatnya, saya menumpukan pada merekod setiap "langkah" yang diambil. Setiap langkah pada asasnya adalah pergerakan dari satu jubin ke jubin seterusnya.
2. Cari corak berulang: Jika robot mula mengulangi urutan langkah yang sama, kami mempunyai gelung!
3. Pastikan ia kekal pada peta: Yang penting, kita perlu memastikan robot itu tidak tersasar dari peta.

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,
        )

Sebab saya memilih untuk menyimpan langkah dalam kamus ialah susunan langkah tidak penting untuk bahagian masalah ini (yang membayangkan konsep yang serupa dalam teka-teki kemudian).

Memandangkan saya perlu kerap menyemak sama ada langkah tertentu telah berlaku, menyimpan langkah dalam kamus telah meningkatkan prestasi dengan ketara. Kamus dalam Python adalah sangat pantas untuk carian, menjadikan semakan ini lebih cepat berbanding menggunakan senarai atau tupel.

Percubaan awal saya, yang menggunakan struktur data yang berbeza, mengambil masa kira-kira 70 saat untuk dijalankan pada kesemua 8 teras mesin saya. Dengan menukar kepada kamus, saya dapat mengurangkan masa jalan dengan ketara kepada beberapa saat sahaja. Ini menunjukkan kuasa memilih struktur data yang betul untuk tugas yang sedang dijalankan!

Itu sahaja untuk hari ini. Memandangkan penambahbaikan masa jalan daripada 70 saat pada semua teras kepada hanya beberapa saat pada teras tunggal, saya agak gembira dengan pengoptimuman itu, walaupun saya tahu penambahbaikan selanjutnya adalah mungkin (sebaik-baiknya menyasarkan untuk pelaksanaan subsaat).

Percubaan saya sebelum ini untuk menjaringkan kerja tidak berakhir dengan baik (ya, masih #OpenToWork, ping saya!), kerana saya menolak permintaan untuk tugasan/ujian tambahan tanpa pampasan. Mudah-mudahan, keadaan akan bertambah baik dengan ketara pada tahun hadapan, dan saya akan menulis semula minggu depan.

Atas ialah kandungan terperinci Bagaimana untuk mengesan langkah dalam peta, Kedatangan Kod ay 6. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!