Zeigerspringen

21

Angenommen , wir haben eine Reihe ps der Länge n mit Zeigern zeigt auf einer Stelle im Array: Der Prozess der „ Zeiger Springen “ wird alle Zeiger auf die Position des Zeigers gesetzt verweist er auf Punkte.

Für die Zwecke dieser Abfrage ist ein Zeiger der (auf Null basierende) Index eines Elements des Arrays. Dies impliziert, dass jedes Element im Array größer oder gleich 0 und kleiner als n . Unter Verwendung dieser Notation kann der Prozess wie folgt formuliert werden:

for i = 0..(n-1) {
  ps[i] = ps[ps[i]]
}

Dies bedeutet (für diese Herausforderung), dass die Zeiger in sequentieller Reihenfolge an Ort und Stelle aktualisiert werden (dh zuerst niedrigere Indizes).

Beispiel

Lassen Sie uns ein Beispiel ps = [2,1,4,1,3,2] , ps = [2,1,4,1,3,2] :

i = 0:das Element an der Position ps [0] = 2 verweist auf 4ps = [4,1,4,1,3,2]i = 1:das Element an der Position ps [1] = 1 verweist auf 1ps = [4,1,4,1,3,2]i = 2:das Element an der Position ps [2] = 4 verweist auf 3ps = [4,1,3,1,3,2]i = 3:das Element an der Position ps [3] = 1 verweist auf 1ps = [4,1,3,1,3,2]i = 4:das Element an der Position ps [4] = 3 verweist auf 1ps = [4,1,3,1,1,2]i = 5:das Element an der Position ps [5] = 2 verweist auf 3ps = [4,1,3,1,1,3]

Nach einer Iteration des " Zeigerspringens " erhalten wir das Array [4,1,3,1,1,3] .

Herausforderung

Bei einem Array mit Indizes wird das Array ausgegeben, das durch Iterieren des oben beschriebenen Zeigersprungs erhalten wird, bis sich das Array nicht mehr ändert.

Regeln

Ihr Programm / Ihre Funktion wird denselben Typ, eine Liste / einen Vektor / ein Array usw. annehmen und zurückgeben / ausgeben, die / das

  • ist garantiert nicht leer und
  • enthält garantiert nur Einträge 0p<n .

Varianten: Sie können wählen

  • 1-basierte Indizierung verwenden oder
  • Verwenden Sie aktuelle Zeiger,

Sie sollten dies jedoch in Ihrem Beitrag erwähnen.

Testfälle

[0]  [0]
[1,0]  [0,0]
[1,2,3,4,0]  [2,2,2,2,2]
[0,1,1,1,0,3]  [0,1,1,1,0,1]
[4,1,3,0,3,2]  [3,1,3,3,3,3]
[5,1,2,0,4,5,6]  [5,1,2,5,4,5,6]
[9,9,9,2,5,4,4,5,8,1,0,0]  [1,1,1,1,4,4,4,4,8,1,1,1]
ბიმო
quelle
Verwandte: Jump the Array
23.
Dürfen wir die Länge nals zusätzliche Eingabe verwenden?
Kevin Cruijssen
2
@ KevinCruijssen finden Sie in dieser Metadiskussion .
Shaggy
Es ist schade, dass die Einträge nacheinander aktualisiert werden müssen. Wenn sie gleichzeitig aktualisiert werden könnten, hätte Mathematica die 21-stellige Lösung #[[#]]&~FixedPoint~#&.
Greg Martin

Antworten:

6

Haskell, 56 Bytes

