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

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

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

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

參加者は、導(dǎo)き出された答えが一致する限り、任意の言語で任意のアルゴリズムを?qū)g裝したり、プログラミングを完全にスキップしたりすることもできます。今年は Python でソリューションをコーディングしようとしていますが、9 日間を経て、この旅を通してかなりの量を?qū)Wんだように感じています。

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()), ((), ())
    )

関數(shù)は入力を input という名前の文字列として受け取り、.splitlines() で行に分割し、內(nèi)部関數(shù)に送信して 2 つのタプル (1 つはページ ルール用、もう 1 つはページ シーケンス用) を生成します。このコードでは、區(qū)切り文字 | によって 2 種類の定義を區(qū)別しています。ページルールの場合は 、ページの場合は ,

パズルの最初の部分では、ストーリーはページが正しいかどうかを確認(rèn)するように求められました。まずは、その仕事を行う関數(shù)を?qū)g裝しましょう:

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

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

パート 2 は意外な結(jié)果になることが多く、パート 1 のコード設(shè)計の修正が必要になることも珍しくありません。これは、実裝したものに小さな変更が加えられたり、別の機(jī)能が必要になったりする可能性があります。さまざまな目的のための呼び出し順序など。私は仕事で (コメントの代わりに) 短い関數(shù)を書く習(xí)慣を維持しています。

このような小さな関數(shù)は、名前が適切である場合にのみ機(jī)能するため、名前付けには十分な注意を払う必要があります。これには練習(xí)が必要ですが、一度慣れてしまえば、このアプローチによりコードが著しく自己文書化されます。より大規(guī)模な関數(shù)は物語のように読むことができ、読者は必要に応じてどの関數(shù)を詳細(xì)に調(diào)べるかを選択できます。

Martin Fowler

が執(zhí)筆した 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

非常に簡単です。すべてを正しく行っていれば、あとはリストの內(nèi)包理解だけです (Python 開発者はマップ/フィルターよりもこれを好むため)。

次は並べ替えアルゴリズムです:

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

私の同僚は本格的な並べ替えアルゴリズムを使わずにこの問題を解決できましたが、私は、ページ ルールを説明するセクションで前述したパズルの方法とまったく同じ方法でそれを行うことにしました。比較部分 (check_pair) はすでに完了しているので、要素を移動する関數(shù)が必要です。

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 があり、関數(shù)が受信した數(shù)値を現(xiàn)在の數(shù)値の直前に移動するとします?，F(xiàn)在 = 2、受信 = 4 と仮定すると、1、4、2、3、5 が返されます (増加する數(shù)値に従って配置していると仮定します)。

友人にアルゴリズムを説明しようとして失敗しました

次は、手書きの下書きに示されたアルゴリズムを?qū)g際のコードに変換します。

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)
    )

どちらも本質(zhì)的には同じですが、最終的な機(jī)能バージョンはわずかに最適化されています。ドラフトのスクリーンショットを參照すると、2 つのポインターがあります。黃色の下線はコード內(nèi)でポインターと呼ばれており、青色の下線は入力されています。

アルゴリズムは次のように機(jī)能します:

1. 最初の要素にポインターを設(shè)定することから始まります。
2. 最初に受信するのは常にその隣の要素です。
3. 受信ポインターは一度に 1 つの要素をステップスルーし、ルールに違反する場合は値を現(xiàn)在の値の直前に移動します。
4. それが起こると、受信ポインタはリセットされ、現(xiàn)在のポインタの次のポインタに戻ります。
5. 現(xiàn)在のポインターの位置は変わりませんが、前のステップで挿入された新しい要素を指しています。

著信ポインタが変更を?qū)毪工毪长趣胜辚攻趣螝垽辘颔攻匹氓抓攻氅`できた場合は、現(xiàn)在のポインタを進(jìn)め (そして著信ポインタはその隣の位置に再初期化され)、このプロセスを再度繰り返します。

アルゴリズムが最後の 2 つの要素を比較した後にプロセスは終了し、結(jié)果としてソートされたページを返します。次に、パート 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 は代わりにソートされたリストを受け取ります。本質(zhì)的に、 if は、関數(shù)の形をしたビルディングブロックから、少し異なる組み合わせで答えを組み立てているようなものです。

時間計算量が O(n^2) に近いため、これはまだ効率的なアルゴリズムとは言えません。 Windsurf のカスケード AI コンパニオンによると、このアルゴリズムはある意味で挿入ソートに似ています (そうです、このような場合に AI ツールが役立ち、アルゴリズムに説明を提供します)。

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

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