Deskripsi tantangan
Sebuah subsequence monoton adalah urutan angka [a1, a2, ..., an]
sehingga
a1 <= a2 <= ... <= an
atau a1 >= a2 >= ... >= an
. [1, 3, 3, 7, 9, 13, 13, 100]
adalah urutan monoton (tidak menurun), juga [9, 4, 4, 3, 0, -10, -12]
(yang ini tidak meningkat), tetapi [1, 3, 6, 9, 8]
tidak. Diberikan daftar bilangan bulat (dalam format apa pun yang masuk akal), mengeluarkan bilangan terkecil N
sedemikian rupa sehingga urutan bilangan bulat ini dapat dibagi menjadi N
urutan monoton.
Contohnya
[1, 3, 7, 5, 4, 2] -> [[1, 3, 7], [5, 4, 2]] -> 2
[1, 2, 3, 4, 5, 6] -> [1, 2, 3, 4, 5, 6] -> 1
[3, 1, 5, 5, 6] -> [[3, 1], [5, 5, 6]] -> 2
[4, 6, 8, 9, 1, 6] -> [[4, 6, 8, 9], [1, 6]] -> 2
[3, 3, 3, 3] -> [[3, 3, 3, 3]] -> 1
[7] -> [[7]] -> 1
[] -> [] -> anything (you don't actually have to handle an empty list case)
[1, 3, 2, -1, 6, 9, 10, 2, 1, -12] -> [[1, 3], [2, -1], [6, 9, 10], [2, 1, -12]] -> 4
[4,4,8,8,1,4,5] -> 2
0 / undefined
, sepertinya itu harus 0 atau representasi dariundefined
dalam bahasa kami, tetapi dari komentar Anda pada jawaban Jonathan Allan's Jelly, sepertinyaundefined
berartianything
... Yang mana itu ? Dalam kasus kedua, saya akan menyarankan menulisanything
bukanundefined
Jawaban:
Brachylog , 12 byte
Cobalah online!
Ini kembali
false.
untuk daftar kosong[]
.Penjelasan
Ini akan mengembalikan yang terkecil karena
~c
akan menghasilkan poin pilihan dari jumlah sublists terkecil ke yang terbesar.sumber
Z
karenaZ
nama variabel; jadi kami katakan "panggil program ini dengan Output sebagai variabel". Anda dapat mengubahZ
ke huruf besar lainnya ; itu hanya nama variabel. Alasan argumen ini ada adalah untuk memungkinkan kemungkinan sebenarnya mengatur output ke sesuatu, bukan variabel.4
dalam contoh itu , ia akan memberi tahu Anda apakah itu benar atau tidak )3
karena tidak akan menemukan daftar sublist di mana semua monoton dan panjang3
. Hanya perlu waktu lama karena akan mencoba semua daftar yang mungkin dari daftar, bahkan yang sebenarnya lebih dari 3 elemen karena panjangnya diperiksa setelah menemukan daftar. Untuk5
itu dikatakantrue
karena memang ada setidaknya satu daftar panjang5
dengan sublists monoton yang berfungsi. Jadi program ini mengembalikan panjang terkecil ketika output adalah variabel dan apakah ada daftar panjang itu yang berfungsi jika output adalah integer.Perl, 65 byte
62 byte kode + 3 byte untuk
-n
flag.monot_seq.pl:
Berikan input tanpa baris akhir final, dengan angka-angka dipisahkan oleh spasi:
-5 byte terima kasih kepada @Gabriel Benamy.
sumber
($&<=>$1)*($1<=>$2)||$1==$2
menjadi($&<=>$1)*($1<=>$2)>=0
Mathematica, 111 byte
Bernama fungsi
f
mengambil daftar nomor kosong (bilangan bulat atau bahkan real) Bekerja dari depan ke belakang, membuang elemen pertama berulang kali dan melacak berapa banyak selanjutnya yang dibutuhkan. Lebih banyak kata kerja:sumber
d=#2-#&@@#&;
juga, mendefinisikan salahf
ataug
sebagai operator unary±
mungkin akan menghemat beberapa byte.Jelly , 19 byte
TryItOnline! atau jalankan semua tes (daftar kosong menghasilkan
1
)Bagaimana?
(Saya tidak yakin bahwa ini adalah metode yang paling cocok untuk meminimalkan jumlah byte)
sumber
1
(yang menurut saya lebih masuk akal daripada0
).undefined
artinya - hasilnya tidak relevan.Perl,
98979679 byteInput disediakan sebagai daftar angka, dipisahkan oleh spasi, disediakan saat runtime, mis
(4 adalah output)
Dapat dibaca:
'Operator pesawat ruang angkasa'
<=>
mengembalikan -1 jika LHS <RHS, 0 jika LHS = RHS, dan +1 jika LHS> RHS. Ketika membandingkan tiga elemen berurutan$a,$b,$c
untuk menentukan apakah mereka monoton, itu hanya perlu untuk menentukan bahwa itu bukan kasus yang tepat satu dari$a<=>$b
,$b<=>$c
adalah 1 dan yang lainnya adalah -1 - yang hanya terjadi ketika produk mereka adalah -1. Jika salah satu$a==$b
atau$b==$c
, maka urutannya adalah monoton, dan produknya adalah 0. Jika$a < $b < $c
, maka keduanya menghasilkan -1, dan -1 * -1 = 1. Jika$a > $b > $c
, maka keduanya menghasilkan 1, dan 1 * 1 = 1. Dalam kedua kasus tersebut, urutannya monoton, dan kami ingin melanjutkan.Jika produk kurang dari 0, kami tahu bahwa urutannya tidak monoton, dan kami membuang nilai yang
$a,$b
kami pegang saat ini, dan menambah penghitung berikutnya. Kalau tidak, kami bergerak maju satu nomor.Tidak menghasilkan apa-apa jika input kosong, jika tidak mengembalikan jumlah terkecil dari monotonik berdekatan
sumber
1
danif
(atau mungkin Anda lakukan pada perl lama, tetapi pada yang baru tidak). Anda juga dapat (mungkin) menggantinyashift
denganpop
. Namun, ada beberapa kasus uji di mana kode Anda tidak berfungsi:6 3 6 3
(Anda mencetak 3 bukannya 2),4 3 2 1
(Anda mencetak 2 bukannya 1). Menggunakanpop
alih-alihshift
menyelesaikannya, tetapi membuat yang baru (1 2 3 4
mencetak 3 bukannya 1) ...C # 6,
297209 byteTidak digabungkan dengan penjelasan
sumber
JavaScript (ES6), 69 byte
Mengambil input sebagai beberapa parameter. Bekerja dengan secara rekursif membandingkan tiga elemen pertama untuk melihat apakah mereka monoton, jika demikian, menghilangkan elemen tengah karena tidak berguna, jika tidak, menghilangkan dua elemen pertama dan memulai urutan baru.
sumber
Clojure, 97 byte
reduce
melacak urutan saat ini dan menghitung berapa kali<=
dan>=
kondisi gagal. Terakhir1
mengambil elemen ke-2 dari hasilnya (menjadi penghitungi
).sumber