코드데이 키패드 수수께끼의 출현

21일차: 키패드 수수께끼

GitHub 저장소 - 솔루션

오늘의 챌린지는 어려웠고 문제를 풀고 논리를 완전히 이해하는 데 2일이 걸렸습니다. 올해 제가 발견한 것은 지침의 의도를 이해하는 데 어려움을 겪었다는 것입니다.

저처럼 여러분도 이 도전과 해결책을 통해 뭔가를 배웠기를 바랍니다. 나는 매년 Advent of Code에 참여하여 많은 것을 배웠습니다. 그래서 다른 언어를 시도하거나 익숙한 곳에서 벗어나기를 좋아합니다. 저는 Advent of Code를 단지 경쟁으로 여기기보다는 개발자들이 자신의 지식과 아이디어를 공유해야 하는 학습/개발 기회라고 생각합니다.

오늘 Python을 다시 시도했는데 솔루션에 만족합니다. 오늘 배운 내용은 다음과 같습니다. 클래스 선언에 @dataclass(frozen=True) 주석을 사용하는 불변 클래스입니다.

좌표를 탐색하고 업데이트하기 위한 도우미 클래스로 Location 클래스를 만들었습니다(이전에 일부 C# 솔루션에서 Point 클래스를 사용하여 했던 것과 비슷합니다.

C#/.Net의 강력한 유형의 배경을 가진 사람으로서 저는 이 복잡한 문제 중에 제가 작업하고 있던 내용을 시각화하는 데 도움이 되도록 코드에 유형을 추가해 보았습니다. 나는 또한 TypeScript를 작성하는 동안 이 작업을 수행하는 데 익숙하므로 거의 제2의 천성입니다.

오늘의 문제

**1부**에서는 숫자 키패드에 코드를 입력하기 위해 다음 로봇에 지침을 전달하기 위해 여러 로봇을 탐색하고 제어하는 ​​문제를 소개합니다.

제2부는 로봇 체인과 방향 키패드를 통해 복잡성을 증가시켜 문제를 해결하고 다단계 종속성의 기하급수적 특성을 보여줍니다.

연습

우리는 길찾기와 키패드의 레이아웃을 이미 알고 있으므로 그들이 이동할 수 있는 모든 위치 매핑과 방향에 대한 사전을 구축할 수 있습니다.

캐싱(cache 및 이동_cache)

캐시: 이전에 계산된 가장 짧은 시퀀스를 저장하여 중복 계산을 방지하고 성능을 향상시킵니다.

moves_cache: 빠른 조회를 위해 미리 계산되어 키패드의 두 버튼 사이에 유효한 모든 이동 시퀀스를 저장합니다.

최단 길이 계산(shortest_length)

주어진 코드를 입력하기 위해 버튼을 누르는 가장 짧은 순서를 재귀적으로 계산합니다.

한도(깊이_한계)까지 레벨(cur_깊이)을 반복하여 키패드의 다중 레벨 연결을 처리합니다.

*위치 간 이동(moves_between_positions)
*

키패드의 두 버튼 사이의 유효한 동작 시퀀스를 모두 계산하여 로봇이 잘못된 위치(틈)를 가리켜 패닉하지 않도록 합니다.

캐시 초기화(create_cache_moves)

숫자 및 방향 키패드의 모든 버튼 쌍에 대해 유효한 이동 시퀀스를 미리 계산하여 런타임 계산을 절약합니다.

해결 기능은 입력을 반복하면서 시퀀스 길이에 코드의 숫자 부분을 곱하여 복잡성을 계산한 다음 퍼즐의 요구 사항에 따라 모든 코드의 복잡성을 간단히 합산합니다.

순열

순열의 기능은 무엇인가요?

Python의 순열 함수(itertools 모듈에 있음)는 항목 모음의 가능한 모든 정렬을 생성합니다.

예:

from itertools import permutations

items = ['a', 'b', 'c']
list(permutations(items))

이 결과는 다음과 같습니다.

[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

각 순열은 원래 컬렉션의 모든 항목을 포함하지만 순서는 다른 고유한 순서입니다.

조합이 아닌 순열을 사용하는 이유는 무엇입니까?

순열:

항목 컬렉션의 가능한 모든 주문 배열을 생성합니다.
항목의 순서가 중요합니다.

그런데
조합:

항목 컬렉션에서 가능한 모든 정렬되지 않은 선택 항목을 생성합니다.

아이템의 순서는 상관없습니다.

이 시나리오에서 순서가 중요한 이유는 무엇입니까?

키패드 탐색: 이동할 때마다 키패드에서 로봇의 위치가 변경되므로 이동이 수행되는 순서가 결과에 직접적인 영향을 미칩니다.

유효한 이동 확인: 이 기능은 탐색 중에 중간 위치의 유효성을 확인합니다. 이동 순서를 변경하면 잘못된 경로가 발생할 수 있습니다.

대신 조합이 언제 유용할까요?

이동 순서가 중요하지 않거나 순서를 고려하지 않고 동작이나 버튼의 하위 집합을 선택하는 경우 조합이 유용할 수 있습니다.

키패드 탐색에서는 이동 순서가 중요하므로 현재 순열 사용이 필요합니다. 이를 조합으로 바꾸면 프로그램의 논리가 깨질 수 있습니다. 작업이 순서에 관계없이 모든 고유한 동작 그룹이나 키를 찾는 데 필요한 경우 조합이 더 적절할 것입니다.

퍼즐에서 가장 어려운 부분은 로봇 명령의 깊이(시작) 수준을 추적하는 훌륭하고 깔끔한 방법을 생각하는 것이었습니다. 여기에 완전히 주의를 기울이는 데 약간의 시간이 걸렸습니다.

위 내용은 코드데이 키패드 수수께끼의 출현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!