A adição de cabeça para baixo da pirâmide é o processo de pegar uma lista de números e adicioná-los consecutivamente até chegar a um número.
Quando dados os números 2, 1, 1
, ocorre o seguinte processo:
2 1 1
3 2
5
Isso termina no número 5
.
SUA TAREFA
Dado o lado direito de uma pirâmide de cabeça para baixo (crescente), escreva um programa ou função que retorne a lista original.
Novo desafio extra : tente fazer isso em menos de O (n ^ 2)
EXEMPLO
f([5, 2, 1]) => [2, 1, 1]
f([84,42,21,10,2]) => [4,7,3,8,2]
NOTA: A pirâmide de cabeça para baixo nunca estará vazia e sempre consistirá SOMENTE em números inteiros positivos.
code-golf
math
fastest-algorithm
algorithm
Whimpers
fonte
fonte
Try doing this in less than O(n)
certamente é impossível alocar uma matriz de tamanho n ou alterar itens de O (n) mais rapidamente que a complexidade de O (n)?Respostas:
JavaScript (ES6),
62 58 4946 bytesGuardado 3 bytes graças a @Oliver
Retorna a lista como uma sequência separada por vírgula.
Experimente online!
Comentado
fonte
Haskell , 22 bytes
Experimente online!
fonte
Haskell, 42 bytes
Experimente online!
fonte
TI-BASIC, 54 bytes
Entrada é a lista do lado direito do triângulo
Ans
, conforme descrito no desafio.Saída é a linha superior do referido triângulo.
Exemplos:
Explicação:
Esta solução abusa do fato de que o triângulo se formou usando o lado direito do triângulo quando o início acaba sendo a alteração em cada elemento.
Em outras palavras,
torna-se:
Portanto, a lista resultante é o lado direito desse novo triângulo, que pode ser formado definindo o último elemento no índice do comprimento da lista pai na lista resultante.
Nota: TI-BASIC é um idioma tokenizado. Contagem de caracteres não é igual à contagem de bytes.
fonte
Gelatina , 6 bytes
Um link monádico que aceita uma lista de números inteiros que produz uma lista de números inteiros.
Experimente online!
Quão?
Constrói o triângulo inteiro e extrai os elementos necessários.
fonte
U
s em vez deṚ
!IƬUZḢA
também trabalharia com a pergunta dada; Gostaria de saber se existe um byte salvar em algum lugar ...ạƝƬZṪ€
funciona também, mas é novamente um seis.MathGolf ,
1411 bytesExperimente online!
Explicação
fonte
Python 2 , 56 bytes
Uma função recursiva que aceita uma lista de números inteiros positivos que retorna uma lista de números inteiros não negativos.
Experimente online!
fonte
Geléia , 5 bytes
Experimente online!
Podemos assumir que toda a pirâmide é positiva, portanto, podemos usar uma operação && em vez de uma operação "correta".
fonte
Pari / GP , 36 bytes
Com base no comentário de @Lynn :
O Pari / GP possui um built-in para a matriz Pascal, e seu inverso é exatamente a matriz que precisamos:
Experimente online!
fonte
R,
6967 bytesTry it online!
Returns a column vector.
-2 bytes thanks to Kirill L.
Also based on Lynn's comment:
It's longer than the other R answer, but it was an interesting approach to take and try to golf.
fonte
Javascript (ES6), 127 bytes
Original code
Oh, I lost like... a lot... to the previous answer...
fonte
Wolfram Language (Mathematica), 57 bytes
Try it online!
fonte
05AB1E,
1211 bytesPort of @JonathanAllan's Jelly answer, although I'm jelly about Jelly's more convenient builtins in this case. ;)
-1 byte thanks to @Emigna.
Try it online or verify all test cases.
Explanation:
fonte
R.¥.Γ¥}¨
by starting from the list whose delta is the input.R,
55635553 bytesTry it online!
-2 bytes thanks to Giuseppe.
fonte
Perl 6, 37 bytes
Try it online!
Repeatedly reduces by elementwise subtraction, and then returns the last number of each list in reverse.
Explanation:
fonte
Python 2, 78 bytes
Try it online!
fonte
C# (Visual C# Interactive Compiler), 164 bytes
Try it online!
fonte
Charcoal, 19 bytes
Try it online! Link is to verbose version of code. Explanation:
Loop once for each term in the original list.
Print the last term in the list, but move the cursor to the beginning of the previous line, so that the terms are output in reverse order.
Compute the deltas, inserting a dummy value at the beginning so that we can use an operation that doesn't change the length of the list.
fonte
APL+WIN, 34 or 28 bytes
Try it online! Courtesy of Dyalog Classic
Prompts for right side vector.
or implementing @Lynn's approach:
Try it online!Courtesy of Dyalog Classic
Prompts for right side vector.
fonte
Attache, 29 bytes
Try it online!
Simply iterates the
Delta
function until its empty. Much shorter than the very verbosePeriodicSteps
solution...fonte
C, 76 bytes
input :
(*a = pointer to array, n = last element's index of that array)
output :
return int* = output
Explanation
going from right side to up, as the last elements are same in both input and output the loop inside function simply finds next higher numbers in the triangle gradually reaching to the top leaving the answer intact in the end.
ungolfed(from C++)
fonte
Japt,
119 bytesTry it
2 bytes saved thanks to Oliver.
1211 bytesTry it
1 byte saved thanks to Oliver.
fonte
y(f)
is bad enough, but completely forgetting the newline is unforgivable! Will update shortly. Thanks :)Julia 0.6, 44 bytes
Try it online!
Same iterative principle as my R answer.
Julia 0.6, 55 bytes
Try it online!
@Lynn's algorithm (inverse of Pascal matrix multiplied by input).
fonte