Introducción
Supongamos que tiene una regla con números del 0 al r-1 . Coloca una hormiga entre dos de los números, y comienza a gatear erráticamente en la regla. La regla es tan estrecha que la hormiga no puede caminar de una posición a otra sin caminar sobre todos los números intermedios. A medida que la hormiga camina sobre un número por primera vez, lo registras, y esto te da una permutación de los números r . Decimos que una permutación es inquieta si puede ser generada por una hormiga de esta manera. Alternativamente, una permutación p es inquieta si cada entrada p [i] excepto la primera está dentro de la distancia 1 de alguna entrada anterior.
Ejemplos
La permutación de longitud 6
4, 3, 5, 2, 1, 0
es inquietante, porque 3 está dentro de la distancia 1 de 4 , 5 está dentro de la distancia 1 de 4 , 2 está dentro de la distancia 1 de 3 , 1 está dentro de la distancia 1 de 2 y 0 está dentro de la distancia 1 de 1 . La permutación
3, 2, 5, 4, 1, 0
no está inquieto, porque 5 no está dentro de la distancia 1 de 3 o 2 ; la hormiga tendría que pasar por 4 para llegar a 5 .
La tarea
Dada una permutación de los números de 0 a r-1 para aproximadamente 1 ≤ r ≤ 100 en cualquier formato razonable, generar un valor verdadero si la permutación es inquietante, y un valor falso si no.
Casos de prueba
[0] -> True
[0, 1] -> True
[1, 0] -> True
[0, 1, 2] -> True
[0, 2, 1] -> False
[2, 1, 3, 0] -> True
[3, 1, 0, 2] -> False
[1, 2, 0, 3] -> True
[2, 3, 1, 4, 0] -> True
[2, 3, 0, 4, 1] -> False
[0, 5, 1, 3, 2, 4] -> False
[6, 5, 4, 7, 3, 8, 9, 2, 1, 0] -> True
[4, 3, 5, 6, 7, 2, 9, 1, 0, 8] -> False
[5, 2, 7, 9, 6, 8, 0, 4, 1, 3] -> False
[20, 13, 7, 0, 14, 16, 10, 24, 21, 1, 8, 23, 17, 18, 11, 2, 6, 22, 4, 5, 9, 12, 3, 15, 19] -> False
[34, 36, 99, 94, 77, 93, 31, 90, 21, 88, 30, 66, 92, 83, 42, 5, 86, 11, 15, 78, 40, 48, 22, 29, 95, 64, 97, 43, 14, 33, 69, 49, 50, 35, 74, 46, 26, 51, 75, 87, 23, 85, 41, 98, 82, 79, 59, 56, 37, 96, 45, 17, 32, 91, 62, 20, 4, 9, 2, 18, 27, 60, 63, 25, 61, 76, 1, 55, 16, 8, 6, 38, 54, 47, 73, 67, 53, 57, 7, 72, 84, 39, 52, 58, 0, 89, 12, 68, 70, 24, 80, 3, 44, 13, 28, 10, 71, 65, 81, 19] -> False
[47, 48, 46, 45, 44, 49, 43, 42, 41, 50, 40, 39, 38, 51, 37, 36, 52, 35, 34, 33, 32, 53, 54, 31, 30, 55, 56, 29, 28, 57, 58, 59, 60, 27, 26, 61, 25, 62, 63, 64, 65, 66, 67, 24, 23, 22, 21, 68, 69, 20, 19, 18, 17, 70, 71, 16, 15, 72, 73, 74, 75, 76, 14, 13, 12, 77, 11, 10, 9, 8, 78, 7, 79, 80, 6, 81, 5, 4, 3, 82, 2, 83, 84, 1, 85, 86, 87, 0, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99] -> True
Dato curioso: para r ≥ 1 , hay exactamente 2 permutaciones ansiosas r-1 de longitud r .
Respuestas:
Pyth, 7 bytes
Pruébalo en línea. (Solo se incluyen casos de prueba pequeños debido al tiempo de ejecución exponencial). Salidas 2 para Truthy, 0 para Falsey.
En otras palabras,
donde
subseq
muestra si los elementos de la primera lista aparecen en orden en la segunda lista, no necesariamente adyacentes. Estosubseq
se realiza en Pyth tomando todos los subconjuntos de la segunda lista, que mantienen el orden de los elementos, y contando el número de ocurrencias de la primera lista. Esto lleva tiempo exponencial.¿Por qué funciona esto? Para que una permutación sea inquieta, pasar de 0 a n-1 debe consistir en ir solo a la izquierda y luego a la derecha. Esto se debe a que los elementos mayores que el primer elemento deben aumentar de izquierda a derecha, y los menores que deben disminuir de izquierda a derecha.
Si duplicamos la lista colocando una copia invertida a su izquierda, este recorrido ahora solo va a la derecha.
Por el contrario, cualquier derecha de esta lista espejo corresponde a un recorrido de izquierda a derecha de la lista original. Esta derecha solo es una subsecuencia ordenada de 0 a n-1. En una lista inquieta, esta subsecuencia ordenada es única, excepto por una elección arbitraria entre las dos copias adyacentes del primer elemento original.
fuente
Haskell, 46 bytes
Comprueba si la diferencia de vectores de los máximos y mínimos de ejecución es [0,1,2,3 ...].
Zgarb guardó 2 bytes con
(%)=scanl1
.fuente
(#)=scanl1
?JavaScript (ES6), 45
Pensé que era demasiado simple como explicación, pero hay un truco, y por si acaso, aquí está mi primera versión, pre-golf
Nota: en el código de golf
a
se utiliza en lugar dek
, ya que no necesito ninguna referencia a la matriz original dentro de laevery
llamada. Así que evito contaminar el espacio de nombres global reutilizando el parámetroPrueba
fuente
f=([q,...a],x=[])=>x&&(x[q]=!(x+x)|x[q+1]|x[q-1])&&(a+a?f(a,x):1)
Python 2, 49 bytes
Comprueba si cada prefijo de la lista contiene todos los números entre su mínimo y máximo inclusive. Lo hace comprobando si la diferencia entre el máximo y el mínimo es menor que su longitud.
54 bytes:
Comprueba si el último elemento es uno menos que el mínimo de los otros elementos, o uno más que su máximo. Luego, elimina el último elemento y vuelve a aparecer. En una lista de un solo elemento, genera True.
Esto también se puede verificar a través de una comprensión de la lista divertida pero más larga.
Me gustaría usar la desigualdad
min(l)-2<l.pop()<max(l)+2
, pero laspop
necesidades deben suceder primero. Usar un programa para generar un código de error probablemente sea más corto.fuente
Mathematica, 42 bytes
Utiliza la coincidencia de patrones para intentar encontrar un prefijo
a
cuya diferencia máxima con respecto al siguiente elementob
sea mayor que1
(y negar el resultado deMatchQ
).fuente
Perl,
393835 bytesIncluye +1 para
-p
Dar secuencia en STDIN:
antsy.pl
:fuente
MATL , 11 bytes
Pruébalo en línea! O verificar todos los casos de prueba .
Explicación
Esto calcula una matriz de todas las diferencias absolutas por pares y mantiene la parte triangular superior. El resultado es verdadero si hay al menos un valor 1 en todas las columnas, excepto en la primera.
fuente
R,
726460 bytesUna permutación es inquieta si y solo si todas sus subpermutaciones izquierdas son continuas (es decir, tienen una diferencia cuando están ordenadas).
Si se garantiza que la entrada tiene una longitud de más de uno, entonces podemos reemplazar1:sum(1|v)
conseq(v)
, lo que ahorra cuatro bytes.La
seq(v)
condición en el if se comporta de manera diferente cuando la entrada es de longitud uno --- genera la secuencia en1:v
lugar deseq_along(v)
. Sin embargo, afortunadamente, la salida resulta serTRUE
en este caso, que es el comportamiento deseado. Lo mismo también sucede para la entrada de longitud cero.En R,
T
es una variable predeterminada igual aTRUE
(pero R le permite redefinirla).TRUE
también se considera igual a1
.Gracias a @Billywob por algunas mejoras útiles a la solución original.
fuente
scan
le ahorraría dos bytes. En ese caso, es exactamente el mismo número de bytes que elfor
enfoque de bucle:v=scan();c=c();for(i in 1:sum(1|v))c=c(c,diff(sort(v[1:i])));all(c==1)
que sería 2 bytes más corto que su enfoque vectorizado.T
. Se editará05AB1E , 7 bytes
Pruébalo en línea! o como un conjunto de pruebas modificado .
Explicación
Utiliza el proceso descrito por xnor en su brillante respuesta de Pyth .
Devuelve 2 para instancias verdaderas y 0 para falsas.
fuente
Perl, 63 bytes
Tenga en cuenta que a @Gabriel Banamy se le ocurrió una respuesta más corta (55 bytes) . Pero creo que esta solución sigue siendo interesante, así que la estoy publicando.
El recuento de bytes incluye 62 bytes de código y
-n
bandera.Para ejecutarlo:
Explicaciones breves : convierte cada número
k
en la representación unaria dek+1
(eso+1
es necesario para0
que no se ignore la s). Luego, para cada númerok+1
(expresado en unario como1(1*)
), observamos sik
($1
retencionesk
) ok+2
(que es entonces11$1
) están presentes en la cadena anterior (referenciada por$-backtick
). Si no, entonces lo ponemos$.
a cero. Al final imprimimos$.
cuál será1
si nunca lo ponemos a cero, o cero de lo contrario.fuente
Brain-Flak
302 264256 BytesGracias a Wheat Wizard por guardar 46 bytes
La parte superior de la pila será un 1 para la verdad y un 0 para la falsedad.
Verdad: ¡ Pruébelo en línea!
Falsy: ¡ Pruébalo en línea!
La idea es mantener el número mínimo y máximo que la hormiga ha visitado en la pila. Luego compare cada número con ambos y actualice el apropiado. Si el siguiente número no es 1 menos que el mínimo o 1 más que el máximo, salga del bucle y devuelva falso.
Breve explicacion:
fuente
([]){({}[()]<({}<>)<>>)}{}
con([]){{}({}<>)<>([])}{}
para guardar un par de bytes másGelatina ,
987 bytes¡Pruébelo en línea!
Una traducción Jelly de la respuesta de xnor.
Viejas soluciones:
Pruébalo en línea!
Funciona de manera muy similar a mi respuesta Pyth a continuación:
fuente
»\_«\⁼Ṣ
pero mucho más eficienteŒBŒPċṢ
y;\Ṣ€IỊȦ
debe guardar un byte en cada enfoque.UŒBŒPċṢ
cual no guarda ningún byte. ElỊ
es agradable, sin embargo; Había leído mal ese átomo para generar el NOT lógico de lo que realmente hizo.U
(o el@
ahora que lo pienso). Si una matriz es inquieta, también lo es la matriz invertida, ¿no?[2, 1, 3, 0]
está inquieto pero[0, 3, 1, 2]
no lo es.CJam (
2120 bytes)Conjunto de pruebas en línea
Disección
Esto utiliza la observación de xnor en su respuesta de Haskell de que la diferencia entre el máximo y el mínimo de los primeros
n
elementos debería sern-1
.Enfoque alternativo (también 20 bytes)
Conjunto de pruebas en línea
Esto comprueba directamente que cada elemento después del primero está a la distancia 1 de un elemento anterior. Dado que la entrada es una permutación y, por lo tanto, no repite valores, esta es una prueba suficiente. Gracias a Martin por un ahorro de 1 byte.
Disección
fuente
{_{a+_)f-:z1&,*}*^!}
Java,
100987975 bytesAntes:
Guardado 3 bytes reemplazando
true
yfalse
con1>0
y0>1
.¡Ahorré 23 bytes gracias a las excelentes sugerencias de Peter Taylor!
Sin golf:
Mantenga un registro de los valores más altos y más bajos vistos hasta ahora
m
yn
; solo acepte un nuevo valor si esm + 1
on - 1
es el siguiente valor más alto o más bajo; inicialice el valor alto,,m
a uno menos que el primer elemento para que "coincida" la primera vez alrededor del ciclo. Nota: este es un algoritmo en línea de tiempo lineal. Requiere solo tres palabras de memoria, para los valores actuales, más alto hasta ahora y más bajo hasta ahora, a diferencia de muchas de las otras soluciones.Si el siguiente valor no alcanza los extremos alto y bajo del rango, el valor más bajo hasta ahora se establece en
-1
y luego el extremo bajo nunca puede continuar y llegar a cero. Luego detectamos una secuencia inquieta verificando si el valor bajon
, alcanzó cero.(Desafortunadamente, esto es menos eficiente porque siempre tenemos que mirar la secuencia completa en lugar de rescatar después del primer número incorrecto , pero es difícil discutir con un ahorro de 23 bytes (!) Cuando otras soluciones están usando O (n ^ 2 ) y enfoques de tiempo exponencial.)
Uso:
Nota: esto también se puede escribir sin aprovechar las lambdas de Java 8:
Java 7, 89 bytes
fuente
int m,n;m=n=a[0];--m;
podría serint n=a[0],m=n-1;
, y lo costosoreturn
yelse
podría reducirse coni==m+1?m++:n=(i==n-1)?i:-1;return n==0;
(o algo similar, no he probado esto).m++
om+=1
allí, por lo que todavía necesito unif
y unelse
, y pierde el aspecto de cortocircuito en el primer valor malo, pero eso es una gran mejora. ¡Gracias!j
y asignarle el resultado, pero sospecha que habría una mejor manera de hacerlo.g
, y no pude hacer que funcionara. (Estoy usando Java 9-ea + 138, ¿tal vez sea una diferencia entre Java 8 y Java 9?) Puedo intentarlo de nuevo mañana.n-=i==m+1?m-m++:i==n-1?1:n+1;
Pyth ( fork ), 13 bytes
No intente en línea enlace para esta bifurcación de Pyth. La bifurcación incluye la función deltas
.+
, que no forma parte de la biblioteca Pyth estándar.Explicación:
fuente
Perl,
6654 +1 = 55 bytes+1 byte para
-n
.Explicación:
Imprime 0 si es falso, 1 si es verdadero.
-11 bytes gracias a @Dada
fuente
perl -nE 's/\d+/$.&=!@a||1~~[map{abs$_-$&}@a];push@a,$&/eg;say$.'
: en-n
lugar de lo<>=~
que le permite deshacerse del/r
modificador. use\d+
y luego en$&
lugar de(\d+)
y$1
.!@a
en lugar de0>$#a
.$.&=
en lugar de$.&&=
.push@a,$&
en lugar de@a=(@a,$&)
Brainfuck, 60 bytes
La permutación se da como bytes sin separadores y sin nueva línea de terminación. Como
\x00
ocurre en la entrada, esto está diseñado para implementaciones conEOF = -1
. La salida es\x00
para falso y\x01
para verdadero.Si se permite una permutación de
\x01
hastachr(r)
, entonces podemos reemplazar todas las instancias de,+
con,
una puntuación de 57 con unaEOF = 0
aplicación.Pruébelo en línea (versión de 57 bytes): la entrada se puede dar como una permutación de cualquier rango contiguo de bytes excluyendo
\x00
, y la salida será\x00
falsa y el mínimo del rango verdadero.Llevamos un registro de los mínimos y máximos vistos hasta ahora, y para cada personaje después del primero, verificamos si es min-1 o max + 1 o ninguno. En el caso de ninguno de los dos, mueva el puntero fuera del espacio de trabajo normal para que las celdas locales se vuelvan cero.
El diseño de memoria del espacio de trabajo normal al comienzo del bucle principal es
c a b 0 0
donde
c
es el caracter actual,a
es min yb
es max. (Para la versión de 60 bytes, todo se maneja con un desplazamiento de 1 debido a,+
).fuente
Brachylog , 22 bytes
Pruébalo en línea!
Explicación
No he encontrado una manera concisa de verificar si una lista contiene enteros consecutivos o no. Lo más corto que encontré es generar un rango entre el primer y el último elemento de esa lista y verificar que ese rango sea la lista original.
fuente
1
. No sé lo fácil que es en Brachylog.Lote, 133 bytes
Toma datos como argumentos de línea de comandos. Sale con nivel de error 0 para éxito, 1 para falla.
fuente
J, 14 bytes
Esto se basa en @ xnor's método de .
Explicación
fuente
Java, 170 bytes
La matriz
x
tiene valores del 0 al número máximo en orden (Python sería mucho mejor aquí ...). El ciclo va hacia atrás tratando de hacer coincidir el número más bajo (x[b]
) o el más alto (x[e]
) que aún no se ha encontrado; si lo hace, ese número podría alcanzarse en ese paso.Prueba el código aquí .
fuente
Mathematica, 47 bytes
Un poco más que la solución de Martin Ender (¡sorpresa sorpresa!). Pero es uno de mis esfuerzos más ilegibles, así que eso es bueno: D
Explicación:
fuente
Java 7,
170169 bytesUngolfed y código de prueba:
Pruébalo aquí
Salida:
fuente