Kleinste Anzahl zusammenhängender monotoner Teilfolgen

23

Herausforderungsbeschreibung

Eine monotone Teilfolge ist eine Folge von Zahlen, [a1, a2, ..., an]so dass

a1 <= a2 <= ... <= anoder a1 >= a2 >= ... >= an. [1, 3, 3, 7, 9, 13, 13, 100]ist eine monotone (nicht abnehmende) Folge sowie [9, 4, 4, 3, 0, -10, -12](diese ist nicht ansteigend), ist es aber [1, 3, 6, 9, 8]nicht. Geben Sie bei einer Liste von Ganzzahlen (in jedem vernünftigen Format) die kleinste Zahl Nso aus, dass die Folge dieser Ganzzahlen in Nmonotone Folgen aufgeteilt werden kann.

Beispiele

[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
quelle
Zur Verdeutlichung müssen die Teilfolgen zusammenhängend sein, oder?
Zgarb
@ Zgarb Ja, das tun sie.
Shooqie
3
Ich würde empfehlen, einen Testfall hinzuzufügen, bei dem die Sequenzen nicht immer in umgekehrter Richtung [4,4,8,8,1,4,5] -> 2
Nathan Merrill,
@ NathanMerrill: Guter Punkt, fügte man hinzu.
Shooqie
Wenn Sie das für eine leere Zeichenkette schreiben, ist das Ergebnis 0 / undefined, es hört sich so an, als ob es entweder 0 oder die Darstellung undefinedin unserer Sprache sein sollte, aber aus Ihrem Kommentar zu Jonathan Allans Gelee-Antwort geht hervor, dass es undefinedbedeutet anything... Welches ist es? ? Im zweiten Fall würde ich vorschlagen, anythinganstelle vonundefined
Dada

Antworten:

6

Brachylog , 12 Bytes

~c:{<=|>=}al

Probieren Sie es online!

Dies wird false.für die leere Liste zurückgegeben [].

Erläuterung

(?)~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

Dies gibt die kleinste zurück, da ~cAuswahlpunkte von der kleinsten Anzahl von Unterlisten bis zur größten generiert werden.

Tödlich
quelle
Was ist das Argument "Z" im TIO-Link? (Es scheint Teil des Programms zu sein, wie es ein Befehlszeilenargument tun würde).
Jonathan Allan
@ JonathanAllan Dieses Argument ist die Ausgabe. Wenn wir die Schnittstelle von TIO anpassen könnten, gäbe es im Idealfall den Input und den Output und keine Argumente. Das Argument lautet, Zweil Zes sich um einen Variablennamen handelt. Wir sagen also "Rufe dieses Programm mit der Ausgabe als Variable auf". Sie können Zzu jedem anderen Großbuchstaben wechseln . Es ist nur ein Variablenname. Der Grund, warum dieses Argument existiert, ist die Möglichkeit, die Ausgabe tatsächlich auf etwas anstatt auf eine Variable zu setzen.
Fatalize
(Wenn Sie beispielsweise die Ausgabe 4in diesem Beispiel auf festlegen , werden Sie darüber
informiert,
1
@JonathanAllan Eine Prolog-ähnliche Sprache sieht folgendermaßen aus: Prädikate können nur erfolgreich sein oder scheitern und geben keinen Wert zurück. Um eine Ausgabe zu erhalten, muss man ein variables Argument für das Prädikat haben, das mit dem Ergebnis vereinheitlicht wird.
Fatalize
1
@ JonathanAllan Es wird irgendwann scheitern, 3weil es keine Liste von Unterlisten findet, in denen alle monoton und lang sind 3. Es dauert nur lange, da alle möglichen Listen von Unterlisten ausprobiert werden, auch diejenigen, die tatsächlich länger als 3 Elemente sind, da die Länge nach dem Auffinden der Liste überprüft wird. Denn 5es heißt, trueweil es in der Tat mindestens eine 5Längenliste mit monotonen Unterlisten gibt, die funktioniert. Dieses Programm gibt also die kleinste Länge zurück, wenn die Ausgabe eine Variable ist und ob es eine Liste dieser Länge gibt, die funktioniert, wenn die Ausgabe eine Ganzzahl ist.
Fatalize
4

Perl, 65 Bytes

62 Byte Code + 3 Byte für -nFlag.

monot_seq.pl:

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

Geben Sie die Eingabe ohne letzten Zeilenumbruch ein, wobei die Zahlen durch Leerzeichen getrennt sind:

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

-5 Bytes dank @Gabriel Benamy.

Dada
quelle
Speichern Sie 5 Bytes, indem Sie sich ($&<=>$1)*($1<=>$2)||$1==$2in($&<=>$1)*($1<=>$2)>=0
Gabriel Benamy 15.11.16
@ GabrielBenamy In der Tat, danke.
Dada
2

Mathematica, 111 Bytes

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]

Benannte Funktion, fdie eine nicht leere Liste von Zahlen (ganze Zahlen oder sogar reelle Zahlen) aufnimmt. Funktioniert von vorne nach hinten, wobei das erste Element wiederholt verworfen wird und nachverfolgt wird, wie viele Untersequenzen erforderlich sind. Ausführlicher:

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
quelle
d=#2-#&@@#&;Wenn Sie entweder foder gals unären Operator definieren, ±werden wahrscheinlich einige Bytes gespart.
Martin Ender
2

Jelly , 19 Bytes

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

TryItOnline! oder alle Tests ausführen (leere Liste ergibt1)

Wie?

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

(Ich bin jedoch nicht davon überzeugt, dass dies die am besten geeignete Methode ist, um die Anzahl der Bytes zu minimieren.)

Jonathan Allan
quelle
@shooqie - Dürfen wir angesichts des "undefinierten" Kommentars irgendeinen Wert für die leere Liste zurückgeben? Dies kehrt zurück 1(was meiner Meinung nach sinnvoller ist als 0).
Jonathan Allan
1
Ich meine, das undefinedheißt, das Ergebnis ist irrelevant.
Shooqie
2

Perl, 98 97 96 79 Bytes

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

Die Eingabe erfolgt als Liste von Zahlen, die zur Laufzeit durch Leerzeichen getrennt sind, z

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

(die 4 ist die Ausgabe)

Lesbar:

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

Der Raumschiff-Operator <=>gibt -1 zurück, wenn LHS <RHS, 0, wenn LHS = RHS und +1, wenn LHS> RHS. Wenn drei aufeinanderfolgende Elemente zu vergleichen , $a,$b,$cum zu bestimmen , ob sie sind monotone, dann ist es nur notwendig , um festzustellen , dass es nicht der Fall ist , dass genau eine $a<=>$b, $b<=>$c1 ist und das andere ist -1 - das geschieht nur , wenn ihr Produkt ist -1. Wenn entweder $a==$boder $b==$c, dann ist die Sequenz monoton und das Produkt ist 0. Wenn $a < $b < $c, dann ergeben beide -1 und -1 * -1 = 1. Wenn $a > $b > $c, dann ergeben beide 1 und 1 * 1 = 1. In beiden Fällen ist die Sequenz monoton und wir möchten fortfahren.

Wenn das Produkt kleiner als 0 ist, wissen wir, dass die Sequenz nicht monoton ist, und wir verwerfen die Werte, die $a,$bwir aktuell halten, und erhöhen unseren Teilsequenzzähler. Ansonsten rücken wir eine Nummer vor.

Gibt nichts zurück, wenn die Eingabe leer ist, andernfalls wird die kleinste Anzahl zusammenhängender monotoner Teilsequenzen zurückgegeben

Gabriel Benamy
quelle
Sie brauchen kein Leerzeichen zwischen 1und if(oder vielleicht auf alten Perls, aber auf neueren nicht). Sie können auch (wahrscheinlich) ersetzen shiftdurch pop. Es gibt jedoch einige Testfälle, bei denen Ihr Code nicht funktioniert: 6 3 6 3(Sie drucken 3 anstelle von 2), 4 3 2 1(Sie drucken 2 anstelle von 1). Verwenden, popanstatt diese zu shiftlösen, aber neue erstellen ( 1 2 3 4druckt 3 statt 1) ​​...
Dada
1

C # 6, 297 209 Bytes

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;

Ungolfed mit Erklärungen

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
Link Ng
quelle
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

Übernimmt die Eingabe als mehrere Parameter. Vergleicht rekursiv die ersten drei Elemente, um festzustellen, ob sie monoton sind. Wenn dies der Fall ist, wird das mittlere Element entfernt, da es unbrauchbar ist. Wenn dies nicht der Fall ist, werden die ersten beiden Elemente entfernt und eine neue Sequenz gestartet.

Neil
quelle
0

Clojure, 97 Bytes

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

reduceVerfolgt die aktuelle Folge und berechnet, wie oft <=und unter welchen >=Bedingungen ein Fehler auftritt. Last 1entnimmt dem Ergebnis das 2. Element (als Zähler i).

NikoNyrh
quelle