코드 4의 출현을 위한 정렬 알고리즘을 코딩하는 방법

저번 포스팅에서 제가 올해 Advent of Code에 참여한다고 간략하게 언급한 적이 있습니다. 공교롭게도 퍼즐 중 하나, 특히 5일차에 게시된 퍼즐에서는 목록의 페이지 순서를 수정하는 작업이 포함됩니다. 정렬 알고리즘 구현에 대한 글을 올린 지 얼마 되지 않아서 글을 써야겠다는 생각이 들었습니다.

일부 정렬 알고리즘을 묘사한 귀여운 이미지

Advent of Code에 대해 아직 들어보지 못한 분들을 위해 Eric Wastl이 주최하는 연례 행사입니다. 매년 휴가철을 배경으로 한 이야기를 들려주는데, 올해는 모든 대형 크리스마스 썰매 출시에서 중요한 인물일 수 있는 수석 역사가를 찾는 이야기입니다. 이 챌린지는 매년 12월 1일부터 25일까지 진행됩니다. 매일 플롯이 진행되며 여기에는 프로그래밍 퍼즐이 포함되어 있습니다(입력도 함께 제공됩니다).

스토리 내레이션 내에서 퍼즐은 일반적으로 명확하게 정의되며 테스트 사례가 포함됩니다. 모든 퍼즐은 두 부분으로 나누어져 있으며, 두 번째 부분은 첫 번째 답변을 제출한 후에만 표시됩니다.

참여자는 파생된 답변이 일치하는 한 모든 언어로 모든 알고리즘을 구현하거나 프로그래밍을 완전히 건너뛸 수도 있습니다. 올해 저는 Python으로 솔루션을 코딩하려고 시도하고 있는데, 9일 후에는 여행 내내 꽤 많은 것을 배운 것 같습니다.

5일째, 사연은 안전 매뉴얼 인쇄를 도와달라는 부탁을 받았습니다. 입력에는 페이지 규칙과 엘프가 인쇄하려고 했던 페이지 목록이 모두 포함되어 있습니다.

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

입력 구문 분석부터 시작하겠습니다.

def parse(
    input: str,
) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
    def inner(
        current, incoming
    ) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
        rules, pages = current

        if "|" in incoming:
            return rules + (
                tuple(int(item) for item in incoming.strip().split("|")),
            ), pages

        else:
            return rules, pages + (
                tuple(int(item) for item in incoming.strip().split(",")),
            )

    return reduce(
        inner, filter(lambda line: line.strip(), input.strip().splitlines()), ((), ())
    )

함수는 입력을 input이라는 문자열로 받고, 이를 .splitlines()를 사용하여 여러 줄로 나누어 내부 함수로 전송하여 두 개의 튜플(페이지 규칙용 튜플과 페이지 시퀀스용 튜플)을 생성합니다. 코드는 구분 기호 |를 통해 두 가지 유형의 정의를 구별합니다. 페이지 규칙의 경우 , 페이지의 경우

퍼즐의 첫 번째 부분에서는 페이지가 순서대로 되어 있는지 확인하라는 이야기가 나왔습니다. 작업을 수행하는 함수를 구현하는 것부터 시작해 보겠습니다.

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules

그리고 페이지의 모든 조합(조합((1,2,3), 2)은 1,2, 1,3 및 2,3을 반환)을 보내는 또 다른 함수는 다음과 같습니다.

from itertools import combinations

def check_pages(rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]) -> bool:
    return all(
        check_pair(rules, alpha, beta)
        for alpha, beta in combinations(pages, 2)
    )

이 두 가지 기능을 개별 기능으로 분리한 주된 이유는 각 부분을 최대한 작게 유지하고 싶기 때문입니다. 내 경험에 따르면, 항목을 충분히 작게 유지하면 테스트가 가능해질 뿐만 아니라 일반적으로 최종 입력(일반적으로 비합리적으로 큼)을 디버깅하는 데에도 도움이 됩니다.

많은 경우 파트 2는 놀랍게도 파트 1의 코드 디자인 수정이 필요한 경우가 많습니다. 구현한 항목에 대한 작은 변형일 수도 있고 다른 기능이 필요할 수도 있습니다. 다른 목표에 대한 호출 순서 등 저는 직장에서 (댓글 대신) 짧은 함수를 작성하는 습관을 유지하고 있습니다.

이런 작은 기능은 이름이 좋을 때만 작동하므로 이름 지정에 주의를 기울여야 합니다. 여기에는 연습이 필요하지만 일단 익숙해지면 이 접근 방식을 통해 코드를 자체적으로 문서화할 수 있습니다. 더 큰 규모의 기능은 마치 이야기처럼 읽을 수 있으며, 독자는 필요할 때 어떤 기능을 더 자세히 살펴보고 싶은지 선택할 수 있습니다.

Martin Fowler가 작성한 Function Length라는 기사에서 인용

퍼즐로 돌아갑니다.

마지막에 퍼즐은 페이지가 제대로 정렬된 모든 경우에 대해 중간 페이지 번호의 합을 요구했습니다.

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

