Bagaimana untuk mengodkan Algoritma Pengisihan untuk Kemunculan Kod 4

Dalam catatan sebelum ini, saya secara ringkas menyatakan bahawa saya akan menyertai Kemunculan Kod tahun ini. Secara kebetulan, dalam salah satu teka-teki, khususnya yang diterbitkan pada hari ke-5, melibatkan penetapan susunan halaman dalam senarai. Ini berlaku tidak lama selepas saya menyiarkan tentang melaksanakan algoritma pengisihan, jadi saya rasa saya patut menulis tentangnya.

Imej comel yang menggambarkan beberapa algoritma pengisihan

Bagi mereka yang belum pernah mendengar tentang Advent of Code, ia adalah acara tahunan yang dianjurkan oleh Eric Wastl. Setiap tahun, ia menceritakan kisah yang bermula pada musim cuti, tahun ini mengenai mencari Ketua Sejarawan, mungkin seorang tokoh penting dalam setiap pelancaran giring Krismas yang besar. Cabaran akan berlangsung dari pertama Disember setiap tahun, sehingga 25hb. Setiap hari, plot itu berjalan, dan ia mengandungi teka-teki pengaturcaraan (dan ia disertakan dengan input).

Dalam penceritaan cerita, teka-teki biasanya ditakrifkan dengan jelas, dan termasuk kes ujian. Setiap teka-teki dibahagikan kepada dua bahagian, dan bahagian kedua muncul hanya selepas menyerahkan jawapan pertama.

Peserta boleh melaksanakan sebarang algoritma, dalam mana-mana bahasa, atau bahkan melangkau pengaturcaraan sama sekali, selagi jawapan yang diperoleh sepadan. Tahun ini saya cuba mengodkan penyelesaian dalam Python, dan selepas 9 hari, saya rasa saya belajar sedikit sebanyak sepanjang perjalanan.

Pada hari ke-5, cerita itu meminta untuk membantu dengan pencetakan manual keselamatan. Input mengandungi kedua-dua peraturan halaman dan senarai halaman yang cuba dicetak oleh bunian.

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

Mari mulakan dengan menghuraikan input:

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

Fungsi menerima input sebagai rentetan bernama input, memecahkannya kepada baris dengan .splitlines(), untuk dihantar ke dalam fungsi dalaman untuk menghasilkan dua tupel, satu untuk peraturan halaman dan satu lagi untuk jujukan halaman. Kod ini membezakan dua jenis definisi melalui pemisah, | untuk peraturan halaman dan , untuk halaman.

Dalam bahagian pertama teka-teki, cerita itu meminta untuk menyemak sama ada halaman itu teratur. Mari mulakan dengan melaksanakan fungsi yang melakukan tugas:

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

Dan kemudian fungsi lain yang menghantar semua gabungan halaman (gabungan((1,2,3), 2) mengembalikan 1,2, 1,3 dan 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)
    )

Sebab utama saya memisahkan kedua-dua ini kepada fungsi individu adalah kerana saya ingin memastikan setiap bahagian sekecil mungkin. Daripada pengalaman saya, mengekalkan perkara yang cukup kecil bukan sahaja menjadikannya boleh diuji, ia biasanya juga membantu menyahpepijat input akhir (yang biasanya tidak munasabah besar).

Banyak kali, bahagian 2 datang sebagai satu kejutan, dan ia adalah perkara biasa untuk mendapati ia memerlukan semakan dalam reka bentuk kod untuk bahagian 1. Ia boleh menjadi variasi kecil kepada sesuatu yang telah anda laksanakan atau memerlukan fungsi yang berbeza perintah doa untuk matlamat yang berbeza, dsb. Saya mengekalkan tabiat menulis fungsi pendek di tempat kerja (sebagai alternatif kepada ulasan).

Fungsi kecil seperti ini hanya berfungsi jika nama itu bagus, jadi anda perlu memberi perhatian yang baik kepada penamaan. Ini memerlukan latihan, tetapi sebaik sahaja anda menguasainya, pendekatan ini boleh menjadikan kod mendokumentasikan diri dengan luar biasa. Fungsi skala yang lebih besar boleh membaca seperti cerita dan pembaca boleh memilih fungsi yang mana untuk diselami untuk mendapatkan butiran lanjut apabila dia memerlukannya.

dipetik daripada artikel bertajuk Function Length, dikarang oleh Martin Fowler

Kembali kepada teka-teki.

