32
\$\begingroup\$

One day you awake only to find yourself caught in an array. You try to just walk out of there, taking one index at the time, but it seems there are other rules:

The array is completely filled with natural numbers.

  • If you find yourself on an index n, you go to the index array[n], except:
  • If you find yourself on an index n which is a prime number, you take array[n] steps back

Example: You start on index 4, in this array (start index is 0):

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

As the value of the field you are on is 8, you go to the index 8 as the first step. The field you land on contains the value 2. You then go to index 2 as your second step. As2is a prime number, you take 5 steps back, which is your third step. As there is no index -3, you successfully escaped the array in a total of 3 steps.

Your task is:

To write a program or function, which accepts an array and a start index as parameter, and outputs the amount of steps to escape the array. If you can't escape the array (e.g. [2,0,2] with start-index 2 => you constantly go from index 2 to 0), output a falsy value. You may use one-based indexing or zero-based indexing, but please specify which you use.

Test cases

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

Output: 1

Input: [2, 0, 2], 2

Output: 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;

Output: 6

The shortest answer wins.

\$\endgroup\$
  • 7
    \$\begingroup\$ Welcome to PPCG! This is a decent first challenge. :) Can we use 1-based indexing as well? Also it might be good to have a few more test cases. For future challenges you can also consider using the sandbox where you can get feedback from the community before a challenge goes live. \$\endgroup\$ – Martin Ender Jul 25 '16 at 11:18
  • 1
    \$\begingroup\$ Very closely related \$\endgroup\$ – Peter Taylor Jul 25 '16 at 13:44
  • 1
    \$\begingroup\$ @Martin Ender it's not related to the question... but me as a mobile user find it impossible to use the sandbox. What should I do to get a feedback on my questions before actually posting them? \$\endgroup\$ – user6245072 Jul 25 '16 at 18:52
  • 1
    \$\begingroup\$ @JerryJeremiah why can't you take 3 steps back? you'll land on index 2 if you start at 5 and take 3 steps back \$\endgroup\$ – Michael Kunst Jul 26 '16 at 6:08
  • 5
    \$\begingroup\$ @user902383 going to index 2, which is prime, so we do 2 steps back and go to index 0, which is not prime. The value at index 0 is 2, so we go to index 2, which is prime ... repeat \$\endgroup\$ – edc65 Jul 26 '16 at 9:27

14 Answers 14

4
\$\begingroup\$

Pyth, 31 Bytes

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

The test cases

It uses zero to indicate a false value, the number of hops otherwise.

\$\endgroup\$
9
\$\begingroup\$

Python, 161 138 bytes

Credits for factorial.

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

Ideone it!

How it works

Wilson's theorem is used for prime checking.

Loop detection by storing seen indices to an array (l) and checking whether current index is in l.

\$\endgroup\$
6
\$\begingroup\$

Python, 107 bytes

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

Usage: f(list, start) ex: f([2,5,6,8,1,2,3], 3)

Returns 0 for loops (detected when n > len(a))

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

Matlab, 138 bytes

This a straighforward approach, using 1-based indices because Matlab uses 1-based indices by default. To count the number of steps we use a for loop counting from 1 to infinity(!). For the case were we cannot escape the array, we use a vector v to keep track of which entries we already visited. If we visit an entry twice, we know we are stuck in an unescapeable cycle. To see check whether we are outside of an array, we use the try/catch structure, which also catches out of bounds exceptions.

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

05AB1E, 32 bytes

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

Explanation

ï                                 # 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

Try it online

\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 100

Index base 0. Note: this function modifies the input array

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

Less golfed

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

Test

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

\$\endgroup\$
4
\$\begingroup\$

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

Thanks to Kevin, 11 bytes bites the dust.

\$\endgroup\$
  • \$\begingroup\$ A few things to golf it down some more: Stack<Integer>i=new Stack<>(); can be changed to Stack i=new Stack(); and return 1==2; can be changed to return 0>1;. Also, you might want to mention it's Java 7 instead of Java in general. \$\endgroup\$ – Kevin Cruijssen Jul 27 '16 at 11:40
  • \$\begingroup\$ @KevinCruijssen I'm not sure is it point to mention that it is java 7, as especially now this solution is compatible with most java versions. \$\endgroup\$ – user902383 Jul 28 '16 at 13:21
  • \$\begingroup\$ Well, in Java 8 you can use a lambdas which is shorter: a,b->{...} instead of Object e(int[]a,int b){...}, which is why I personally mention Java 7 to let people know I purposely haven't used Java 8 lambdas, but it's up to you. \$\endgroup\$ – Kevin Cruijssen Jul 28 '16 at 14:25
  • \$\begingroup\$ @KevinCruijssen fair enough, when I'm using lamda, I'm specifying java version, but when solution works with java 7, it's usually works with java 8 as well, so it was pointless to add version. But you might be right, i should specify minimum version. \$\endgroup\$ – user902383 Jul 28 '16 at 14:39
4
\$\begingroup\$

CJam, 44 bytes

Expects index array on the stack.

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

Try it online!

My first CJam answer, hence why it's so terrible and imperative...

: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

(it is considered okay to crash after the correct output as printed, which is what the program here does)

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

C, 121 bytes

Function f accepts array, starting index (0-based) and number of elements in the array, since there is no way how to test the end of an array in C (at least I don't know any).

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

Try it on ideone!

Note: function p(n) tests if n is prime or not. Credit for this goes to @Lynn and his answer for Is this number a prime?

\$\endgroup\$
  • 1
    \$\begingroup\$ @raznagul nonsense, you can't determine the length of an input parameter array. See answer 2 on the same question \$\endgroup\$ – edc65 Jul 26 '16 at 9:58
  • \$\begingroup\$ @edc65: Sorry, I should have read beyond the first answer. \$\endgroup\$ – raznagul Jul 26 '16 at 10:01
  • \$\begingroup\$ @Jasmes - In code golf, a function should be able to be called multiple times to get the same output. Your code requires resetting c to call the function again. \$\endgroup\$ – owacoder Jul 26 '16 at 12:09
3
\$\begingroup\$

JavaScript, 121 132 bytes

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, missed the bit about returning number of steps. fix coming soonish.

edit 2: fixed

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

Racket, 183 156 bytes

Probably more bytes savable with further golfing, but that's it for me. :)

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

Complete module with test suite with cleaner function:

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

Run it like raco test e.rkt

Major kudos for @cat discovering the undocumented prime? function.

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

Java, 163 160 bytes

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) is for prime testing, f(a,n) is for the escape function. Usage:

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

Ungolfed version:

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]);
    }
}
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 85 bytes

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

Explanation:

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

This is a lazy sequence of the indices traversed according to the rule. If the index eventually exceeds the input array bounds (the !(0 <= * < a) condition), the sequence is finite; otherwise, the indices cycle infinitely.

That sequence is fed to the internal anonymous function:

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

If the sequence is defined at the index given by the size of the input array, it must have entered an infinite cycle, so 0 is returned. Otherwise, the size of the sequence +$_ is returned.

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

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

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

Try it online!

0-based list. Returns false (blank) if the list is unescapable.

\$\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.