Jumlah terkecil dari urutan monotonik yang berdekatan

23

Deskripsi tantangan

Sebuah subsequence monoton adalah urutan angka [a1, a2, ..., an]sehingga

a1 <= a2 <= ... <= anatau 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 Nsedemikian rupa sehingga urutan bilangan bulat ini dapat dibagi menjadi Nurutan 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
shooqie
sumber
Untuk memperjelas, kalimat selanjutnya harus bersebelahan, bukan?
Zgarb
@ Zgarb Ya, benar.
shooqie
3
Saya akan merekomendasikan menambahkan test case di mana urutannya tidak selalu mengarah sebaliknya: [4,4,8,8,1,4,5] -> 2
Nathan Merrill
@NathanMerrill: Poin bagus, tambahkan satu.
shooqie
Ketika Anda menulis itu untuk string kosong, hasilnya adalah 0 / undefined, sepertinya itu harus 0 atau representasi dari undefineddalam bahasa kami, tetapi dari komentar Anda pada jawaban Jonathan Allan's Jelly, sepertinya undefinedberarti anything... Yang mana itu ? Dalam kasus kedua, saya akan menyarankan menulis anythingbukanundefined
Dada

Jawaban:

6

Brachylog , 12 byte

~c:{<=|>=}al

Cobalah online!

Ini kembali false.untuk daftar kosong [].

Penjelasan

(?)~c                 Take a list of sublists which when concatenated result in the Input
     :{<=|>=}a        Each sublist must be either increasing or decreasing
              l(.)    Output is the length of that list

Ini akan mengembalikan yang terkecil karena ~cakan menghasilkan poin pilihan dari jumlah sublists terkecil ke yang terbesar.

Fatalisasi
sumber
Apa argumen "Z" di tautan TIO? (Tampaknya menjadi bagian dari program seperti argumen baris perintah akan).
Jonathan Allan
@ JonathanAllan Argumen ini adalah output. Idealnya jika kita dapat menyesuaikan antarmuka TIO, akan ada Input dan Output dan tidak ada argumen. Argumennya adalah Zkarena Znama variabel; jadi kami katakan "panggil program ini dengan Output sebagai variabel". Anda dapat mengubah Zke huruf besar lainnya ; itu hanya nama variabel. Alasan argumen ini ada adalah untuk memungkinkan kemungkinan sebenarnya mengatur output ke sesuatu, bukan variabel.
Fatalkan
(Misalnya jika Anda mengatur Output ke 4dalam contoh itu , ia akan memberi tahu Anda apakah itu benar atau tidak )
Fatalkan
1
@JonathanAllan Setiap bahasa seperti Prolog seperti ini: predikat hanya dapat berhasil atau gagal dan tidak mengembalikan nilai apa pun. Jadi untuk mendapatkan output kita harus memiliki argumen variabel untuk predikat yang akan disatukan dengan hasilnya.
Fatalkan
1
@ Jonathanathan Allan Pada akhirnya akan gagal 3karena tidak akan menemukan daftar sublist di mana semua monoton dan panjang 3. 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. Untuk 5itu dikatakan truekarena memang ada setidaknya satu daftar panjang 5dengan 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.
Fatalkan
4

Perl, 65 byte

62 byte kode + 3 byte untuk -nflag.

monot_seq.pl:

