var QUESTION_ID=117879,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/117879/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
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><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners 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><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>
Geléia ,
87 bytesObrigado a @ErikTheOutgolfer por economizar 1 byte!
Experimente online!
Como funciona
fonte
Alice , 27 bytes
Obrigado ao Sp3000 pela
.C
ideia.Experimente online!
Explicação
Acho que pode haver uma maneira mais curta de calcular isso usando números triangulares, mas achei que esse é um abuso interessante de um built-in, então aqui está uma solução diferente.
A idéia básica é fazer uso dos "pack" e "desempacotar" internos de Alice. "Pack", ou
Z
, leva dois números inteiros mapeia-os bijetivamente para um único número inteiro. "Descompactar" ouY
inverte essa bijeção e transforma um número inteiro em dois. Normalmente, isso pode ser usado para armazenar uma lista ou árvore de números inteiros em um único inteiro (grande) e recuperar os valores individuais posteriormente. No entanto, neste caso, podemos usar as funções na ordem oposta, para permitir que a natureza da bijeção funcione para nós.Descompactar um número inteiro em dois números inteiros consiste basicamente em três etapas:
Mapa ℕ → ℕ 2 , usando a função de emparelhamento Cantor . Ou seja, os naturais são escritos ao longo das diagonais de uma grade infinita e retornamos os índices:
Por exemplo,
8
seria mapeado para o par(1, 2)
.Mapeie ℕ 2 → ℤ 2 , usando o inverso da etapa 1 em cada número inteiro individualmente. Ou seja, naturais ímpares são mapeados para números inteiros negativos e até naturais são mapeados para números inteiros não negativos.
Para compactar dois números inteiros em um, simplesmente invertemos cada uma dessas etapas.
Agora, podemos ver que a estrutura da função de emparelhamento do Cantor codifica convenientemente o triângulo que precisamos (embora os valores sejam um por um). Para reverter essas diagonais, tudo o que precisamos fazer é trocar o x e y coordenadas para a rede.
Infelizmente, como as três etapas acima são combinadas em uma única
Y
(ouZ
) interna , precisamos desfazer os mapeamentos ℤ → ℕ ou ℕ → ℤ . No entanto, ao fazer isso, podemos salvar alguns bytes usando diretamente os mapeamentos ℕ + → ℤ ou ℤ → ℕ + , para cuidar do erro de um por um na tabela. Então, aqui está o algoritmo inteiro:Com isso fora do caminho, podemos olhar para o programa:
Isso é simplesmente uma estrutura para programas aritméticos lineares com entrada e saída inteiras.
fonte
Geléia , 8 bytes
Experimente online!
Porta da minha resposta MATL.
fonte
MATL ,
1511 bytesExperimente online!
Isso usa a fórmula
fonte
Oitava ,
7168 bytes3 bytes salvos graças a Conor O'Brien .
Isso não funciona para entradas grandes devido a limitações de memória.
Experimente online!
Explicação
Considere entrada
n = 4
. O código primeiro cria a matrizEm seguida, ele substitui entradas diferentes de zero, a fim de coluna-major (para baixo, em seguida, do outro lado) por
1
,2
,3
...:Em seguida, vira a matriz verticalmente:
Finalmente, ele assume o
n
-ésimo valor diferente de zero na ordem da coluna principal, que neste caso é6
.fonte
e
é genial! Você definitivamente deve publicá-lo como resposta, juntamente com outras sugestões muito boas. Quantoans =
, eu nunca tenho certeza que ele é válido ou nãoHaskell , 31 bytes
Experimente online!
Esta resposta apenas usa a fórmula. É a resposta menos interessante aqui, mas também é a mais golfista.
Haskell ,
383634 bytesExperimente online!
(!0)
é a função sem ponto em que estamos preocupados.Explicação
Deixe-me começar dizendo que estou muito feliz com esta resposta.
A idéia básica aqui é que, se removermos o maior número triangular menor que a nossa entrada, podemos revertê-lo e adicionar o número triangular novamente. Então, definimos um operador
!
, pegamos!
nossa entrada regularx
, mas também pegamos um número extray
.y
controla o tamanho do número triangular crescente. Sex>y
queremos recurse, diminuímosx
pory
e aumentary
a um. Então calculamos(x-y)!(y+1)
e adicionamosy+1
a ele. Sex<=y
chegamos ao nosso caso base, para reverterx
a posição na linha do triângulo, retornamos1-x
.Haskell , 54 bytes
Experimente online!
(!!)$0:(>>=)[1..]f
é uma função sem pontoExplicação
A primeira coisa que nos preocupa é
f
,f
é uma função que pegax
e retorna ax
linha th do triângulo em sentido inverso. Isso é feito calculando primeiro ox-1
número triangular nd e atribuindo-o au
.u<-div(x^2-x)2
. Em seguida, retornamos a lista[u+x,u+x-1..u+1]
.u+x
é ox
th número triangular e o primeiro número na linha,u+x-1
é um a menos que isso e o segundo número na linhau+1
é um a mais que o último número triangular e, portanto, o último número na linha.Uma vez que temos
f
, formamos uma lista(>>=)[1..]f
, que é um achatamento do triângulo. Adicionamos zero à frente0:
para que nossas respostas não sejam compensadas por uma e fornecemos à nossa função de indexação(!!)
.Haskell , 56 bytes
Experimente online!
Este é 2 bytes mais longo, mas um pouco mais elegante na minha opinião.
fonte
C (gcc) , 48 bytes
Experimente online!
Provavelmente abaixo do ideal, mas estou muito feliz com este. Usa o fato de que
NTF N = T N + A057944 ( N ) - N + 1
(Se eu escrevi a fórmula corretamente, isso é.)
fonte
05AB1E , 30 bytes
Experimente online!
fonte
Casca , 6 bytes
Experimente online!
Explicação
fonte
tinylisp , 78 bytes
Define uma função
f
que executa o mapeamento. Experimente online!Ungolfed
Encontramos o menor número triangular que é maior ou igual ao número de entrada, bem como em qual linha do triângulo nosso número está. Desses, podemos calcular a versão invertida do número.
A função principal
flip
simplesmente chama a função auxiliar_flip
a partir da linha superior.fonte
05AB1E , 9 bytes
Experimente online!
Explicação
Infelizmente, o achatamento de matrizes não lida muito bem com listas maiores.
Ao custo de 1 byte, poderíamos fazer · t2z + ïn¹-> usando a fórmula matemática
floor(sqrt(2*n)+1/2)^2 - n + 1
encontrada no OEIS .fonte
Lote, 70 bytes
Usa um loop para encontrar o índice do número triangular pelo menos tão grande quanto
n
.fonte
PHP, 35 bytes
Mesma fórmula usada na abordagem de Arnaulds
fonte
C #,
4644 bytesPorto a solução da @ Arnauld . Obrigado!
fonte
APL (Dyalog), 27 bytes
Eu tenho duas soluções no mesmo bytecount.
Um trem:
Experimente online!
E um dfn:
Experimente online!
Ambas as soluções primeiro criam o triângulo invertido e depois extraem o elemento no índice indicado pelo argumento (
1
baseado em).fonte
J, 25 bytes
Como explicação, considere
f(n) = n(n+1)/2
.f(r)
, dada a linhar
, retorna o número mais à esquerda dar
quinta linha do triângulo espelhado. Agora considereg(n) = ceiling[f⁻¹(n)]
.g(i)
, dado o índicei
, retorna a linha na qual o índice i é encontrado. Em seguida,f(g(n))
retorna o número mais à esquerda da linha na qual o índice n é encontrado. Então,h(n) = f(g(n)) - (n - f(g(n)-1)) + 1
é a resposta para o problema acima.Simplificando, entendemos
h(n) = [g(n)]² - n + 1 = ceiling[(-1 + sqrt(1 + 8n))/2]² - n + 1
.Pela aparência da fórmula de @ Arnauld, parece que:
ceiling[(-1 + sqrt(1 + 8n))/2] = floor[1/2 + sqrt(2n)]
.fonte
Pyt ,
1312 bytesAbordagem do porto de Arnauld
fonte