Check my tunneling arrays

Question

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 code-golf, so may the shortest code for each language win!

Answer 1

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
}

Answer 2

Python 2, 66 61 60 bytes

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

Try it online!

Answer 3

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)

Answer 4

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

Answer 5

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!

Answer 6

Jelly, 16 bytes

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

Try it online!

1-indexed.

Answer 7

Japt -e, 11 bytes

§JªU¦V«aWgU

Try it

---

Original (w/o flag), 14 13 bytes

eȧJªX¦Y«aUgX

Try it or run all test cases

Answer 8

05AB1E, 16 15 14 bytes

εèNQyNÊ*y0‹~}P

-1 byte thanks to @Dorian.

Try it online or verify all test cases.

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)

Answer 9

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.

Answer 10

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                 

Answer 11

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

Try it Online!

Returns True or False.

-10 bytes thanks to @Rod and @TFeld.

Answer 12

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

• -3 bytes thanks to AlexRacer
• -6 bytes thanks to ceilingcat

Answer 13

K (ngn/k), 33 bytes

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

Try it online!

Answer 14

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.

Answer 15

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

Answer 16

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;

Try it online!

Made function this time because the input is array. Returns 1 for truthy and 0 for falsey.

Answer 17

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

Answer 18

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

Answer 19

Ruby, 44 bytes

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

Try it online!

Answer 20

Groovy, 52 bytes

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

Try it online!

Answer 21

Perl 5, 54 bytes

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

Try it online!

Answer 22

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!

Answer 23

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

Answer 24

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.

For completeness, here's the answer.

Python 2, 59 bytes

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

Try it online!

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