Einführung
Angenommen, Sie haben ein Lineal mit Zahlen von 0 bis r-1 . Sie platzieren eine Ameise zwischen zwei der Zahlen und sie kriecht unregelmäßig auf dem Lineal. Das Lineal ist so schmal, dass die Ameise nicht von einer Position zur nächsten gehen kann, ohne auf allen dazwischen liegenden Zahlen zu laufen. Wenn die Ameise zum ersten Mal auf einer Zahl läuft, zeichnen Sie sie auf, und dies gibt Ihnen eine Permutation der r- Zahlen. Wir sagen, dass eine Permutation ärgerlich ist, wenn sie auf diese Weise von einer Ameise erzeugt werden kann. Alternativ ist eine Permutation p ärgerlich, wenn sich jeder Eintrag p [i] mit Ausnahme des ersten Eintrags innerhalb des Abstands 1 von einem vorhergehenden Eintrag befindet.
Beispiele
Die Länge-6-Permutation
4, 3, 5, 2, 1, 0
ist nervös, weil 3 in der Entfernung 1 von 4 liegt , 5 in der Entfernung 1 von 4 liegt , 2 in der Entfernung 1 von 3 liegt , 1 in der Entfernung 1 von 2 liegt und 0 in der Entfernung 1 von 1 liegt . Die Permutation
3, 2, 5, 4, 1, 0
ist nicht nervös, weil 5 nicht in der Entfernung 1 von 3 oder 2 liegt ; Die Ameise müsste 4 durchlaufen , um zu 5 zu gelangen .
Die Aufgabe
Geben Sie bei einer Permutation der Zahlen von 0 bis r-1 für 1 ≤ r ≤ 100 in einem beliebigen vernünftigen Format einen Wahrheitswert aus, wenn die Permutation ärgerlich ist, und einen falschen Wert, wenn nicht.
Testfälle
[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True
Tolle Tatsache: Für r ≥ 1 gibt es genau 2 r-1- Ameisenpermutationen der Länge r .
Antworten:
Pyth, 7 Bytes
Probieren Sie es online aus. (Aufgrund der exponentiellen Laufzeit sind nur kleine Testfälle enthalten.) Ausgänge 2 für Truthy, 0 für Falsey.
Mit anderen Worten,
Dabei wird
subseq
ausgegeben, ob die Elemente der ersten Liste in der Reihenfolge in der zweiten Liste erscheinen, nicht notwendigerweise nebeneinander. Dassubseq
wird in Pyth getan , indem alle Untergruppen der zweiten Liste nehmen, die die Reihenfolge der Elemente zu halten, und durch Zählen der Anzahl des Auftretens der ersten Liste. Dies nimmt exponentielle Zeit in Anspruch.Warum funktioniert das? Damit eine Permutation ärgerlich ist, muss das Springen von 0 zu n-1 darin bestehen, nur nach links und dann nur nach rechts zu gehen. Dies liegt daran, dass die Elemente, die größer als das erste Element sind, von links nach rechts zunehmen müssen, und diejenigen, die kleiner als das erste Element sind, von links nach rechts abnehmen müssen.
Wenn wir die Liste spiegeln, indem wir eine umgedrehte Kopie links davon platzieren, geht dieser Spaziergang nur noch nach rechts.
Umgekehrt entspricht jeder Rechtslauf dieser Spiegelliste einem Links-Rechts-Lauf der ursprünglichen Liste. Dies ist nach rechts eine sortierte Folge von 0 bis n-1. In einer Antsy-Liste ist diese sortierte Untersequenz bis auf eine willkürliche Auswahl zwischen den beiden benachbarten Kopien des ursprünglichen ersten Elements eindeutig.
quelle
Haskell, 46 Bytes
Prüft, ob die Vektordifferenz zwischen Laufmaxima und Laufminima [0,1,2,3 ...] beträgt.
Zgarb sparte 2 Bytes mit
(%)=scanl1
.quelle
(#)=scanl1
?JavaScript (ES6), 45
Ich dachte, es ist zu einfach, um es zu erklären, aber es gibt einen Trick, und für den Fall, hier ist meine erste Version, Pre-Golf
Hinweis: Im Golf
a
wird stattdessen der Code verwendetk
, da ich keinen Verweis auf das ursprüngliche Array innerhalb desevery
Aufrufs benötige . Ich vermeide es also, den globalen Namespace zu verschmutzen, indem ich den Parameter wieder verwendePrüfung
quelle
f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1)
Python 2, 49 Bytes
Überprüft, ob jedes Präfix der Liste alle Zahlen zwischen min und max enthält. Dabei wird geprüft, ob die Differenz zwischen max und min kleiner als die Länge ist.
54 Bytes:
Prüft, ob das letzte Element entweder kleiner als das Minimum der anderen Elemente oder größer als deren Maximum ist. Entfernt dann das letzte Element und rekursiert. Gibt in einer Einzelelementliste True aus.
Dies kann auch durch ein amüsantes, aber längeres Listenverständnis überprüft werden.
Ich würde gerne die Ungleichung verwenden
min(l)-2<l.pop()<max(l)+2
, aber daspop
muss zuerst geschehen. Die Verwendung eines Programms zur Ausgabe über einen Fehlercode wäre wahrscheinlich kürzer.quelle
Mathematica, 42 Bytes
Verwendet die Mustererkennung, um ein Präfix zu finden,
a
dessen maximale Differenz zum nächsten Elementb
größer ist als1
(und das Ergebnis von negiertMatchQ
).quelle
Perl,
393835 BytesBeinhaltet +1 für
-p
Gib die Reihenfolge auf STDIN an:
antsy.pl
:quelle
MATL , 11 Bytes
Probieren Sie es online! Oder überprüfen Sie alle Testfälle .
Erläuterung
Dies berechnet eine Matrix aller paarweisen absoluten Differenzen und behält den oberen dreieckigen Teil bei. Das Ergebnis ist wahr, wenn in allen Spalten außer der ersten mindestens ein 1-Wert vorhanden ist.
quelle
R,
726460 BytesEine Permutation ist genau dann ärgerlich, wenn alle ihre linken Subpermutationen fortlaufend sind (dh wenn sie sortiert sind, haben sie einen Unterschied von eins).
Wenn der Eingang garantiert Länge als ein mehr hat, dann können wir ersetzen1:sum(1|v)
mitseq(v)
, die vier Bytes speichert.Die
seq(v)
if-Bedingung verhält sich anders, wenn die Eingabe die Länge eins hat -1:v
stattdessen wird die Sequenz generiertseq_along(v)
. Glücklicherweise stellt sich jedoch heraus, dass die AusgabeTRUE
in diesem Fall das gewünschte Verhalten ist. Gleiches gilt auch für die Eingabe mit der Länge Null.In R
T
ist eine voreingestellte Variable gleichTRUE
(mit R können Sie sie jedoch neu definieren).TRUE
gilt auch als gleich1
.Vielen Dank an @Billywob für einige hilfreiche Verbesserungen an der ursprünglichen Lösung.
quelle
scan
würde Ihnen zwei Bytes sparen. In diesem Fall entspricht dies genau der Anzahl der Bytes desfor
Loop-Ansatzes: Diesv=scan();c=c();for(i in 1:sum(1|v))c=c(c,diff(sort(v[1:i])));all(c==1)
wären 2 Bytes weniger als bei Ihrem vektorisierten Ansatz.T
. Wird bearbeiten.05AB1E , 7 Bytes
Probieren Sie es online! oder als modifizierte Testsuite .
Erläuterung
Verwendet den von xnor in seiner brillanten Pyth-Antwort beschriebenen Prozess .
Gibt 2 für wahrheitsgemäße Instanzen und 0 für falsch zurück.
quelle
Perl, 63 Bytes
Beachten Sie, dass @ Gabriel Banamy eine kürzere Antwort (55 Byte) lieferte . Aber ich denke, diese Lösung ist immer noch interessant, also poste ich sie.
Die Byteanzahl umfasst 62 Bytes Code und
-n
Flag.Um es auszuführen:
Kurze Erklärungen : Konvertiert jede Zahl
k
in die unäre Darstellung vonk+1
(das+1
wird benötigt, damit die0
s nicht ignoriert werden). Dannk+1
prüfen1(1*)
wir für jede Zahl (ausgedrückt in unary als ), ob entwederk
($1
holdk
) oderk+2
(what is then11$1
) in der vorhergehenden Zeichenfolge (referenziert von$-backtick
) vorhanden sind. Wenn nein, setzen wir$.
auf Null. Am Ende des Druckvorgangs$.
wird gedruckt, was der Fall ist,1
wenn der Wert nie auf Null gesetzt wird, oder ansonsten auf Null.quelle
Brain-Flak
302 264256 BytesVielen Dank an Wheat Wizard für das Speichern von 46 Bytes
Die Spitze des Stapels wird eine 1 für wahr und eine 0 für falsch sein.
Wahrheit: Probieren Sie es online!
Falsy: Probieren Sie es online!
Die Idee ist, die minimale und maximale Anzahl, die die Ameise besucht hat, im Off-Stack zu halten. Vergleichen Sie dann jede Zahl mit beiden und aktualisieren Sie die entsprechende. Wenn die nächste Zahl nicht 1 kleiner als die min oder 1 größer als die max ist, brechen Sie die Schleife ab und geben Sie false zurück.
Kurze Erklärung:
quelle
([]){({}[()]<({}<>)<>>)}{}
durch ersetzen([]){{}({}<>)<>([])}{}
, um ein paar Bytes mehr zu sparenJelly ,
987 BytesProbieren Sie es online!
Eine Gelee-Übersetzung von xnors Antwort.
Alte Lösungen:
Probieren Sie es online!
Funktioniert sehr ähnlich wie meine Pyth-Antwort unten:
quelle
»\_«\⁼Ṣ
aber viel effizienterŒBŒPċṢ
und;\Ṣ€IỊȦ
sollte ein Byte in jedem Ansatz speichern.UŒBŒPċṢ
keine Bytes gespeichert werden. DasỊ
ist aber schön; Ich hatte dieses Atom falsch verstanden, um das logische NICHT dessen auszugeben, was es tatsächlich tat.U
(oder das@
Jetzt, wo ich darüber nachdenke). Wenn ein Array ärgerlich ist, ist es das umgekehrte Array, nein?[2, 1, 3, 0]
Ist nervös,[0, 3, 1, 2]
ist es aber nicht.CJam (
21 bis20 Bytes)Online-Testsuite
Präparation
Dies basiert auf der Beobachtung von xnor in seiner Haskell-Antwort, dass die Differenz zwischen dem Maximum und dem Minimum der ersten
n
Elemente sein sollten-1
.Alternativer Ansatz (auch 20 Bytes)
Online-Testsuite
Dadurch wird direkt überprüft, ob sich jedes Element nach dem ersten im Abstand 1 von einem vorherigen Element befindet. Da die Eingabe eine Permutation ist und daher keine Werte wiederholt, ist dies ein ausreichender Test. Vielen Dank an Martin für die 1-Byte-Speicherung.
Präparation
quelle
{_{a+_)f-:z1&,*}*^!}
Java,
100987975 BytesFrüher:
3 Bytes durch Ersetzen von
true
undfalse
durch1>0
und gespart0>1
.23 Bytes gespart dank exzellenter Vorschläge von Peter Taylor!
Ungolfed:
Verfolgen Sie die höchsten und niedrigsten Werte, die bis zu
m
und gesehen wurdenn
. nur einen neuen Wert annehmen , wenn esm + 1
odern - 1
den nächst höheren oder niedrigeren Wert , dh; Initialisieren Sie den hohen Wert,m
auf eins weniger als das erste Element, damit es beim ersten Mal in der Schleife "übereinstimmt". Hinweis: Dies ist ein linearer Online-Algorithmus. Im Gegensatz zu vielen anderen Lösungen werden für die aktuellen Werte, die höchsten bis jetzt und die niedrigsten bis jetzt, nur drei Speicherwörter benötigt.Wenn der nächste Wert sowohl das obere als auch das untere Ende des Bereichs verfehlt, wird der bisher niedrigste Wert auf gesetzt,
-1
und das untere Ende kann niemals fortfahren und Null erreichen. Wir erkennen dann eine Antsy-Sequenz, indem wir prüfen, ob der niedrige Wertn
Null erreicht hat.(Leider ist dies weniger effizient, da wir uns immer die gesamte Sequenz ansehen müssen, anstatt nach der ersten falschen Zahl auszusteigen. Es ist jedoch schwierig, mit einer Einsparung von 23 Byte (!) Zu argumentieren, wenn andere Lösungen O (n ^ 2) verwenden ) und exponentielle Zeitansätze.)
Verwendung:
Hinweis: Dies kann auch geschrieben werden, ohne Java 8-Lambdas zu nutzen:
Java 7, 89 Bytes
quelle
int m,n;m=n=a[0];--m;
könnte seinint n=a[0],m=n-1;
, und das teuerreturn
undelse
könnte reduziert werden miti==m+1?m++:n=(i==n-1)?i:-1;return n==0;
(oder so ähnlich - ich habe das nicht getestet).m++
oderm+=1
dort, so brauchen ich noch einif
und einelse
, und es verliert den Aspekt eines Kurzschlusses auf dem ersten schlechten Wert, aber das ist eine große Verbesserung. Danke!j
und ihr das Ergebnis zuweisen. Sie können jedoch davon ausgehen, dass dies besser möglich ist.g
, und ich konnte es nicht zum Laufen bringen. (Ich verwende Java 9-ea + 138, vielleicht ist es ein Unterschied zwischen Java 8 und Java 9?) Ich kann es morgen erneut versuchen.n-=i==m+1?m-m++:i==n-1?1:n+1;
Pyth ( Gabel ), 13 Bytes
Kein Try It Online-Link für diesen Pyth-Fork. Die Verzweigung enthält die Delta-Funktion
.+
, die nicht Teil der Standard-Pyth-Bibliothek ist.Erläuterung:
quelle
Perl,
6654 +1 = 55 Bytes+1 Byte für
-n
.Erläuterung:
Gibt 0 aus, wenn falsch, 1, wenn wahr.
-11 Bytes dank @Dada
quelle
perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.'
:-n
statt<>=~
dem Sie loswerden können/r
Modifikator. benutze\d+
und dann$&
statt(\d+)
und$1
.!@a
statt0>$#a
.$.&=
statt$.&&=
.push@a,$&
statt@a=(@a,$&)
Brainfuck, 60 Bytes
Die Permutation wird als Byte ohne Trennzeichen und ohne abschließende Newline angegeben. Da
\x00
in der Eingabe vorkommt, ist diese für Implementierungen mit ausgelegtEOF = -1
. Die Ausgabe ist\x00
für falsch und\x01
für wahr.Wenn eine Permutation von
\x01
bis zuchr(r)
zulässig ist, können wir alle Instanzen von,+
mit,
für eine Punktzahl von 57 durch eineEOF = 0
Implementierung ersetzen .Probieren Sie es online aus (57-Byte-Version): Die Eingabe kann als Permutation eines zusammenhängenden Bereichs von Bytes ohne angegeben
\x00
werden. Die Ausgabe erfolgt\x00
für false und das Minimum des Bereichs für true.Wir verfolgen die bisher gesehenen Min- und Max-Werte und prüfen für jedes Zeichen nach dem ersten, ob es sich um Min-1 oder Max-1 + 1 oder keines von beiden handelt. Bewegen Sie den Zeiger in keinem Fall außerhalb des normalen Arbeitsbereichs, sodass die lokalen Zellen zu Null werden.
Das Speicherlayout des normalen Arbeitsbereichs am Anfang der Hauptschleife ist
c a b 0 0
Wo
c
ist das aktuelle Zeichen,a
ist min undb
ist max. (Bei der 60-Byte-Version wird alles wegen mit einem Offset von 1 behandelt,+
.)quelle
Brachylog , 22 Bytes
Probieren Sie es online!
Erläuterung
Ich habe keine präzise Methode gefunden, um zu überprüfen, ob eine Liste aufeinanderfolgende ganze Zahlen enthält oder nicht. Der kürzeste, den ich gefunden habe, besteht darin, einen Bereich zwischen dem ersten und dem letzten Element dieser Liste zu generieren und zu überprüfen, ob dieser Bereich der ursprünglichen Liste entspricht.
quelle
1
. Ich weiß nicht, wie einfach das in Brachylog ist.Batch, 133 Bytes
Übernimmt Eingaben als Befehlszeilenargumente. Beendet mit der Fehlerstufe 0 für Erfolg, 1 für Misserfolg.
quelle
J, 14 Bytes
Dies basiert auf der Methode von @ xnor .
Erläuterung
quelle
Java, 170 Bytes
Das Array
x
hat Werte von 0 bis zur maximalen Anzahl (Python wäre hier viel besser ...). Die Schleife wird rückwärts ausgeführt und versucht, die niedrigste (x[b]
) oder die höchste (x[e]
) noch nicht angetroffene Zahl zu ermitteln. In diesem Fall könnte diese Nummer in diesem Schritt erreicht werden.Code hier testen .
quelle
Mathematica, 47 Bytes
Ein bisschen länger als Martin Enders Lösung (Überraschung Überraschung!). Aber es ist eine meiner unleserlicheren Bemühungen, also ist das gut: D
Erläuterung:
quelle
Java 7,
170169 BytesUngolfed & Testcode:
Probieren Sie es hier aus.
Ausgabe:
quelle