Pointer melompat

21

Misalkan kita memiliki array ps dengan panjang n dengan pointer yang menunjuk ke beberapa lokasi dalam array: Proses " pointer jumping " akan mengatur setiap pointer ke lokasi pointer menunjuk ke poin.

Untuk tujuan tantangan ini, penunjuk adalah indeks (berbasis nol) dari elemen array, ini menyiratkan bahwa setiap elemen dalam array akan lebih besar atau sama dengan 0 dan kurang dari n . Dengan menggunakan notasi ini prosesnya dapat dirumuskan sebagai berikut:

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

Ini berarti (untuk tantangan ini) bahwa pointer diperbarui di tempat dalam urutan berurutan (mis. Indeks lebih rendah terlebih dahulu).

Contoh

Mari kita bekerja melalui sebuah contoh, ps = [2,1,4,1,3,2] :

i = 0:the element at position ps[0] = 2 points to 4ps = [4,1,4,1,3,2]i = 1:the element at position ps[1] = 1 points to 1ps = [4,1,4,1,3,2]i = 2:the element at position ps[2] = 4 points to 3ps = [4,1,3,1,3,2]i = 3:the element at position ps[3] = 1 points to 1ps = [4,1,3,1,3,2]i = 4:the element at position ps[4] = 3 points to 1ps = [4,1,3,1,1,2]i = 5:the element at position ps[5] = 2 points to 3ps = [4,1,3,1,1,3]

Jadi setelah satu iterasi " pointer jumping " kita mendapatkan array [4,1,3,1,1,3] .

Tantangan

Diberikan array dengan indeks output array yang diperoleh dengan mengulangi lompatan pointer yang dijelaskan di atas sampai array tidak berubah lagi.

Aturan

Program / fungsi Anda akan mengambil dan mengembalikan / menampilkan jenis yang sama, daftar / vektor / array dll

  • dijamin tidak kosong dan
  • dijamin hanya mengandung entri 0p<n .

Varian: Anda dapat memilih

  • untuk menggunakan pengindeksan berbasis 1 atau
  • gunakan pointer aktual,

namun Anda harus menyebutkan ini dalam kiriman Anda.

Uji kasus

[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]
ბიმო
sumber
Terkait: Lompat array
ბიმო
Apakah kami diizinkan mengambil panjang nsebagai input tambahan?
Kevin Cruijssen
2
@KevinCruijssen, lihat diskusi meta ini .
Shaggy
Sayang sekali entri harus diperbarui berurutan; jika mereka dapat diperbarui secara bersamaan, Mathematica akan memiliki solusi 21 karakter #[[#]]&~FixedPoint~#&.
Greg Martin

Jawaban:

8

JavaScript, 36 byte

Memodifikasi array input asli.

a=>a.map(_=>a.map((x,y)=>a[y]=a[x]))

Cobalah online

Shaggy
sumber
6

Haskell, 56 byte

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

Pembaruan Haskell dan di tempat adalah pertandingan yang buruk.

Cobalah online!

nimi
sumber
5

C ++ 14 (gcc) , 61 byte

Sebagai lambda generik yang tidak disebutkan namanya. Membutuhkan wadah berurutan seperti std::vector.

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

Cobalah online!

Bierpfurz
sumber
5

Swift , 68 53 byte

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

Cobalah online!

Terima kasih kepada BMO

Sean
sumber
2
Selamat datang di PPCG! Saya tidak tahu Swift, tetapi pada codegolf. SE standarnya adalah untuk menerima fungsi lambda yang diketik yang saya kira penutupan akan dihitung sebagai. Jadi ini bisa menjadi 53 byte (Anda tidak perlu menghitung f=). Nikmati masa tinggal Anda di sini!
ბიმო
Terima kasih atas sambutan dan saran yang saya gunakan untuk memperbarui jawaban saya.
Sean
Bagaimana kalau menggunakan mapbukannya forEachmembuatnya lebih pendek?
Jaeyong dinyanyikan
4

JavaScript (ES6), 41 byte

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

Cobalah online!

Arnauld
sumber
Gah! Saya menunggu tantangan ini diposting sehingga saya bisa memposting solusi yang sama persis: \ Sialan keterampilan ninja Anda! : p
Shaggy
2
@shaggy 🐱‍👤 (ini seharusnya Ninja Kucing ... tapi mungkin tidak didukung di mana-mana)
Arnauld
4

05AB1E (warisan) , 8 byte

ΔDvDyèNǝ

Cobalah online!

Penjelasan

Δ          # apply until the top of the stack stops changing
 D         # duplicate current list
  v        # for each (element y, index N) in the list
   Dyè     # get the element at index y
      Nǝ   # and insert it at index N

05AB1E , 14 byte

[D©vDyèNǝ}D®Q#

Cobalah online!

Emigna
sumber
4

Japt, 15 13 7 byte

Memodifikasi array input asli.

££hYXgU

