Mi maestro de Precalc tiene uno de sus problemas favoritos que inventó (o más probablemente robó inspirado por xkcd ) que involucra una fila de n
urinarios. "Jaque mate" es una situación en la que cada urinario ya está ocupado O tiene un urinario ocupado junto a ellos. Por ejemplo, si una persona es un X
, entonces
X-X--X
se considera jaque mate. Tenga en cuenta que una persona no puede ocupar un orinal junto a un orinal ya ocupado.
Tarea
Su programa tomará un número stdin
, argumentos de línea de comando o un argumento de función. Luego, su programa imprimirá o devolverá la cantidad de formas en que el jaque mate puede ocurrir con la cantidad ingresada de urinarios.
Ejemplos
0 -> 1
(el caso nulo cuenta como jaque mate)
1 -> 1
( X
)
2 -> 2
( X-
o -X
)
3 -> 2
( X-X
o -X-
)
4 -> 3
( X-X-
, -X-X
o X--X
)
5 -> 4
( X-X-X
, X--X-
, -X-X-
, o -X--X
)
6 -> 5
( X-X-X-
, X--X-X
, X-X--X
, -X--X-
o -X-X-X
)
7 -> 7
( X-X-X-X
, X--X-X-
, -X-X--X
, -X--X-X
, X-X--X-
, X--X--X
o -X-X-X-
)
8 -> 9
( -X--X--X
, -X--X-X-
, -X-X--X-
, -X-X-X-X
, X--X--X-
, X--X-X-X
, X-X--X-X
, X-X-X--X
, X-X-X-X-
)
...
Tanteo
El programa más pequeño en bytes gana.
''
. Esto es lo mismo que con factorial y permutaciones, 0! = 1, porque hay exactamente 1 forma de organizar 0 elementos.Respuestas:
Oasis , 5 bytes
Código
Versión extendida
Explicación
Pruébalo en línea!
fuente
info.txt
info.txt
es útil, contiene una documentación para cada comando de OasisJava 7,
6542 bytesLa secuencia solo agrega elementos anteriores para obtener nuevos. Punta de sombrero para orlp y Rod para este método más corto;)
Antiguo:
Después del quinto elemento, la brecha en la secuencia aumenta en el elemento cinco anterior.
fuente
f
función desde el otro fragmento en lugar de recurrir. Estúpido, arreglando ...u>0?u:1;
)1;
?u>0?u:1;)
por1;
si cambia la primera comparación au>1
, luego en u = 2 la salida será g (0) + g (-1), que será 2Python 2,
42403935 bytesGenerando los conjuntos reales:
fuente
Ruby,
5834 bytesMuy inspirado por la respuesta original de Java de Geobits.
Véalo en repl.it: https://repl.it/Dedh/1
Primer intento
Véalo en repl.it: https://repl.it/Dedh
fuente
Python, 33 bytes
Utiliza los casos base desplazados
f(-1) = f(0) = f(1) = 1
. SiTrue
pudiera usarse para 1, no necesitaríamos 3 bytes para el+()
.fuente
J,
312723 bytes¡Guardado 4 bytes gracias a millas!
Una explicación vendrá pronto.
Vieja solución
Esta es una agenda. El LHS es un gerundio compuesto por dos verbos:
>.1&^
y-&3+&$:-&2
. El primero se usa si la condición (2&<
) falla. Eso significa que la bifurcación>.1&^
se activa sobre el argumento. Observar:Aquí,
>.
toma el máximo de dos valores. Por lo tanto, produce 1, 1 y 2 como los términos iniciales.El segundo verbo en el gerundio es un tenedor:
Los dientes izquierdo y derecho se aplican al verbo, restando 3 y 2 respectivamente; entonces el verbo del medio se llama con argumentos izquierdo y derecho iguales a esos.
$:
llama al verbo en cada argumento y+
agrega esos dos. Básicamente es equivalente a($: arg - 3) + ($: arg - 2)
Casos de prueba
fuente
MATL ,
2523 bytesPruébalo en línea! O revise todos los casos de prueba .
Explicación
¡Dos convoluciones! ¡Hurra!
Esto crea una matriz, digamos A, donde cada configuración posible es una fila.
1
en esta matriz representa una posición ocupada. Por ejemplo, para la entrada,4
la matriz A esEl código entonces involucra la matriz A con
[1 1 1]
. Esto proporciona una matriz B. Las posiciones ocupadas y las vecinas de las posiciones ocupadas en A dan un resultado distinto de cero en la matriz B:Entonces, la primera condición para que una configuración sea un jaque mate es que B no contiene ceros en esa fila. Esto significa que en esa fila de A no había puestos vacíos, o había algunos pero eran vecinos de puestos ocupados.
Necesitamos una segunda condición. Por ejemplo, la última fila cumple la condición anterior, pero no es parte de la solución porque, para empezar, la configuración no era válida. Una configuración válida no puede tener dos posiciones ocupadas vecinas, es decir, no puede tener dos contiguas
1
en A. De manera equivalente, no puede tener dos valores contiguos en B superiores1
. Por lo tanto, podemos detectar esto haciendo girar B con[1 1]
y verificando que en la matriz resultante, C,ningún valor en esa fila excede
3
. El resultado final es el número de configuraciones que cumplen las dos condiciones.fuente
PHP,
10511393 bytes+3 para
n=1
; +9 para$argv
, -1-3 golf-20: noté que no tengo para las combinaciones, sino solo su cuenta
corre con
-r
bucle de 2 ** n-1 a 0:
11
,000
,00
al principio o al final, o una sola0
resultado de impresión
mismo tamaño, expresiones regulares un poco más simples
11
,00
al principio o al final, o000
PHP, 82 bytes
La respuesta de Arnauld portó y jugó golf:
no imprime nada para n = 0
fuente
n=0
: inserte?:1
antes de la final;
Jalea , 11 bytes
Pruébalo en línea! o verificar todos los casos de prueba .
Cómo funciona
fuente
JavaScript (ES6) / Recursivo,
3027 bytesEditar: guardado 3 bytes gracias a Shaun H
JavaScript (ES6) / No recursivo
9077 bytesEditar: guardado 13 bytes gracias a Conor O'Brien y Titus
fuente
((i|r|l)&(k-1))
can become((i|r|l)&k-1)
, or even((i|r|l)&~-k)
i<<1
->i*2
ori+i
!(i&(x=i>>1|i+i))&&((i|x)&(k-1))==k-1
; and if you can insert,k--
somewhere, you can replacek-1
withk
to save parens.&(k-1)
needs no parens anyway; but you can use&~k
instead.f=n=>n<3?n||1:f(n-2)+f(n-3)
Mathematica, 35 bytes
Defines a function
a
. Takes an integer as input and returns an integer as output. Simple recursive solution.fuente
AnyDice, 51 bytes
There should be more AnyDice answers around here.
My solution defines a recursive function that calculates
a(n)=a(n-2)+a(n-3)
. It returnsa(0)=a(1)=1
anda(2)=2
using some integer division magic.Try it online
Nota: el resultado puede parecer extraño, y eso se debe a que generalmente se usa para generar probabilidades de dados. Solo mira el número a la izquierda del gráfico de barras.
fuente
Perl,
3534 bytesIncluye +1 para
-p
Dar entrada sobre STDIN
checkmate.pl
:Una fórmula secreta recientemente desarrollada. Ripple actualiza 3 variables de estado sin la necesidad de asignaciones paralelas.
Es igualmente corto (pero mucho más lento y requiere mucha más memoria) para resolver el problema original:
pero eso no funciona para
0
fuente
JavaScript (ES6), 62 bytes
Esta es la primera vez que necesito dos nombres de variables ficticias. Una versión recursiva probablemente sería más corta, pero realmente me gusta
reduce
... Editar: Encontré una solución, también 62 bytes, que solo tiene una variable ficticia:fuente
Jalea , 19 bytes
La solución recursiva es
probablementemás corta ...Véalo en TryItOnline
O vea la serie para
n = [0, 99]
, también en TryItOnline¿Cómo?
Devuelve el
n+3
número de Padovan contando combinacionesfuente
> <> , 25 + 2 = 27 bytes
Necesita que la entrada esté presente en la pila al inicio del programa, por lo que +2 bytes para el
-v
indicador. Pruébalo en línea!La primera línea inicializa la pila
1 1 2 n
, donden
está el número de entrada. La segunda línea, que va hacia atrás, verifica quen
sea mayor que 1. Si es así,n
se reduce y el siguiente elemento en la secuencia se genera de la siguiente manera:La línea final genera el número en la parte inferior de la pila, que es el elemento requerido en la secuencia.
fuente
CJam , 20 bytes
Pruébalo en línea!
Explicación
Esto utiliza la relación de recurrencia que se muestra en la página OEIS .
fuente
05AB1E , 12 bytes
Explicación
Pruébalo en línea!
fuente
FRACTRAN,
10493 bytesLa entrada es
11**n*29
y la salida es29**checkmate(n)
.Esto es principalmente por diversión, especialmente porque actualmente estoy siendo superado por Python, JS y Java. Sin embargo, el mismo número de bytes que PHP: D Se aceptan sugerencias de golf.
Ungolfing
fuente
En realidad, 25 bytes
Esto parece un poco largo para una
f(n) = f(n-2) + f(n-3)
relación de recurrencia simple . Sugerencias de golf bienvenidas. Pruébalo en línea!Ungolfing
fuente
Actualmente , 18 bytes
Este es un puerto de la respuesta más larga de Jelly de Dennis. Sugerencias de golf bienvenidas. Pruébalo en línea!
Ungolfing
fuente
Stax , 7 bytes
Ejecutar y depurarlo
Utiliza la relación de recurrencia.
C(n) = C(n-2) + C(n-3)
fuente
C (gcc) , 33 bytes
Pruébalo en línea!
fuente
Haskell , 27 bytes
Pruébalo en línea!
fuente