# Check my tunneling arrays

Imagine you have an array of integers, whose non-negative values are pointers to other positions in the same array, only that those values represent tunnels, so if the value in position A is positive and points to position B, then the value in position B must be also positive and point to position A to represent both ends of the tunnel. So:

### Challenge

• Given an array of integers, check if the array complies with the restriction to be a tunneling array and return two distinct, coherent values for truthy and falsey.
• The values in the array will be below zero for non-tunnel positions, and zero or above for tunnel positions. If your array is 1-indexed, then the zero value represents a non-tunnel position. Non-tunnel values do not need to be checked.
• If a positive value in a cell points to itself, that's a falsey. If A points to B, B to C and C to A, that's a falsey. If a positive value points beyond the limits of the array, that's a falsey.

### Examples

The following examples are 0-indexed:

[-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)


This is , so may the shortest code for each language win!

• what should we return for [0]? – ngn Sep 4 '18 at 17:44
• Expanding on ngn's question, are self tunnels allowed? What would the cases [0,1] and [0,-1,2] give? – dylnan Sep 4 '18 at 17:50
• @dylnan [0,1] is in the examples. "If a positive value in a cell points to itself, that's a falsey" – ngn Sep 4 '18 at 17:51
• suggested test: [2,3,0,1] – ngn Sep 4 '18 at 17:55
• @JonathanAllan the tunnel values are values indicating possible array positions. If your array is 0-indexed then every value below 0 is not a tunnel value. If it's 1-indexed then every value below 1 is not a tunnel value. – Charlie Sep 4 '18 at 19:49

# R, 47 bytes

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


Try it online!

Unrolled code and explanation :

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
}

• I would really appreciate an explanation for this answer. :-) – Charlie Sep 4 '18 at 15:51
• @Charlie : explanation added – digEmAll Sep 4 '18 at 17:27

# Python 2, 6661 60 bytes

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


Try it online!

# APL (Dyalog Unicode), 19 24 bytes

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


Try it online!

Prefix anonymous lambda, returning 1 for truthy and 0 for falsy. The TIO link contains a "prettified" version of the output for the test cases.

Shoutouts to @ngn and @Adám for saving approximately a bazillion bytes.

An extra shoutout to @ngn for the help with fixing the answer for some test cases, and with making it a train.

The updated answer uses ⎕IO←0, setting the Index Origin to 0.

### How:

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

• I think this doesn't work for (1), (3 2 1), (5 4 3 2 1). – nwellnhof Sep 4 '18 at 23:42
• 0<× I think – Uriel Sep 5 '18 at 21:11

# JavaScript (ES6), 35 bytes

Saved 1 byte thanks to @Shaggy

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


Try it online!

### Commented

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

• Good thing I checked the solutions before posting a port of my Japt solution, which is nearly identical to this. You can save a byte with a=>a.every((v,i)=>v<0|v!=i&a[v]==i). – Shaggy Sep 4 '18 at 15:09

# Python 2, 65 bytes

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


Try it online!

• 62 bytes – TFeld Sep 4 '18 at 14:48
• 61 bytes – Οurous Sep 5 '18 at 0:42

# Jelly, 16 bytes

