깊이 우선 탐색의 언덕을 오르다, Advent of Code day 10
오늘의 챌린지는 6일차와 비슷하지만 여러 경로를 탐색해야 하는 2D 그리드인 10일차 퍼즐을 다룹니다. 이 퍼즐은 깊이 우선 검색(DFS)의 힘을 우아하게 보여줍니다.
AI가 만든 퍼즐 일러스트
지도는 사전으로 표현됩니다. 키는 (x, y) 좌표이고 값은 높이를 나타내는 한 자리 정수(0-9)이며, 9는 최고점을 나타냅니다. 구문 분석 기능은 다음 데이터 구조를 효율적으로 처리합니다.
def parse(input: str) -> dict[tuple[int, int], int | None]: return { (x, y): int(item) if item.isdigit() else None for y, row in enumerate(input.strip().splitlines()) for x, item in enumerate(row) }
트레일은 트레일 시작점(높이 0)에서 정상(높이 9)까지 올라가며 높이가 단계당 정확히 1씩 증가합니다. next_step
함수는 유효한 다음 단계를 식별합니다.
TRAIL_MAX = 9 def next_step( topo_map: dict[tuple[int, int], int | None], x: int, y: int ) -> tuple[tuple[int, int], ...]: assert topo_map[(x, y)] != TRAIL_MAX return tuple( incoming for incoming in ( (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1), ) if ( isinstance(topo_map.get(incoming), int) and isinstance(topo_map.get((x, y)), int) and (topo_map[incoming] - topo_map[(x, y)] == 1) ) )
트레일헤드(높이 0)는 find_trailheads
:
TRAILHEAD = 0 def find_trailheads( topo_map: dict[tuple[int, int], int | None], ) -> tuple[tuple[int, int], ...]: return tuple(key for key, value in topo_map.items() if value == TRAILHEAD)
솔루션의 핵심은 깊이우선탐색을 구현한 climb
기능입니다. Wikipedia의 DFS 정의에 따라 역추적하기 전에 각 분기를 완전히 탐색합니다.
깊이우선탐색의 시각적 표현
지도 지점은 "노드"이며 한 번에 한 높이씩 올라갑니다. climb
함수는 DFS 프로세스를 관리합니다.
def climb( topo_map: dict[tuple[int, int], int | None], trailheads: tuple[tuple[int, int], ...] ) -> dict[ tuple[tuple[int, int], tuple[int, int]], tuple[tuple[tuple[int, int], ...], ...] ]: candidates: list[tuple[tuple[int, int], ...]] = [(head,) for head in trailheads] result = {} while candidates: current = candidates.pop() while True: if topo_map[current[-1]] == TRAIL_MAX: result[(current[0], current[-1])] = result.get( (current[0], current[-1]), () ) + (current,) break elif steps := next_step(topo_map, *current[-1]): incoming, *rest = steps candidates.extend([current + (step,) for step in rest]) current = current + (incoming,) else: break return result
else
절의 break
은 막다른 골목을 처리하여 무한 루프를 방지합니다. 이 함수는 각 트레일 기점에서 정상까지의 모든 경로를 반환합니다.
1부에서는 고유한 최고 목적지를 계산합니다.
def part1(input: str) -> int: topo_map = parse(input) return len(climb(topo_map, find_trailheads(topo_map)))
2부에서는 모든 고유 경로를 계산합니다.
def part2(input: str) -> int: topo_map = parse(input) return sum( len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values() )
대체 접근 방식(예: 트레일 시작 부분 감지를 구문 분석에 통합)이 존재하지만 이 솔루션의 성능은 괜찮습니다. 최근 구직 활동의 실패로 인해 내 기분이 꺾이지는 않았습니다. 나는 여전히 희망적이다. 중급 Python 개발자를 찾고 있다면 연락하세요. 다음주까지!
위 내용은 깊이 우선 탐색의 언덕을 오르다, Advent of Code day 10의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

Video Face Swap
완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

