Mampatan batang mancis

Cabaran Mingguan 296

Setiap minggu Mohammad S. Anwar menghantar Cabaran Mingguan, peluang untuk kita semua mencari penyelesaian kepada dua tugas mingguan. Penyelesaian saya ditulis dalam Python terlebih dahulu, dan kemudian ditukar kepada Perl. Ini cara yang bagus untuk kita semua mempraktikkan beberapa pengekodan.

Cabaran, Penyelesaian saya

Tugasan 1: Mampatan Rentetan

Tugasan

Anda diberi rentetan aksara abjad, $chars.

Tulis skrip untuk memampatkan rentetan dengan pengekodan panjang larian, seperti yang ditunjukkan dalam contoh.

Unit termampat boleh sama ada satu aksara atau kiraan diikuti dengan aksara.

BONUS: Tulis fungsi penyahmampatan.

penyelesaian saya

Terima kasih kepada kuasa ungkapan biasa, ini adalah tugas yang agak lurus ke hadapan. Kedua-dua Python dan Perl membenarkan nilai gantian menjadi fungsi. Oleh itu saya mempunyai fungsi yang dipanggil sc yang akan menukar beberapa huruf menjadi nombor dan huruf. Contohnya jika input ialah aaa, ia akan mengembalikan 3a.

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

Maka ia adalah masalah untuk memanggil fungsi ini mengikut keperluan.

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])+)', sc, s)

Fungsi nyahmampat (Python sahaja) berfungsi dengan cara yang sama. Ia memerlukan corak nombor diikuti dengan huruf dan menukarnya kepada huruf yang mengulangi bilangan kejadian yang ditentukan.

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

Untuk pelaksanaan daripada baris arahan, saya menggunakan modul argparse untuk melihat sama ada pilihan --decompress ditentukan.

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("--decompress", help="decompress the input", action='store_true')
    parser.add_argument("str", help="the string to compress/decompress")
    args = parser.parse_args()

    if args.decompress:
        result = string_decompress(args.str)
    else:
        result = string_compress(args.str)
    print(result)

Contoh

$ ./ch-1.py abbc
a2bc

$ ./ch-1.py aaabccc
3ab3c

$ ./ch-1.py abcc
ab2c

$ ./ch-1.py --decompress a2bc
abbc

$ ./ch-1.py --decompress 3ab3c
aaabccc

$ ./ch-1.py --decompress ab2c
abcc

Tugasan 2: Petak Mancis

Tugasan

Anda diberi tatasusunan integer, @ints.

Tulis skrip untuk mengetahui sama ada boleh membuat satu segi empat sama menggunakan kayu seperti dalam tatasusunan @ints yang diberikan dengan $ints[ì] ialah panjang kayu ke-i.

penyelesaian saya

Ini akan menjadi sedikit panjang, jadi ikat diri anda. Perkara pertama yang saya periksa ialah jumlah batang boleh dibahagi dengan empat. Jika tidak, tiada penyelesaian yang mungkin dan saya boleh mengembalikan palsu

Saya juga boleh menyemak bahawa tiada satu batang lebih panjang daripada satu sisi. Jika ini berlaku, saya juga membalas palsu.

Dengan dua semakan ini, semua contoh akan memberikan hasil yang betul. Walau bagaimanapun, ia akan tersilap melaporkan bahawa 4 3 3 3 3 adalah benar sedangkan ia sebenarnya tidak.

Percubaan dua

Melihat contoh dan pemikiran saya sendiri, saya fikir penyelesaiannya ialah memadankan sepasang nilai untuk dipadankan dengan setiap sisi. Jadi untuk contoh 3 4 1 4 3 1 kita mempunyai dua pasang batang 3 dan 1 yang menjadikan empat. Ini akan menyelesaikan isu 4 3 3 3 3, kerana tiga tidak mempunyai yang sepadan.

Tetapi ini tidak akan berfungsi jika kayu itu 4 4 3 1 2 1 1, kerana sebelah menggunakan tiga kayu (satu 2 dan dua 1)

Percubaan tiga

Jadi percubaan saya yang seterusnya adalah lebih rumit sedikit, dan saya fikir adalah penyelesaian yang baik ... sehingga tidak. Untuk percubaan ini, saya mulakan dengan kayu terpanjang. Jika ia bukan panjang sisi, saya kemudian mengambil kayu terpanjang seterusnya yang diperlukan untuk melengkapkan sisi, dan mengulangi sehingga tiada penyelesaian yang mungkin. Menggunakan kaedah ini penyelesaian berikut adalah benar.

• 4 4 3 1 2 1 1
• 9 5 4 3 3 3 3 3 3
• 9 6 3 5 4 3 3 3
• 9 6 3 5 4 3 3 2 1

Saya fikir ini adalah penyelesaiannya, sehingga saya menyedari bahawa 9 5 3 1 5 2 2 3 3 3 tidak akan berfungsi. Bahagian pertama ialah 9, bahagian seterusnya ialah 5 3 1, dan bahagian ketiga akan gagal dengan 5 3 dan no 1.

Percubaan empat

Pada ketika ini, saya mula tertanya-tanya sama ada ia mungkin untuk menghasilkan penyelesaian yang tidak melibatkan kekerasan. Jadi saya tidur di atasnya, mencoretkan banyak perkara dalam tablet saya (saya sedang bercuti jadi tidak boleh menggunakan papan putih saya), dan tidur di atasnya semula. Kesimpulan saya ialah menggunakan fungsi rekursif adalah satu-satunya penyelesaian.

Mungkin saya terlalu memikirkan semua ini, atau mungkin ada penyelesaian mudah yang baru saya fikirkan (seperti yang berlaku minggu lepas).

Kod terakhir

Masih membaca? Syabas :)

Untuk tugasan ini, saya mempunyai fungsi rekursif yang dipanggil make_side. Ia memerlukan senarai (arrayref dalam Perl) kayu yang tinggal, dan panjang yang diperlukan. Ia kemudian pergi melalui kayu yang tinggal (tertinggi dahulu). Kemudian satu daripada tiga perkara berlaku:

• Jika kayu itu lebih panjang daripada panjang yang diperlukan, saya langkau.
• Jika panjang yang diperlukan, saya pulangkan.
• Jika ia pendek, saya menggunakannya dan memanggil fungsi itu semula untuk menggunakan batang lain. Panggilan itu mengeluarkan kayu terpakai dan mengurangkan panjang yang diperlukan dengan panjang kayu terpakai.

Fungsi ini akan mengembalikan senarai kayu yang digunakan, atau Tiada (undef dalam Perl) jika tiada gabungan kayu yang sah ditemui.

def sc(match):
    m = match.group(0)
    return str(len(m)) + m[0]

Sekeping akhir teka-teki, saya melakukan semakan yang dinyatakan dalam bahagian pertama (jumlah boleh dibahagikan dengan empat, tidak melekat lebih daripada satu sisi), dan kemudian memanggil fungsi di atas. Jika itu mengembalikan Tiada, saya kembali palsu. Jika semua kayu digunakan, saya kembali benar.

def string_compress(s: str) -> str:
    return re.sub(r'(([a-z])+)', sc, s)

Contoh

def usc(match):
    m = match.group(0)
    return m[-1] * int (m[:-1])

def string_decompress(s: str) -> str:
    return re.sub(r'(\d+[a-z])', usc, s)

Atas ialah kandungan terperinci Mampatan batang mancis. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!