Bayangkan Anda memiliki array bilangan bulat, yang nilai non-negatifnya adalah pointer ke posisi lain dalam array yang sama, hanya saja nilai-nilai itu mewakili terowongan, jadi jika nilai di posisi A positif dan menunjuk ke posisi B, maka nilai di posisi B harus juga positif dan arahkan ke posisi A untuk mewakili kedua ujung terowongan. Begitu:

Tantangan

• Diberikan array bilangan bulat, periksa apakah array sesuai dengan batasan menjadi array tunneling dan mengembalikan dua nilai koheren yang berbeda untuk truthy dan falsey.
• Nilai dalam array akan berada di bawah nol untuk posisi non-terowongan, dan nol atau di atas untuk posisi terowongan. Jika larik Anda diindeks 1, maka nilai nol mewakili posisi non-terowongan. Nilai-nilai non-terowongan tidak perlu diperiksa.
• Jika nilai positif dalam sel menunjuk ke dirinya sendiri, itu adalah kesalahan. Jika A menunjuk ke B, B ke C dan C ke A, itu kesalahan. Jika nilai positif menunjuk di luar batas array, itu kesalahan.

Contohnya

Contoh-contoh berikut diindeks 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)

Ini adalah kode-golf , jadi semoga kode terpendek untuk setiap bahasa menang!

R , 47 byte

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

Cobalah online!

Kode dan penjelasan yang belum dibuka:

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 byte

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

Cobalah online!

APL (Dyalog Unicode) , 19 24 byte

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

Cobalah online!

Awali lambda anonim, kembalikan 1 untuk truey dan 0 untuk falsy. TIO link berisi versi "prettified" dari output untuk kasus uji.

Shoutouts to @ngn dan @ Adám untuk menghemat sekitar satu miliar bita.

Sebuah shoutout ekstra ke @ngn untuk bantuan memperbaiki jawaban untuk beberapa kasus uji, dan menjadikannya kereta.

Jawaban yang diperbarui menggunakan ⎕IO←0, mengatur I ndex O rigin ke 0.

Bagaimana:

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

Disimpan 1 byte berkat @Shaggy

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

Cobalah online!

Berkomentar

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 byte

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

Cobalah online!

Jelly , 16 byte

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

Cobalah online!

1-diindeks.

Perl 6 , 36 byte

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

Cobalah online!

Ide dasarnya adalah untuk memeriksa apakah set { i, a[i], a[a[i]] }berisi tepat dua elemen yang berbeda untuk masing-masing indeks idengan a[i] >= 0. Jika sebuah elemen menunjuk ke dirinya sendiri, set hanya berisi satu elemen yang berbeda. Jika ujung yang lain tidak mengarah ke belakang i, set tersebut berisi tiga elemen berbeda. Jika a[i] < 0, xxfaktornya nol atau negatif, maka himpunannya { i, a[i] }, juga dengan dua elemen berbeda.

MATL , 19 18 Bytes

-1 Byte, terima kasih untuk Luis

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

Cobalah online! , untuk yang pertama saja, karena saya tidak tahu bagaimana melakukan semuanya!

Memberi 0jika benar, bilangan bulat bukan nol jika falsey, mis. untuk test case 6 memberikan 4.

Harap diingat bahwa seperti MATLAB, MATL 1-diindeks jadi 1 harus ditambahkan ke dalam test case!

Tidak pernah bermain golf di Esolang sebelumnya, jadi saran sangat diterima!

Dijelaskan:

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 byte

εèNQyNÊ*y0‹~}P

-1 byte terima kasih kepada @Dorian .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

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

§JªU¦V«aWgU

Cobalah

Asli (tanpa bendera), 14 13 byte

eȧJªX¦Y«aUgX

Cobalah atau jalankan semua test case

Python, 112 97 96 86 byte

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

Cobalah secara Online!

Pengembalian Trueatau False.

-10 byte berkat @Rod dan @TFeld.

K (ngn / k) , 33 byte

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

Cobalah online!

Haskell , 48 byte

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

Verifikasi semua testcases!