Cobalah (byte tambahan adalah untuk menulis input yang dimodifikasi ke konsol)

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

Java 8, 105 54 byte

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

Memodifikasi array input alih-alih mengembalikan yang baru untuk menghemat byte.

length2

Cobalah online.

Penjelasan:

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
sumber
3

Japt , 17 byte


®
£hYUgX
eV ?U:ß

Coba semua uji kasus

Ini terasa seperti itu harus lebih pendek, tetapi sayangnya pemikiran awal saya UmgUtidak berfungsi karena masing-masing gmengakses yang asliU daripada mengubahnya pada setiap langkah. Mempertahankan komponen-komponen berbeda dengan tepat membutuhkan biaya beberapa byte juga.

Penjelasan:

           #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
sumber
2

Ruby , 37 34 byte

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

Cobalah online!

Kembali dengan memodifikasi array input di tempat.

Kirill L.
sumber
2

Merah , 63 byte

func[b][loop(l: length? b)* l[repeat i l[b/:i: b/(1 + b/:i)]]b]

Cobalah online!

Memodifikasi array di tempat

Galen Ivanov
sumber
2

R , 60 58 byte

-2 byte terima kasih kepada @digEmAll untuk membaca aturannya.

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

Cobalah online!

1-diindeks.

n adalah panjang dari array input.

rep(1:n,n)ulangan 1:n nkali (misalnya n=3 => 1,2,3,1,2,3,1,2,3)

Loop melalui waktu array n. Keadaan mantap akan tercapai pada saat itu pasti, bahkan pada akhir waktu n-1 sampai saya pikir. Buktinya diserahkan kepada pembaca.

ngm
sumber
1
Saya pikir Anda dapat menghapus +1dan hanya mengambil input berbasis 1, pos menyatakan: Anda dapat memilih untuk menggunakan pengindeksan berbasis 1
digEmAll
-4 dengan beralih ke scan()untuk input. Saya selalu merasa scan()solusi saya tidak optimal, jadi awasi cara yang lebih pendek untuk menetapkan xdan nbersama - sama: n=length(x<-scan());for(i in rep(1:n,n))x[i]=x[x[i]];x Cobalah secara online!
Penjahat
2

Common Lisp, 59 58 byte

(lambda(a)(dolist(j a)(map-into a(lambda(x)(elt a x))a))a)

Cobalah online!

Renzo
sumber
2

Bersih , 80 byte

import StdEnv

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

Cobalah online!

Suram
sumber
2

Clojure , 136 byte

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

Cobalah online!

Ethan McCue
sumber
Halo dan selamat datang di PPCG. Apakah mungkin bagi Anda untuk memberikan tautan ke juru bahasa online sehingga orang dapat dengan mudah memverifikasi solusi Anda? Selanjutnya, loop [tidak bisa menjadi loop[?
Jonathan Frech
1
Hasil edit terbaru harus memperbaiki kegagalan pengujian. Maaf atas ketidaknyamanan semua orang.
Ethan McCue
1

Perl 5, 35 34 26 byte

menggunakan fakta bahwa konvergensi mencapai paling banyak untuk jumlah ukuran iterasi

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

26 byte

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

34 byte

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

35 byte

Nahuel Fouilleul
sumber
1

Clojure , 88 byte

#(reduce(fn[x i](assoc x i(get x(get x i))))%(flatten(repeat(count %)(range(count %)))))

Cobalah online!

Kirill L.
sumber
1

Arang , 16 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Sayangnya semua fungsi pemetaan yang biasa hanya beroperasi pada salinan array dengan hasilnya adalah mereka hanya mengijinkan elemen daripada melompat, sehingga kode harus melakukan semuanya secara manual. Penjelasan:

Fθ

Ulangi loop dalam sekali untuk setiap elemen. Ini hanya memastikan bahwa hasilnya stabil.

FLθ

Lewati indeks array.

§≔θκ§θ§θκ

Dapatkan elemen array di indeks saat ini, gunakan itu untuk mengindeks ke dalam array, dan ganti elemen saat ini dengan nilai itu.

Iθ

Keluarkan elemen ke string dan cetak masing-masing secara tersirat pada baris mereka sendiri.

Neil
sumber
1

F #, 74 73 byte

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

Tidak ada yang spesial. Menggunakan ide modulus yang terlihat pada jawaban lain.

LSM07
sumber
1

K, 27 Bytes

{{@[x;y;:;x x y]}/[x;!#x]}/
  • {..}/ berlaku lambda {..} di atas arg (hingga konvergensi)

  • di dalam lambda luar:

    • {..}/[x;y]berlaku lambda secara berulang lebih dari x (diperbarui pada setiap iterasi) dan item y (y adalah daftar nilai, dan menggunakan item pada setiap iterasi). Dalam hal ini arg y adalah!#x (til hitung x, yaitu indeks array)

    • @[x;y;:;x x y] ubah array x (pada indeks y tetapkan x [x [y]])

J. Sendra
sumber