Array Escape - keluar dari sana

32

Suatu hari Anda bangun hanya untuk menemukan diri Anda terjebak dalam array. Anda mencoba keluar begitu saja, mengambil satu indeks pada saat itu, tetapi tampaknya ada aturan lain:

Array diisi dengan bilangan asli.

  • Jika Anda menemukan diri Anda pada indeks n, Anda pergi ke indeks array[n], kecuali:
  • Jika Anda menemukan diri Anda pada indeks nyang merupakan bilangan prima, Anda mengambil array[n]langkah mundur

Contoh: Anda memulai pada indeks 4, dalam array ini (indeks awal adalah 0):

array = [1,4,5,6,8,10,14,15,2,2,4,5,7];
-----------------^ you are here

Karena nilai bidang tempat Anda berada 8, Anda masuk ke indeks 8sebagai langkah pertama. Bidang yang Anda gunakan berisi nilai 2. Anda kemudian pergi untuk mengindeks 2sebagai langkah kedua Anda. Seperti halnya 2bilangan prima, Anda mengambil 5 langkah mundur, yang merupakan langkah ketiga Anda. Karena tidak ada indeks -3, Anda berhasil keluar dari array dalam total 3 langkah.

Tugas Anda adalah:

Untuk menulis program atau fungsi, yang menerima array dan indeks awal sebagai parameter, dan menampilkan jumlah langkah untuk keluar dari array. Jika Anda tidak dapat keluar dari array (mis. [2,0,2]Dengan start-index 2=> Anda terus berpindah dari indeks 2ke 0), output nilai yang salah. Anda dapat menggunakan pengindeksan satu berbasis atau pengindeksan berbasis nol, tetapi harap tentukan yang Anda gunakan.

Uji kasus

Memasukkan: [2,5,6,8,1,2,3], 3

Keluaran: 1

Memasukkan: [2, 0, 2], 2

Keluaran: false

Input: [14,1,2,5,1,3,51,5,12,3,4,41,15,4,12,243,51,2,14,51,12,11], 5;

Keluaran: 6

Jawaban terpendek menang.

Michael Kunst
sumber
7
Selamat datang di PPCG! Ini adalah tantangan pertama yang layak. :) Bisakah kita menggunakan pengindeksan berbasis 1 juga? Juga mungkin lebih baik untuk memiliki beberapa test case lagi. Untuk tantangan di masa depan, Anda juga dapat mempertimbangkan untuk menggunakan kotak pasir di mana Anda bisa mendapatkan umpan balik dari komunitas sebelum tantangan ditayangkan.
Martin Ender
1
Sangat terkait erat
Peter Taylor
1
@ Martin Ender itu tidak terkait dengan pertanyaan ... tapi saya sebagai pengguna seluler merasa tidak mungkin menggunakan kotak pasir. Apa yang harus saya lakukan untuk mendapatkan umpan balik tentang pertanyaan saya sebelum benar-benar mempostingnya?
user6245072
1
@ Jeregeremia mengapa Anda tidak bisa mengambil 3 langkah kembali? Anda akan mendarat di indeks 2 jika Anda mulai dari 5 dan mengambil 3 langkah kembali
Michael Kunst
5
@ user902383 akan mengindeks 2, yang merupakan prime, jadi kami melakukan 2 langkah mundur dan pergi ke indeks 0, yang tidak prima. Nilai pada indeks 0 adalah 2, jadi kami pergi ke indeks 2, yang merupakan prime ... repeat
edc65

Jawaban:

4

Pyth, 31 Bytes

KlQ%tl-.u?}NUK?P_N-N@QN@QNKQEKK

Kasus uji

Ini menggunakan nol untuk menunjukkan nilai palsu, jumlah hop sebaliknya.

Cameron McCluskie
sumber
9

Python, 161 138 byte

Kredit untuk faktorial.

g=lambda x:0**x or x*g(x-1)
f=lambda a,i,n=0,l=[]:(i<0)+(i>=len(a))and n or(0 if i in l else f(a,[a[i],i-a[i]][i and-g(i-1)%i],n+1,l+[i]))

Ide itu!

Bagaimana itu bekerja

Teorema Wilson digunakan untuk pemeriksaan prima.

