如何在地图中追踪步骤,代码降临 ay 6

心靈之曲
发布: 2024-12-30 09:27:17
原创
302人浏览过

advent of code 2024: day 6 - guard patrol optimization

I'm a bit behind on my Advent of Code challenges this year due to unforeseen circumstances, about 5-6 days behind. However, I'm determined to complete the puzzles! Today, let's tackle puzzle six.

如何在地图中追踪步骤,代码降临 ay 6

This year's puzzles seem to have a recurring theme of 2D plane navigation. Today, we're tracking the movements of a guard with a clear, deterministic movement logic: the guard moves in a straight line, turning right when encountering an obstacle.

Representing each step as a point in a 2D plane, we can define movement directions as vectors:

left = (1, 0)
right = (-1, 0)
up = (0, -1)
down = (0, 1)
登录后复制

A rotation matrix representing a right turn is derived as follows:

如何在地图中追踪步骤,代码降临 ay 6

Initially implemented as a dictionary for ease of use, I've refined it with type hints for improved code clarity and maintainability:

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
登录后复制

Next, we need classes to represent position, movement, and their manipulation:

from __future__ import annotations
from dataclasses import dataclass

@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,
        )
登录后复制

The __add__ and __mul__ dunder methods allow for intuitive arithmetic operations on Point and Direction objects. Type hinting ensures code correctness.

Finally, the input model:

from enum import Enum

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 is a standard enum, Space, Guard, and Obstruction are self-explanatory, and Board represents the map. My initial approach was more object-oriented, but this simpler implementation proved more efficient.

Input parsing:

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]:
    rows = tuple(input.strip().splitlines())
    width = len(rows[0])
    height = len(rows)
    tiles = {Point(x, y): Obstruction() for y, row in enumerate(rows) for x, item in enumerate(row) if item == Symbol.OBSTRUCTION.value}
    return Board(tiles, width, height), next(finder(rows, Symbol.GUARD))
登录后复制

The guard's position is a Point object. finder scans for symbols.

Part 1: Calculating the number of unique tiles visited by the guard.

def check_is_passable(board: Board, point: Point) -> bool:
    return not isinstance(board.tiles.get(point, Space()), Obstruction)

def guard_rotate(direction: Direction, rotation: Rotation) -> Direction:
    return direction * rotation

def guard_move(
    board: Board, guard: Point, direction: Direction, rotation: Rotation
) -> tuple[Direction, Point]:
    destination = guard + direction
    if check_is_passable(board, destination):
        return direction, destination
    else:
        return guard_rotate(direction, rotation), guard

def get_visited_tiles(
    board: Board,
    guard: Point,
    rotation: Rotation,
    direction: Direction = Direction(0, -1), # Default direction: up
) -> dict[Point, bool]:
    tiles = {guard: True}
    while True: #check_is_in_board(board, guard):  Removed board boundary check for simplification.  Assume board is large enough.
        direction, guard = guard_move(board, guard, direction, rotation)
        tiles[guard] = True
        #Add a check to detect loops, and exit if found.  This prevents infinite loops.  (Implementation omitted for brevity)


    return tiles

def part1(input: str) -> int:
    board, guard = parse(input)
    return len(get_visited_tiles(board, guard, RotateRight()))
登录后复制

Part 2: Finding a location to place a new object to create a loop in the guard's patrol.

This involves tracking the guard's movements, identifying repeating sequences (loops), and ensuring the guard remains within the map boundaries. (Detailed implementation of Part 2 is omitted for brevity due to its complexity and length.) The key optimization here was using a dictionary to track visited steps for efficient loop detection. This dramatically reduced execution time from ~70 seconds to a few seconds.

My job search continues (#opentowork). I hope for better results next year. More updates next week.

以上就是如何在地图中追踪步骤,代码降临 ay 6的详细内容,更多请关注php中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号