#!perl -n
s/\S+ /($_<=>$&)*($&<=>$')-$g>=0?$g=1:$.++;$g--;$_=$&/ge,$_=$.

Berikan input tanpa baris akhir final, dengan angka-angka dipisahkan oleh spasi:

$ echo -n "1 3 2 -1 6 9 10 2 1 -12" | perl -M5.010 monot_seq.pl
4

-5 byte terima kasih kepada @Gabriel Benamy.

Dada
sumber
Simpan 5 byte dengan mengubahnya ($&<=>$1)*($1<=>$2)||$1==$2menjadi($&<=>$1)*($1<=>$2)>=0
Gabriel Benamy
@GabrielBenamy Memang, terima kasih.
Dada
2

Mathematica, 111 byte

d=#[[2]]-#[[1]]&;r=Rest;f@{n_}:=1;f@k__:=If[d@k==0,f@r@k,g[k Sign@d@k]];g@{n_}:=1;g@k__:=If[d@k>0,g@r@k,1+f@r@k]

Bernama fungsi fmengambil 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:

d = #[[2]] - #[[1]] &;         function: difference of the first two elements
r = Rest;                      function: a list with its first element dropped
f@{n_} := 1;                   f of a length-1 list equals 1
f@k__ := If[d@k == 0, f@r@k,   if the first two elements are equal, drop one
                                 element and call f again ...
            g[k Sign@d@k]];  ... otherwise call the helper function g on the
                                 list, multiplying by -1 if necessary to ensure
                                 that the list starts with an increase
g@{n_} := 1;                   g of a length-1 list equals 1
g@k__ := If[d@k > 0, g@r@k,    if the list starts with an increase, drop one
                                 element and call g again ...
            1 + f@r@k];        ... otherwise drop one element, call f on the
                                 resulting list, and add 1
Greg Martin
sumber
d=#2-#&@@#&;juga, mendefinisikan salah fatau gsebagai operator unary ±mungkin akan menghemat beberapa byte.
Martin Ender
2

Jelly , 19 byte

IṠḟ0E
ŒṖÇ€€0e$Ðḟḅ1Ṃ

TryItOnline! atau jalankan semua tes (daftar kosong menghasilkan1)

Bagaimana?

IṠḟ0E - Link 1, test for monotonicity: a sublist
I     - incremental differences
 Ṡ    - sign {fall:-1; same:0; rise:1}
  ḟ0  - filter out the zeros
    E - all equal?

ŒṖÇ€€0e$Ðḟḅ1Ṃ - Main link
ŒṖ            - all partitions of the input list
  Ç€€         - call last link (1) as a monad for €ach for €ach
        Ðḟ    - filter out results:
       $      -    last two links as a monad
     0e       -        contains zero?
          ḅ1  - convert from unary (vectorises)
            Ṃ - minimum

(Saya tidak yakin bahwa ini adalah metode yang paling cocok untuk meminimalkan jumlah byte)

Jonathan Allan
sumber
@shooqie - Bolehkah kami mengembalikan nilai apa pun untuk daftar kosong yang diberikan komentar "tidak ditentukan"? Ini kembali 1(yang menurut saya lebih masuk akal daripada 0).
Jonathan Allan
1
Maksud saya, itulah undefinedartinya - hasilnya tidak relevan.
shooqie
2

Perl, 98 97 96 79 byte

($a,$b)=($a<=>$b)*($b<=>$c)<0?($c,shift,$d++):($b,$c)while$c=shift;say$d+1 if$a

Input disediakan sebagai daftar angka, dipisahkan oleh spasi, disediakan saat runtime, mis

perl -M5.010 monotonic.pl 1 3 2 -1 6 9 10 2 1 -12
4

(4 adalah output)

Dapat dibaca:

($a,$b)=($a<=>$b)*($b<=>$c)<0
    ?($c,shift,$d++)
    :($b,$c)
  while$c=shift;
say$d+1
  if$a

'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,$cuntuk menentukan apakah mereka monoton, itu hanya perlu untuk menentukan bahwa itu bukan kasus yang tepat satu dari $a<=>$b, $b<=>$cadalah 1 dan yang lainnya adalah -1 - yang hanya terjadi ketika produk mereka adalah -1. Jika salah satu $a==$batau $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,$bkami 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

Gabriel Benamy
sumber
Anda tidak perlu ruang di antara 1dan if(atau mungkin Anda lakukan pada perl lama, tetapi pada yang baru tidak). Anda juga dapat (mungkin) menggantinya shiftdengan pop. 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). Menggunakan popalih-alih shiftmenyelesaikannya, tetapi membuat yang baru ( 1 2 3 4mencetak 3 bukannya 1) ...
Dada
1

C # 6, 297 209 byte

using System.Linq;int G(int[] a)=>a.Any()?a.SkipWhile((x,i)=>i<1||x>=a[i-1]).Count()<a.SkipWhile((x,i)=>i<1||x<=a[i-1]).Count()?G(a.Select(x=>-x).ToArray()):G(a.SkipWhile((x,i)=>i<1||x<=a[i-1]).ToArray())+1:0;

Tidak digabungkan dengan penjelasan

int G(int[] a)=>
    a.Any()
        ?a.SkipWhile((x,i)=>i<1||x>=a[i-1]).Count()<a.SkipWhile((x,i)=>i<1||x<=a[i-1]).Count()   // If a begins by decreasing (including whole a decreasing)...
            ?G(a.Select(x=>-x).ToArray())   // ... Then flip sign to make a begins by increasing
            :G(a.SkipWhile((x,i)=>i<1||x<=a[i-1]).ToArray())+1   // ... Else skip the increasing part, recursively find the remaining part number, then add 1
        :0;   // Return 0 if a is empty
Tautan Ng
sumber
1

JavaScript (ES6), 69 byte

f=(d,c,b,...a)=>1/b?(d>c)*(b>c)+(d<c)*(b<c)?1+f(b,...a):f(d,b,...a):1

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.

Neil
sumber
0

Clojure, 97 byte

#((reduce(fn[[C i]s](let[S(conj C s)](if(or(apply <= S)(apply >= S))[S i][[s](inc i)])))[[]1]%)1)

reducemelacak urutan saat ini dan menghitung berapa kali <=dan >=kondisi gagal. Terakhir 1mengambil elemen ke-2 dari hasilnya (menjadi penghitung i).

NikoNyrh
sumber