Deteksi loop dengan menyimpan indeks yang terlihat ke array ( l) dan memeriksa apakah indeks saat ini di l.

Biarawati Bocor
sumber
6

Python, 107 byte

import sympy
f=lambda a,i,n=0:0if n>len(a)else f(a,[a[i],i-a[i]][sympy.isprime(i)],n+1)if 0<=i<len(a)else n

Penggunaan: f(list, start)mis:f([2,5,6,8,1,2,3], 3)

Pengembalian 0loop (terdeteksi saat n > len(a))

RootTwo
sumber
5

Matlab, 138 byte

Ini pendekatan lurus ke depan, menggunakan indeks berbasis 1 karena Matlab menggunakan indeks berbasis 1 secara default. Untuk menghitung jumlah langkah, kami menggunakan forpenghitungan loop dari 1 hingga tak terbatas (!). Jika kita tidak bisa keluar dari array, kita menggunakan vektor vuntuk melacak entri mana yang sudah kita kunjungi. Jika kami mengunjungi entri dua kali, kami tahu kami terjebak dalam siklus yang tidak bisa dilewati. Untuk melihat apakah kita berada di luar array, kita menggunakan try/catchstruktur, yang juga menangkap pengecualian batas.

function r=f(a,i);v=a*0;v(i)=1;for k=1:Inf;if isprime(i);i=i-a(i);else;i=a(i);end;try;if v(i);r=0;break;end;v(i)=1;catch;r=k;break;end;end
cacat
sumber
5

05AB1E, 32 byte

ï[U¯Xåi0,q}²gL<Xå_#X²XèXDˆpi-]¯g

Penjelasan

ï                                 # explicitly convert input to int
 [                            ]   # infinite loop
  U                               # store current index in X
   ¯Xåi0,q}                       # if we've already been at this index, print 0 and exit
           ²gL<Xå_#               # if we've escaped, break out of infinite loop
                   X²XèXDˆpi-     # else calculate new index
                               ¯g # print nr of indices traversed

Cobalah online

Emigna
sumber
4

JavaScript (ES6), 100

Basis indeks 0. Catatan: fungsi ini mengubah array input

(a,p)=>eval("for(s=0;1/(q=a[p]);++s,p=p>1&&p%i||p==2?p-q:q)for(a[p]=NaN,i=1;p%++i&&i*i<p;);q==q&&s")

Kurang golf

(a,p)=>
{
  for(s = 0; 
      1/ (q = a[p]); 
      ++s)
  {
    a[p] = NaN; // mark visited position with NaN to detect loops
    for(i = 1; p % ++i && i*i < p;); // prime check
    p = p > 1 && p % i || p == 2 ? p-q : q;
  }
  return q==q && s // return false if landed on NaN as NaN != NaN
}

Uji

F=
(a,p)=>eval("for(s=0;1/(q=a[p]);++s,p=p>1&&p%i||p==2?p-q:q)for(a[p]=NaN,i=1;p%++i&&i*i<p;);q==q&&s")

;[
 [[2,5,6,8,1,2,3], 3, 1]
,[[2, 0, 2], 2, false]
,[[14,1,2,5,1,3,51,5,12,3,4,41,15,4,12,243,51,2,14,51,12,11], 5, 6]
].forEach(t=>{
  var [a,b,k]=t, i=a+' '+b,r=F(a,b)
  console.log(r==k?'OK':'KO',i+' -> '+r)
  
})  

edc65
sumber
4

JAVA, 229 218 Bytes

Object e(int[]a,int b){Stack i=new Stack();int s=0;for(;!(a.length<b|b<0);s++){if(i.contains(b))return 1>2;i.add(b);b=p(b)>0?b-a[b]:a[b];}return s;}int p(int i){for(int j=2;j<i/2;j++)if(i%j<1)return 0;return i<2?0:1;}

Berkat Kevin, 11 byte menggigit debu.