ị=JanJ$>L<$o<1$Ạ  Try it online! 1-indexed. # Perl 6, 36 bytes {!.grep:{2-set$++,$^v,.[$v]xx$v+1}}  Try it online! The basic idea is to check whether the set { i, a[i], a[a[i]] } contains exactly two distinct elements for each index i with a[i] >= 0. If an element points to itself, the set contains only a single distinct element. If the other end doesn't point back to i, the set contains three distinct elements. If a[i] < 0, the xx factor is zero or negative, so the set is { i, a[i] }, also with two distinct elements. # MATL, 19 18 Bytes -1 Byte thanks to Luis n:G=GGG0>f))7M-|hs  Try it online!, for the first one only, because I don't know how to do all of them! Gives 0 if truthy, a non-zero integer if falsey, eg. for test case 6 gives 4. Please remember that like MATLAB, MATL is 1-indexed so 1 must be added to the test cases! Never golfed in an Esolang before, so advice greatly received! Explained: 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  • Is my explanation too wordy? I want to make it obvious without going totally overboard. – Lui Sep 5 '18 at 10:39 # 05AB1E, 1615 14 bytes εèNQyNÊ*y0‹~}P  -1 byte thanks to @Dorian. Explanation: ε # 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)  • My try was the same except with filter. I don't see a way to improve on this. – Emigna Sep 4 '18 at 16:43 • 14 bytes. You can push the current value of the ε with y. So no need for ©, and each ® replaced by y – Dorian Oct 1 '19 at 12:36 • @Dorian Ah, of course.. That wasn't possible in the legacy when I posted this answer, but should have thought about it when I made my golf earlier today. Thanks! :) – Kevin Cruijssen Oct 1 '19 at 12:38 # Japt-e, 11 bytes §JªU¦V«aWgU  Try it ## Original (w/o flag), 14 13 bytes eÈ§JªX¦Y«aUgX  ## Python, 1129796 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  Try it Online! Returns True or False. -10 bytes thanks to @Rod and @TFeld. # K (ngn/k), 33 bytes {*/(x<0)|(x<#x)&(~x=!#x)&x=x?x?x}  Try it online! # Haskell, 48 bytes (all=<< \u(x,y)->y<0||x/=y&&elem(y,x)u).zip[0..]  Verify all testcases! ## Explanation Let's first ungolf the code a bit. As f =<< g is the same as \x -> f (g x) x, the code is equivalent to (\u->all(\(x,y)->y<0||x/=y&&elem(y,x)u)u).zip[0..]  which is a bit clearer. (\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)  This solution is based on a simple observation: let a be the input array, and u the list of pairs (i, a[i]) where i is an index. Then a is a valid array if and only if for every (x, y) in u with y >= 0, the pair (y, x) belongs to u as well. # 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;}  Try it online! ## Credits • Could have been 87 bytes if it weren't for that pesky IndexOutOfBoundsException. Maybe you see something to fix it easily? – Kevin Cruijssen Sep 4 '18 at 15:41 • @KevinCruijssen I can see how to fix that for 102 bytes. Nothing shorter yet :( – Olivier Grégoire Sep 4 '18 at 15:45 • -3 bytes - omit r and break out of the loop analogous to here – AlexRacer Sep 4 '18 at 19:00 # Charcoal, 22 bytes ¬Φθ∨⁼ικ¬∨‹ι⁰∧‹ιＬθ⁼κ§θι  Try it online! Link is to verbose version of code. Outputs - for truthy and nothing for falsy. Note: Inputting an empty array seems to crash Charcoal, but for now you can enter a space instead, which is near enough. Explanation:  θ 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  • This doesn't seem to be a very Charcoalable challenge... :-) – Charlie Sep 4 '18 at 15:24 # Pascal (FPC), 165155 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;  Try it online! Made function this time because the input is array. Returns 1 for truthy and 0 for falsey. # Clean, 60 bytes import StdEnv @l=and[v<0||l%(v,v)==[i]&&v<>i\\v<-l&i<-[0..]]  Try it online! # Clean, 142 bytes Vastly over-complicated monster version: 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


Try it online!

Explained:

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


Try it online!

# Pyth, 17 16 bytes

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


Try it online here, or verify all the test cases at once here.

.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: realised that the trailing k was also unnecessary

# Groovy, 52 bytes

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


Try it online!

# Perl 5, 54 bytes

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


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


Try it online!

# Mathematica, 42 bytes

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


Pure function. Takes a 1-indexed list of numbers as input and returns True or False as output. Just follows the tunnels, ensuring that 0 maps to 0, no 1-cycles exist, and all cycles are 2-cycles. (I'm not entirely sure if this fails on any edge cases, but it gives the correct results for the examples.)

# This answer does not work. Here for illustration purposes only.

This answer passes all of the (currently) posted test cases. However, it fails (raises an error) on other valid input, such as [1, 2] or [1, 0, 3, 7].

How could it pass [1, 0, 3] and fail [1, 0, 3, 7]? Well, it proceeds through the list, just like you'd expect. When it reads an element x of the list a, it first checks whether x is less than len(a), and immediately returns False, if so. So it correctly returns False on [1, 0, 3], because 3 is not less than len(a).

But assuming that x passes that check, the code will then go on to do some other checks, and at a certain point it happens to evaluate a[a[x]]. We've already guaranteed that evaluating a[x] will be OK...but not a[a[x]], which resolves to a[7] when x is 3 in the [1, 0, 3, 7] example. At this point Python raises an IndexError, rather than returning False.

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

I wanted to do x<len(a)and-1<a[x]..., but of course len(a) is always >-1, so the above is equivalent. This check is a total of 5 chained relations (<, >, <, !=, and ==), plus a separate check -1<x in the if condition.
Python (conveniently) short-circuits chained relations like this, so for example if x>=len(a) then the check returns False before it gets to a[x] (which would otherwise raise an IndexError).