매우 간단합니다. 모든 작업을 올바르게 수행했다면 목록 이해만 하면 됩니다(Python 개발자는 맵/필터보다 이것을 선호하기 때문입니다).

다음은 정렬 알고리즘입니다.

1부에 이어 두 번째 부분에서는 중간 페이지의 합계를 원했지만 페이지 순서가 제대로 지정되지 않은 경우가 있었습니다. 중간 페이지 번호를 검색하기 전에 순서를 수정하라는 지시도 나와 있습니다.

동료들이 완전한 정렬 알고리즘 없이 문제를 해결하는 동안 저는 페이지 규칙을 설명하는 섹션에서 앞서 설명한 퍼즐과 똑같은 방식으로 문제를 해결하기로 결정했습니다. 이미 비교 부분(check_pair)이 완료되었으므로 이제 요소를 이동하는 함수가 필요합니다.

def parse(
    input: str,
) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
    def inner(
        current, incoming
    ) -> tuple[tuple[tuple[int, int], ...], tuple[tuple[int, ...], ...]]:
        rules, pages = current

        if "|" in incoming:
            return rules + (
                tuple(int(item) for item in incoming.strip().split("|")),
            ), pages

        else:
            return rules, pages + (
                tuple(int(item) for item in incoming.strip().split(",")),
            )

    return reduce(
        inner, filter(lambda line: line.strip(), input.strip().splitlines()), ((), ())
    )

1,2,3,4,5가 있고 함수가 수신 번호를 현재 번호 바로 앞으로 이동한다고 가정합니다. 전류 = 2, 수신 = 4라고 가정하면 그 대가로 1,4,2,3,5를 얻게 됩니다(증가하는 숫자 값에 따라 정렬한다고 가정).

친구에게 알고리즘을 설명하려 했으나 실패했습니다

다음은 제가 직접 작성한 초안에 표시된 알고리즘을 실제 코드로 바꾸는 것입니다.

def check_pair(rules: tuple[tuple[int, int], ...], alpha: int, beta: int) -> bool:
    return (beta, alpha) not in rules

네, 안타깝게도 재귀 상태입니다. 읽기에 더 친숙할 수 있는 첫 번째 버전을 게시해야 합니다.

from itertools import combinations

def check_pages(rules: tuple[tuple[int, int], ...], pages: tuple[int, ...]) -> bool:
    return all(
        check_pair(rules, alpha, beta)
        for alpha, beta in combinations(pages, 2)
    )

두 가지 모두 본질적으로 동일하며 최종 기능 버전은 약간 최적화되었습니다. 초안 스크린샷을 참고하면 포인터가 2개 있는데 노란색 밑줄은 코드에서 포인터라는 이름으로, 파란색 밑줄은 입력됩니다.

알고리즘은 다음과 같이 작동합니다.

1. 첫 번째 요소에 포인터를 설정하는 것부터 시작됩니다.
2. 처음에 들어오는 요소는 항상 옆에 있는 요소입니다.
3. 들어오는 포인터는 한 번에 한 요소씩 진행하며 규칙을 위반하는 경우 값을 현재 바로 앞의 값으로 이동합니다.
4. 이런 일이 발생하면 수신 포인터가 재설정되고 현재의 다음으로 다시 이동합니다.
5. 현재 포인터는 위치를 변경하지 않지만 이제 이전 단계에서 삽입된 새 요소를 가리키고 있습니다.

들어오는 포인터가 변경 사항을 적용하지 않고 목록의 나머지 부분을 단계별로 진행하는 경우 현재 포인터를 전진시키고(그리고 들어오는 포인터는 옆 위치로 다시 초기화됨) 프로세스를 다시 반복합니다.

마지막 2개 요소를 비교하는 알고리즘이 완료된 후 프로세스가 종료되고, 정렬된 페이지가 결과로 반환됩니다. 그런 다음 2부에서 사용할 수 있는 모든 것을 조립할 수 있습니다.

47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47

두 부분의 코드는 비슷합니다. part1을 약간 수정하고 필터 절을 약간 변형한 것뿐입니다. get_middle은 대신 정렬된 목록을 받습니다. 본질적으로 if는 약간 다른 조합으로 함수 형태의 빌딩 블록에서 답을 조립하는 것과 같습니다.

시간 복잡도가 O(n^2)에 가깝기 때문에 이는 여전히 효율적인 알고리즘은 아닙니다. 윈드서핑의 캐스케이드 AI 동반자에 따르면 알고리즘은 어떤 면에서는 삽입 정렬과 유사합니다(예, 알고리즘에 대한 설명을 제공하는 AI 도구가 유용한 경우입니다).

오늘은 여기까지입니다. 알고리즘이 잘 작동해서 다행입니다. 비록 현재 내 생활은 엉망이지만(자금 문제로 인해 프로젝트에서 제외되었습니다). 시간이 지날수록 상황이 좋아지길 바라면서 다음주에 다시 글을 쓰겠습니다.

위 내용은 코드 4의 출현을 위한 정렬 알고리즘을 코딩하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!