16
\$\begingroup\$

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!

\$\endgroup\$
  • 3
    \$\begingroup\$ what should we return for [0]? \$\endgroup\$ – ngn Sep 4 '18 at 17:44
  • \$\begingroup\$ Expanding on ngn's question, are self tunnels allowed? What would the cases [0,1] and [0,-1,2] give? \$\endgroup\$ – dylnan Sep 4 '18 at 17:50
  • \$\begingroup\$ @dylnan [0,1] is in the examples. "If a positive value in a cell points to itself, that's a falsey" \$\endgroup\$ – ngn Sep 4 '18 at 17:51
  • 1
    \$\begingroup\$ suggested test: [2,3,0,1] \$\endgroup\$ – ngn Sep 4 '18 at 17:55
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Charlie Sep 4 '18 at 19:49

24 Answers 24

8
\$\begingroup\$

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
}
\$\endgroup\$
  • \$\begingroup\$ I would really appreciate an explanation for this answer. :-) \$\endgroup\$ – Charlie Sep 4 '18 at 15:51
  • 3
    \$\begingroup\$ @Charlie : explanation added \$\endgroup\$ – digEmAll Sep 4 '18 at 17:27
6
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I think this doesn't work for (1), (3 2 1), (5 4 3 2 1). \$\endgroup\$ – nwellnhof Sep 4 '18 at 23:42
  • \$\begingroup\$ 0<× I think \$\endgroup\$ – Uriel Sep 5 '18 at 21:11
4
\$\begingroup\$

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()
\$\endgroup\$
  • \$\begingroup\$ 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). \$\endgroup\$ – Shaggy Sep 4 '18 at 15:09
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 62 bytes \$\endgroup\$ – TFeld Sep 4 '18 at 14:48
  • \$\begingroup\$ 61 bytes \$\endgroup\$ – Οurous Sep 5 '18 at 0:42
3
\$\begingroup\$

Japt, 14 bytes

eȧJªX¦Y©Y¥UgX

Try it or run all test cases


Explanation

                   :Implicit input of array U
 È                 :Map each X at (0-based) index Y
  §J               :  X less than or equal to -1?
    ª              :  Logical OR
     X¦Y           :  X does not equal Y?
        ©          :  Logical AND
         Y¥UgX     :  Y equals the element in U at index X?
e                  :All truthy?
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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                 
\$\endgroup\$
  • \$\begingroup\$ Is my explanation too wordy? I want to make it obvious without going totally overboard. \$\endgroup\$ – Lui Sep 5 '18 at 10:39
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 16 bytes

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

Try it online!

1-indexed.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 16 bytes

ε©0‹®NÊI®èNQ*~}P

Try it online or verify all test cases.

Explanation:

ε             }     # Map each value to:
 ©                  #  Store the current item in the register (without popping)
  0‹                #  If the current value is negative
             ~      #  Or if:
    ®NÊ             #   The current value is not equal to the current index
            *       #   And
       I®èNQ        #   The current value indexed into the input is equal to the index
               P    # And output whether all values are truthy after the map
\$\endgroup\$
  • \$\begingroup\$ My try was the same except with filter. I don't see a way to improve on this. \$\endgroup\$ – Emigna Sep 4 '18 at 16:43
2
\$\begingroup\$

Java (JDK 10), 95 bytes

a->{int l=a.length,i=l;for(;i-->0;)if(a[i]>=0&&(a[i]>=l||a[i]==i||a[a[i]]!=i))i=-2;return-2<i;}

Try it online!

Credits

\$\endgroup\$
  • \$\begingroup\$ Could have been 87 bytes if it weren't for that pesky IndexOutOfBoundsException. Maybe you see something to fix it easily? \$\endgroup\$ – Kevin Cruijssen Sep 4 '18 at 15:41
  • \$\begingroup\$ @KevinCruijssen I can see how to fix that for 102 bytes. Nothing shorter yet :( \$\endgroup\$ – Olivier Grégoire Sep 4 '18 at 15:45
  • 1
    \$\begingroup\$ -3 bytes - omit r and break out of the loop analogous to here \$\endgroup\$ – AlexRacer Sep 4 '18 at 19:00
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 22 bytes

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

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
               L        Length of
                θ       Input array
            ∧           And
                  κ     Current index
                 ⁼      Equals
                   §θι  Indexed value
¬                       Logical Not (i.e. is result empty)
                        Implicitly print
\$\endgroup\$
  • \$\begingroup\$ This doesn't seem to be a very Charcoalable challenge... :-) \$\endgroup\$ – Charlie Sep 4 '18 at 15:24
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Ruby, 44 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Groovy, 52 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 5, 54 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 33 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.