Los números catalanes ( OEIS ) son una secuencia de números naturales que a menudo aparecen en combinatoria.
El enésimo número catalán es el número de palabras Dyck (cadenas equilibradas de paréntesis o paréntesis como [[][]]
; formalmente definido como una cadena que usa dos caracteres ayb de modo que cualquier subcadena que comience desde el principio tenga un número de caracteres mayor o igual a número de caracteres b, y toda la cadena tiene el mismo número de caracteres ayb) con longitud 2n. El enésimo número catalán (para n> = 0) también se define explícitamente como:
A partir de n = 0, los primeros 20 números catalanes son:
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...
Reto
Escriba un programa o función completa que tome un número entero no negativo n a través de STDIN o una alternativa aceptable, y genere el enésimo número catalán. Su programa debe funcionar como mínimo para las entradas 0-19.
I / O
Entrada
Su programa debe recibir información de STDIN, argumentos de función o cualquiera de las alternativas aceptables según esta meta publicación. Puede leer el número ingresado como su representación decimal estándar, representación unaria o bytes.
- Si (y solo si) su idioma no puede recibir información de STDIN o alguna alternativa aceptable, puede recibir información de una variable codificada o equivalente adecuado en el programa.
Salida
Su programa debe generar el enésimo número catalán a STDOUT, resultado de la función o cualquiera de las alternativas aceptables según esta meta publicación. Puede generar el número catalán en su representación decimal estándar, representación unaria o bytes.
El resultado debe consistir en el número catalán apropiado, seguido opcionalmente por una o más líneas nuevas. No se puede generar otra salida, excepto la salida constante del intérprete de su idioma que no se puede suprimir (como un saludo, códigos de color ANSI o sangría).
No se trata de encontrar el idioma más corto. Se trata de encontrar el programa más corto en todos los idiomas. Por lo tanto, no aceptaré una respuesta.
En este desafío, los idiomas más nuevos que el desafío son aceptables siempre que tengan una implementación. Se permite (e incluso se recomienda) escribir este intérprete usted mismo para un idioma previamente no implementado. Aparte de eso, todas las reglas estándar del código de golf deben ser obedecidas. Las presentaciones en la mayoría de los idiomas se puntuarán en bytes en una codificación preexistente apropiada (generalmente UTF-8). Tenga en cuenta también que están permitidos los elementos integrados para calcular el enésimo número catalán.
Catalogar
El Fragmento de pila al final de esta publicación genera el catálogo a partir de las respuestas a) como una lista de la solución más corta por idioma yb) como una tabla de clasificación general.
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
Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:
## Perl, 43 + 2 (-p flag) = 45 bytes
También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento:
## [><>](http://esolangs.org/wiki/Fish), 121 bytes
<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><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="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 66127; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>
Respuestas:
C,
7852393433 bytesAún más magia C (gracias xsot):
?:
es una extensión de GNU .Esta vez expandiendo la recurrencia a continuación (gracias xnor y Thomas Kwa):
-(n+1)
se reemplaza por~n
, que es equivalente en el complemento a dos y ahorra 4 bytes.De nuevo como una función, pero esta vez explotando la siguiente recurrencia:
c(n)
entra en una recursión infinita para negativon
, aunque no es relevante para este desafío.Dado que llamar a una función parece una alternativa aceptable a la consola de E / S:
c(n)
toma unint
y devuelve unint
.Entrada original:
En lugar de calcular directamente la definición, la fórmula se reescribe como:
La fórmula supone
n >= 2
, pero representa el códigon = 0
yn = 1
también.En el lío C anterior,
n
yk
tienen el mismo papel que en la fórmula, mientrasc
acumula el producto. Todos los cálculos se realizan en coma flotantedouble
, lo cual es casi siempre una mala idea, pero en este caso los resultados son correctos hasta al menos n = 19, por lo que está bien.float
habría guardado 1 byte, desafortunadamente no es lo suficientemente preciso.fuente
c(n){return!n?:(4+6./~n)*c(n-1);}
?:
! Aparentemente, es una extensión GNU C pero creo que aún califica.Jalea , 4 bytes
Pruébalo en línea!
Cómo funciona
fuente
c
Conseguir2z
yz
como sus argumentos?CJam, 12 bytes
Pruébalo en línea.
Más allá de la entrada 11, deberá indicarle a su máquina virtual Java que use más memoria. Y en realidad no recomendaría ir mucho más allá de 11. Sin embargo, en teoría, funciona para cualquier N, ya que CJam usa enteros de precisión arbitraria.
Explicación
CJam no tiene incorporados coeficientes binomiales, y calcularlos a partir de tres factoriales requiere muchos bytes ... así que tendremos que hacer algo mejor que eso. :)
fuente
ri_2*m!1$m!_*/\)/
) en mi implementación. Lo único bueno es que es mucho más rápido. :)Mathematica,
1613 bytesMuebles empotrados, amirite: /
Versión no incorporada (21 bytes):
Una versión sin binomio (25 bytes):
fuente
TI-BASIC, 11 bytes
Curiosamente, nCr tiene mayor prioridad que la multiplicación.
fuente
Python 3, 33 bytes
Utiliza la recurrencia
El caso base de 0 se maneja como
0**n or
, que se detiene como1
cuandon==0
y de lo contrario evalúa la expresión recursiva a la derecha. El operador bit a bit~n==-n-1
acorta el denominador y ahorra en parens.Python 3 se usa para su división de flotación. Python 2 podría hacer lo mismo con un byte más para escribir
6.
.fuente
n<1
más que0**n
?True
porn==0
más que por1
. Por supuesto,True == 1
peroTrue is not 1
y se imprime de manera diferente. Esperaría que esto no esté permitido. ¿Sabes si tenemos una decisión sobre esto?isinstance(True, int) is True
después de todo.J, 8 bytes
Este es un tren monádico; utiliza la fórmula (2x nCr x) / (x + 1). Probarlo aquí .
fuente
pl, 4 bytes
Pruébalo en línea.
Explicación
En pl, las funciones eliminan sus argumentos de la pila y vuelven a colocar el resultado en la pila. Normalmente, cuando no hay suficientes argumentos en la pila, la función simplemente falla en silencio. Sin embargo, sucede algo especial cuando la cantidad de argumentos en la pila es uno fuera de la aridad de la función: la variable de entrada
_
se agrega a la lista de argumentos:En efecto, este es el pseudocódigo:
fuente
Sesos ,
948668 bytes8 bytes cambiando el factorial-er de la versión 1 a la versión 2.
18 bytes calculando
n!(n+1)!
en un solo paso. En gran parte inspirado por el algoritmo de prueba de primalidad de Dennis .Hexdump:
Pruébalo en línea!
Utiliza la fórmula
a(n) = (2n)! / (n!(n+1)!)
.Ensamblador
Brainfuck equivalente
Este script de Retina se usa para generar el equivalente de brainfuck. Tenga en cuenta que solo acepta un dígito como argumento de comando y no verifica si hay un comando en los comentarios.
fuente
Pyth, 8
Pruébelo en línea o ejecute Test Suite
Explicación
fuente
En serio, 9 bytes
Hex Dump:
Pruébalo en línea
Explicación:
fuente
2n
fila th esC(2n,n)
. Por lo tanto:,;u@τ╣║/
para 8 bytes.║
yM
funcionaría.JavaScript (ES6), 24 bytes
Basado en la respuesta de Python .
Cómo funciona
Creo que esto es lo más corto que puede ser, pero las sugerencias son bienvenidas.
fuente
Julia, 23 bytes
Esta es una función anónima que acepta un entero y devuelve un flotante. Utiliza la fórmula binomial básica. Para llamarlo, dale un nombre, por ejemplo
f=n->...
.fuente
Matlab,
3525 bytesOctava, 23 bytes
fuente
@(n)
lugar de la función, las funciones anónimas están bien.n
:@(n)nchoosek(2*n,n++)/n
.../++n
que tampoco funciona. : /𝔼𝕊𝕄𝕚𝕟, 3 caracteres / 6 bytes
Try it here (Firefox only).
Construido ftw! Me alegro de haber implementado math.js desde el principio.
Solución extra, 12 caracteres / 19 bytes
Try it here (Firefox only).
¡Sí! ¡19 byte!
Evalúa a pseudo-ES6 como:
fuente
Haskell, 27 bytes
Una fórmula recursiva. Tiene que haber una manera de ahorrar en los padres ...
Tomar directamente el producto fue 2 bytes más largo:
fuente
g(n-1)
=>g$n-1
guarda un byte. Editar: en realidad esto no funciona porque entonces la fórmula se interpreta como(...*g) (n-1)
.Dyalog APL, 9 bytes
Este es un tren monádico; utiliza la fórmula (2x nCr x) / (x + 1). Pruébelo en línea aquí .
fuente
C,
122121119108 bytesUsé gcc (GCC) 3.4.4 (cygming special, gdc 0.12, usando dmd 0.125) para compilar en un entorno Windows cygwin. La entrada entra en la línea de comando. Es similar a la solución Python de Sherlock9, pero los bucles se combinan en uno para evitar el desbordamiento y obtener una salida hasta el vigésimo número catalán (n = 19).
fuente
main
definición para guardar un byte.char**v
lugar dechar *v[]
. (El espacio anterior*
no es necesario, y los tipos son equivalentes.)n
.Javagony , 223 bytes
Completamente expandido:
fuente
Japt, 16 bytes
Incluso Mathematica es más corto.
:-/
Pruébalo en línea!
Sin golfos y explicación
Versión alternativa, basada en la fórmula recursiva:
fuente
Vitsy , 13 bytes
Esta es una función en Vitsy . ¿Cómo convertirlo en un programa que haga esto? Concatenar
N
. do:Pruébalo en línea!
fuente
Vía Láctea 1.5.14 , 14 bytes
Explicación
o, alternativamente, la versión mucho más eficiente:
Vía Láctea 1.5.14 , 22 bytes
Explicación
Uso
fuente
Clojure / ClojureScript, 53 bytes
Clojure puede ser bastante frustrante para jugar al golf. Es muy concienzudo aunque sigue siendo muy legible, pero algunas de las características más antiguas son realmente detalladas.
(inc x)
es más idiomático que(+ x 1)
y "se siente" más conciso, pero en realidad no guarda caracteres. Y escribir cadenas de operaciones es mejor(->> x inc (/ 6) (- 4))
, pero en realidad es más largo que hacerlo de la manera más fea.fuente
Prólogo, 42 bytes
Usar la recursión es casi siempre el camino a seguir con Prolog.
Código:
Ejemplo:
Pruébalo en línea aquí
fuente
*
símbolo aquí?Octava, 22 bytes
fuente
Ceilán, 60 bytes
Esto funciona hasta C 30 , ya que los enteros de Ceylon son números con signo de 64 bits (C 31 tiene desbordamiento, se calculará como -4050872099593203).
No sé si Ceilán tiene alguna función matemática superior incorporada, pero luego importar el paquete correcto probablemente sea más largo que calcularlo a pie.
fuente
R,
352816 bytesEditar: Use el paquete de números incorporado.
fuente
MATL , 8 bytes
Pruébalo en línea!
Explicación
fuente
05AB1E , 6 bytes
Explicación:
fuente
R, 28 bytes
No usa un paquete, por lo que es un poco más largo que una respuesta anterior
fuente