Advent of Code 4 の並べ替えアルゴリズムをコーディングする方法

前回の投稿で、私が今年の Advent of Code に参加していることを簡単に述べました。偶然にも、パズルの 1 つ、特に 5 日目に公開されたものでは、リスト内のページの順序を修正する必要があります。これは、ソート アルゴリズムの実装について投稿してから間もなくのことなので、それについて書くべきだと思います。

ソートアルゴリズムを描いたかわいい画像

Advent of Code について聞いたことがない人のために説明すると、これは Eric Wastl が主催する毎年恒例のイベントです。毎年、ホリデーシーズンを舞台にした物語が語られますが、今年は主任歴史家を探す物語であり、おそらくクリスマスの大きなそりの打ち上げで重要な人物となるでしょう。このチャレンジは毎年12月1日から25日まで実施されます。毎日プロットが進行し、プログラミング パズルが含まれています (入力機能も付いています)。

ストーリーのナレーション内で、通常、パズルは明確に定義され、テスト ケースが含まれます。すべてのパズルは 2 つの部分に分かれており、2 番目の部分は最初の答えを送信した後にのみ表示されます。

参加者は、導き出された答えが一致する限り、任意の言語で任意のアルゴリズムを実装したり、プログラミングを完全にスキップしたりすることもできます。今年は 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() で行に分割し、内部関数に送信して 2 つのタプル (1 つはページ ルール用、もう 1 つはページ シーケンス用) を生成します。このコードでは、区切り文字 | によって 2 種類の定義を区別しています。ページルールの場合は 、ページの場合は ,

パズルの最初の部分では、ストーリーはページが正しいかどうかを確認するように求められました。まずは、その仕事を行う関数を実装しましょう:

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

次に、ページのすべての組み合わせを送信する別の関数 (combinations((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 つを個別の関数に分割した主な理由は、各部分をできるだけ小さくしたいためです。私の経験から言えば、物事を十分に小さくしておくと、テストしやすくなるだけでなく、最終入力 (通常は不当に大きい) のデバッグにも役立ちます。

パート 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 から引き続き、2 番目のパートでは中間ページの合計が必要でしたが、ページが適切に順序付けされていない場合に対応しました。この指示では、中央のページ番号を取得する前に順序を修正するよう求められました。

私の同僚は本格的な並べ替えアルゴリズムを使わずにこの問題を解決できましたが、私は、ページ ルールを説明するセクションで前述したパズルの方法とまったく同じ方法でそれを行うことにしました。比較部分 (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. 受信ポインターは一度に 1 つの要素をステップスルーし、ルールに違反する場合は値を現在の値の直前に移動します。
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) に近いため、これはまだ効率的なアルゴリズムとは言えません。 Windsurf のカスケード AI コンパニオンによると、このアルゴリズムはある意味で挿入ソートに似ています (そうです、このような場合に AI ツールが役立ち、アルゴリズムに説明を提供します)。

今日はここまでです。アルゴリズムが正常に動作していることを嬉しく思います。ただし、私の生活は現在めちゃくちゃです (資金の問題でプロジェクトから撤退したばかりです)。時間が経つにつれて状況が良くなることを願っています。また来週も書きます。

以上がAdvent of Code 4 の並べ替えアルゴリズムをコーディングする方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。