Herausforderungsbeschreibung
Eine monotone Teilfolge ist eine Folge von Zahlen, [a1, a2, ..., an]
so dass
a1 <= a2 <= ... <= an
oder 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 N
so aus, dass die Folge dieser Ganzzahlen in N
monotone 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
[4,4,8,8,1,4,5] -> 2
0 / undefined
, es hört sich so an, als ob es entweder 0 oder die Darstellungundefined
in unserer Sprache sein sollte, aber aus Ihrem Kommentar zu Jonathan Allans Gelee-Antwort geht hervor, dass esundefined
bedeutetanything
... Welches ist es? ? Im zweiten Fall würde ich vorschlagen,anything
anstelle vonundefined
Antworten:
Brachylog , 12 Bytes
Probieren Sie es online!
Dies wird
false.
für die leere Liste zurückgegeben[]
.Erläuterung
Dies gibt die kleinste zurück, da
~c
Auswahlpunkte von der kleinsten Anzahl von Unterlisten bis zur größten generiert werden.quelle
Z
weilZ
es sich um einen Variablennamen handelt. Wir sagen also "Rufe dieses Programm mit der Ausgabe als Variable auf". Sie könnenZ
zu 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.4
in diesem Beispiel auf festlegen , werden Sie darüber3
weil es keine Liste von Unterlisten findet, in denen alle monoton und lang sind3
. 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. Denn5
es heißt,true
weil es in der Tat mindestens eine5
Lä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.Perl, 65 Bytes
62 Byte Code + 3 Byte für
-n
Flag.monot_seq.pl:
Geben Sie die Eingabe ohne letzten Zeilenumbruch ein, wobei die Zahlen durch Leerzeichen getrennt sind:
-5 Bytes dank @Gabriel Benamy.
quelle
($&<=>$1)*($1<=>$2)||$1==$2
in($&<=>$1)*($1<=>$2)>=0
Mathematica, 111 Bytes
Benannte Funktion,
f
die 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:quelle
d=#2-#&@@#&;
Wenn Sie entwederf
oderg
als unären Operator definieren,±
werden wahrscheinlich einige Bytes gespart.Jelly , 19 Bytes
TryItOnline! oder alle Tests ausführen (leere Liste ergibt
1
)Wie?
(Ich bin jedoch nicht davon überzeugt, dass dies die am besten geeignete Methode ist, um die Anzahl der Bytes zu minimieren.)
quelle
1
(was meiner Meinung nach sinnvoller ist als0
).undefined
heißt, das Ergebnis ist irrelevant.Perl,
98979679 BytesDie Eingabe erfolgt als Liste von Zahlen, die zur Laufzeit durch Leerzeichen getrennt sind, z
(die 4 ist die Ausgabe)
Lesbar:
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,$c
um 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<=>$c
1 ist und das andere ist -1 - das geschieht nur , wenn ihr Produkt ist -1. Wenn entweder$a==$b
oder$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,$b
wir 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
quelle
1
undif
(oder vielleicht auf alten Perls, aber auf neueren nicht). Sie können auch (wahrscheinlich) ersetzenshift
durchpop
. 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,pop
anstatt diese zushift
lösen, aber neue erstellen (1 2 3 4
druckt 3 statt 1) ...C # 6,
297209 BytesUngolfed mit Erklärungen
quelle
JavaScript (ES6), 69 Byte
Ü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.
quelle
Clojure, 97 Bytes
reduce
Verfolgt die aktuelle Folge und berechnet, wie oft<=
und unter welchen>=
Bedingungen ein Fehler auftritt. Last1
entnimmt dem Ergebnis das 2. Element (als Zähleri
).quelle