pengguna902383
sumber
Beberapa hal untuk golf itu lagi: Stack<Integer>i=new Stack<>();dapat diubah ke Stack i=new Stack();dan return 1==2;dapat diubah ke return 0>1;. Juga, Anda mungkin ingin menyebutkan itu Java 7 bukan Java secara umum.
Kevin Cruijssen
@KevinCruijssen Saya tidak yakin apakah maksudnya menyebutkan bahwa itu adalah java 7, karena terutama sekarang solusi ini kompatibel dengan sebagian besar versi java.
user902383
Nah, di Java 8 Anda bisa menggunakan lambdas yang lebih pendek: a,b->{...}alih-alih Object e(int[]a,int b){...}, itulah sebabnya saya pribadi menyebutkan Java 7 untuk memberi tahu orang bahwa saya sengaja tidak menggunakan lambda Java 8, tetapi terserah Anda.
Kevin Cruijssen
@KevinCruijssen cukup adil, ketika saya menggunakan lamda, saya menentukan versi java, tetapi ketika solusi bekerja dengan java 7, biasanya bekerja dengan java 8 juga, jadi tidak ada gunanya menambahkan versi. Tapi Anda mungkin benar, saya harus menentukan versi minimum.
user902383
4

CJam, 44 byte

Harapkan index arraydi tumpukan.