foldr(\_->([]#))=<<id
x#a@(b:c)=(x++[(x++a)!!b])#c
x#_=x

Haskell- und In-Place-Updates stimmen nicht überein.

Probieren Sie es online!

nimi
quelle
5

C ++ 14 (gcc) , 61 Bytes

Wie unbenanntes generisches Lambda. Benötigt sequentielle Container wie std::vector.

[](auto&c){auto d=c;do{d=c;for(auto&x:c)x=c[x];}while(d!=c);}

Probieren Sie es online!

Bierpfurz
quelle
5

Schnell , 68 53 Bytes

{a in for _ in a{var i=0;a.forEach{a[i]=a[$0];i+=1}}}

Probieren Sie es online!

-15 dank BMO

Sean
quelle
2
Willkommen bei PPCG! Ich kenne Swift nicht, aber auf codegolf.SE ist die Voreinstellung, getippte Lambda-Funktionen zu akzeptieren, als die ein Abschluß meiner Meinung nach gelten würde. Dies können also 53 Bytes sein (Sie müssen nicht zählen f=). Genieße deinen Aufenthalt hier!
24.
Vielen Dank für die Begrüßung und den Rat, mit dem ich meine Antwort aktualisiert habe.
Sean
Wie wäre es mit mapanstatt forEaches kürzer zu machen?
Jaeyong gesungen
4

JavaScript (ES6), 41 Byte

f=a=>a+''==a.map((x,i)=>a[i]=a[x])?a:f(a)

Probieren Sie es online!

Arnauld
quelle
Gah! Ich habe darauf gewartet, dass diese Herausforderung veröffentlicht wird, damit ich genau die gleiche Lösung veröffentlichen kann: \ Verdammt, deine Ninja-Fähigkeiten! : p
Shaggy
2
@ shaggy 🐱‍👤 (dies soll eine Ninja-Katze sein ... aber es wird wahrscheinlich nicht überall unterstützt)
Arnauld
4

Japt, 15, 13 7 Bytes

Ändert das ursprüngliche Eingabearray.

££hYXgU

Probieren Sie es aus (zusätzliche Bytes werden benötigt, um die geänderte Eingabe in die Konsole zu schreiben)

££hYXgU
£           :Map
 £          :  Map each X at index Y
  hY        :    Replace the element at index Y
    XgU     :    With the element at index X
Zottelig
quelle
4

Java 8, 105 54 Bytes

a->{for(int l=a.length,i=0;i<l*l;)a[i%l]=a[a[i++%l]];}

Ändert das Eingabearray, anstatt ein neues zurückzugeben, um Bytes zu sparen.

lenGth2

Probieren Sie es online aus.

Erläuterung:

a->{                // Method with integer-array parameter and no return-type
  int l=a.length,   //  Length of the input-array
  i=0;i<l*l;)       //  Loop `i` in the range [0, length squared):
    a[i%l]=         //   Set the (`i` modulo-length)'th item in the array to:
      a[            //    The `p`'th value of the input-array,
        a[i++%l]];} //    where `p` is the (`i` modulo-length)'th value of the array
Kevin Cruijssen
quelle
3

Japt , 17 Bytes


®
£hYUgX
eV ?U:ß

Probieren Sie alle Testfälle aus

Das fühlt sich an, als sollte es kürzer sein, aber leider UmgUfunktioniert mein erster Gedanke nicht, weil jeder gauf das Original zugreift, Uanstatt es bei jedem Schritt zu ändern. Die Aufbewahrung verschiedener Komponenten kostet ebenfalls eine Handvoll Bytes.

Erläuterung:

           #Blank line preserves input in U long enough for the next line

®          #Copy U into V to preserve its original value

£hY        #Modify U in-place by replacing each element X with...
   UgX     #The value from the current U at the index X

eV ?U      #If the modified U is identical to the copy V, output it
     :ß    #Otherwise start again with the modified U as the new input
Kamil Drakari
quelle
2

Ruby , 37 34 Bytes

->a{a.size.times{a.map!{|x|a[x]}}}

Probieren Sie es online!

Gibt zurück, indem das Eingangsarray direkt geändert wird.

Kirill L.
quelle
2

R , 60 58 Bytes

-2 Bytes Dank an @digEmAll für das Lesen der Regeln.

function(x,n=sum(x|1)){for(i in rep(1:n,n))x[i]=x[x[i]];x}

Probieren Sie es online!

1-indiziert.

n ist die Länge des Eingabearrays.

rep(1:n,n) repliziert 1:n n mal (zB n=3 => 1,2,3,1,2,3,1,2,3)

Durchlaufen Sie die Array- nZeiten. Der stationäre Zustand wird dann sicher erreicht sein, und zwar bis zum Ende des n-1. Males, denke ich. Der Beweis bleibt dem Leser überlassen.

ngm
quelle
1
Ich denke, Sie können die entfernen +1und einfach die 1-basierte Eingabe nehmen, heißt es im Beitrag: Sie können 1-basierte Indizierung verwenden
digEmAll
-4 durch Umschalten auf scan()für die Eingabe. Ich habe immer das Gefühl, dass meine scan()Lösungen suboptimal sind. Halten Sie also ein Auge auf einen kürzeren Weg, um sie zuzuweisen xund nzusammen: n=length(x<-scan());for(i in rep(1:n,n))x[i]=x[x[i]];x Probieren Sie es online aus!
CriminallyVulgar
2

Sauber , 80 Bytes

import StdEnv

limit o iterate\b=foldl(\l i=updateAt i(l!!(l!!i))l)b(indexList b)

Probieren Sie es online!

Οurous
quelle
2

Clojure , 136 Bytes

(defn j[a](let[f(fn[a](loop[i 0 a a](if(= i(count a))a(recur(inc i)(assoc a i(a(a i)))))))](loop[p nil a a](if(= p a)a(recur a(f a))))))

Probieren Sie es online!

Ethan McCue
quelle
Hallo und willkommen bei PPCG. Wäre es Ihnen möglich, einen Link zu einem Online-Dolmetscher bereitzustellen, über den Sie Ihre Lösung leicht überprüfen können? Außerdem kann loop [nicht werden loop[?
Jonathan Frech
1
Die letzte Änderung sollte die Testfehler beheben. Entschuldigen Sie die Unannehmlichkeiten.
Ethan McCue
1

Perl 5, 35 34 26 Bytes

unter Verwendung der Tatsache, dass die Konvergenz höchstens für die Größenanzahl der Iterationen erreicht wird

$_=$F[$_]for@F x@F;$_="@F"

26 Bytes

$_=$F[$_]for@F;/@F/ or$_="@F",redo

34 Bytes

$_=$F[$_]for@F;$_="@F",redo if!/@F/

35 Bytes

Nahuel Fouilleul
quelle
1

Kohle , 16 Bytes

FθFLθ§≔θκ§θ§θκIθ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Leider arbeiten alle üblichen Mapping-Funktionen nur mit einer Kopie des Arrays, was dazu führt, dass sie die Elemente nur permutieren und nicht springen, sodass der Code alles manuell erledigen muss. Erläuterung:

Fθ

Wiederholen Sie die innere Schleife einmal für jedes Element. Dies stellt nur sicher, dass sich das Ergebnis stabilisiert.

FLθ

Schleife über die Array-Indizes.

§≔θκ§θ§θκ

Rufen Sie das Array-Element am aktuellen Index ab, indizieren Sie es im Array und ersetzen Sie das aktuelle Element durch diesen Wert.

Iθ

Wandeln Sie die Elemente in Strings um und drucken Sie sie implizit in einer eigenen Zeile.

Neil
quelle
1

F #, 74 73 Bytes

fun(c:'a[])->let l=c.Length in(for i in 0..l*l do c.[i%l]<-c.[c.[i%l]]);c

Nichts Besonderes. Verwendet die Modulidee aus anderen Antworten.

LSM07
quelle
1

K, 27 Bytes

{{@[x;y;:;x x y]}/[x;!#x]}/
  • {..}/ Wendet Lambda {..} auf Arg an (bis zur Konvergenz)

  • inneres äußeres Lambda:

    • {..}/[x;y]Wendet Lambda iterativ auf x (bei jeder Iteration aktualisiert) und ein Element von y an (y ist eine Liste von Werten und verwendet bei jeder Iteration ein Element). In diesem Fall ist arg y !#x(bis count x, also die Indizes des Arrays).

    • @[x;y;:;x x y] Array x ändern (bei Index y x [x [y]] zuweisen)

J. Sendra
quelle