Antsy-Permutationen

37

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 .

Zgarb
quelle
7
Dies ist eine sehr interessante Herausforderung mit vielen verschiedenen Lösungen: Ich zähle mindestens 7 einzigartige Strategien, die bisher verwendet wurden.
ETHproductions
1
Die strukturierte Eingabeform von Permutationen trägt wesentlich zur Vielfalt der Ansätze bei. Die Bedingung für Ameisenheit kann auf verschiedene Arten ausgedrückt werden, die in allgemeinen Listen nicht gleichbedeutend sind.
XNOR
1
Ich bin enttäuscht, dass es noch keine ANTSI C-Lösung gibt.
NoSeatbelts

Antworten:

18

Pyth, 7 Bytes

/y+_QQS

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.

/          Count the number of occurences of
      S     the sorted input (implicit Q)
 y          in the order-preserved power set
  +_QQ       of the input prepended by its reverse

Mit anderen Worten,

lambda l: subseq(sorted(l), concat(reverse(l), l))

Dabei wird subseqausgegeben, ob die Elemente der ersten Liste in der Reihenfolge in der zweiten Liste erscheinen, nicht notwendigerweise nebeneinander. Das subseqwird 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.

[2, 3, 1, 4, 0]
             ^
       ^     0
 ^     1      
 2  ^        
    3     ^
          4

Wenn wir die Liste spiegeln, indem wir eine umgedrehte Kopie links davon platzieren, geht dieser Spaziergang nur noch nach rechts.

[0, 4, 1, 3, 2, 2, 3, 1, 4, 0]
 ^            |             
 0     ^      |             
       1      | ^           
              | 2  ^        
              |    3     ^  
              |          4                                  

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.

xnor
quelle
7
Sie können es auf 6 Bytes reduzieren, indem Sie ... nur Spaß machen.
JWG
2
Es ist etwas Abscheuliches, einen Exponential-Zeit-Ansatz für ein Problem mit einer offensichtlichen Linear-Zeit-Lösung zu verwenden, selbst wenn es gut abschneidet.
David Conrad
@jwg Ich würde es wirklich glauben. Wenn die Anzahl der Listen Argumente in umgekehrter Reihenfolge enthält, können Sie 6 Bytes erhalten, indem Sie implizit zwei Eingaben vornehmen.
XNOR
ayyyyy, wendet sich der Pyth-Seite zu: D
Maltysen
11

Haskell, 46 Bytes

(%)=scanl1
f l=zipWith(+)(min%l)[0..]==max%l

Prüft, ob die Vektordifferenz zwischen Laufmaxima und Laufminima [0,1,2,3 ...] beträgt.

l =             [2, 3, 1, 4, 0]

scanl1 max l =  [2, 3, 3, 4, 0]
scanl1 min l =  [2, 2, 1, 1, 0]  
difference =    [0, 1, 2, 3, 4]

Zgarb sparte 2 Bytes mit (%)=scanl1.

xnor
quelle
Das ist so schlau! +1
Gabriel Benamy
1
Könnten Sie durch die Definition einige Bytes einsparen (#)=scanl1?
Zgarb
1
@Zgarb Danke, ich habe vergessen, dass du das machen könntest.
XNOR
9

JavaScript (ES6), 45

a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

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

a => {
  k = []; // I'll put a 1 in this array at position of each value 
          // that I find scanning the input list
  return a.every((v,i) => { // execute for each element v at position i
    // the index i is needed to manage the first iteration
    // return 1/true if ok, 0/false if not valid
    // .every will stop and return false if any iteration return falsy
    k[v] = 1; // mark the current position
    if ( i == 0 )
    {  // the first element is always valid
       return true;
    }
    else
    {
       return k[v-1] == 1 // valid if near a lesser value
              || k[v+1] == 1; // or valid if near a greater value
    }
  })
}

Hinweis: Im Golf awird stattdessen der Code verwendet k, da ich keinen Verweis auf das ursprüngliche Array innerhalb des everyAufrufs benötige . Ich vermeide es also, den globalen Namespace zu verschmutzen, indem ich den Parameter wieder verwende

Prüfung

antsy=
a=>a.every((v,i)=>a[v]=!i|a[v-1]|a[v+1],a=[])

var OkAll=true
;`[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`
.split`\n`.forEach(row => {
  var rowElements = row.match(/\w+/g), 
      expected = rowElements.pop()=='True',
      input = rowElements.map(x => +x),
      result = antsy(input),
      ok = result == expected;
  OkAll = OkAll && ok;
  console.log(ok?'OK':'KO', input+' -> '+result)
})
console.log(OkAll ? 'All passed' : 'Failed')

edc65
quelle
Wirklich nett. Ich habe diesen Ansatz mit Rekursion versucht, aber ich kann ihn nicht unter 65 bringen:f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1)
ETHproductions 24.10.16
Wie funktioniert das? Verwenden Sie eine veränderbare Listenmagie?
Zgarb
@ Zgarb Erklärung hinzugefügt
edc65
6

Python 2, 49 Bytes

f=lambda l:l==[]or max(l)-min(l)<len(l)*f(l[:-1])

Ü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:

f=lambda l:1/len(l)or-~l.pop()in[min(l),max(l)+2]*f(l)

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.

lambda l:all(l.pop()in[min(l)-1,max(l)+1]for _ in l[1:])

Ich würde gerne die Ungleichung verwenden min(l)-2<l.pop()<max(l)+2, aber das popmuss zuerst geschehen. Die Verwendung eines Programms zur Ausgabe über einen Fehlercode wäre wahrscheinlich kürzer.

xnor
quelle
6

Mathematica, 42 Bytes

!MatchQ[#,{a__,b_,___}/;Min@Abs[{a}-b]>1]&

Verwendet die Mustererkennung, um ein Präfix zu finden, adessen maximale Differenz zum nächsten Element bgrößer ist als 1(und das Ergebnis von negiert MatchQ).

Martin Ender
quelle
6

Perl, 39 38 35 Bytes

Beinhaltet +1 für -p

Gib die Reihenfolge auf STDIN an:

antsy.pl <<< "2 1 3 0"

antsy.pl:

#!/usr/bin/perl -p
s%\d+%--$a[$&]x"@a"=~/1  /%eg;$_++
Tonne Hospel
quelle
2
Es fällt mir schwer, das zu verstehen ... Möchtest du es mir ein wenig erklären? danke :-) (nur die Hauptidee sollte reichen)
Dada
4

MATL , 11 Bytes

&-|R1=a4L)A

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.

&-     % All pairwise differences
|      % Absolute value
R      % Upper triangular part
1=     % Does each entry equal 1?
a      % Logical "or" along each column
4L)    % Remove first value
A      % Logical "and" of all results
Luis Mendo
quelle
4

R, 72 64 60 Bytes

v=scan();for(i in seq(v))T=c(T,diff(sort(v[1:i])));all(T==1)

Eine 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 ersetzen 1:sum(1|v)mit seq(v), die vier Bytes speichert.

Die seq(v)if-Bedingung verhält sich anders, wenn die Eingabe die Länge eins hat - 1:vstattdessen wird die Sequenz generiert seq_along(v). Glücklicherweise stellt sich jedoch heraus, dass die Ausgabe TRUEin diesem Fall das gewünschte Verhalten ist. Gleiches gilt auch für die Eingabe mit der Länge Null.

In R Tist eine voreingestellte Variable gleich TRUE(mit R können Sie sie jedoch neu definieren). TRUEgilt auch als gleich 1.

Vielen Dank an @Billywob für einige hilfreiche Verbesserungen an der ursprünglichen Lösung.

JDL
quelle
1
Das Lesen von Eingaben mit scanwürde Ihnen zwei Bytes sparen. In diesem Fall entspricht dies genau der Anzahl der Bytes des forLoop-Ansatzes: Dies v=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.
Billywob
Gute Idee, und ich kann es besser machen, wenn ich es missbrauche T. Wird bearbeiten.
JDL
3

05AB1E , 7 Bytes

Âìæ¹{¢O

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.

Âì        # prepend a reversed copy of input to input
  æ       # take powerset
   ¹{     # push a sorted copy of input
     ¢    # count occurances of sorted input in powerset
      O   # sum occurances (which for some reason is needed, feels like a bug)
Emigna
quelle
3

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 -nFlag.

s/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.

Um es auszuführen:

perl -nE 's/\d+/1x($&+1)/ge;/ 1(1*)\b(?{$.&=$`=~m%\b(11)?$1\b%})^/;say$.' <<< "3 2 5 4 1 0"

Kurze Erklärungen : Konvertiert jede Zahl kin die unäre Darstellung von k+1(das +1wird benötigt, damit die 0s nicht ignoriert werden). Dann k+1prüfen 1(1*)wir für jede Zahl (ausgedrückt in unary als ), ob entweder k( $1hold k) oder k+2(what is then 11$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, 1wenn der Wert nie auf Null gesetzt wird, oder ansonsten auf Null.

Dada
quelle
3

Brain-Flak 302 264 256 Bytes

Vielen 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:

([])                             # duplicate the bottom element by
{{}({}<>)<>([])}{}<>             # reversing everything onto the other stack 
(({}))([])                       # duplicating the top element
{{}({}<>)<>([])}{}<>             # and reversing everything back

(({}<>))<>                       # copy the top element to the other stack (push twice)
(()){{}                          # push a 1 so the loop starts, and repeat until the top
                                 # two elements are equal
(({})<                           # hold onto the top element to compare later
(({})<>[({})]<>(()))             # push a 0 if diff with the top of the other stack is +1
{{}({}<><{}>)(<>)}{}             # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)<>(<()>)}{}         # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>({}<<>                         # take the minimum off the other stack temporarily 
(({})<>[({})<>(())])             # push a 0 if diff with the top of the other stack is -1
{((<{}{}>))}{}                   # logical not (the previous line pushed a 1 as the second
                                 # element already)
{{}({}<><{}>)(<>)}{}             # replace the top of the other stack with this element if
                                 # the logical not gave us 1
<>>)<>                           # put the minimum on back on
>)                               # put the element you were comparing back on
[({})](<()>)){{}{}(<(())>)}{}    # push 1 or 0 for not equal to the element we held earlier
                                 # (push the second number back on)
}                                # repeat the loop if the top 2 weren't equal
([][()(())]){((<{}{}>))}{}       # logical not of the height of the stack
Riley
quelle
Ich würde nach Push-Pop-Reduzierungen suchen. Ich sehe bereits einige Stellen, an denen Sie diese Strategie anwenden können.
Wheat Wizard
@ WheatWizard Ich bin sicher, es gibt ein paar, ich hatte nur noch keine Zeit, um sie auszuarbeiten. Danke für die Erinnerung.
Riley
Ich bin froh, dass dir das zumindest Sinn macht. O_O
Gabriel Benamy
Sie können auch Instanzen von ([]){({}[()]<({}<>)<>>)}{}durch ersetzen ([]){{}({}<>)<>([])}{}, um ein paar Bytes mehr zu sparen
Weizen-Assistent
3

Jelly , 9 8 7 Bytes

;@UŒPċṢ

Probieren Sie es online!

Eine Gelee-Übersetzung von xnors Antwort.

Alte Lösungen:

;\Ṣ€IỊȦ
;\Ṣ€IE€P

Probieren Sie es online!

Funktioniert sehr ähnlich wie meine Pyth-Antwort unten:

;\          All prefixes (Accumulate (\) over concatenation (;))
  Ṣ€        (Ṣ)ort each (€) prefix
    I       (I)ncrements of each prefix (differences between consecutive elements).  Implicit vectorization.
     E€     Check if all elements are (E)qual (they will be iff the permutation is antsy,
               and all elements will be 1) for each (€) prefix
       P    Is this true for all prefixes?
     ỊȦ     For the other answer, are (Ȧ)ll elements 1 or less (Ị)?
Steven H.
quelle
Die Konvertierung von xnors anderer Methode in Jelly ist ebenfalls 7 Bytes, »\_«\⁼Ṣaber viel effizienter
Meilen
ŒBŒPċṢund ;\Ṣ€IỊȦsollte ein Byte in jedem Ansatz speichern.
Dennis
Leider funktioniert die erste nicht, da ich die umgekehrte Eingabe für das Bounce benötigen würde, so dass 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.
Steven H.
Ich bin nicht sicher, warum Sie das brauchen würden U(oder das @Jetzt, wo ich darüber nachdenke). Wenn ein Array ärgerlich ist, ist es das umgekehrte Array, nein?
Dennis
1
Nicht unbedingt: [2, 1, 3, 0]Ist nervös, [0, 3, 1, 2]ist es aber nicht.
Steven H.
3

CJam ( 21 bis 20 Bytes)

{:A,{_)A<$2*)@-#},!}

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 nElemente sein sollte n-1.

{         e# Define a block. Stack: array
  :A,     e#   Store the array in A and get its length
  {       e#   Filter (with implicit , so over the array [0 ... len-1])
    _)A<  e#     Get the first i+1 elements of A (so we iterate over prefixes)
    $2*)  e#     Extract the last element without leaving an empty array if the
          e#     prefix is of length 1 by first duplicating the contents of the
          e#     prefix and then popping the last element
    @-#   e#     Search the prefix for max(prefix)-i, which should be min(prefix)
          e#     giving index 0
  },      e#   So the filter finds values of i for which the prefix of length i+1
          e#   doesn't have max(prefix) - min(prefix) = i
  !       e#   Negate, giving truthy iff there was no i matching the filter
}

Alternativer Ansatz (auch 20 Bytes)

{_{a+_)f-:z1&,*}*^!}

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

{_{a+_)f-:z1&,*}*^!}

{         e# Declare a block. Stack: array
  _       e#   Work with a copy of the array
  {       e#   Fold...
    a+    e#     Add to the accumulator.
    _)f-  e#     Dup, pop last, map subtraction to get distance of this element from
          e#     each of the previous ones
    :z1&, e#     Check whether the absolute values include 1
    *     e#     If not, replace the accumulator with an empty array
  }*
  ^!      e#   Test whether the accumulator is equal to the original array
          e#   Note that this can't just be = because if the array is of length 1
          e#   the accumulator will be 0 rather than [0]
}
Peter Taylor
quelle
Ich denke das spart einen? {_{a+_)f-:z1&,*}*^!}
Martin Ender
@ MartinEnder, sehr schön. Seltsamerweise haben Sie das gepostet, als ich einen völlig anderen Ansatz mit der gleichen Byteanzahl gepostet habe.
Peter Taylor
3

Java, 100 98 79 75 Bytes

a->{int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}

Früher:

a->{int m,n;m=n=a[0];--m;for(int i:a)if(i==m+1)m=i;else if(i==n-1)n=i;else return 0>1;return 1>0;}

3 Bytes durch Ersetzen von trueund falsedurch 1>0und gespart 0>1.

23 Bytes gespart dank exzellenter Vorschläge von Peter Taylor!

Ungolfed:

a -> {
    int n = a[0], m = n - 1;
    for (int i : a)
        n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
    return n == 0;
}

Verfolgen Sie die höchsten und niedrigsten Werte, die bis zu mund gesehen wurden n. nur einen neuen Wert annehmen , wenn es m + 1oder n - 1den nächst höheren oder niedrigeren Wert , dh; Initialisieren Sie den hohen Wert, mauf 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, -1und das untere Ende kann niemals fortfahren und Null erreichen. Wir erkennen dann eine Antsy-Sequenz, indem wir prüfen, ob der niedrige Wert nNull 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:

import java.util.function.Predicate;

public class Antsy {
    public static void main(String[] args) {
        int[] values = { 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 };
        System.out.println(test(values,
            a -> {
                int n = a[0], m = n - 1;
                for (int i : a)
                    n -= i == m + 1? m - m++ : i == n - 1? 1 : n + 1;
                return n == 0;
            }
        ));
    }

    public static boolean test(int[] values, Predicate<int[]> pred) {
        return pred.test(values);
    }
}

Hinweis: Dies kann auch geschrieben werden, ohne Java 8-Lambdas zu nutzen:

Java 7, 89 Bytes

boolean c(int[]a){int n=a[0],m=n-1;for(int i:a)n-=i==m+1?m-m++:i==n-1?1:n+1;return n==0;}
David Conrad
quelle
Gute Behandlung des Sonderfalls. int m,n;m=n=a[0];--m;könnte sein int n=a[0],m=n-1;, und das teuer returnund elsekönnte reduziert werden mit i==m+1?m++:n=(i==n-1)?i:-1;return n==0;(oder so ähnlich - ich habe das nicht getestet).
Peter Taylor
@PeterTaylor Fantastisch! Leider Java wird alle Nebenwirkungen nicht zulassen , wie m++oder m+=1dort, so brauchen ich noch ein ifund ein else, und es verliert den Aspekt eines Kurzschlusses auf dem ersten schlechten Wert, aber das ist eine große Verbesserung. Danke!
David Conrad
Es wird Nebenwirkungen in einem komplexen Ausdruck ermöglichen. Was es vielleicht nicht mag, ist die Verwendung eines allgemeinen Ausdrucks als Anweisung. Im schlimmsten Fall müssen Sie eine Dummy-Variable erstellen jund ihr das Ergebnis zuweisen. Sie können jedoch davon ausgehen, dass dies besser möglich ist.
Peter Taylor
@PeterTaylor Nun, ich habe ein paar Variationen probiert, einschließlich der Zuweisung zu einer Dummy-Variablen 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.
David Conrad
Ich habs. n-=i==m+1?m-m++:i==n-1?1:n+1;
Peter Taylor
2

Pyth ( Gabel ), 13 Bytes

!sstMM.+MSM._

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:

           ._  For each of the prefixes:
         SM    Sort it
      .+M      Get deltas (differences between consecutive elements), which for antsy
                 permutations would all be 1s
   tMM         Decrement each of the elements (all 0s for antsy permutations)
 ss            Sum all the results from the above together, 0 for antsy and >0 for non-antsy
!              Logical negation.
Steven H.
quelle
3
Wenn ich das sehe, überzeuge ich mich, das mit Pyth zu verschmelzen.
Isaacg
2

Perl, 66 54 +1 = 55 Bytes

+1 Byte für -n.

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.

Erläuterung:

s/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.
#input is automatically read into $_.
#regex automatically is performed on $_.
s/   /                                       /eg;
    #Substitution regex.
    #/g means to keep searching after the first match
    #/e evaluates the replacement as code instead of regex.
  \d+  #Match of at least 1 digit.  Match automatically gets stored in $&
      $.&=  #$. is initially 1.  This basically says $. = $. & (code)
           !@a  #Since @a is uninitialized, this returns !0, or 1
                #We don't want to check anything for the first match
              || #logical or
                1~~
                   #~~ is the smartmatch operator.  When RHS is scalar and LHS is array reference,
                   #it returns 1 iff RHS is equal to at least one value in de-referenced LHS.
                   [map{abs$_-$&}@a];
                       #Return an array reference to the array calculated by |$_ - $&|
                       #where $_ iterates over @a.  Remember $& is the stored digit capture.
                                     push@a,$& #pushes $& at the end of @a.
                                                 say$. #output the result

Gibt 0 aus, wenn falsch, 1, wenn wahr.

-11 Bytes dank @Dada

Gabriel Benamy
quelle
1
Das ist wirklich nett. Sie können es , Golf zu 55 Byte nach unten aber: perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.': -nstatt <>=~dem Sie loswerden können /rModifikator. benutze \d+und dann $&statt (\d+)und $1. !@astatt 0>$#a. $.&=statt $.&&=. push@a,$&statt@a=(@a,$&)
Dada
Aus irgendeinem Grund teilt mir mein System mit, dass die neue Datei 55 Byte lang ist, was offensichtlich falsch ist, da sie nur 54 Zeichen enthält.
Gabriel Benamy
Hmm das ist komisch. (Und ich habe keine Ahnung, woher das kommt). Aber ich bin mir ziemlich sicher, dass es nur 54 sind (das PPCG-Design-Skript sagt mir 54, und meine bytecount-App sagt mir auch 54).
Dada
2
Ist es möglich, dass die Byteanzahl aufgrund einer unnötigen Zeilenumbrüche am Ende der Datei abgelaufen ist?
Trichoplax
2

Brainfuck, 60 Bytes

,+[>+>+<<-]
,+
[
  [>->->+<<<-]
  >-
  [
    +>+
    [
      <<<
    ]
  ]
  >[>]
  <[<+<+>>-]
  <<<,+
]
>.

Die Permutation wird als Byte ohne Trennzeichen und ohne abschließende Newline angegeben. Da \x00in der Eingabe vorkommt, ist diese für Implementierungen mit ausgelegt EOF = -1. Die Ausgabe ist \x00für falsch und \x01für wahr.

Wenn eine Permutation von \x01bis zu chr(r)zulässig ist, können wir alle Instanzen von ,+mit ,für eine Punktzahl von 57 durch eine EOF = 0Implementierung ersetzen .

Probieren Sie es online aus (57-Byte-Version): Die Eingabe kann als Permutation eines zusammenhängenden Bereichs von Bytes ohne angegeben \x00werden. Die Ausgabe erfolgt \x00fü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 cist das aktuelle Zeichen, aist min und bist max. (Bei der 60-Byte-Version wird alles wegen mit einem Offset von 1 behandelt ,+.)

Mitch Schwartz
quelle
1

Brachylog , 22 Bytes

:@[fb:{oLtT,Lh:T:efL}a

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.

:@[fb                       Take all but the first prefixes of the Input
     :{             }a      This predicate is true for all those prefixes
       oLtT,                Sort the prefix, call it L, its last element is T
            Lh:T            The list [First element of L, T]
                :efL        Find all integers between the First element of L and T. It must
                              result in L
Tödlich
quelle
Der Bereich vom ersten bis zum letzten ist ein Ansatz, der mir in CJam eingefallen war. Das andere waren sortenreine, paarweise Unterschiede. Überprüfen Sie, ob sie alle sind 1. Ich weiß nicht, wie einfach das in Brachylog ist.
Peter Taylor
@PeterTaylor Es gibt leider (vorerst) keine Möglichkeit, aufeinanderfolgende Paare zu generieren (oder paarweise Differenzen direkt zu berechnen).
Fatalize
1

Batch, 133 Bytes

@set/au=%1,l=%1-1,a=0
@for %%n in (%*)do @call:l %%n
@exit/b%a%
:l
@if %1==%u% (set/au+=1)else if %1==%l% (set/al-=1)else set a=1

Übernimmt Eingaben als Befehlszeilenargumente. Beendet mit der Fehlerstufe 0 für Erfolg, 1 für Misserfolg.

Neil
quelle
1

J, 14 Bytes

/:~-:>./\-<./\

Dies basiert auf der Methode von @ xnor .

Erläuterung

/:~-:>./\-<./\  Input: array P
        \       For each prefix of P
     >./          Reduce using the maximum
          <./\  Get the minimum of each prefix of p
         -      Subtract between each
   -:           Test if it matches
/:~               P sorted
Meilen
quelle
1

Java, 170 Bytes

boolean f(int[]a){int l=a.length,i=0,b=0,e=l-1;int[]x=new int[l];for(;i<l;i++)x[i]=i;for(i--;i>0;i--)if(a[i]==x[b])b++;else if(a[i]==x[e])e--;else return 0>1;return 1>0;}

Das Array xhat 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 .

AlexRacer
quelle
0

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

#=={}||{Max@#,Min@#}~MemberQ~Last@#&&#0@Most@#&

Erläuterung:

#=={}                         empty lists are antsy (function halts with True)
 ||                            or
{Max@#,Min@#}~MemberQ~Last@#  lists where the last number is largest or smallest
                              are possibly antsy (else function halts with False)
 &&                            and
#0@Most@#&                    recursively call this function after dropping the
                              last element of the list
Greg Martin
quelle
0

Java 7, 170 169 Bytes

import java.util.*;Object c(int[]a){List l=new ArrayList();l.add(a[0]);for(int i:a){if(l.indexOf(i)<0&l.indexOf(i-1)<0&l.indexOf(i+1)<0)return 0>1;l.add(i);}return 1>0;}

Ungolfed & Testcode:

Probieren Sie es hier aus.

import java.util.*;
class M{
  static Object c(int[] a){
    List l = new ArrayList();
    l.add(a[0]);
    for(int i : a){
      if(l.indexOf(i) < 0 & l.indexOf(i-1) < 0 & l.indexOf(i+1) < 0){
        return 0>1; //false
      }
      l.add(i);
    }
    return 1>0; //true
  }

  public static void main(String[] a){
    System.out.println(c(new int[]{ 0 }));
    System.out.println(c(new int[]{ 0, 1 }));
    System.out.println(c(new int[]{ 1, 0 }));
    System.out.println(c(new int[]{ 0, 1, 2 }));
    System.out.println(c(new int[]{ 0, 2, 1 }));
    System.out.println(c(new int[]{ 2, 1, 3, 0 }));
    System.out.println(c(new int[]{ 3, 1, 0, 2 }));
    System.out.println(c(new int[]{ 1, 2, 0, 3 }));
    System.out.println(c(new int[]{ 2, 3, 1, 4, 0 }));
    System.out.println(c(new int[]{ 0, 5, 1, 3, 2, 4 }));
    System.out.println(c(new int[]{ 6, 5, 4, 7, 3, 8, 9, 2, 1, 0 }));
    System.out.println(c(new int[]{ 4, 3, 5, 6, 7, 2, 9, 1, 0, 8 }));
    System.out.println(c(new int[]{ 5, 2, 7, 9, 6, 8, 0, 4, 1, 3 }));
    System.out.println(c(new int[]{ 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 }));
    System.out.println(c(new int[]{ 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 }));
    System.out.println(c(new int[]{ 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 }));
  }
}

Ausgabe:

true
true
true
true
false
true
false
true
true
false
true
false
false
false
false
true
Kevin Cruijssen
quelle