:G\{_G,,&{G=_L#)0{_L+:L;_mp3T?-F}?}L,?}:F~o@

Cobalah online!

Jawaban CJam pertama saya, maka mengapa itu begitu mengerikan dan sangat penting ...

:G\{_G,,&{G=_L#)0{_L+:L;_mp3T?-F}?}L,?}:F~o@
:G                                              Store the array as G
  \                                             Put the index first
   {                                  }:F~      The recursive F function
     G,,                                        Generate a 0..length(G) sequence
    _   &                            ?          Check that the index is contained
         {                        }             If so, then...
          G=                                    Get the value at the index
            _L#)                 ?              If the value is in L (`-1)` gives `0` which is falsy)
                0                               Return 0 (infinite loop)
                 {              }               Otherwise...
                  _L+:L;                        Store the value we're accessing in L (infinite loop check)
                        _mp3T?-                 Remove 3 if the number is prime
                               F                Then recursively call F
                                   L,           We escaped! Return the size of "L" (number of steps)
                                          o     Print the top value of the stack
                                           @    Tries to swap 3 elements, which will error out

(dianggap oke untuk macet setelah hasil yang benar seperti yang dicetak, yang dilakukan oleh program di sini)

Yang Mulia
sumber
3

C, 121 byte

Fungsi fmenerima array, indeks awal (berbasis-0) dan jumlah elemen dalam array, karena tidak ada cara bagaimana menguji akhir array di C (setidaknya saya tidak tahu).

p(n,i,z){return--i?p(n,i,z*i*i%n):z%n;}c;f(a,i,n)int*a;{return i<0||i/n?c:c++>n?0:i&&p(i,i,1)?f(a,i-a[i],n):f(a,a[i],n);}

Cobalah di ideone!

Catatan: function p(n) tes apakah nprima atau tidak. Penghargaan untuk ini diberikan ke @Lynn dan jawabannya untuk Apakah nomor ini utama?

Jasmes
sumber
1
@raznagul omong kosong, Anda tidak dapat menentukan panjang array parameter input. Lihat jawaban 2 pada pertanyaan yang sama
edc65
@ edc65: Maaf, saya seharusnya membaca di luar jawaban pertama.
raznagul
@ Jasmes - Dalam golf kode, suatu fungsi harus dapat dipanggil beberapa kali untuk mendapatkan hasil yang sama. Kode Anda memerlukan cpengaturan ulang untuk memanggil fungsi lagi.
owacoder
3

JavaScript, 121 132 byte

p=n=>t=i=>n%i&&n>i?t(i+1):(0<n&&n<=i?1:0),c=-1,a=>r=s=>(++c,0<=s&&s<a.length?(p(s)(2)?r(s-a[s]):0||([a[s],s]=[0,a[s]])[1]?r(s):0):c)

f=(p=n=>t=i=>n%i&&n>i?t(i+1):(0<n&&n<=i?1:0),c=-1,a=>r=s=>(++c,0<=s&&s<a.length?(p(s)(2)?r(s-a[s]):0||([a[s],s]=[0,a[s]])[1]?r(s):0):c));

let test_data = [[[1,4,5,6,8,10,14,15,2,2,4,5,7],4],
                 [[2,5,6,8,1,2,3],3],
                 [[2,0,2],2],
                 [[14,1,2,5,1,3,51,5,12,3,4,41,15,4,12,243,51,2,14,51,12,11],5]];
for (test of test_data) {
    c = -1;
    console.log(f(test[0])(test[1]));
}

edit 1: oops, melewatkan sedikit tentang pengembalian jumlah langkah. memperbaiki datang segera.

sunting 2: diperbaiki

Yay295
sumber
3

Racket, 183 156 byte

Mungkin lebih banyak byte yang bisa dinikmati dengan bermain golf lebih lanjut, tapi hanya itu untuk saya. :)

(require math)(define(e l i[v'()][g length])(cond[(memq i v)#f][(not(< -1 i(g l)))(g v)][else(e l((λ(a)(if(prime? i)(- i a)a))(list-ref l i))(cons i v))]))

Modul lengkap dengan test suite dengan fungsi pembersih:

#lang racket

(require math)

(define (e l i [v'()] [g length])
  (cond
    [(memq i v) #f]
    [(not (< -1 i (g l))) (g v)]
    [else (e l
             ((λ (a) (if (prime? i)
                         (- i a)
                         a))
              (list-ref l i))
             (cons i v))]))

(module+ test
  (require rackunit)
  (define escape-tests
    '((((2 5 6 8 1 2 3) 3) . 1)
      (((2 0 2) 2) . #f)
      (((14 1 2 5 1 3 51 5 12 3 4 41 15 4 12 243 51 2 14 51 12 11) 5) . 6)))
  (for ([t escape-tests])
    (check-equal? (apply e (car t)) (cdr t) (~a t))))

Jalankan seperti raco test e.rkt

Pujian besar untuk @cat menemukan prime?fungsi tidak berdokumen .

Winny
sumber
2

Java, 163 160 byte

boolean p(int n){for(int i=2;i<n;)if(n%i++==0)return 0>1;return 1>0;}
int f(int[]a,int n){return n<0||n>=a.length?1:p(n)?n<a[n]?1:1+f(a,a[n-a[n]]):1+f(a,a[n]);}

p(n)adalah untuk pengujian utama, f(a,n)adalah untuk fungsi pelarian. Pemakaian:

public static void main(String[] args) {
    int[] array = {14,1,2,5,1,3,51,5,12,3,4,41,15,4,12,243,51,2,14,51,12,11};
    System.out.println(f(array, 5));
}

Versi tidak disatukan:

static boolean isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

static int escape(int[] array, int n) {
    if (n < 0 || n >= array.length) {
        return 1;
    } else if (isPrime(n)) {
        if (n < array[n]) {
            return 1;
        } else {
            return 1 + escape(array, array[n - array[n]]);
        }
    } else {
        return 1 + escape(array, array[n]);
    }
}
Justin
sumber
1

Perl 6 , 85 byte

->\n,\a{{.[+a].defined??0!!+$_}(lazy n,{.is-prime??$_- a[$_]!!a[$_]}...^!(0 <=* <a))}

Penjelasan:

lazy n, { .is-prime ?? $_ - a[$_] !! a[$_] } ...^ !(0 <= * < a)

Ini adalah urutan malas dari indeks yang dilalui menurut aturan. Jika indeks akhirnya melebihi batas array input ( !(0 <= * < a)kondisi), urutannya terbatas; jika tidak, siklus indeks tidak terbatas.

Urutan itu diumpankan ke fungsi anonim internal:

{ .[+a].defined ?? 0 !! +$_ }

Jika urutan didefinisikan pada indeks yang diberikan oleh ukuran array input, itu harus telah memasuki siklus tak terbatas, sehingga 0dikembalikan. Jika tidak, ukuran urutan +$_dikembalikan.

Sean
sumber
1

Perl 5 , 107 + 1 ( -a) = 108 byte

for($i=<>;!$k{$i}++&&$i>=0&&$i<@F;$s++){$f=0|sqrt$i||2;1while$i%$f--;$i=$f?$F[$i]:$i-$F[$i]}say$k{$i}<2&&$s

Cobalah online!

Daftar berbasis 0. Mengembalikan false (kosong) jika daftar tidak dapat dihilangkan.

Xcali
sumber