Imaginez que vous ayez un tableau d'entiers, dont les valeurs non négatives sont des pointeurs vers d'autres positions dans le même tableau, seulement que ces valeurs représentent des tunnels, donc si la valeur en position A est positive et pointe vers la position B, alors la valeur en position B doit également être positif et pointer vers la position A pour représenter les deux extrémités du tunnel. Donc:

Défi

• Étant donné un tableau d'entiers, vérifiez si le tableau est conforme à la restriction d'être un tableau de tunnellisation et renvoyez deux valeurs distinctes et cohérentes pour truey et falsey.
• Les valeurs dans le tableau seront inférieures à zéro pour les positions non tunnel et à zéro ou supérieures pour les positions tunnel. Si votre tableau est indexé sur 1, la valeur zéro représente une position non tunnel. Les valeurs non tunnel n'ont pas besoin d'être vérifiées.
• Si une valeur positive dans une cellule pointe vers elle-même, c'est une falsey. Si A pointe vers B, B vers C et C vers A, c'est une falsey. Si une valeur positive pointe au-delà des limites du tableau, c'est une falsey.

Exemples

Les exemples suivants sont indexés 0:

[-1, -1, -1, 6, -1, -1, 3, -1, -1]  Truthy (position 3 points to position 6 and vice versa)
[1, 0]                              Truthy (position 0 points to position 1 and vice versa)
[0, 1]                              Falsey (positions 0 and 1 point to themselves)
[4, 2, 1, -1, 0, -1]                Truthy
[2, 3, 0, 1]                        Truthy
[1, 2, 0]                           Falsey (no circular tunnels allowed)
[-1, 2, -1]                         Falsey (tunnel without end)
[]                                  Truthy (no tunnels, that's OK)
[-1, -2, -3]                        Truthy (no tunnels, that's OK)
[1, 0, 3]                           Falsey (tunnel goes beyond limits)
[1]                                 Falsey (tunnel goes beyond limits)
[1, 0, 3, 7]                        Falsey (tunnel goes beyond limits)

C'est du code-golf , alors le code le plus court pour chaque langue peut gagner!

R , 47 octets

function(v,a=v[v>0],b=sort(a))all(v[a]==b&a!=b)

Essayez-le en ligne!

Code déroulé et explication:

f=
function(v){          # v vector of tunnel indexes (1-based) or values <= 0

  a = v[v>0]          # get the tunnel positions

  b = sort(a)         # sort the tunnel positions ascending

  c1 = v[a]==b        # get the values of 'v' at positions 'a'
                      # and check if they're equal to the sorted positions 'b'
                      # (element-wise, returns a vector of TRUE/FALSE)

  c2 = a != b         # check if positions 'a' are different from sorted positions 'b' 
                      # (to exclude tunnels pointing to themselves, element-wise,
                      #  returns a vector of TRUE/FALSE)

  all(c1 & c2)        # if all logical conditions 'c1' and 'c2' are TRUE then
                      # returns TRUE otherwise FALSE
}

Python 2 , 66 61 60 octets

lambda l:all(len(l)>v!=i==l[v]for i,v in enumerate(l)if-1<v)

Essayez-le en ligne!

APL (Dyalog Unicode) , 19 24 octets

×/<∘≢⍨×≠∘⍳∘≢⍨×0∘>∨⊢=⊢⍳⍳⍨

Essayez-le en ligne!

Préfixe lambda anonyme, renvoyant 1 pour la vérité et 0 pour la fausse. Le lien TIO contient une version "prettified" de la sortie pour les cas de test.

Shoutouts à @ngn et @ Adám pour avoir économisé environ un milliard d'octets.

Un remerciement supplémentaire à @ngn pour l'aide à fixer la réponse pour certains cas de test et à en faire un train.

La réponse mise à jour utilise ⎕IO←0, définissant le I ndex O rigin à 0.

Comment:

×/<∘≢⍨×≠∘⍳∘≢⍨×0∘>∨⊢=⊢⍳⍳⍨ ⍝ Prefix lambda, argument ⍵ → 4 2 1 ¯1 0 ¯1.
                       ⍳⍨ ⍝ Index of (⍳) ⍵ in ⍵. ⍵⍳⍵ → 0 1 2 3 4 3
                     ⊢⍳   ⍝ Index of that in ⍵ (returns the vector length if not found). 
                          ⍝ ⍵⍳⍵⍳⍵ → 4 2 1 6 0 6
                  ⊢=      ⍝ Compare that with ⍵. ⍵=⍵⍳⍵⍳⍵ → 1 1 1 0 1 0
                          ⍝ This checks if positive indices tunnel back and forth correctly.
                 ∨        ⍝ Logical OR with
              0∘>         ⍝ 0>⍵ → 0 0 0 1 0 1∨1 1 1 0 1 0 → 1 1 1 1 1 1
                          ⍝ Removes the zeroes generated by negative indices
             ×            ⍝ Multiply that vector with
            ⍨             ⍝ (using ⍵ as both arguments)
         ⍳∘≢              ⍝ Generate the range [0..length(⍵)-1]
       ≠∘                 ⍝ And do ⍵≠range; this checks if any          
                          ⍝ element in ⍵ is tunneling to itself.
                          ⍝ ⍵≠⍳≢⍵ → 4 2 1 ¯1 0 ¯1≠0 1 2 3 4 5 → 1 1 1 1 1 1  
      ×                   ⍝ Multiply that vector with
     ⍨                    ⍝ (using ⍵ as both arguments)
  <∘≢                     ⍝ ⍵ < length(⍵) → 4 2 1 ¯1 0 ¯1 < 6 → 1 1 1 1 1 1
                          ⍝ This checks if any index is out of bounds
×/                        ⍝ Finally, multiply and reduce.
                          ⍝ ×/1 1 1 1 1 1 → 1 (truthy)

JavaScript (ES6), 35 octets

1 octet enregistré grâce à @Shaggy

a=>a.every((v,i)=>v<0|v!=i&a[v]==i)

Essayez-le en ligne!

Commenté

a =>                // a[] = input array
  a.every((v, i) => // for each value v at position i in a[]:
    v < 0 |         //   force the test to succeed if v is negative (non-tunnel position)
    v != i &        //   make sure that this cell is not pointing to itself
    a[v] == i       //   check the other end of the tunnel
  )                 // end of every()

Python 2 , 65 octets

lambda l:all(l[v:]>[]and v!=i==l[v]or v<0for i,v in enumerate(l))

Essayez-le en ligne!

Gelée , 16 octets

ị=JanJ$>L<$o<1$Ạ

Essayez-le en ligne!

1 indexé.

Perl 6 , 36 octets

{!.grep:{2-set $++,$^v,.[$v]xx$v+1}}

Essayez-le en ligne!

L'idée de base est de vérifier si l'ensemble { i, a[i], a[a[i]] }contient exactement deux éléments distincts pour chaque index iavec a[i] >= 0. Si un élément pointe vers lui-même, l'ensemble ne contient qu'un seul élément distinct. Si l'autre extrémité ne pointe pas vers i, l'ensemble contient trois éléments distincts. Si a[i] < 0le xxfacteur est nul ou négatif, l'ensemble l'est { i, a[i] }aussi, avec deux éléments distincts.

MATL , 19 18 octets

-1 octet grâce à Luis

n:G=GGG0>f))7M-|hs

