Überprüfen Sie meine Tunnel-Arrays

18

Stellen Sie sich vor, Sie haben ein Array von Ganzzahlen, deren nicht negative Werte Zeiger auf andere Positionen im selben Array sind, nur dass diese Werte Tunnel darstellen. Wenn also der Wert an Position A positiv ist und auf Position B zeigt, dann der Wert an Position B muss ebenfalls positiv sein und auf Position A zeigen, um beide Enden des Tunnels darzustellen. So:

Herausforderung

  • Überprüfen Sie bei einem gegebenen Array von Ganzzahlen, ob das Array der Einschränkung entspricht, ein Tunnel-Array zu sein, und geben Sie zwei unterschiedliche, kohärente Werte für truthy und falsey zurück.
  • Die Werte im Array liegen für Nicht-Tunnelpositionen unter Null und für Tunnelpositionen über Null. Wenn Ihr Array 1-indiziert ist, repräsentiert der Nullwert eine Nicht-Tunnel-Position. Nicht-Tunnel-Werte müssen nicht überprüft werden.
  • Wenn ein positiver Wert in einer Zelle auf sich selbst zeigt, ist das eine Falschmeldung. Wenn A auf B, B auf C und C auf A zeigt, ist das eine Falschmeldung. Wenn ein positiver Wert über die Grenzen des Arrays hinausweist, ist das eine Falschmeldung.

Beispiele

Die folgenden Beispiele sind 0-indiziert:

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

Das ist , also kann der kürzeste Code für jede Sprache gewinnen!

Charlie
quelle
3
Wofür sollen wir zurückkehren [0]?
4.
1
Erweitere die Frage von ngn: Sind Selbsttunnel erlaubt? Was würden die Fälle [0,1]und [0,-1,2]geben?
Dylnan
1
@ Dylnan [0,1]ist in den Beispielen. „Wenn ein positiver Wert in einer Zelle auf sich selbst, das ist ein Falsey“
ngn
1
[2,3,0,1]
Vorgeschlagener
1
@JonathanAllan Die Tunnelwerte sind Werte, die mögliche Array-Positionen angeben. Wenn Ihr Array 0-indiziert ist, ist jeder Wert unter 0 kein Tunnelwert. Wenn es 1-indiziert ist, ist jeder Wert unter 1 kein Tunnelwert.
Charlie

Antworten:

8

R , 47 Bytes

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

Probieren Sie es online!


Abgerollter Code und Erklärung:

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
}
digEmAll
quelle
Ich würde eine Erklärung für diese Antwort sehr begrüßen. :-)
Charlie
3
@ Charlie: Erklärung hinzugefügt
digEmAll
5

APL (Dyalog Unicode) , 19 24 Bytes

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

Probieren Sie es online!

Präfix anonymes Lambda, das 1 für wahr und 0 für falsch zurückgibt. Der TIO-Link enthält eine "hübsche" Version der Ausgabe für die Testfälle.

Grüße an @ngn und @ Adám, weil sie ungefähr eine Milliarde Bytes gespart haben.

Ein zusätzliches Dankeschön an @ngn für die Hilfe beim Beheben der Antwort für einige Testfälle und beim Erstellen eines Zuges.

Die aktualisierten Antwort Anwendungen ⎕IO←0, die Einstellung der I ndex O Rigin auf 0.

Wie:

×/<∘≢⍨×≠∘⍳∘≢⍨×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 11 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 ¯10 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)
J. Sallé
quelle
Ich denke, das funktioniert nicht für (1), (3 2 1), (5 4 3 2 1).
Nwellnhof
0<×Ich denke
Uriel
4

JavaScript (ES6), 35 Byte

1 Byte dank @Shaggy gespeichert

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

Probieren Sie es online!

Kommentiert

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()
Arnauld
quelle
Gut, dass ich die Lösungen überprüft habe, bevor ich einen Port meiner Japt-Lösung gepostet habe, der fast identisch mit diesem ist. Mit können Sie ein Byte speichern a=>a.every((v,i)=>v<0|v!=i&a[v]==i).
Shaggy
3

Perl 6 , 36 Bytes

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

Probieren Sie es online!

Die Grundidee ist zu prüfen, ob die Menge { i, a[i], a[a[i]] }genau zwei unterschiedliche Elemente für jeden Index imit enthält a[i] >= 0. Wenn ein Element auf sich selbst zeigt, enthält die Menge nur ein einzelnes unterschiedliches Element. Wenn das andere Ende nicht zurück zeigt i, enthält die Menge drei verschiedene Elemente. Wenn a[i] < 0der xxFaktor Null oder negativ ist, besteht die Menge { i, a[i] }ebenfalls aus zwei unterschiedlichen Elementen.

nwellnhof
quelle
3

MATL , 19 18 Bytes

-1 Byte dank Luis

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

Probieren Sie es online!, nur für die erste, weil ich nicht weiß, wie ich sie alle machen soll!

Gibt, 0wenn wahr, eine ganze Zahl ungleich Null, wenn falsch, z. für Testfall 6 gibt4 .

Bitte denken Sie daran, dass MATL wie MATLAB 1-indiziert ist, sodass 1 zu den Testfällen hinzugefügt werden muss!

Nie zuvor in einem Esolang Golf gespielt, daher wurden Ratschläge sehr gerne entgegengenommen!

Erklärt:

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                 
Lui
quelle
Ist meine Erklärung zu wortreich? Ich möchte es deutlich machen, ohne völlig über Bord zu gehen.
Lui
3

05AB1E , 16 15 14 Bytes

εèNQyNÊ*y0‹~}P

-1 Byte dank @Dorian .

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

