Imagine que você tenha uma matriz de números inteiros, cujos valores não negativos são ponteiros para outras posições na mesma matriz, apenas que esses valores representem túneis; portanto, se o valor na posição A for positivo e apontar para a posição B, então o valor na posição B também deve ser positivo e apontar para a posição A para representar as duas extremidades do túnel. Então:

Desafio

• Dada uma matriz de números inteiros, verifique se a matriz está de acordo com a restrição de ser uma matriz de encapsulamento e retorne dois valores distintos e coerentes para truthy e falsey.
• Os valores na matriz estarão abaixo de zero para posições fora do túnel e zero ou acima para posições no túnel. Se sua matriz é indexada em 1, o valor zero representa uma posição que não é do túnel. Valores não relacionados ao túnel não precisam ser verificados.
• Se um valor positivo em uma célula aponta para si mesmo, isso é falso. Se A aponta para B, B para C e C para A, isso é falso. Se um valor positivo aponta além dos limites da matriz, isso é um erro.

Exemplos

Os exemplos a seguir são indexados em 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)

Este é o código-golfe , portanto, pode ganhar o código mais curto para cada idioma!

R , 47 bytes

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

Experimente online!

Código desenrolado e explicação:

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 bytes

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

Experimente online!

APL (Dyalog Unicode) , 19 24 bytes

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

Experimente online!

Prefixo lambda anônimo, retornando 1 para truthy e 0 para falsy. O link TIO contém uma versão "prettified" da saída para os casos de teste.

Gritos para @ngn e @ Adám por economizar aproximadamente um bazilhão de bytes.

Uma mensagem extra para @ngn pela ajuda na correção da resposta para alguns casos de teste e na criação de um trem.

A resposta atualizada utiliza ⎕IO←0, configurando o I ndex O como 0.

Quão:

×/<∘≢⍨×≠∘⍳∘≢⍨×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 bytes

Guardado 1 byte graças a @Shaggy

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

Experimente online!

Comentado

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 bytes

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

Experimente online!

Gelatina , 16 bytes

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

Experimente online!

1 indexado.

Perl 6 , 36 bytes

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

Experimente online!

A idéia básica é verificar se o conjunto { i, a[i], a[a[i]] }contém exatamente dois elementos distintos para cada índice icom a[i] >= 0. Se um elemento apontar para si mesmo, o conjunto conterá apenas um único elemento distinto. Se a outra extremidade não apontar de volta i, o conjunto conterá três elementos distintos. Se a[i] < 0, o xxfator é zero ou negativo, então o conjunto é { i, a[i] }, também com dois elementos distintos.

MATL , 19 18 bytes

-1 Byte graças a Luis

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

Experimente online!, apenas para o primeiro, porque eu não sei como fazer todos eles!

Dá 0se realmente, um número inteiro diferente de zero se falsey, por exemplo. para o caso de teste 6 fornece4 .

Lembre-se de que, como o MATLAB, o MATL é indexado 1, portanto, 1 deve ser adicionado aos casos de teste!

Nunca jogou golfe em um Esolang antes, então os conselhos foram muito bem recebidos!

Explicado:

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 bytes

εèNQyNÊ*y0‹~}P

-1 byte graças a @Dorian .

Experimente online ou verifique todos os casos de teste .

Explicação:

ε               # 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)

Japonês -e , 11 bytes

§JªU¦V«aWgU

Tente

Original (sem sinalizador), 14 13 bytes

eȧJªX¦Y«aUgX

Experimente ou execute todos os casos de teste

Python, 112 97 96 86 bytes

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

Experimente Online!

Retorna Trueou False.

-10 bytes graças a @Rod e @TFeld.

K (ngn / k) , 33 bytes

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

Experimente online!

Haskell , 48 bytes

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

Verifique todos os casos de teste!

Explicação

Vamos primeiro desfazer um pouco o código. Como f =<< gé o mesmo que \x -> f (g x) x, o código é equivalente a

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

o que é um pouco mais claro.

(\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)

Esta solução é baseada em uma observação simples: aseja a matriz de entrada e ua lista de pares em (i, a[i])que ié um índice. Então aé uma matriz válida se e somente se para cada (x, y)no ucom y >= 0, o par (y, x)pertence utambém.

Java (JDK) , 89 bytes

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

Experimente online!

Créditos

• -3 bytes graças a AlexRacer
• -6 bytes graças ao ceilingcat

Carvão , 22 bytes

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

Experimente online! Link é a versão detalhada do código. Saídas -para verdade e nada para falsidade. Nota: A inserção de uma matriz vazia parece travar o carvão, mas por enquanto você pode inserir um espaço, o que é próximo o suficiente. Explicação:

  θ                     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 bytes

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;

Experimente online!

Função Made desta vez porque a entrada é array. Retorna 1para verdade e 0para falsey.

Limpo , 60 bytes

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

Experimente online!

Limpo , 142 bytes

Versão monstro extremamente complicada:

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

Experimente online!

Explicado:

$ 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

Ruby , 44 bytes

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

Experimente online!

Pitão , 17 16 bytes

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

Experimente online aqui ou verifique todos os casos de teste de uma vez aqui .

.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: percebeu que o k à direita também era desnecessário

Groovy , 52 bytes

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

Experimente online!

Perl 5 , 54 bytes

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

Experimente online!

C (gcc) , 95 bytes

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

Experimente online!

Mathematica, 42 bytes

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

Função pura. Toma uma lista de números indexada em 1 como entrada e retorno Trueou Falsecomo saída. Apenas segue os túneis, assegurando que os 0mapas para 0, não existam 1 ciclo e todos os ciclos sejam 2 ciclos. (Não tenho certeza absoluta se isso falhar em casos extremos, mas fornece os resultados corretos para os exemplos.)

Esta resposta não funciona. Aqui apenas para fins ilustrativos.

Esta resposta passa em todos os casos de teste publicados (atualmente). No entanto, ele falha (gera um erro) em outra entrada válida, como [1, 2]ou [1, 0, 3, 7].

Como isso poderia passar [1, 0, 3]e falhar [1, 0, 3, 7]? Bem, ele prossegue na lista, exatamente como você esperaria. Quando lê um elemento xda lista a, primeiro verifica se xé menor len(a)e retorna imediatamente False, se houver. Por isso corretamente retorna Falseem [1, 0, 3], porque 3não é inferior a len(a).

Mas, supondo que seja xaprovado nessa verificação, o código continuará executando outras verificações e, em um determinado momento, ele será avaliado a[a[x]]. Já garantimos que a avaliação a[x]será boa ... mas não a[a[x]], o que resolve a[7]quando xestá 3no [1, 0, 3, 7]exemplo. Neste ponto, o Python gera um IndexError, em vez de retornar False.

Para completar, aqui está a resposta.

Python 2 , 59 bytes

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

Experimente online!

Eu queria fazer x<len(a)and-1<a[x]..., mas len(a)é claro que é sempre >-1, então o acima é equivalente. Essa verificação é um total de 5 relações encadeadas ( <,> , <, !=, e ==), além de um controlo separado-1<x noif condição.

Curto-circuitos em Python (convenientemente) encadearam relações como esta; portanto, por exemplo, se x>=len(a)a verificação retornar Falseantes que chegue aoa[x] (o que de outra forma aumentaria umIndexError ).