Pada akhirnya, teka-teki meminta jumlah nombor halaman tengah untuk semua kes di mana halaman itu disusun dengan betul.

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

Agak lurus ke hadapan, jika anda telah melakukan semuanya dengan betul, ia hanya perlu memahami senarai sahaja (kerana pembangun Python lebih suka ini berbanding peta / penapis).

Seterusnya, ialah algoritma pengisihan:

Bersambung dari bahagian 1, bahagian kedua mahukan jumlah halaman tengah, tetapi untuk kes di mana halaman tidak disusun dengan betul. Arahan juga meminta untuk membetulkan pesanan sebelum mendapatkan semula nombor halaman tengah.

Walaupun rakan sebaya saya berjaya membetulkannya tanpa algoritma pengisihan sepenuhnya, saya memutuskan untuk melakukannya dengan cara yang tepat yang diterangkan teka-teki sebelum ini, dalam bahagian yang menerangkan peraturan halaman. Saya sudah menyelesaikan bahagian perbandingan (check_pair), sekarang saya memerlukan fungsi yang akan menggerakkan elemen.

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

Andaikan saya mempunyai 1,2,3,4,5 dan fungsi itu mengalihkan nombor masuk, ke kanan sebelum nombor semasa. Dengan mengandaikan semasa = 2, dan masuk = 4, maka saya akan mendapat 1,4,2,3,5 sebagai balasan (dengan mengandaikan kita menyusun mengikut nilai berangka yang semakin meningkat).

Percubaan saya yang tidak berjaya untuk menerangkan algoritma kepada rakan

Seterusnya ialah menukar algoritma, yang ditunjukkan dalam draf tulisan tangan saya, kepada kod sebenar.

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

Ya, malangnya ia dalam rekursi. Saya sepatutnya menyiarkan versi pertama, yang mungkin lebih mesra untuk dibaca:

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

Kedua-duanya pada asasnya adalah sama, dengan versi fungsi akhir dioptimumkan sedikit. Dengan merujuk kepada tangkapan skrin draf, saya mempunyai dua penunjuk, garis bawah kuning dinamakan penunjuk dalam kod dan garis bawah biru yang masuk.

Algoritma berfungsi seperti berikut:

1. Ia bermula dengan menetapkan penuding kepada elemen pertama.
2. Pada mulanya masuk sentiasa menjadi elemen di sebelahnya.
3. Penunjuk masuk akan melangkah melalui satu elemen pada satu masa dan akan mengalihkan nilai ke kanan sebelum semasa jika ia melanggar peraturan.
4. Apabila itu berlaku, penuding masuk ditetapkan semula dan beralih semula ke arus seterusnya.
5. Penunjuk semasa tidak menukar kedudukan, tetapi ia kini menghala ke elemen baharu yang telah dimasukkan dalam langkah sebelumnya.

Jika penuding masuk berjaya melangkah melalui baki senarai tanpa memperkenalkan perubahan, kami memajukan penuding semasa (dan penuding masuk dimulakan semula ke kedudukan di sebelahnya), dan ulangi proses itu sekali lagi.

Proses tamat selepas algoritma selesai membandingkan 2 elemen terakhir, dan kemudian mengembalikan halaman yang diisih sebagai hasilnya. Kemudian, kita boleh meneruskan untuk memasang apa sahaja yang kita ada untuk bahagian 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

Kod untuk kedua-dua bahagian adalah serupa. Ia hanyalah sedikit pengubahsuaian kepada bahagian1, hanya beberapa variasi dalam klausa penapis, dan sebaliknya get_middle menerima senarai yang diisih. Pada asasnya, seolah-olah saya sedang menyusun jawapan daripada blok binaan dalam bentuk fungsi, dalam gabungan yang sedikit berbeza.

Walaupun ini masih bukan algoritma yang cekap, kerana kerumitan masa hampir dengan O(n^2). Menurut pendamping AI lata dalam luncur angin, algoritma menyerupai jenis sisipan dalam beberapa cara (ya, ini adalah apabila alat AI berguna, memberikan penjelasan kepada algoritma).

Itu sahaja untuk hari ini, saya gembira kerana algoritma ini berfungsi dengan baik, walaupun hidup saya pada masa ini kucar-kacir (baru menarik diri daripada projek kerana isu pembiayaan). Semoga keadaan menjadi lebih baik seiring dengan berlalunya masa, dan saya akan menulis lagi, minggu depan.

Atas ialah kandungan terperinci Bagaimana untuk mengodkan Algoritma Pengisihan untuk Kemunculan Kod 4. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!