ε               # 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)
Kevin Cruijssen
quelle
Mein Versuch war der gleiche, außer mit Filter. Ich sehe keinen Weg, dies zu verbessern.
Emigna
1
14 Bytes . Sie können den aktuellen Wert der εmit schieben y. Also keine Notwendigkeit ©, und jeder ®ersetzt durchy
Dorian
@Dorian Ah, natürlich .. Das war im Erbe, als ich diese Antwort gepostet habe, nicht möglich, hätte aber darüber nachdenken müssen, als ich heute früher Golf gespielt habe. Vielen Dank! :)
Kevin Cruijssen
2

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

Probieren Sie es online!

Rückgabe Trueoder False.

-10 Bytes dank @Rod und @TFeld.

DimChtz
quelle
2

Haskell , 48 Bytes

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

Überprüfen Sie alle Testfälle!

Erläuterung

Lassen Sie uns zuerst den Code ein wenig entgolfen. Wie f =<< gist das gleiche \x -> f (g x) x, ist der Code gleichbedeutend mit

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

Das ist ein bisschen klarer.

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

Diese Lösung basiert auf einer einfachen Beobachtung: Sei adas Eingabearray und udie Liste der Paare, bei (i, a[i])denen ies sich um einen Index handelt. Dann aist genau dann ein gültiges Array, wenn für jedes (x, y)in umit y >= 0auch das Paar (y, x)dazugehört u.

Delfad0r
quelle
2

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

Probieren Sie es online!

Credits

Olivier Grégoire
quelle
Hätte 87 Bytes betragen können, wenn diese lästige IndexOutOfBoundsException nicht gewesen wäre. Vielleicht sehen Sie etwas, um es leicht zu beheben?
Kevin Cruijssen
@ KevinCruijssen Ich kann sehen, wie man das für 102 Bytes behebt . Noch nichts kürzeres :(
Olivier Grégoire
1
-3 Bytes - weglassen rund aus der Schleife ausbrechen analog hier
AlexRacer
1

Holzkohle , 22 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Ausgaben -für Wahres und nichts für Falsches. Hinweis: Die Eingabe eines leeren Arrays scheint Charcoal zum Absturz zu bringen, aber Sie können stattdessen ein Leerzeichen eingeben, das nahe genug ist. Erläuterung:

  θ                     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
Neil
quelle
Dies scheint keine große Herausforderung für Holzkohle zu sein ... :-)
Charlie
1

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;

Probieren Sie es online!

Diesmal funktioniert es, weil die Eingabe ein Array ist. Returns 1für truthy und 0für Falsey.

AlexRacer
quelle
1

Sauber , 60 Bytes

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

Probieren Sie es online!

Sauber , 142 Bytes

Sehr überkomplizierte 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

Probieren Sie es online!

Erklärt:

$ 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
Οurous
quelle
1

Pyth , 17 16 Bytes

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

Versuchen Sie es online hier oder überprüfen alle Testfälle auf einmal hier .

.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: erkannte, dass das nachgestellte k auch unnötig war

Sok
quelle
1

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

Probieren Sie es online!

Jonathan Frech
quelle
0

Mathematica, 42 Bytes

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

Funktion pur. Nimmt eine 1-indizierte Liste von Zahlen als Eingabe und Rückgabe Trueoder Falseals Ausgabe. Folgt einfach den Tunneln und stellt sicher, dass 0Maps zu 0keinen 1-Zyklen existieren und alle Zyklen 2-Zyklen sind. (Ich bin mir nicht ganz sicher, ob dies in Randfällen fehlschlägt, aber es gibt die richtigen Ergebnisse für die Beispiele.)

LegionMammal978
quelle
0

Diese Antwort funktioniert nicht. Hier nur zur Veranschaulichung.

Diese Antwort besteht alle (aktuell) geposteten Testfälle. Es schlägt jedoch bei anderen gültigen Eingaben wie [1, 2]oder fehl (löst einen Fehler aus) [1, 0, 3, 7].

Wie konnte es passieren [1, 0, 3]und scheitern [1, 0, 3, 7]? Nun, es geht durch die Liste, genau wie Sie es erwarten würden. Wenn es ein Element xder Liste liest a, prüft es zuerst, ob xes kleiner als ist len(a), und gibt es False, falls dies der Fall ist , sofort zurück . Also kehrt es richtig Falseweiter[1, 0, 3] , da 3ist nicht weniger alslen(a) .

Unter der Annahme, xdass diese Prüfung bestanden wurde, führt der Code dann einige weitere Prüfungen durch und wird zu einem bestimmten Zeitpunkt ausgewertet a[a[x]]. Wir haben bereits garantiert, dass die Auswertung a[x]in Ordnung sein wird ... aber nicht a[a[x]], was sich in dem Beispiel dahingehend auflöst, a[7]wann . An diesem Punkt wirft Python ein , anstatt zurückzukehrenx3[1, 0, 3, 7]IndexErrorFalse .

Der Vollständigkeit halber hier die Antwort.

Python 2 , 59 Bytes

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

Probieren Sie es online!

Ich wollte es tun x<len(a)and-1<a[x]..., aber natürlich len(a)ist es immer >-1so, dass das oben Genannte äquivalent ist. Diese Prüfung ist insgesamt 5 gekettet Beziehungen ( <, >, <, !=, und ==), sowie eine separate Prüfung -1<xim ifZustand.

Python (bequemerweise) schließt verkettete Relationen wie diese kurz. Wenn also zum Beispiel x>=len(a)der Scheck zurückkommt, Falsebevor er ankommt a[x](was andernfalls einen auslösen würde IndexError).

mathmandan
quelle