Представьте, что у вас есть массив целых чисел, неотрицательные значения которых являются указателями на другие позиции в том же массиве, только эти значения представляют туннели, поэтому, если значение в позиции A положительно и указывает на позицию B, то значение в позиции B также должен быть положительным и указывать на положение A для представления обоих концов туннеля. Так:

Вызов

• Учитывая массив целых чисел, проверьте, соответствует ли массив ограничению для туннельного массива, и верните два различных, согласованных значения для истинности и ложности.
• Значения в массиве будут ниже нуля для не туннельных позиций и ноль или выше для туннельных позиций. Если ваш массив индексируется 1, то нулевое значение представляет собой не туннельную позицию. Нетуннельные значения проверять не нужно.
• Если положительное значение в ячейке указывает на себя, это фальшивка. Если A указывает на B, B на C и C на A, это фальшивка. Если положительное значение указывает за пределы массива, это фальшивка.

Примеры

Следующие примеры с 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)

Это код-гольф , поэтому победит самый короткий код для каждого языка!

R , 47 байт

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

Попробуйте онлайн!

Развернутый код и объяснение:

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 байт

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

Попробуйте онлайн!

APL (Dyalog Unicode) , 19 24 байта

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

Попробуйте онлайн!

Префикс анонимной лямбды, возвращающий 1 для правды и 0 для фальсификации. Ссылка TIO содержит «предварительно подтвержденную» версию выходных данных для тестовых случаев.

Приветствую @ngn и @ Adám за экономию около миллиарда байтов.

Дополнительный крик @ngn за помощь в исправлении ответа для некоторых тестовых случаев и в создании поезда.

В обновленном ответе используется ⎕IO←0настройка I ndex O rigin на 0.

Как:

×/<∘≢⍨×≠∘⍳∘≢⍨×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 байт

Сохранено 1 байт благодаря @Shaggy

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

Попробуйте онлайн!

комментарии

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 байт

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

Попробуйте онлайн!

Желе , 16 байт

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

Попробуйте онлайн!

1-индексироваться.

Perl 6 , 36 байт

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

Попробуйте онлайн!

Основная идея состоит в том, чтобы проверить, { i, a[i], a[a[i]] }содержит ли набор ровно два отдельных элемента для каждого индекса iс a[i] >= 0. Если элемент указывает на себя, набор содержит только один отдельный элемент. Если другой конец не указывает на назад i, набор содержит три различных элемента. Еслиa[i] < 0 , то xxмножитель равен нуль или отрицательный, так что множество { i, a[i] }, а также с двумя различными элементами.

MATL , 19 18 байт

-1 байт благодаря Луису

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

Попробуйте онлайн!Только для первого, потому что я не знаю, как все это сделать!

Дает, 0если верно, ненулевое целое число, если фальси, например. для теста 6 дает4 .

Помните, что, как и MATLAB, MATL индексируется 1, поэтому 1 необходимо добавить в тестовые случаи!

Никогда прежде не играл в гольф на Esolang, поэтому совет получен!

Разъяснение:

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 байтов

εèNQyNÊ*y0‹~}P

-1 байт благодаря @Dorian .

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

ε               # 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 байт

§JªU¦V«aWgU

Попытайся

Оригинал (без флага), 14 13 байт

eȧJªX¦Y«aUgX

Попробуйте или запустите все тесты

Python, 112 97 96 86 байт

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

Попробуйте онлайн!

Возвращает Trueили False.

-10 байт благодаря @Rod и @TFeld.

К (нгн / к) , 33 байта

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

Попробуйте онлайн!

Haskell , 48 байтов

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

Проверьте все тестовые случаи!

объяснение

Давайте сначала немного разгадать код. В f =<< gтакой же , как \x -> f (g x) xкод эквивалентен

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

что немного понятнее.

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

Это решение основано на простом наблюдении: пусть aбудет входной массив и uсписок пар, (i, a[i])где iесть индекс. Тогда aэто допустимый массив, если и только если для каждого (x, y)в uс y >= 0, пара также (y, x)принадлежит u.

Java (JDK) , 89 байт

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

Попробуйте онлайн!

кредиты

• -3 байта благодаря AlexRacer
• -6 байт благодаря потолку

Древесный уголь , 22 байта

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

Попробуйте онлайн! Ссылка на подробную версию кода. Выходы -для правды и ничего для фальши. Примечание: ввод пустого массива, похоже, приводит к сбою Charcoal, но сейчас вы можете ввести вместо него пробел, которого достаточно. Объяснение:

  θ                     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

Паскаль (FPC) , 165 155 153 байта

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;

Попробуйте онлайн!

На этот раз сделал функцию, потому что вход является массивом. Возвращается 1за правду и 0за фалси.

Чисто , 60 байт

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

Попробуйте онлайн!

Чисто , 142 байта

Значительно сложная версия монстра:

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

Попробуйте онлайн!

Разъяснение:

$ 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

Рубин , 44 байта

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

Попробуйте онлайн!

Pyth , 17 16 байт

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

Попробуйте онлайн здесь или проверьте все тестовые примеры сразу здесь .

.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

Редактировать: понял, что тянущийся k тоже не нужен

Groovy , 52 байта

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

Попробуйте онлайн!

Perl 5 , 54 байта

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

Попробуйте онлайн!

C (gcc) , 95 байт

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

Попробуйте онлайн!

Mathematica, 42 байта

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

Чистая функция. Принимает 1-индексированный список чисел как ввод и возвращает Trueили Falseкак вывод. Просто следует за туннелями, обеспечивая 0соответствие 01-циклам, и все циклы являются 2-циклами. (Я не совсем уверен, если это не удается в каких-либо крайних случаях, но это дает правильные результаты для примеров.)

Этот ответ не работает. Здесь только для иллюстрации.

Этот ответ проходит все (в настоящее время) опубликованные контрольные примеры. Однако, это терпит неудачу (вызывает ошибку) на другом допустимом вводе, таком как [1, 2]или[1, 0, 3, 7] .

Как это могло пройти [1, 0, 3]и потерпеть неудачу [1, 0, 3, 7]? Ну, это происходит по списку, как и следовало ожидать. Когда он читает элемент xсписка a, он сначала проверяет, xменьше ли он len(a), и сразу же возвращает False, если это так. Так что правильно возвращается Falseна [1, 0, 3], так как 3не менееlen(a) .

Но если предположить, что xэта проверка прошла, код продолжит выполнять некоторые другие проверки, и в определенный момент это произойдет a[a[x]]. Мы уже гарантировали , что оценка a[x]будет хорошо ... но не a[a[x]], который решает , a[7]когда xэто 3в [1, 0, 3, 7]примере. В этот момент Python поднимает IndexError, а не возвращаетFalse .

Для полноты вот ответ.

Python 2 , 59 байт

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

Попробуйте онлайн!

Я хотел сделать x<len(a)and-1<a[x]..., но, конечно len(a), всегда >-1, поэтому вышесказанное эквивалентно. Эта проверка в общей сложности 5 прикованных отношений ( <, >, <, !=, и ==), плюс отдельного чека -1<xвif состоянии.

Python (удобно) замыкает цепочечные отношения, как это, например, если x>=len(a)тогда проверка вернется Falseдо того, как доберется a[x](что в противном случае вызвало бы IndexError).