Los números de escopeta son una secuencia con una definición bastante simple pero con una estructura interesante. Comience con los números naturales:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...
Ahora tome todos los números en índices divisibles por 2 , agrúpelos en pares e intercambie los números en cada par:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
^ ^ ^ ^ ^ ^ ^
<---> <---> <-----> <----
1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...
Ahora haz lo mismo con los índices divisibles por 3 :
1, 4, 3, 2, 5, 8, 7, 6, 9, 12, 11, 10, 13, 16, ...
^ ^ ^ ^
<------> <--------->
1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...
Y luego para 4 , 5 , 6 , y así sucesivamente:
1, 4, 8, 2, 5, 3, 7, 6, 10, 12, 11, 9, 13, 16, ...
1, 4, 8, 6, 5, 3, 7, 2, 10, 12, 11, 14, 13, 16, ...
1, 4, 8, 6, 12, 3, 7, 2, 10, 5, 11, 14, 13, 16, ...
1, 4, 8, 6, 12, 14, 7, 2, 10, 5, 11, 3, 13, 16, ...
...
Después de k tales pasos, los primeros k + 1 números serán corregidos. Entonces podemos definir la secuencia infinita de números de escopeta como el límite de dejar que k vaya al infinito. Los primeros 66 números son:
1, 4, 8, 6, 12, 14, 16, 9, 18, 20, 24, 26, 28, 22, 39, 15, 36, 35, 40, 38, 57, 34, 48, 49, 51, 44,
46, 33, 60, 77, 64, 32, 75, 56, 81, 68, 76, 58, 100, 55, 84, 111, 88, 62, 125, 70, 96, 91, 98, 95,
134, 72, 108, 82, 141, 80, 140, 92, 120, 156, 124, 94, 121, 52, 152, 145, ...
Dato curioso: a pesar de haberse obtenido al permutar solo los números naturales, esta secuencia no contiene ningún primo.
El reto
Dado un número entero n > 0
, encuentra el n
número de escopeta th. Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y devolver el resultado o imprimirlo en STDOUT (o la alternativa más cercana).
Este es el código de golf, por lo que gana el envío más corto (en bytes).
Tablas de clasificación
Esto está obteniendo más respuestas de lo que pensaba, así como varias personas que compiten en el mismo idioma. Así que aquí hay un Fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.
Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:
# Language Name, N bytes
¿Dónde N
está el tamaño de su envío? Si mejora su puntaje, puede mantener los puntajes antiguos en el título, tachándolos. Por ejemplo:
# Ruby, <s>104</s> <s>101</s> 96 bytes
function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=0,c=0,p=-1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);t++;c=p==o?c:t;i=i.replace("{{PLACE}}",c+".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);p=o;$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=47338;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*([^,]+)/
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src=https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js></script><link rel=stylesheet type=text/css href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id=answer-list><h2>Leaderboard</h2><table class=answer-list><thead><tr><td></td><td>Author<td>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>
10
,21
,25
y30
no aparecen ya sea, por ejemplo.k
iteración th, elk
elemento th en la matriz se transpone a la2k
posición th, y no se volverá a tocar hasta la2k
iteración th, momento en el que se transpone a la4k
posición th, hasta el infinito. Un primo no se transpone hasta que llega su turno, por así decirlo, por lo que todos los primos se barajan hacia adelante. Pero podemos hacer fácilmente una lista de las víctimas inocentes simplemente imprimiendo el primer elemento que se transpondrá en la iteración 2 y cada iteración impar. La lista va: 2, 3, 5, 7, 10, 11, 13, 21, 17, 19, 30, 23, 27, 25, 29, 31, 45, 42, 37, 54, 41, 43, 65, ...Respuestas:
Pyth, 19
22Una implementación bastante ingenua de la respuesta de golfscript de @ PeterTaylor .
Pruébalo en línea aquí
Utiliza los mismos trucos para convertir un bucle while en un pliegue como lo hace el otro programa Pyth a continuación.
Una copia ingenua del algoritmo de @ Sp3000 traducido a Pyth.
Puedes probarlo en línea aquí.
Utiliza reduce (nombre de python para pliegue) para emular el ciclo while. Enumera sobre lo
range(input, 2)
que en Pyth funcionarange(2, input)[::-1]
. Los otros campos de golf relacionados con Pyth implica el usonot
en lugar de<2
y el uso dey
'S modo de duplicar el valor de argumentos numéricos oculta.fuente
> <>,
5245 bytesPágina de Esolangs para> <>
Hay muchos elementos de copia y movimiento, gracias a los diversos módulos y multiplicaciones necesarios. La lógica es exactamente la misma que mi solución Python .
Toma entrada a través de un punto de código de STDIN, por ejemplo
"!" = 33 -> 75
.fuente
-v
cuenta como tres: /Python 2, 58 bytes
Como la mayoría de las otras respuestas, la idea es trabajar al revés.
Llamemos paso a
k+1
pasoi
, para que en el paso se intercambieni
todos los múltiplos dei
. Necesitamos dos observaciones simples:n
en la matriz solo se intercambia en el pasoi
sin
es divisible pori
,n/i mod 2
. Si este es 1, usted es el número más bajo (y cambiará hacia arriba), de lo contrario, es el número más alto (y cambiará hacia abajo).Esto nos da un algoritmo para trabajar hacia atrás. Probémoslo con 6, comenzando desde el último paso (paso
i = 6
):Entonces ahora sabemos que el número vino de la posición 12. Luego:
Así que ahora sabemos que vino de 16 antes de eso. Finalmente:
Como este es el primer paso (recuerde
k+1
), hemos terminado y el número que termina en la posición 6 vino originalmente de la posición 14, es decir, el sexto número de escopeta es 14.Así que ahora para la explicación de Python:
fuente
i-1
como~-i
while
. Buen trabajo, Sp3000.u+G**H!%GHty%/GH2rhQ2Q
Haskell, 68 bytes
Probablemente más golfable, especialmente la primera fila. Esto define una función
s
que toman
y devuelve eln
número de escopeta th.Explicación
La función auxiliar
#
toma dos númerosn
yk
, y devuelve elk
número th en la lista definida aplicando la operación de intercambio de pares a cadan
número th. Por ejemplo, aplicándolo a los primeros 20 números conn = 4
rendimientos esto:El resultado de
s n
se obtiene al reducir ("plegar") la lista[2..n]
por la función de segundo orden(.).(#)
, que toma un númerom
y una funciónf
(inicialmente la función de identidadid
), y devuelve una función que tomak
y devuelvef (m # k)
. Por ejemplo, en el caso,n = 4
la lista[2,3,4]
se reduce a una función que tomak
y devuelveid (4 # (3 # (2 # k)))
. Laid
única que se necesita para el caso basen = 1
, donde la lista está vacía. Finalmente, le damos entrada a esta funciónk = n
, obteniendo eln
número de escopeta th.fuente
CJam, 32 bytes
Simplemente siguiendo las especificaciones hasta el punto. Ejecutar las instrucciones en un conjunto más grande para no afectar el enésimo número.
Pruébalo en línea aquí
fuente
Ruby, 92 bytes
Mi primer esfuerzo de código de golf. No se basa en ninguna otra respuesta.
Ahora que he visto algunos de los otros, noto que la mayoría simplemente define una función, no un programa completo que acepta entrada y produce salida. El OP solicitó un programa completo con entrada y salida. ¿Es costumbre ignorar tales requisitos?
84 bytes
Después de mirar otras respuestas y darse cuenta de que es posible una solución iterativa.
fuente
ARGV
a la$*
magia global. 2. Elto_s
es innecesario. 3. En lugar de asignard
an
una línea separada, simplemente hazlod=n=...
para eliminar un carácter. ¡Buen trabajo para tu primer golf! :)n+=
línea son innecesarios, y ambas ocurrencias==0
pueden cambiarse de manera segura<1
.Python 2,
9779 caracteresDetermina para cada índice el valor correcto persiguiendo recursivamente el número hacia atrás. El algoritmo fue descubierto de forma independiente.
editar: ahora solo imprime el
n
número th en lugar de los primerosn
números. Por supuesto, un enfoque iterativo sería más corto, pero no quiero copiar el código de Sp3000.fuente
g(i,i)
parte me pareció particularmente molesta ...print
declaración.Haskell, 79 bytes
Uso:
p 66
que salidas145
No hay mucho que explicar: la función
#
calcula recursivamente el número de escopeta en la posicióni
del pasos
.p n
devuelve el número en la posiciónn
del pason
.fuente
k, 41 bytes
{{x+$[y!x;0;$[2!_x%y;y;-y]]}/[x;|2+!x-1]}
{...}
lambda, x e y son el primer y segundo argumento implícito$[b;t;f]
operador ternario, evalúa b seguido de t / f respectivamenteb!a
a módulo b_
piso, arroja el resultado de la división a un int%
división{...}/[x;y]
imprima {...} con x y aplique sobre la lista y, es equivalente a f [f [.. f [f [x; y0]; y1]; .. yn-1]; yn]|
marcha atrás!
función iota, genera la lista de 0 a n-1fuente
Lisp común,
11391(iterativo: 91)
(original, recursivo: 113)
Ejemplo
Con la versión recursiva:
Pruebas
Verificaciones y medidas para la versión iterativa:
fuente
Mathematica,
5349 bytesDecidí jugar golf a mi implementación de referencia. El
∣
es el símbolo Unicode para "divide", y cuenta para 3 bytes. De lo contrario, esto usa el mismo algoritmo que todos los demás.Define una función sin nombre que toma
n
como parámetro único y devuelve eln
número de escopeta.fuente
GolfScript, 27 caracteres
Explicación
Si
f(i, n)
es el valor en la posiciónn
después de lasi-1
transformaciones, tenemosdonde
^
denota bitor xor; dada entradan
, queremos calcularf(n, n)
.La conversión de una función recursiva a un ciclo no es interesante; lo interesante es la forma en que
puede ser reescrito El enfoque más obvio es decir que debe ser
para algunos
g
. Obviamenteg
alterna entre1
y-1
, a medida que las posiciones cambian alternativamente hacia arriba y hacia abajo; desdeg(1) = 1
(porque1
intercambia hasta2
), tenemosdonde
**
denota exponenciación. Los ahorros finales provienen de reescribir esto comoDisección
fuente
u-G*H^_!%GH/GHrhQ2Q
Si no desea publicar esto usted mismo, dígame / agréguelo a la respuesta de CW.CJam, 24 bytes
Demostración en línea
Este es un puerto de mi respuesta GolfScript , tomando prestado el bucle de la respuesta CJam de Martin y explotando el
divmod
operador de CJam . ( ¡Dije que sería útil!).fuente
Julia,
6157 bytesEsto crea una función sin nombre que toma un solo argumento
n
y devuelve eln
número de escopeta th. Para llamarlo, dale un nombre, por ejemplof=n->(...)
.Ejemplos:
Actualmente esto se basa en la increíble respuesta de Python de @ Sp3000 . Revisaré esto pronto porque debe haber una forma más corta de hacer esto en Julia que lo que he hecho aquí. Cualquier aportación es bienvenida, como siempre.
fuente
GML, 76 bytes
Información sobre GML
fuente
CJam,
2827 bytesAsí que esto es un poco vergonzoso ... antes de publicar esto, intenté jugar al golf y llegué a 30 bytes en CJam. Ninguna de las respuestas existentes ha superado eso todavía. Mientras tanto, también logré eliminar tres bytes más. No es una solución más corto Pyth en un comentario, pero nada más corto ha sido publicado en una respuesta, así que aquí está. Tal vez inspire a las personas de APL / J a esforzarse un poco más (o alguien realmente publique la solución Pyth), antes de que tenga que aceptar mi propia respuesta. ;)
Pruébalo aquí.
Explicación
fuente
J,
3432 bytesIntentaré jugar al golf un poco más y agregaré alguna explicación más adelante.
Pruébelo en línea aquí.
fuente
TI-Basic 83/84, 40 bytes
Información sobre TI-Basic
fuente
Ruby,
5747 bytesEsto es esencialmente SP3000 solución Python 's (con la sugerencia de XNOR ) traducida a Ruby. Sin embargo, probablemente podría jugar golf en algunos lugares.
fuente