Python은 배우고 사용하기 쉽고 C는 더 강력하지만 복잡합니다. 1. Python Syntax는 간결하며 초보자에게 적합합니다. 동적 타이핑 및 자동 메모리 관리를 사용하면 사용하기 쉽지만 런타임 오류가 발생할 수 있습니다. 2.C는 고성능 응용 프로그램에 적합한 저수준 제어 및 고급 기능을 제공하지만 학습 임계 값이 높고 수동 메모리 및 유형 안전 관리가 필요합니다.

하루에 2 시간 동안 파이썬을 배우는 것으로 충분합니까? 목표와 학습 방법에 따라 다릅니다. 1) 명확한 학습 계획을 개발, 2) 적절한 학습 자원 및 방법을 선택하고 3) 실습 연습 및 검토 및 통합 연습 및 검토 및 통합,이 기간 동안 Python의 기본 지식과 고급 기능을 점차적으로 마스터 할 수 있습니다.

Python은 개발 효율에서 C보다 낫지 만 C는 실행 성능이 높습니다. 1. Python의 간결한 구문 및 풍부한 라이브러리는 개발 효율성을 향상시킵니다. 2.C의 컴파일 유형 특성 및 하드웨어 제어는 실행 성능을 향상시킵니다. 선택할 때는 프로젝트 요구에 따라 개발 속도 및 실행 효율성을 평가해야합니다.

Python과 C는 각각 고유 한 장점이 있으며 선택은 프로젝트 요구 사항을 기반으로해야합니다. 1) Python은 간결한 구문 및 동적 타이핑으로 인해 빠른 개발 및 데이터 처리에 적합합니다. 2) C는 정적 타이핑 및 수동 메모리 관리로 인해 고성능 및 시스템 프로그래밍에 적합합니다.

Pythonlistsarepartoftsandardlardlibrary, whileraysarenot.listsarebuilt-in, 다재다능하고, 수집 할 수있는 반면, arraysarreprovidedByTearRaymoduledlesscommonlyusedDuetolimitedFunctionality.

파이썬은 자동화, 스크립팅 및 작업 관리가 탁월합니다. 1) 자동화 : 파일 백업은 OS 및 Shutil과 같은 표준 라이브러리를 통해 실현됩니다. 2) 스크립트 쓰기 : PSUTIL 라이브러리를 사용하여 시스템 리소스를 모니터링합니다. 3) 작업 관리 : 일정 라이브러리를 사용하여 작업을 예약하십시오. Python의 사용 편의성과 풍부한 라이브러리 지원으로 인해 이러한 영역에서 선호하는 도구가됩니다.

과학 컴퓨팅에서 Python의 응용 프로그램에는 데이터 분석, 머신 러닝, 수치 시뮬레이션 및 시각화가 포함됩니다. 1.numpy는 효율적인 다차원 배열 및 수학적 함수를 제공합니다. 2. Scipy는 Numpy 기능을 확장하고 최적화 및 선형 대수 도구를 제공합니다. 3. 팬더는 데이터 처리 및 분석에 사용됩니다. 4. matplotlib는 다양한 그래프와 시각적 결과를 생성하는 데 사용됩니다.

웹 개발에서 Python의 주요 응용 프로그램에는 Django 및 Flask 프레임 워크 사용, API 개발, 데이터 분석 및 시각화, 머신 러닝 및 AI 및 성능 최적화가 포함됩니다. 1. Django 및 Flask 프레임 워크 : Django는 복잡한 응용 분야의 빠른 개발에 적합하며 플라스크는 소형 또는 고도로 맞춤형 프로젝트에 적합합니다. 2. API 개발 : Flask 또는 DjangorestFramework를 사용하여 RESTFULAPI를 구축하십시오. 3. 데이터 분석 및 시각화 : Python을 사용하여 데이터를 처리하고 웹 인터페이스를 통해 표시합니다. 4. 머신 러닝 및 AI : 파이썬은 지능형 웹 애플리케이션을 구축하는 데 사용됩니다. 5. 성능 최적화 : 비동기 프로그래밍, 캐싱 및 코드를 통해 최적화
