Kemunculan Code Day Keypad Conundrum

Hari 21 : Teka-teki papan kekunci

GitHub Repo - Penyelesaian

Cabaran hari ini adalah sukar dan saya mengambil masa 2 hari untuk mempunyai sedikit masa untuk menyelesaikannya, serta memahami sepenuhnya logiknya. Sesuatu yang saya temui tahun ini ialah, saya telah bergelut untuk memahami niat arahan itu.

Saya harap seperti diri saya anda telah belajar sesuatu daripada cabaran dan penyelesaian ini. Saya mendapati setiap tahun saya mengambil bahagian dalam Advent of Code, saya belajar banyak, itulah sebabnya saya suka mencuba bahasa yang berbeza atau mendorong diri saya keluar dari zon selesa saya. Saya menganggap Advent of Code lebih kepada peluang pembelajaran / pembangunan di mana pembangun harus berkongsi pengetahuan dan idea mereka, dan bukannya menganggapnya sebagai satu persaingan sahaja.

Satu lagi tikaman Python hari ini dan saya gembira dengan penyelesaiannya. Sesuatu yang saya pelajari hari ini ialah; Kelas tidak boleh ubah menggunakan anotasi @dataclass(frozen=True) pada pengisytiharan kelas.

Saya mencipta kelas Lokasi sebagai kelas pembantu untuk menavigasi dan mengemas kini koordinat (sedikit seperti yang saya lakukan sebelum ini dengan kelas Point dalam beberapa penyelesaian C#.

Sebagai seseorang yang datang dari latar belakang C# / .Net yang ditaip kuat, saya cuba menambahkan jenis pada kod saya untuk membantu saya memvisualisasikan perkara yang saya sedang usahakan semasa masalah kompleks ini. Saya juga biasa melakukan ini semasa menulis TypeScript, jadi hampir kedua.

Masalah Hari Ini

**Bahagian Pertama **memperkenalkan masalah menavigasi dan mengawal berbilang robot untuk menghantar arahan ke robot seterusnya untuk memasukkan kod pada papan kekunci berangka.

Bahagian Kedua membina masalah dengan meningkatkan kerumitan melalui rantaian robot dan papan kekunci arah, menunjukkan sifat eksponen kebergantungan berbilang peringkat.

Walkthrough

Seperti yang telah kita ketahui susun atur arah dan pad kekunci, kita boleh membina kamus semua pemetaan lokasi dan arah di mana ia boleh bergerak.

Caching (cache dan moves_cache)

cache: Menyimpan urutan terpendek yang dikira sebelum ini untuk mengelakkan pengiraan berlebihan, meningkatkan prestasi.

moves_cache: Menyimpan semua urutan pergerakan yang sah antara mana-mana dua butang pada pad kekunci, diprakira untuk carian pantas.

Pengiraan Panjang Terpendek (panjang_terpendek)

Mengira urutan tekan butang terpendek secara rekursif untuk menaip kod yang diberikan.

Mengendalikan rantaian berbilang peringkat pad kekunci dengan mengulangi tahap (kedalaman_kereta) sehingga had (had_kedalaman).

*Bergerak Antara Kedudukan (bergerak_antara_kedudukan)
*

Mengira semua urutan pergerakan yang sah antara dua butang pada pad kekunci, memastikan robot tidak panik dengan menunjuk pada kedudukan yang tidak sah (jurang).

Permulaan Cache (create_cache_moves)

Mengira urutan pergerakan yang sah untuk semua pasangan butang pada kedua-dua pad kekunci angka dan arah, menjimatkan pengiraan masa jalan.

Fungsi penyelesaian, kemudian gelung melalui input mengira kerumitannya dengan mendarab panjang jujukan dengan bahagian berangka kod, dan kemudian ringkaskan kerumitan untuk semua kod mengikut keperluan teka-teki.

Permutasi

Apakah yang dilakukan oleh pilih atur?

Fungsi pilih atur dalam Python (daripada modul itertools) menjana semua kemungkinan susunan tertib bagi koleksi item.

Contohnya:

from itertools import permutations

items = ['a', 'b', 'c']
list(permutations(items))

Ini akan menghasilkan:

[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

Setiap pilih atur ialah urutan unik yang mengandungi semua item dalam koleksi asal, tetapi dalam susunan yang berbeza.

Mengapa menggunakan pilih atur dan bukan gabungan?

permutasi:

Menjana semua kemungkinan susunan terpesan bagi koleksi item.
Urutan item penting.

manakala,
gabungan:

Menjana semua kemungkinan pilihan tidak tertib bagi koleksi item.

Tempahan barang tidak penting.

Mengapakah ketertiban penting dalam senario ini?

Navigasi Pad Kekunci: Kedudukan robot pada pad kekunci berubah selepas setiap pergerakan, jadi urutan pergerakan dilakukan secara langsung memberi kesan kepada keputusan.

Semakan Pergerakan yang Sah: Fungsi menyemak kesahihan kedudukan perantaraan semasa navigasi. Menukar susunan pergerakan mungkin membawa kepada laluan yang tidak sah.

Bilakah gabungan Akan Berguna Sebaliknya?

kombinasi mungkin berguna dalam senario di mana susunan pergerakan tidak penting atau anda memilih subset pergerakan atau butang tanpa mengambil kira urutannya.

Penggunaan pilih atur semasa adalah perlu kerana susunan pergerakan penting untuk navigasi pad kekunci. Menggantikannya dengan kombinasi akan memecahkan logik program. Jika tugas itu memerlukan mencari semua kumpulan pergerakan atau kekunci unik tanpa mengira urutan, maka gabungan akan lebih sesuai.

Bahagian yang paling sukar dalam teka-teki ialah memikirkan cara yang bagus dan bersih untuk menjejaki tahap kedalaman (permulaan) arahan robot -- saya mengambil sedikit masa untuk memberikan perhatian sepenuhnya kepadanya.

Atas ialah kandungan terperinci Kemunculan Code Day Keypad Conundrum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!