讲师中心 微信公众号

工具推荐

视频效率加速
SoundView
SoundView

字幕擦除翻译、配音口型同步

Seko
Seko

AI短剧一键生成成片

立刻MV
立刻MV

低成本歌曲 MV、视频生成

Laper
Laper

剧本策划到成片协作

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

冬浩吖_7774

冬浩吖_7774

发布时间:2024-12-30 09:27:17

|

367人浏览过

|

来源于php中文网

原创

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.

Camoufox Open Source Anti-Detect Browser for Python Automation
Camoufox Open Source Anti-Detect Browser for Python Automation

Camoufox 是一个基于 Firefox 构建的开源反检测浏览器,为 Python 自动化工作流程提供强大的指纹注入和反机器人检测规避功能。它与 Playwright 集成,以提供能够绕过现代机器人检测系统的隐身浏览能力。

下载

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.

热门AI工具

更多
Laper
Laper Hot

Laper是专为编剧、导演和制片人推出的 AI 原生剧本创作工具。

讯飞绘文

讯飞绘文是一款由科大讯飞推出的一站式 AIGC 内容运营平台。

小橡皮AI

一款AI工具,主要用于小橡皮一键去AI味,将机器味重的内容改得更有活人感,防止因为 AI 内容被平台打上 AI 标签,以及限流,适合需要提升相关任务效率的用户。

创客贴AI

创客贴AI是一款AI图像与设计工具,AI辅助的智能在线设计工具。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

PixTV
PixTV Hot

PixTV是一款面向AIGC内容创作的AI视频生成工具。

SoundView
SoundView Hot

SoundView是一款面向跨境电商的视频翻译、配音和本地化 AI 创作平台。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

相关专题

更多
typedef和define区别
typedef和define区别

typedef和define区别在类型检查、作用范围、可读性、错误处理和内存占用等。本专题为大家提供typedef和define相关的文章、下载、课程内容,供大家免费下载体验。

313

2023.09.26

define的用法
define的用法

define用法:1、定义常量;2、定义函数宏:3、定义条件编译;4、定义多行宏。更多关于define的用法的内容,大家可以阅读本专题下的文章。

619

2023.10.11

length函数用法
length函数用法

length函数用于返回指定字符串的字符数或字节数。可以用于计算字符串的长度,以便在查询和处理字符串数据时进行操作和判断。 需要注意的是length函数计算的是字符串的字符数,而不是字节数。对于多字节字符集,一个字符可能由多个字节组成。因此,length函数在计算字符串长度时会将多字节字符作为一个字符来计算。更多关于length函数的用法,大家可以阅读本专题下面的文章。

2027

2023.09.19

golang map内存释放
golang map内存释放

本专题整合了golang map内存相关教程,阅读专题下面的文章了解更多相关内容。

770

2025.09.05

golang map相关教程
golang map相关教程

本专题整合了golang map相关教程,阅读专题下面的文章了解更多详细内容。

343

2025.11.16

golang map原理
golang map原理

本专题整合了golang map相关内容,阅读专题下面的文章了解更多详细内容。

553

2025.11.17

java判断map相关教程
java判断map相关教程

本专题整合了java判断map相关教程,阅读专题下面的文章了解更多详细内容。

323

2025.11.27

location.assign
location.assign

在前端开发中,我们经常需要使用JavaScript来控制页面的跳转和数据的传递。location.assign就是JavaScript中常用的一个跳转方法。通过location.assign,我们可以在当前窗口或者iframe中加载一个新的URL地址,并且可以保存旧页面的历史记录。php中文网为大家带来了location.assign的相关知识、以及相关文章等内容,供大家免费下载使用。

3442

2023.06.27

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

0

2026.11.17

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn