Permutations Antsy

37

introduction

Supposons que vous ayez une règle avec des nombres de 0 à r-1 . Vous placez une fourmi entre deux des nombres et elle commence à ramper de manière erratique sur la règle. La règle est si étroite que la fourmi ne peut pas marcher d'une position à une autre sans marcher sur tous les chiffres entre les deux. Lorsque la fourmi découvre un numéro pour la première fois, vous l’enregistrez, ce qui vous donne une permutation des nombres r . Nous disons qu'une permutation est angoissante si elle peut être générée de cette manière par une fourmi. Alternativement, une permutation p est antsy si chaque entrée p [i] sauf la première est à une distance de 1 d'une entrée précédente.

Exemples

La permutation de longueur 6

4, 3, 5, 2, 1, 0

est antsé, parce que 3 est dans la distance 1 de 4 , 5 est dans la distance 1 de 4 , 2 est dans la distance 1 de 3 , 1 est dans la distance 1 de 2 , et 0 est dans la distance 1 de 1 . La permutation

3, 2, 5, 4, 1, 0

n'est pas nerveux, car 5 n'est pas à la distance 1 de 3 ou 2 ; la fourmi devrait passer par 4 pour arriver à 5 .

La tâche

Étant donné une permutation des nombres de 0 à r-1 pour quelque 1 ≤ r ≤ 100 dans un format raisonnable, donne une valeur de vérité si la permutation est antsy, et une valeur de fausseté sinon.

Cas de test

[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

Anecdote: pour r ≥ 1 , il existe exactement 2 r-1 permutations antsy de longueur r .

Zgarb
la source
7
C'est un défi très intéressant avec de nombreuses solutions différentes: je compte au moins 7 stratégies uniques utilisées jusqu'à présent.
ETHproductions
1
La forme structurée des permutations en entrée contribue beaucoup à la variété des approches. La condition pour être énervé peut être exprimée de différentes manières qui sont inégales sur les listes générales.
xnor
1
Je suis déçu qu'il n'y ait pas encore de solution ANTSI C.
NoSeatbelts

Réponses:

18

Pyth, 7 octets

/y+_QQS

Essayez-le en ligne. (Seuls les petits cas de test sont inclus en raison du temps d'exécution exponentiel.) Sorties 2 pour Truthy, 0 pour 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

En d'autres termes,

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

subseqsorties indique si les éléments de la première liste apparaissent dans l’ordre dans la deuxième liste, pas nécessairement adjacents. Le subseqest fait en Pyth en prenant tous les sous-ensembles de la deuxième liste, qui gardent l'ordre des éléments, et en comptant le nombre d'occurrences de la première liste. Cela prend du temps exponentiel.

Pourquoi ça marche? Pour qu'une permutation soit angoissante, passer de 0 à n-1 doit consister à aller uniquement à gauche, puis à droite. En effet, les éléments supérieurs au premier élément doivent augmenter de gauche à droite et ceux inférieurs à celui-ci doivent diminuer de gauche à droite.

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

Si nous reflétons la liste en plaçant une copie inversée à sa gauche, cette marche ne va plus que vers la droite.

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

Inversement, toute droite de cette liste miroir correspond à une marche gauche puis droite de la liste d'origine. Ce vers la droite est juste une sous-séquence triée de 0 à n-1. Dans une liste antsy, cette sous-séquence triée est unique, à l'exception d'un choix arbitraire entre les deux copies adjacentes du premier élément d'origine.

Xnor
la source
7
Vous pouvez le réduire à 6 octets en utilisant ... je plaisante.
Jwg
2
Il est horrible d'utiliser une approche à temps exponentiel pour résoudre un problème avec une solution temps linéaire évident, même si le problème est résolu.
David Conrad
@ jwg j'y crois, en fait. Si le nombre de listes a pris des arguments dans l'ordre inverse, vous pouvez obtenir 6 octets en prenant implicitement deux entrées.
xnor
ayyyyy, se tournant du côté pyth: D
Maltysen
11

Haskell, 46 octets

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

Vérifie si la différence vectorielle des maxima et des minima est de [0,1,2,3 ...].

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 a sauvegardé 2 octets avec (%)=scanl1.

Xnor
la source
C'est tellement intelligent! +1
Gabriel Benamy
1
Pourriez-vous économiser des octets en définissant (#)=scanl1?
Zgarb
1
@ Zgarb Merci, j'ai oublié que vous pouviez le faire.
xnor
9

JavaScript (ES6), 45

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

Je pensais que c'était trop simple pour avoir besoin d'explication, mais il y a une astuce, et juste au cas où, voici ma première 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
    }
  })
}

Remarque: le code golfé aest utilisé à la place de k, car je n'ai pas besoin de faire référence au tableau d'origine dans l' everyappel. J'évite donc de polluer l'espace de noms global en réutilisant le paramètre

Tester

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
la source
Vraiment sympa. J'ai essayé cette approche avec la récursivité, mais je ne peux pas l'obtenir en dessous de 65:f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1)
ETHproductions
Comment cela marche-t-il? Utilisez-vous une magie de liste modifiable?
Zgarb
Explication de @Zgarb ajoutée
edc65
6

Python 2, 49 octets

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

Vérifie si chaque préfixe de la liste contient tous les nombres compris entre min et max inclus. Pour ce faire, vérifiez si la différence entre max et min est inférieure à sa longueur.


54 octets:

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

Vérifie si le dernier élément est inférieur de un au minimum des autres éléments ou d'un de plus à leur maximum. Ensuite, supprime le dernier élément et revient. Sur une liste à un seul élément, renvoie True.

Cela peut également être vérifié via une liste amusante mais plus longue.

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

J'aimerais utiliser l'inégalité min(l)-2<l.pop()<max(l)+2, mais les popbesoins doivent être d'abord. L'utilisation d'un programme pour générer un code d'erreur serait probablement plus courte.

Xnor
la source
6

Mathematica, 42 octets

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

Utilise la correspondance de modèle pour essayer de trouver un préfixe adont la différence maximale par rapport à l'élément suivant best supérieure à 1(et inversant le résultat de MatchQ).

Martin Ender
la source
6

Perl, 39 38 35 octets

Comprend +1 pour -p

Donner séquence sur STDIN:

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

antsy.pl:

#!/usr/bin/perl -p
s%\d+%--$a[$&]x"@a"=~/1  /%eg;$_++
Ton Hospel
la source
2
J'ai du mal à comprendre celui-ci ... Voulez-vous expliquer un peu? merci :-) (juste l'idée principale devrait suffire)
Dada
4

MATL , 11 octets

&-|R1=a4L)A

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

Ceci calcule une matrice de toutes les différences absolues par paires et conserve la partie triangulaire supérieure. Le résultat est true dans la mesure où il existe au moins une valeur 1 dans toutes les colonnes, sauf la première.

&-     % 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
la source
4

R, 72 64 60 octets

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

Une permutation est angoissée si et seulement si toutes ses sous-permutations de gauche sont continues (c'est-à-dire qu'elles ont une différence lorsqu'elles sont triées).

S'il est garanti que l'entrée a plus d'une longueur, nous pouvons remplacer 1:sum(1|v)par seq(v), ce qui économise quatre octets.

La seq(v)condition dans le si se comporte différemment lorsque l'entrée est de longueur un - elle génère la séquence à la 1:vplace de seq_along(v). Cependant, heureusement, la sortie s'avère être TRUEdans ce cas, ce qui est le comportement souhaité. Il en va de même pour les entrées de longueur nulle.

Dans R, Tune variable prédéfinie est égale à TRUE(mais R vous permet de la redéfinir). TRUEest également réputé être égal à 1.

Merci à @Billywob pour certaines améliorations utiles apportées à la solution d'origine.

JDL
la source
1
Lire une entrée en utilisant vous scanpermettrait d’économiser deux octets. Dans ce cas, il s'agit exactement du même nombre d'octets que l' forapproche en boucle: v=scan();c=c();for(i in 1:sum(1|v))c=c(c,diff(sort(v[1:i])));all(c==1)ce qui serait 2 octets plus court que votre approche vectorisée.
Billywob
Belle idée, et je peux aller mieux je pense en abusant T. Va éditer.
JDL
3

05AB1E , 7 octets

Âìæ¹{¢O

Essayez-le en ligne! ou en tant que suite de tests modifiée .

Explication

Utilise le processus décrit par xnor dans sa brillante réponse Pyth .
Renvoie 2 pour les instances de vérité et 0 pour la fausseté.

Âì        # 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
la source
3

Perl, 63 octets

Notez que @Gabriel Banamy a fourni une réponse plus courte (55 octets) . Mais je pense que cette solution est toujours intéressante, alors je la poste.

Le nombre d'octets comprend 62 octets de code et d' -nindicateur.

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

Pour l'exécuter:

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

Brèves explications : convertit chaque nombre ken représentation unaire de k+1( +1nécessaire pour 0ne pas les ignorer). Ensuite, pour chaque numéro k+1(exprimé en unary as 1(1*)), nous regardons si k( $1hold k) ou k+2(qui est alors 11$1) sont présents dans la chaîne précédente (référencée par $-backtick). Si non, alors nous mettons $.à zéro. À la fin, nous imprimons $.ce qui sera 1si nous ne le fixons jamais à zéro, ou zéro sinon.

Dada
la source
3

Brain-Flak 302 264 256 octets

Merci à Wheat Wizard pour la sauvegarde de 46 octets

([]){{}({}<>)<>([])}{}<>(({}))([]){{}({}<>)<>([])}{}<>(({}<>))<>(()){{}(({})<(({})<>[({})]<>(())){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>({}<<>(({})<>[({})<>(())]){((<{}{}>))}{}{{}({}<><{}>)(<>)}{}<>>)<>>[({})](<()>)){{}{}(<(())>)}{}}([][()(())]){((<{}{}>))}{}

Le sommet de la pile sera 1 pour la vérité et 0 pour la fausseté.

Truthy: Essayez-le en ligne!
Falsy: essayez-le en ligne!

L'idée est de contenir les nombres minimum et maximum que la fourmi a visités dans la pile. Ensuite, comparez chaque nombre aux deux et mettez à jour le nombre approprié. Si le nombre suivant n'est pas inférieur au minimum ou inférieur de 1 au maximum, sortez de la boucle et renvoyez false.


Brève explication:

([])                             # 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
la source
Je vérifierais les réductions push-pop. Je vois déjà quelques endroits où vous pourriez utiliser cette stratégie.
Wheat Wizard
@ WheatWizard Je suis sûr qu'il y en a quelques-uns, je n'ai pas encore eu le temps de les résoudre. Merci pour le rappel.
Riley
Je suis content que cela ait au moins un sens pour vous. O_O
Gabriel Benamy
Vous pouvez également remplacer des instances de ([]){({}[()]<({}<>)<>>)}{}avec ([]){{}({}<>)<>([])}{}pour enregistrer quelques octets supplémentaires
Wheat Wizard
3

Gelée , 9 8 7 octets

;@UŒPċṢ

Essayez-le en ligne!

Une traduction en gelée de la réponse de xnor.

Anciennes solutions:

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

Essayez-le en ligne!

Fonctionne de manière très similaire à ma réponse Pyth ci-dessous:

;\          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.
la source
La conversion de l’autre méthode de xnor en Jelly est également de 7 octets »\_«\⁼Ṣmais est beaucoup plus efficace
miles
ŒBŒPċṢet ;\Ṣ€IỊȦdevrait économiser un octet dans chaque approche.
Dennis
Malheureusement, le premier ne fonctionne pas, car j’aurais besoin que l’entrée inversée soit renvoyée, comme UŒBŒPċṢce qui ne sauvegarde aucun octet. Le est bien, cependant; J'avais mal interprété cet atome pour sortir le NON logique de ce qu'il a réellement fait.
Steven H.
Je ne suis pas sûr de savoir pourquoi vous auriez besoin du U(ou du @maintenant que j'y pense). Si un tableau est perturbé, le tableau inversé l'est aussi.
Dennis
1
Pas nécessairement: [2, 1, 3, 0]est antsy mais [0, 3, 1, 2]n'est pas.
Steven H.
3

CJam ( 21 à 20 octets)

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

Suite de tests en ligne

Dissection

Ceci utilise l'observation de xnor dans sa réponse de Haskell selon laquelle la différence entre le maximum et le minimum des premiers néléments devrait être 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
}

Approche alternative (également 20 octets)

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

Suite de tests en ligne

Ceci vérifie directement que chaque élément après le premier est à la distance 1 d'un élément précédent. Comme l'entrée est une permutation et ne répète donc pas les valeurs, il s'agit d'un test suffisant. Merci à Martin pour une économie de 1 octet.

Dissection

{_{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
la source
Je pense que cela en sauve un? {_{a+_)f-:z1&,*}*^!}
Martin Ender
@MartinEnder, très sympa. Curieusement, vous avez écrit cela, tout comme je publiais une approche complètement différente avec le même nombre d'octets.
Peter Taylor
3

Java, 100 98 79 75 octets

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;}

Anciennement:

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;}

Sauvegardé 3 octets en remplaçant trueet falseavec 1>0et 0>1.

23 octets sauvés grâce aux excellentes suggestions de 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;
}

Gardez une trace des valeurs les plus élevées et les plus basses observées jusqu'à présent met n; n'accepter une nouvelle valeur que si c'est m + 1ou n - 1c'est-à-dire la prochaine valeur supérieure ou inférieure; initialisez la valeur haute m, à un moins que le premier élément, de sorte qu'elle "corresponde" la première fois autour de la boucle. Remarque: il s'agit d'un algorithme en ligne à temps linéaire. Il ne nécessite que trois mots de mémoire, pour les valeurs actuelles, les plus élevées jusqu'à présent et les moins élevées jusqu'à présent, contrairement à beaucoup d'autres solutions.

Si la valeur suivante omet les extrémités haute et basse de la plage, la valeur la plus basse jusqu'à présent est définie sur -1et l'extrémité inférieure ne peut jamais continuer et atteindre zéro. Nous détectons ensuite une séquence antsy en vérifiant si la valeur basse natteint zéro.

(Malheureusement, cela est moins efficace car nous devons toujours regarder la séquence entière plutôt que de casser après le premier numéro erroné , mais il est difficile de discuter avec une économie de 23 octets (!) Lorsque d’autres solutions utilisent O (n ^ 2 ) et approches temporelles exponentielles.)

Usage:

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);
    }
}

Remarque: ceci peut également être écrit sans tirer parti de Java 8 lambdas:

Java 7, 89 octets

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
la source
Bon traitement du cas particulier. int m,n;m=n=a[0];--m;pourrait être int n=a[0],m=n-1;, et le cher returnet elsepourrait être réduit avec i==m+1?m++:n=(i==n-1)?i:-1;return n==0;(ou quelque chose de similaire - je n'ai pas testé cela).
Peter Taylor
@PeterTaylor Fantastique! Malheureusement, Java ne permet pas d'effets secondaires tels que m++ou m+=1là-bas, j'ai donc toujours besoin d'un ifet d'un else, et il perd l'aspect de court-circuit sur la première mauvaise valeur, mais c'est une grosse amélioration. Merci!
David Conrad
Cela permettra des effets secondaires dans une expression complexe. Ce qui pourrait ne pas l’aimer, c’est utiliser une expression générale comme une déclaration. Dans le pire des cas, vous devez créer une variable muette jet lui attribuer le résultat, mais pensez qu'il y aurait une meilleure façon de le faire.
Peter Taylor
@PeterTaylor Eh bien, j'ai essayé quelques variantes, notamment en l'attribuant à une variable muette g, et je n'ai pas réussi à la faire fonctionner. (J'utilise Java 9-ea + 138, c'est peut-être une différence entre Java 8 et Java 9?) Je pourrais réessayer demain.
David Conrad
Je l'ai. n-=i==m+1?m-m++:i==n-1?1:n+1;
Peter Taylor
2

Pyth ( fourche ), 13 octets

!sstMM.+MSM._

Pas de lien Try It Online pour ce fork de Pyth. Le fork inclut la fonction deltas .+, qui ne fait pas partie de la bibliothèque Pyth standard.

Explication:

           ._  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.
la source
3
Voir cela me convainc de fusionner cela en Pyth.
Isaac
2

Perl, 66 54 +1 = 55 octets

+1 octet pour -n.

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

Explication:

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

Imprime 0 si faux, 1 si vrai.

-11 octets grâce à @Dada

Gabriel Benamy
la source
1
Celui-là est vraiment sympa. Cependant, vous pouvez utiliser jusqu'à 55 octets de golf perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.': -nau lieu de <>=~ce qui vous permet de vous débarrasser du /rmodificateur. utiliser \d+et puis $&au lieu de (\d+)et $1. !@aau lieu de 0>$#a. $.&=au lieu de $.&&=. push@a,$&au lieu de@a=(@a,$&)
Dada
Pour une raison quelconque, mon système me dit que le nouveau fichier a une longueur de 55 octets, ce qui est évidemment faux car il ne comporte que 54 caractères, alors ???
Gabriel Benamy
Hmm c'est étrange. (et je n'ai aucune idée d'où cela vient). Mais je suis à peu près sûr qu'il ne s'agit que de 54 (le script PPCG-Design m'en dit 54 et mon application de décompte intermédiaire en dit 54 également).
Dada
2
Est-il possible que le nombre d'octets ait été annulé en raison d'une fin de ligne inutile dans le fichier?
Trichoplax
2

Brainfuck, 60 octets

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

La permutation est donnée sous forme d'octets sans séparateurs ni saut de ligne. Puisque \x00se produit dans l'entrée, ceci est conçu pour les implémentations avec EOF = -1. La sortie est \x00pour false et \x01pour true.

Si une permutation de \x01jusqu'à chr(r)est autorisée, nous pouvons remplacer toutes les occurrences de ,+avec ,un score de 57 avec une EOF = 0implémentation.

Essayez-le en ligne (version à 57 octets): l’entrée peut être donnée sous forme de permutation de toute plage d’octets contigus à l’exclusion \x00, et le résultat sera \x00pour false et le minimum de l’étendue pour true.

Nous gardons une trace des min et max vus jusqu'ici, et pour chaque caractère après le premier, vérifions s'il s'agit de min-1, max + 1 ou aucun. Dans le cas de ni l'un ni l'autre, déplacez le pointeur en dehors de l'espace de travail normal afin que les cellules locales deviennent zéro.

La disposition de la mémoire de l’espace de travail normal au début de la boucle principale est

c a b 0 0

cest le caractère actuel, aest min et bmax. (Pour la version à 60 octets, tout est traité avec un décalage de 1 à cause de ,+.)

Mitch Schwartz
la source
1

Brachylog , 22 octets

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

Essayez-le en ligne!

Explication

Je n'ai pas trouvé de moyen concis de vérifier si une liste contient des entiers consécutifs ou non. Le plus court que j'ai trouvé est de générer une plage entre le premier et le dernier élément de cette liste et de vérifier que cette plage est la liste d'origine.

:@[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
Fataliser
la source
La gamme du premier au dernier est une approche qui m’était venue à l'esprit de CJam. L'autre était le tri, les différences par paires, vérifiez qu'elles sont toutes 1. Je ne sais pas à quel point c'est facile dans Brachylog.
Peter Taylor
@PeterTaylor Il n'y a pas de moyen court de générer des paires consécutives (ou de calculer directement les différences par paires) malheureusement (pour l'instant).
Fataliser
1

Lot, 133 octets

@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

Prend l'entrée en tant qu'argument de ligne de commande. Quitte avec le niveau d'erreur 0 en cas de succès, 1 en cas d'échec.

Neil
la source
1

J, 14 octets

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

Ceci est basé sur la méthode de @ xnor .

Explication

/:~-:>./\-<./\  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
milles
la source
1

Java, 170 octets

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;}

Array xa des valeurs allant de 0 au nombre maximum dans l'ordre (Python serait beaucoup mieux ici ...). La boucle revient en arrière en essayant de faire correspondre le nombre le plus bas ( x[b]) ou le plus élevé ( x[e]) non encore rencontré; si c'est le cas, ce nombre pourrait être atteint à cette étape.

Code de test ici .

AlexRacer
la source
0

Mathematica, 47 octets

Un peu plus long que la solution de Martin Ender (surprise surprise!). Mais c’est l’un de mes efforts les plus illisibles, alors c’est bien: D

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

Explication:

#=={}                         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
la source
0

Java 7, 170 169 octets

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 & code de test:

Essayez ici.

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 }));
  }
}

Sortie:

true
true
true
true
false
true
false
true
true
false
true
false
false
false
false
true
Kevin Cruijssen
la source