Essayez-le en ligne! , pour le premier seulement, car je ne sais pas comment les faire tous!

Donne 0si véridique, un entier non nul si falsey, par exemple. pour le cas de test 6 donne 4.

N'oubliez pas que, comme MATLAB, MATL est indexé 1, donc 1 doit être ajouté aux cas de test!

Jamais joué au golf dans un Esolang auparavant, donc les conseils ont été grandement reçus!

Expliqué:

n:G=GGG0>f))7M-|hs
                        Implicit - input array
n                       Number of values in array
 :                      Make array 1:n
  G                     Push input
   =                    Equality
n:G=                    Makes non-zero array if any of the tunnels lead to themselves
    GGG                 Push input 3x
       0                Push literal 0
        >               Greater than
      G0>               Makes array of ones where input > 0
         f              Find - returns indeces of non-zero values
                        Implicit - copy this matrix to clipboard
          )             Indeces - returns array of positive integers in order from input
           )            Ditto - Note, implicit non-zero any above maximum
            7M          Paste from clipboard
              -         Subtract
    GGG0>f))7M-         Makes array of zeros if only two-ended tunnels evident
               |        Absolute value (otherwise eg. [3,4,2,1] -> '0')
                h       Horizontal concat (ie. joins check for self tunnels and wrong tunnels)
                 s      Sum; = 0 if truthy, integer otherwise                 

05AB1E , 16 15 14 octets

εèNQyNÊ*y0‹~}P

-1 octet grâce à @Dorian .

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

Explication:

ε               # Map each value `y` of the (implicit) input-list to:
 è              #   If the current value indexed into the (implicit) input-list
  NQ            #   is equal to the index
       *        #   And
    yNÊ         #   If the current value is not equal to the current index
           ~    #  Or if:
        y0‹     #   The current value is negative
            }P  # After the map: check if everything is truthy
                # (after which the result is output implicitly)

Japt -e , 11 octets

§JªU¦V«aWgU

Essayez-le

Original (sans indicateur), 14 13 octets

eȧJªX¦Y«aUgX

Essayez-le ou exécutez tous les cas de test

Python, 112 97 96 86 octets

f=lambda l:sum(i==l[i]or len(l)<=l[i]or 0<=l[i]and i!=l[l[i]]for i in range(len(l)))<1

Essayez-le en ligne!

Retour True ou False.

-10 octets grâce à @Rod et @TFeld.

K (ngn / k) , 33 octets

{*/(x<0)|(x<#x)&(~x=!#x)&x=x?x?x}

Essayez-le en ligne!

Haskell , 48 octets

(all=<< \u(x,y)->y<0||x/=y&&elem(y,x)u).zip[0..]

Vérifiez tous les cas de test!

Explication

Détruisons d'abord un peu le code. Comme f =<< gc'est le même que \x -> f (g x) x, le code est équivalent à

(\u->all(\(x,y)->y<0||x/=y&&elem(y,x)u)u).zip[0..]

ce qui est un peu plus clair.

(\u ->                                  -- given u, return
    all (\(x, y) ->                     -- whether for all elements (x, y) of u
            y < 0 ||                    -- either y < 0, or
            x /= y && elem (y, x) u     -- (x /= y) and ((y, x) is in u)
        )
    u
) . zip [0..]                           -- given the array a (implicitly via point-free style),
                                        -- return the array augmented with indices (it's the u above)

Cette solution est basée sur une observation simple: asoit le tableau d'entrée, et ula liste des paires (i, a[i])où se itrouve un index. Ensuite aest un tableau valide si et seulement si pour tout (x, y)dans uavec y >= 0, la paire (y, x)appartient uaussi.

Java (JDK) , 89 octets

a->{int l=a.length,i=l;for(;i-->0;)i=a[i]<1||a[i]<l&&a[i]!=i&a[a[i]]==i?i:-2;return-2<i;}

Essayez-le en ligne!

Crédits

• -3 octets grâce à AlexRacer
• -6 octets grâce au plafond

Fusain , 22 octets

¬Φθ∨⁼ικ¬∨‹ι⁰∧‹ιＬθ⁼κ§θι

Essayez-le en ligne! Le lien est vers la version détaillée du code. Sorties -pour la vérité et rien pour la fausse. Remarque: Saisie d'un tableau vide semble planter du charbon de bois, mais pour l'instant, vous pouvez entrer un espace à la place, qui est assez proche. Explication:

  θ                     Input array
 Φ                      Filter elements
     ι                  Current value
    ⁼                   Equals
      κ                 Current index
   ∨                    Or
       ¬                Not
          ι             Current value
         ‹ ⁰            Is less than zero
        ∨               Or
              ι         Current value
             ‹          Is less than
               Ｌ        Length of
                θ       Input array
            ∧           And
                  κ     Current index
                 ⁼      Equals
                   §θι  Indexed value
¬                       Logical Not (i.e. is result empty)
                        Implicitly print

Pascal (FPC) , 165 155 153 octets

function f(a:array of int32):byte;var i:int32;begin f:=1;for i:=0to length(a)-1do if a[i]>-1then if(a[i]=i)or(a[i]>length(a))or(a[a[i]]<>i)then f:=0;end;

Essayez-le en ligne!

Fait fonctionner cette fois parce que l'entrée est un tableau. Retourne 1pour véridique et 0pour falsey.

Nettoyer , 60 octets

import StdEnv
@l=and[v<0||l%(v,v)==[i]&&v<>i\\v<-l&i<-[0..]]

Essayez-le en ligne!

Nettoyer , 142 octets

Version monstre extrêmement compliquée:

import StdEnv,Data.List,Data.Maybe
$l=and[?i(mapMaybe((!?)l)j)j\\i<-l&j<-map((!?)l)l|i>=0]with?a(Just(Just c))(Just b)=a==c&&b<>c;?_ _ _=False

Essayez-le en ligne!

Expliqué:

$ l                           // function $ of `l` is
 = and [                      // true when all elements are true
  ?                           // apply ? to
   i                          // the element `i` of `l`
   (mapMaybe                  // and the result of attempting to
    ((!?)l)                   // try gettting an element from `l`
    j)                        // at the potentially invalid index `j`
   j                          // and `j` itself, which may not exist
  \\ i <- l                   // for every element `i` in `l`
  & j <- map                  // and every potential `j` in
    ((!?)l)                   // `l` trying to be indexed by
    l                         // every element in `l`
  | i >= 0                    // where `i` is greater than zero
 ]
with
 ? a (Just (Just c)) (Just b) // function ? when all the arguments exist
  = a==c && b<>c              // `a` equals `c` and not `b`
  ;
 ? _ _ _ = False              // for all other arguments, ? is false

Rubis , 44 octets

->a{a.all?{|x|x<0||(w=a[x])&&x!=w&&a[w]==x}}

Essayez-le en ligne!

Pyth , 17 16 octets

.A.e|>0b&nbkq@Qb

Essayez-le en ligne ici ou vérifiez tous les cas de test en même temps ici .

.A.e|>0b&nbkq@QbkQ   Implicit: Q=eval(input())
                     Trailing k, Q inferred
  .e             Q   Map the input with b=element, k=index, using:
     >0b               0>b
    |                  OR (
         nbk           b != k
        &              AND
            q@Qbk      Q[b] == k)
.A                   Check if all elements are truthy

Edit: réalisé que le k de fin était également inutile

Groovy , 52 octets

{o=!(i=0);it.each{e->o&=e<0||(it[e]==i&&i-e);i++};o}

Essayez-le en ligne!

Perl 5 , 54 octets

{$i=-1;!grep$_>=0*$i++&&($_==$i||$i!=($_[$_]//-1)),@_}

Essayez-le en ligne!

C (gcc) , 95 octets

i(_,o,O,Q,I)int*_;{for(I=O=0;O<o;O++)_[O]<0||(Q=_[O[_]],I|=_[O]>=o|Q<0|Q>=o|O[_]==O|Q!=O);Q=I;}

Essayez-le en ligne!

Mathematica, 42 octets

#=={}||(a=0@@#)[[#]]=!=a&&a[[#]][[#]]===a&

Fonction pure. Prend une liste de nombres indexés 1 comme entrée et retourne Trueou Falsecomme sortie. Suit juste les tunnels, s'assurant que les 0cartes 0ne correspondent à aucun cycle 1 et que tous les cycles sont à 2 cycles. (Je ne suis pas tout à fait sûr que cela échoue dans les cas de bord, mais cela donne les résultats corrects pour les exemples.)

Cette réponse ne fonctionne pas. Ici à des fins d'illustration uniquement.

Cette réponse passe tous les cas de test (actuellement) publiés. Cependant, il échoue (déclenche une erreur) sur une autre entrée valide, telle que [1, 2]ou[1, 0, 3, 7] .

Comment pourrait-il passer [1, 0, 3]et échouer [1, 0, 3, 7]? Eh bien, il passe par la liste, comme vous vous en doutez. Lorsqu'il lit un élément xde la liste a, il vérifie d'abord s'il xest inférieur à len(a), et retourne immédiatement False, si c'est le cas. Donc , il retourne correctement Falsesur [1, 0, 3], parce que3 n'est pas moinslen(a) .

Mais en supposant que xcette vérification soit réussie, le code continuera ensuite à faire d'autres vérifications, et à un certain moment, il se trouvera à évaluer a[a[x]]. Nous avons déjà garanti que l'évaluation a[x]sera OK ... mais pas a[a[x]], ce qui résout a[7]quand xest 3dans l' [1, 0, 3, 7]exemple. À ce stade, Python soulève un IndexError, plutôt que de revenir False.

Pour être complet, voici la réponse.

Python 2 , 59 octets

lambda a:all(x<len(a)>-1<a[x]!=x==a[a[x]]for x in a if-1<x)

Essayez-le en ligne!

Je voulais le faire x<len(a)and-1<a[x]..., mais bien sûr, len(a)c'est toujours le cas >-1, donc ce qui précède est équivalent. Ce contrôle est un total de 5 relations (enchaînées <, >, <, !=et ==), plus un chèque séparé -1<xdans laif condition.

Python court-circuite (commodément) les relations enchaînées comme celle-ci, donc par exemple si x>=len(a)le chèque revient Falseavant d'arriver à a[x](ce qui autrement déclencherait un IndexError).