Bagaimana untuk membaiki jambatan, Advent of Code ay 7

Selepas apa yang dirasakan selama-lamanya (lima jam, tepatnya), Hari 20 bahagian 2 akhirnya memutuskan untuk bekerjasama. Saya masih sedikit terpinga-pinga kerana menunggu, tetapi tugas memanggil! Hari ini kita menangani Hari Ke-7 Kedatangan Kod, menyambung dari tempat yang kita tinggalkan dengan Hari 6 minggu lepas. Tugas kami hari ini ialah membaiki jambatan supaya kami boleh menyeberanginya dan meneruskan pencarian kami untuk Ketua Sejarawan.

Ilustrasi comel yang dihasilkan oleh Microsoft Copilot

Cabaran hari ini memberi kami jenis masalah yang berbeza: kami diberi senarai nombor yang disusun dalam format tertentu (nasib baik, bukan teka-teki 2D hari ini…). Setiap baris direka bentuk untuk membentuk persamaan, tetapi operator tidak hadir. Tugas kami adalah untuk menguji pelbagai operator untuk menentukan sama ada persamaan yang terhasil adalah benar.

Kami menggunakan dua fungsi penghuraian untuk memproses input. Fungsi parse mula-mula membahagikan setiap baris dengan aksara bertindih (:):

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

parse_line menukar rentetan yang dijangkakan dan rentetan operan kepada integer, mengembalikan tuple yang mengandungi integer dijangka dan tuple of integer operan

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

Saya lebih suka gaya pengaturcaraan berfungsi, dan walaupun Python bersifat penting, perpustakaan seperti toolz/cytoolz sangat berguna. Hari ini, kami menggunakan thread_first daripada toolz.functoolz. Begini cara thread_first beroperasi: Ia memerlukan nilai awal dan kemudian menggunakan jujukan pasangan fungsi-hujah, menjalinkan hasilnya melalui setiap langkah.

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

Dalam contoh ini, thread_first bermula dengan 1, kemudian menggunakan tambah dengan 2 (menghasilkan 3), dan akhirnya menggunakan mul dengan 2 (menghasilkan 6). Ini bersamaan dengan mul(tambah(1, 2), 2).

Kami kini mentakrifkan fungsi kira untuk menggunakan operasi. Ia memerlukan satu tuple fungsi (funcs) dan tuple of operand (operand) sebagai input:

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

Penegasan memastikan satu lebih banyak operan daripada fungsi. operan[1:] menyediakan operan untuk fungsi. zip dan * buat pasangan fungsi-operand untuk thread_first, yang melakukan pengiraan berantai.

Contoh:

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

Kini kita boleh mengesahkan setiap baris input menggunakan fungsi check_can_calibrate. Fungsi ini mengambil hasil yang dijangkakan, operan dan sekumpulan fungsi yang mungkin sebagai input dan mengembalikan True jika mana-mana gabungan fungsi menghasilkan hasil yang dijangkakan, dan False sebaliknya:

def check_can_calibrate(
    expected: int,
    operands: tuple[int, ...],
    funcs: tuple[Callable[[int, int], int], ...],
) -> bool:
    return next(
        filter(
            None,
            (
                calculate(funcs, operands) == expected
                for funcs in product(funcs, repeat=len(operands) - 1)
            ),
        ),
        False,
    )

itertools.product menjana semua gabungan fungsi. Ungkapan penjana menyemak sama ada sebarang kombinasi sepadan dengan hasil yang dijangkakan. penapis(Tiada, ...) dan seterusnya(..., Salah) dengan cekap mencari hasil Benar pertama atau kembalikan Salah jika tiada yang ditemui.

Untuk Bahagian 1, kami hanya diberikan pengendali pendaraban dan penambahan. Teka-teki meminta jumlah nilai yang dijangkakan, di mana persamaan yang sah boleh dibentuk menggunakan operator ini. Kami melaksanakan fungsi menilai untuk mengira jumlah ini:

def parse(input: str) -> tuple[tuple[int, tuple[int, ...]], ...]:
    return tuple(
        parse_line(*line.strip().split(":")) for line in input.strip().splitlines()
    )

Ia berulang melalui input yang dihuraikan dan menjumlahkan nilai yang dijangkakan yang check_can_calibrate mengembalikan True.

Akhir sekali, kami menyusun bahagian 1 daripada apa yang telah kami bina setakat ini

def parse_line(expected: str, operands: str) -> tuple[int, tuple[int, ...]]:
    return int(expected), tuple(int(item) for item in operands.strip().split(" "))

Fungsi ini menghuraikan input menggunakan parse dan kemudian memanggil menilai dengan data yang dihuraikan dan tuple fungsi (operator.mul, operator.add), masing-masing mewakili pendaraban dan penambahan.

Dalam Bahagian 2, kami menemui operator gabungan yang menggabungkan dua nombor bersama-sama. Dalam Python, ini bersamaan dengan menggunakan f-string:

>>> from operator import add, mul
>>> assert thread_first(1, (add, 2), (mul, 2)) == mul(add(1, 2), 2)

Ini secara berkesan mencipta nombor baharu dengan menambahkan digit nombor kedua pada penghujung nombor pertama.

Sebagai alternatif, kita boleh melakukan penggabungan menggunakan formula matematik. Bilangan digit dalam integer positif x boleh dikira menggunakan formula:

Ini berfungsi kerana log₁₀(x) memberikan kuasa yang mana 10 mesti dinaikkan untuk mendapatkan x. Fungsi lantai membundarkan ini ke integer terdekat, dan menambah 1 memberikan bilangan digit. Mari kita ambil 123 sebagai contoh:

Melaksanakan ini sebagai fungsi int_concat:

def calculate(
    funcs: tuple[Callable[[int, int], int], ...], operands: tuple[int, ...]
) -> int:
    assert len(operands) - len(funcs) == 1

    return thread_first(operands[0], *(zip(funcs, operands[1:])))

Melaksanakan penyatuan integer secara matematik mengelakkan overhed penukaran rentetan. Penggabungan rentetan melibatkan peruntukan dan manipulasi memori, yang kurang cekap daripada aritmetik integer langsung, terutamanya untuk nombor besar atau banyak gabungan. Oleh itu, pendekatan matematik ini secara amnya lebih pantas dan lebih cekap ingatan.

Akhir sekali, kami melaksanakan bahagian 2. Satu-satunya perbezaan berbanding bahagian 1 ialah penambahan operator int_concat:

>>> from operator import add, mul
>>> calculate((add, mul), (2,3,4))
20

Ta-da! Kami telah memecahkan Hari ke-7. Ini adalah cabaran yang agak mudah, terutamanya berbanding hari-hari kemudian (pengoptimuman Hari ke-20 masih membuat saya sakit kepala?). Walaupun ia mungkin bukan yang paling berprestasi, saya mengutamakan kebolehbacaan.

Itu sahaja untuk hari ini. Selamat bercuti dan selamat tahun baru?! Bergerak untuk situasi pekerjaan yang lebih baik tahun depan (masih #OpenToWork, ping saya untuk kerjasama!), dan saya akan menulis lagi, minggu depan.

Atas ialah kandungan terperinci Bagaimana untuk membaiki jambatan, Advent of Code ay 7. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!