Array Escape - sal de ahí

32

Un día te despiertas solo para encontrarte atrapado en una serie. Intenta salir de allí, tomando un índice a la vez, pero parece que hay otras reglas:

La matriz está completamente llena de números naturales.

  • Si te encuentras en un índice n, vas al índice array[n], excepto:
  • Si te encuentras en un índice nque es un número primo, array[n]retrocedes pasos

Ejemplo: comienza en el índice 4, en esta matriz (el índice de inicio es 0):

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

Como el valor del campo en el que se encuentra es 8, usted va al índice 8como primer paso. El campo en el que aterrizas contiene el valor 2. Luego vas al índice 2como tu segundo paso. Como 2es un número primo, retrocede 5 pasos, que es su tercer paso. Como no hay índice -3, escapó con éxito de la matriz en un total de 3 pasos.

Tu tarea es:

Para escribir un programa o función, que acepta una matriz y un índice de inicio como parámetro, y genera la cantidad de pasos para escapar de la matriz. Si no puede escapar de la matriz (por ejemplo, [2,0,2]con start-index 2=> pasa constantemente del índice 2a 0), genera un valor falso. Puede usar indexación basada en uno o indexación basada en cero, pero especifique cuál usa.

Casos de prueba

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

Salida: 1

Entrada: [2, 0, 2], 2

Salida: false

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

Salida: 6

La respuesta más corta gana.

Michael Kunst
fuente
77
Bienvenido a PPCG! Este es un primer desafío decente. :) ¿Podemos usar también la indexación basada en 1? También podría ser bueno tener algunos casos de prueba más. Para los desafíos futuros, también puede considerar usar el sandbox donde puede obtener comentarios de la comunidad antes de que se active un desafío.
Martin Ender
1
Muy relacionado
Peter Taylor
1
@ Martin Ender no está relacionado con la pregunta ... pero a mí, como usuario de dispositivos móviles, me resulta imposible usar el sandbox. ¿Qué debo hacer para recibir comentarios sobre mis preguntas antes de publicarlas?
user6245072
1
@JerryJeremiah ¿por qué no puedes retroceder 3 pasos? aterrizará en el índice 2 si comienza en 5 y retrocede 3 pasos
Michael Kunst
55
@ user902383 va al índice 2, que es primo, por lo que hacemos 2 pasos hacia atrás y vamos al índice 0, que no es primo. El valor en el índice 0 es 2, así que vamos al índice 2, que es primo ... repetir
edc65

Respuestas:

4

Pyth, 31 bytes

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

Los casos de prueba

Utiliza cero para indicar un valor falso, el número de saltos de lo contrario.

Cameron McCluskie
fuente
9

Python, 161 138 bytes

Créditos por 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!

Cómo funciona

El teorema de Wilson se utiliza para la verificación de primos.

Detección de bucle almacenando índices vistos en una matriz ( l) y verificando si el índice actual está dentro l.

Monja permeable
fuente
6

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

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

Devoluciones 0para bucles (detectados cuando n > len(a))

RootTwo
fuente
5

Matlab, 138 bytes

Este es un enfoque sencillo, que utiliza índices basados ​​en 1 porque Matlab usa índices basados ​​en 1 de forma predeterminada. Para contar el número de pasos, usamos un forciclo que cuenta de 1 a infinito (!). En el caso de que no podamos escapar de la matriz, utilizamos un vector vpara realizar un seguimiento de las entradas que ya visitamos. Si visitamos una entrada dos veces, sabemos que estamos atrapados en un ciclo no escapable. Para ver si estamos fuera de una matriz, usamos la try/catchestructura, que también captura excepciones fuera de límites.

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
falla
fuente
5

05AB1E, 32 bytes

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

Explicación

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

Pruébalo en línea

Emigna
fuente
4

JavaScript (ES6), 100

Índice base 0. Nota: esta función modifica la matriz de entrada

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

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

Prueba

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

Gracias a Kevin, 11 bytes muerden el polvo.

usuario902383
fuente
Algunas cosas para jugar golf un poco más: Stack<Integer>i=new Stack<>();se puede cambiar Stack i=new Stack();y return 1==2;se puede cambiar a return 0>1;. Además, es posible que desee mencionar que es Java 7 en lugar de Java en general.
Kevin Cruijssen
@KevinCruijssen No estoy seguro de si es importante mencionar que es Java 7, ya que especialmente ahora esta solución es compatible con la mayoría de las versiones de Java.
user902383
Bueno, en Java 8 puedes usar un lambdas que es más corto: en a,b->{...}lugar de eso Object e(int[]a,int b){...}, es por eso que personalmente menciono Java 7 para que la gente sepa que a propósito no he usado lambdas de Java 8, pero depende de ti.
Kevin Cruijssen
@KevinCruijssen es justo, cuando estoy usando lamda, estoy especificando la versión de Java, pero cuando la solución funciona con Java 7, generalmente también funciona con Java 8, por lo que no tenía sentido agregar la versión. Pero puede que tengas razón, debería especificar la versión mínima.
user902383
4

CJam, 44 bytes

Espera index arrayen la pila.

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

Pruébalo en línea!

Mi primera respuesta de CJam, por eso es tan terrible e imperativo ...

: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

(se considera correcto bloquear después de la salida correcta impresa, que es lo que hace el programa aquí)

Ven
fuente
3

C, 121 bytes

La función facepta la matriz, el índice de inicio (basado en 0) y el número de elementos en la matriz, ya que no hay forma de probar el final de una matriz en C (al menos no sé ninguno).

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

Pruébalo en ideone!

Nota: function p(n) prueba si nes primo o no. El crédito por esto va para @Lynn y su respuesta para ¿Es este número un primo?

Jasmes
fuente
1
@raznagul sin sentido, no puedes determinar la longitud de una matriz de parámetros de entrada. Vea la respuesta 2 sobre la misma pregunta
edc65
@ edc65: Lo siento, debería haber leído más allá de la primera respuesta.
raznagul
@Jasmes: en Code Golf, una función debería poder llamarse varias veces para obtener la misma salida. Su código requiere reinicio cpara volver a llamar a la función.
owacoder
3

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, perdí el bit sobre devolver el número de pasos. La solución llegará pronto.

editar 2: fijo

Yay295
fuente
3

Raqueta, 183156 bytes

Probablemente más bytes ahorrables con más golf, pero eso es todo para mí. :)

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

Módulo completo con conjunto de pruebas con función de limpieza:

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

Ejecútalo como raco test e.rkt

Grandes felicitaciones para @cat por descubrir la prime?función indocumentada .

Winny
fuente
2

Java, 163160 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)es para pruebas principales, f(a,n)es para la función de escape. Uso:

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ón sin golf:

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
fuente
1

Perl 6 , 85 bytes

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

Explicación:

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

Esta es una secuencia perezosa de los índices recorridos de acuerdo con la regla. Si el índice finalmente excede los límites de la matriz de entrada (el!(0 <= * < a) condición), la secuencia es finita; de lo contrario, los índices circulan infinitamente.

Esa secuencia se alimenta a la función anónima interna:

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

Si la secuencia se define en el índice dado por el tamaño de la matriz de entrada, debe haber entrado en un ciclo infinito, por lo que 0se devuelve. De lo contrario, +$_se devuelve el tamaño de la secuencia .

Sean
fuente
1

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

Pruébalo en línea!

Lista basada en 0. Devuelve falso (en blanco) si la lista es inevitable.

Xcali
fuente