Tugas Anda adalah menentukan panjang keturunan terpanjang di bawah "gunung" yang direpresentasikan sebagai kisi-kisi bilangan bulat. "Keturunan" adalah setiap jalur dari sel awal ke sel yang berdekatan secara ortogonal dengan ketinggian yang sangat menurun (yaitu tidak diagonal dan tidak dengan ketinggian yang sama). Misalnya, Anda dapat beralih dari 5-4-3-1 tetapi tidak 5-5-4-3-3-2-1. Panjang jalur ini adalah berapa banyak pergerakan sel yang ada dari sel awal ke sel akhir, sehingga 5-4-3-1 adalah panjang 3.
Anda akan menerima kotak persegi panjang sebagai input dan Anda harus menampilkan bilangan bulat yang menunjukkan penurunan terpanjang.
Contohnya
1 2 3 2 2
3 4 5 5 5
3 4 6 7 4
3 3 5 6 2
1 1 2 3 1
Panjang keturunan terpanjang di gunung ini adalah 5. Jalur terpanjang dimulai pada 7, bergerak ke kiri, ke atas, ke kiri, ke atas, lalu ke kiri (7-6-5-4-2-1). Karena ada 5 gerakan di jalur ini, panjang jalur adalah 5.
Mereka mungkin semua nomor yang sama.
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
Karena peta ketinggian ini datar, penurunan terpanjang adalah 0. (bukan 19, karena urutan jalur harus benar-benar turun)
Peta ketinggian dapat terdiri dari angka yang lebih besar dari angka satu digit.
10 12 13 14 15 15
17 14 15 15 15 16
18 20 21 15 15 15
21 14 10 11 11 15
15 15 15 15 15 15
Jalur terpanjang di sini adalah panjang 6. (21, 20, 18, 17, 14, 12, 10)
... Dan jumlah yang lebih besar juga baik-baik saja.
949858 789874 57848 43758 387348
5848 454115 4548 448545 216464
188452 484126 484216 786654 145451
189465 474566 156665 132645 456651
985464 94849 151654 151648 484364
Keturunan terpanjang di sini adalah panjang 7. (786654, 484216, 484126, 474566, 156665, 151654, 151648, 151648, 132645)
Aturan dan Catatan
- Kisi dapat diambil dalam format apa pun yang nyaman. Tentukan format Anda dalam jawaban Anda.
- Anda dapat mengasumsikan bahwa peta ketinggian berbentuk persegi panjang sempurna, tidak kosong, dan hanya berisi bilangan bulat positif dalam rentang bilangan bulat 32-bit yang ditandatangani.
- Jalur turun terpanjang dapat dimulai dan berakhir di mana saja di grid.
- Anda tidak perlu menjelaskan jalur penurunan terpanjang dengan cara apa pun. Hanya panjangnya yang dibutuhkan.
- Kode terpendek menang
Jawaban:
JavaScript (ES7),
106 103 10298 byteCobalah online!
Berkomentar
Bagaimana?
Selama iterasi pertama, , dan semuanya tidak terdefinisi dan kedua tes ( A dan B dalam komentar) dievaluasi ke NaN , yang memicu panggilan rekursif. Oleh karena itu, semua sel dianggap sebagai titik awal yang mungkin dari jalur.x y hal
sumber
Jelly ,
23 2120 byte-2 Terima kasih kepada Erik the Outgolfer
Cobalah online! (terlalu tidak efisien untuk contoh - path di sini
95 94 93 83 77 40 10
begitu6
dihasilkan)Bagaimana?
sumber
Python 2,
150147140136134132125123120 byteCobalah online!
Mengambil input dalam bentuk kamus
(x, y): value
.-7 byte terima kasih kepada wizzwizz4, -2 byte terima kasih kepada Jonathan Allen, -2 byte terima kasih kepada BMO
Alternatif,
123121 byteCobalah online!
Pada dasarnya solusi yang sama, hanya dengan lambda akhir digantikan oleh program yang sebenarnya. Saya pribadi lebih suka yang pertama, tetapi yang ini mendekati jumlah byte dengan memungkinkan
g
untuk digunakan sebagai variabel global.sumber
Bersih ,
211207 byteCobalah online!
Solusi brute force mengambil daftar-daftar-bilangan bulat (
[[Int]]
).Driver TIO mengambil format yang sama dengan contoh melalui STDIN.
Terlalu lambat untuk menjalankan salah satu contoh pada TIO dan mungkin juga secara lokal, tetapi bekerja secara teori.
Yang ini melakukan hal yang sama lebih cepat, dapat melakukan 3x3 atau 2x4 pada TIO dan 4x4 dan 3x5 secara lokal.
Bertakuk:
sumber
Python 3 , 219 byte
Cobalah online!
Kisi direpresentasikan sebagai daftar daftar:
Kode ungolf asli:
sumber
Haskell ,
188186 byteCobalah online!
notElem
(not.).(#)
Cobalah online!
Penjelasan & Tidak Disatukan
Strategi: Cobalah secara rekursif semua jalur yang layak, catat entri yang dikunjungi dan maksimalkan panjangnya.
elem
notElem
(#)
elem
maximize
Sekarang kita siap mendefinisikan fungsi rekursif kita
fun :: [[Integer]] -> Integer
:sumber
[[Integer]]
adalah daftar daftar. Meskipun dalam TIO tertaut Anda memiliki pembungkusparse :: String -> [[Integer]]
, st. Anda dapat menggunakan string yang dipisah pada spasi dan baris baru.Python 3,
263227 byteCobalah online!
-2 byte terima kasih kepada BMO
Mengambil kisi-kisi dalam format
{(0, 0): 1, (1, 0): 2, ...}
. Format ini dapat dihasilkan dari format contoh menggunakan fungsi utilitas berikut:sumber