Penjelasan

Mari kita ungolf sedikit kode dulu. Sama f =<< gseperti \x -> f (g x) x, kode ini setara dengan

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

yang sedikit lebih jelas.

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

Solusi ini didasarkan pada pengamatan sederhana: biarkan amenjadi array input, dan udaftar pasangan di (i, a[i])mana iindeks. Kemudian aadalah array valid jika dan hanya jika untuk setiap (x, y)dalam udengan y >= 0, pasangan (y, x)milik ujuga.

Java (JDK) , 89 byte

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

Cobalah online!

Kredit

• -3 byte terima kasih kepada AlexRacer
• -6 bytes berkat ceilingcat

Arang , 22 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Keluaran -untuk kebenaran dan tidak ada untuk kepalsuan. Catatan: Memasukkan array kosong tampaknya menabrak Arang, tetapi untuk saat ini Anda dapat memasukkan spasi, yang cukup dekat. Penjelasan:

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

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;

Cobalah online!

Berfungsi kali ini karena inputnya adalah array. Kembali 1untuk kebenaran dan 0kepalsuan.

Bersih , 60 byte

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

Cobalah online!

Bersih , 142 byte

Versi monster yang sangat rumit:

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

Cobalah online!

Dijelaskan:

$ 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 byte

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

Cobalah online!

Pyth , 17 16 byte

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

Coba online di sini , atau verifikasi semua uji sekaligus di sini .

.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

Sunting: menyadari bahwa trailing k juga tidak perlu

Groovy , 52 byte

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

Cobalah online!

Perl 5 , 54 byte

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

Cobalah online!

C (gcc) , 95 byte

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

Cobalah online!

Mathematica, 42 byte

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

Fungsi murni. Mengambil daftar angka 1-diindeks sebagai input dan pengembalian Trueatau Falsesebagai output. Cukup ikuti terowongan, pastikan 0peta untuk 0, tidak ada siklus 1, dan semua siklus siklus 2. (Saya tidak sepenuhnya yakin apakah ini gagal pada setiap kasus tepi, tetapi memberikan hasil yang benar untuk contoh-contoh.)

Jawaban ini tidak berfungsi. Di sini hanya untuk ilustrasi.

Jawaban ini melewati semua kasus uji yang diposting (saat ini). Namun, gagal (menimbulkan kesalahan) pada input yang valid lainnya, seperti [1, 2]atau [1, 0, 3, 7].

Bagaimana itu bisa berlalu [1, 0, 3]dan gagal [1, 0, 3, 7]? Yah, itu berlanjut melalui daftar, seperti yang Anda harapkan. Ketika membaca elemen xdaftar a, itu pertama-tama memeriksa apakah xkurang dari len(a), dan segera kembali False, jika demikian. Jadi benar mengembalikan Falsepada [1, 0, 3], karena 3tidak kurang dari len(a).

Tetapi dengan asumsi bahwa xmelewati pemeriksaan itu, kode kemudian akan melakukan beberapa pemeriksaan lain, dan pada titik tertentu itu terjadi untuk mengevaluasi a[a[x]]. Kami sudah dijamin bahwa evaluasi a[x]akan OK ... tapi tidak a[a[x]], yang memutuskan untuk a[7]saat xini 3dalam [1, 0, 3, 7]contoh. Pada titik ini Python memunculkan IndexError, bukannya kembali False.

Untuk kelengkapan, inilah jawabannya.

Python 2 , 59 byte

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

Cobalah online!

Saya ingin melakukannya x<len(a)and-1<a[x]..., tetapi tentu saja len(a)selalu >-1, jadi di atas adalah setara. Pemeriksaan ini total 5 hubungan dirantai ( <, >, <, !=, dan ==), ditambah pemeriksaan terpisah -1<xdi ifkondisi.

Python (dengan mudah) hubungan pendek hubungan berantai seperti ini, jadi misalnya jika x>=len(a)kemudian cek kembali Falsesebelum sampai ke a[x](yang sebaliknya akan meningkatkan suatu IndexError).