L'ajout de pyramide à l'envers est le processus consistant à prendre une liste de nombres et à les additionner consécutivement jusqu'à ce que vous atteigniez un nombre.

Lorsque les chiffres sont donnés, le 2, 1, 1processus suivant se produit:

 2   1   1
   3   2 
     5

Cela se termine par le nombre 5.

TA TÂCHE

Étant donné le côté droit d'une pyramide à l'envers (ascendant), écrivez un programme ou une fonction qui renverra la liste d'origine.

Nouveau défi supplémentaire : essayez de faire cela en moins de O (n ^ 2)

EXEMPLE

f([5, 2, 1]) => [2, 1, 1]
f([84,42,21,10,2]) => [4,7,3,8,2]

REMARQUE: la pyramide à l'envers ne sera jamais vide et sera toujours composée uniquement d'entiers positifs.

code-golf math fastest-algorithm algorithm Gémissements
la source

6

Bienvenue chez PP&CG! Ce défi est décent, mais il pourrait être amélioré. Je recommanderais de publier vos défis dans le bac à sable pour améliorer le message avant qu'il ne soit mis en place.

Tau

13

Aperçu gratuit que je ne trouve pas de langue dans laquelle il est plus court:

f ([a, b, c, d, e]) = [\begin{matrix} 1 & - 4 & 6 & - 4 & 1 \\ 0 & 1 & - 3 & 3 & - 1 \\ 0 & 0 & 1 & - 2 & 1 \\ 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}] \cdot [\begin{matrix} a \\ b \\ c \\ d \\ e \end{matrix}]

$f([a,b,c,d,e]) = \begin{bmatrix} 1&-4&6&-4&1 \\ 0&1&-3&3&-1 \\ 0&0&1&-2&1 \\ 0&0&0&1&-1 \\ 0&0&0&0&1 \end{bmatrix} \cdot \begin{bmatrix}a\\b\\c\\d\\e\end{bmatrix}$

Lynn

4

Juste pour info, c'est la même chose que le kata CodeWars .

ggorlen

6

@ggorlen je sais. Je suis celui qui a fait le kata :)

Whimpers

8

Try doing this in less than O(n)il est sûrement impossible d'allouer un tableau de taille n ou de modifier O (n) éléments plus rapidement que la complexité O (n)?

mon pronom est monicareinstate

17

JavaScript (ES6), 62 58 49 46 octets

Enregistré 3 octets grâce à @Oliver

Renvoie la liste sous forme de chaîne séparée par des virgules.

f=a=>+a||f(a.map(n=>a-(a=n),a=a.shift()))+[,a]

Essayez-le en ligne!

Commenté

f = a =>              // f = recursive function taking the input list a[]
  +a                  // if a[] consists of a single positive integer:
                      //   stop recursion and return this integer
  ||                  // else:
    f(                //   do a recursive call to f:
      a.map(n =>      //     for each value n in a[]:
        a - (a = n),  //       yield the difference between the previous value and n
                      //       and update a to n
        a = a.shift() //       start by removing the first element and saving it in a
                      //       (because of the recursion, it's important here to reuse
                      //       a variable which is defined in the scope of f)
      )               //     end of map()
    )                 //   end of recursive call
    + [, a]           //   append the last entry from a[]

Arnauld
la source

@Oliver, oui

Shaggy

8

Haskell , 22 octets

foldl(flip$scanr(-))[]

Essayez-le en ligne!

xnor
la source

7

Haskell, 42 octets

f[]=[]
f a=f(zipWith(-)a$tail a)++[last a]

Essayez-le en ligne!

nimi
la source

6

TI-BASIC, 54 octets

Ans→L₁:dim(L₁→dim(L₂:While 1-Ans:L₁(Ans→L₂(Ans:-ΔList(L₁→L₁:dim(Ans:End:L₁(Ans→L₂(Ans:L₂

L'entrée est la liste du côté droit du triangle Ans, comme décrit dans le défi.
La sortie est la ligne supérieure dudit triangle.

Exemples:

{5,2,1
         {5 2 1}
prgmCDGF19
         {2 1 1}
{84,42,21,10,2
 {84 42 21 10 2}
prgmCDGF19
     {4 7 3 8 2}

Explication:
Cette solution abuse du fait que le triangle formé en utilisant le côté droit du triangle comme départ finit par être le changement dans chaque élément.

En d'autres termes,

2 1 1
 3 2
  5

devient:

5 2 1
 3 1
  2

Ainsi, la liste résultante est le côté droit de ce nouveau triangle, qui peut être formé en définissant le dernier élément sur l'index de la longueur de sa liste parent dans la liste résultante.

Ans→L₁          ;store the input list in L₁
dim(L₁→dim(L₂   ;set the length of L₂ to the length of L₁
While 1-Ans     ;while the L₁'s length is not 1
L₁(Ans→L₂(Ans   ;set the last element of L₁ to the corresponding index in L₂
-ΔList(L₁→L₁    ;get the change in each element, then negate
                ; (elements are in descending order so the change in each
                ;  element will be negative)
                ; and store the resulting list in L₁
dim(Ans         ;leave the length of L₁ in "Ans"
End
L₁(Ans→L₂(Ans   ;set the element again
                ; (needed for final step)
L₂              ;leave L₂ in "Ans"
                ;implicit print of "Ans"

Remarque: TI-BASIC est un langage à jetons. Le nombre de caractères n'est pas égal au nombre d'octets.

Tau
la source

4

Gelée , 6 octets

ṚIƬZḢṚ

Un lien monadique acceptant une liste d'entiers qui donne une liste d'entiers.

Essayez-le en ligne!

Comment?

Construit tout le triangle puis extrait les éléments requis.

ṚIƬZḢṚ - Link: list of integers          e.g.  [84,42,21,10,2]
Ṛ      - reverse                               [2,10,21,42,84]
  Ƭ    - collect & apply until a fixed point:
 I     -   incremental differences            [[2,10,21,42,84],[8,11,21,42],[3,10,21],[7,11],[4],[]]
   Z   - transpose                            [[2,8,3,7,4],[10,11,10,11],[21,21,21],[42,42],[84]]
    Ḣ  - head                                  [2,8,3,7,4]
     Ṛ - reverse                               [4,7,3,8,2]

Jonathan Allan
la source

Avait une solution presque identique mais avec Us au lieu de Ṛ!

Nick Kennedy

IƬUZḢAfonctionnerait aussi avec la question donnée; Je me demande s'il y a un octet sauf quelque part ...

Jonathan Allan

ạƝƬZṪ€fonctionne aussi mais est à nouveau un six.

Nick Kennedy

Oui, j'ai remarqué cette variante; J'ai moins d'espoir maintenant.

Jonathan Allan

Je viens de poster un 5 octets, mais c'est un peu différent de votre approche concernant la partie après la construction de la pyramide.

Erik the Outgolfer

4

MathGolf , 14 11 octets

xÆ‼├│?;∟;]x

Essayez-le en ligne!

Explication

x             reverse int/array/string
 Æ     ∟      do while true without popping using 5 operators
  ‼           apply next 2 operators to TOS
   ├          pop from left of list
    │         get differences of list
     ?        rot3
      ;       discard TOS (removes rest from ├ command)
              loop ends here
        ;     discard TOS (removes empty array from stack)
         ]    wrap stack in array
          x   reverse array

maxb
la source

3

Python 2 , 56 octets

f=lambda a:a and f([l-r for l,r in zip(a,a[1:])])+a[-1:]

Une fonction récursive acceptant une liste d'entiers positifs qui renvoie une liste d'entiers non négatifs.

Essayez-le en ligne!

Jonathan Allan
la source

3

Gelée , 5 octets

_ƝƬa/

Essayez-le en ligne!

Nous pouvons supposer que toute la pyramide est positive, nous pouvons donc utiliser une opération && au lieu d'une opération "correcte".

Erik le Outgolfer
la source

3

Pari / GP , 36 octets

D'après le commentaire de @Lynn :

$f ([a, b, c, d, e]) = [\begin{matrix} 1 & - 4 & 6 & - 4 & 1 \\ 0 & 1 & - 3 & 3 & - 1 \\ 0 & 0 & 1 & - 2 & 1 \\ 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}] \cdot [\begin{matrix} a \\ b \\ c \\ d \\ e \end{matrix}]$ $f([a,b,c,d,e]) = \begin{bmatrix} 1&-4&6&-4&1 \\ 0&1&-3&3&-1 \\ 0&0&1&-2&1 \\ 0&0&0&1&-1 \\ 0&0&0&0&1 \end{bmatrix} \cdot \begin{bmatrix}a\\b\\c\\d\\e\end{bmatrix}$

Pari / GP a un intégré pour la matrice Pascal, et son inverse est exactement la matrice dont nous avons besoin:

{[\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 \\ 1 & 3 & 3 & 1 & 0 \\ 1 & 4 & 6 & 4 & 1 \end{matrix}]}^{- 1} = [\begin{matrix} 1 & 0 & 0 & 0 & 0 \\ - 1 & 1 & 0 & 0 & 0 \\ 1 & - 2 & 1 & 0 & 0 \\ - 1 & 3 & - 3 & 1 & 0 \\ 1 & - 4 & 6 & - 4 & 1 \end{matrix}]

$\begin{bmatrix} 1&0&0&0&0 \\ 1&1&0&0&0 \\ 1&2&1&0&0 \\ 1&3&3&1&0 \\ 1&4&6&4&1 \end{bmatrix}^{-1} = \begin{bmatrix} 1&0&0&0&0 \\ -1&1&0&0&0 \\ 1&-2&1&0&0 \\ -1&3&-3&1&0 \\ 1&-4&6&-4&1 \end{bmatrix}$

a->r=Vecrev;r(r(a)/matpascal(#a-1)~)

Essayez-le en ligne!

alephalpha
la source

3

R , 69 67 octets

function(n,x=sum(n|1):1-1,`[`=outer)(x[x,choose]*(-1)^x[x,"+"])%*%n

Essayez-le en ligne!

Renvoie un vecteur de colonne.

-2 octets grâce à Kirill L.

Également basé sur le commentaire de Lynn :

$f ([a, b, c, d, e]) = [\begin{matrix} 1 & - 4 & 6 & - 4 & 1 \\ 0 & 1 & - 3 & 3 & - 1 \\ 0 & 0 & 1 & - 2 & 1 \\ 0 & 0 & 0 & 1 & - 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}] \cdot [\begin{matrix} a \\ b \\ c \\ d \\ e \end{matrix}]$ $f([a,b,c,d,e]) = \begin{bmatrix} 1&-4&6&-4&1 \\ 0&1&-3&3&-1 \\ 0&0&1&-2&1 \\ 0&0&0&1&-1 \\ 0&0&0&0&1 \end{bmatrix} \cdot \begin{bmatrix}a\\b\\c\\d\\e\end{bmatrix}$

C'est plus long que l'autre réponse R, mais c'était une approche intéressante à adopter et à essayer de jouer au golf.

Giuseppe
la source

2

Javascript (ES6), 127 octets

f=a=>{for(e=[a],a=[a[l=a.length-1]],i=0;i<l;i++){for(e.push(g=[]),j=-1;j<l;)g.push(e[i][j]-e[i][++j]);r.unshift(g[j])}return r}

Code d'origine

function f(a){
  var e=[a];
  var r=[a[a.length-1]];
  for (var i=1;i<a.length;i++){
    var g=[];
    for (var j=0;j<a.length;j++){
      g.push(e[i-1][j-1]-e[i-1][j]);
    }
    e.push(g);
    r.unshift(g[j-1]);
  }
  return r;
}

Oh, j'ai perdu comme ... beaucoup ... à la réponse précédente ...

Naruyoko
la source

2

Wolfram Language (Mathematica) , 57 octets

(r=Reverse)[#&@@@Most@NestList[Differences,r@#,Tr[1^#]]]&

Essayez-le en ligne!

J42161217
la source

2

05AB1E , 12 11 octets

R.¥.Γ¥}¨ζнR

Port de la réponse Jelly de @JonathanAllan , bien que je sois jelly sur les fonctionnalités intégrées plus pratiques de Jelly dans ce cas. ;)
-1 octet grâce à @Emigna .

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

R            # Reverse the (implicit) input-list
             #  i.e. [16,7,4,3] → [3,4,7,16]
 .¥          # Undelta it (with leading 0)
             #  → [0,3,7,14,30]
   .Γ }      # Continue until the result no longer changes, and collect all steps:
     ¥       #  Get the deltas / forward differences of the current list
             #  → [[3,4,7,16],[1,3,9],[2,6],[4],[]]
       ¨     # Remove the trailing empty list
             #  → [[3,4,7,16],[1,3,9],[2,6],[4]]
        ζ    # Zip/transpose; swapping rows/column (with space as default filler)
             #  → [[3,1,2,4],[4,3,6," "],[7,9," "," "],[16," "," "," "]]
         н   # Only leave the first inner list
             #  → [3,1,2,4]
          R  # Revert it back
             #  → [4,2,1,3]
             # (after which it's output implicitly as result)

Kevin Cruijssen
la source

2

Vous pouvez enregistrer un octet avec R.¥.Γ¥}¨en commençant par la liste dont le delta est l'entrée.

Emigna

@Emigna Ah, undelta dans une boucle avec deltas pour enregistrer un octet sur le préfixe. :) Merci!

Kevin Cruijssen

2

R , 55 63 55 53 octets

x=scan();for(i in sum(1|x):1){F[i]=x[i];x=-diff(x)};F

Essayez-le en ligne!

-2 octets grâce à Giuseppe.

Kirill L.
la source

2

Perl 6 , 37 octets

{[R,]($_,{@(.[]Z-.skip)}...1)[*;*-1]}

Essayez-le en ligne!

Réduit de façon répétée par soustraction élément par élément, puis retourne le dernier numéro de chaque liste en sens inverse.

Explication:

{                                  }  # Anonymous code block
      $_,               ...   # Create a sequence starting from the input
         {             }      # Where each element is
            .[]Z-.skip          # Each element minus the next element
          @(          )         # Arrayified
                           1  # Until the list has one element left
 [R,]                                # Reverse the sequence
     (                     )[*;   ]  # For every list
                               *-1   # Take the last element

Jo King
la source

1

Python 2 , 78 octets

lambda n,*a:R(lambda r,v:R(lambda x,w:x+[w-x[-1]],r,[v]),a,[n])[::-1]
R=reduce

Essayez-le en ligne!

TFeld
la source

1

C # (Visual C # Interactive Compiler) , 164 octets

a=>{int x=a.Length;var l=new int[x][];for(int i=0;i<x;i++){l[i]=new int[x];l[i][0]=a[i];for(int j=0;j<i;j++)l[i][j+1]=l[i-1][j]-l[i][j];}return l.Last().Reverse();}

Essayez-le en ligne!

Innat3
la source

1

Fusain , 19 octets

Ｆθ«ＰＩ§θ±¹↑ＵＭθ⁻§θ⊖λκ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

Ｆθ«

Boucle une fois pour chaque terme dans la liste d'origine.

ＰＩ§θ±¹↑

Imprimez le dernier terme de la liste, mais déplacez le curseur au début de la ligne précédente, afin que les termes soient sortis dans l'ordre inverse.

ＵＭθ⁻§θ⊖λκ

Calculez les deltas, en insérant une valeur fictive au début afin que nous puissions utiliser une opération qui ne change pas la longueur de la liste.

Neil
la source

1

APL + WIN, 34 ou 28 octets

v←⊂⌽⎕⋄1↓⌽↑¨⍎∊'v',(∊⍴¨v)⍴⊂',-2-/¨v'

Essayez-le en ligne! Gracieuseté de Dyalog Classic

Demande le vecteur du côté droit.

ou en mettant en œuvre l'approche de @ Lynn:

0⍕⌽(⌹⍉n∘.!n←0,⍳¯1+⍴n)+.×⌽n←⎕

Essayez-le en ligne avec l'aimable autorisation de Dyalog Classic

Demande le vecteur du côté droit.

Graham
la source

1

Attaché , 29 octets

{y.=Delta@-_If[_,$@y'_@-1,y]}

Essayez-le en ligne!

Itère simplement la Deltafonction jusqu'à ce qu'elle soit vide. Beaucoup plus court que la PeriodicStepssolution très verbeuse ...

Conor O'Brien
la source

1

C, 76 octets

i=0;int*f(int*a,int n){for(;i<n;a[i++]=a[i]-a[i+1]);if(!n)return a;f(a,n-1);}

entrée : (*a = pointer to array, n = last element's index of that array)
sortie :return int* = output

Explication
allant du côté droit vers le haut, car les derniers éléments sont les mêmes en entrée et en sortie, la fonction de boucle à l'intérieur trouve simplement les nombres supérieurs suivants dans le triangle atteignant progressivement vers le haut, laissant la réponse intacte à la fin.

non golfé (de C ++)

#include <iostream>
#define SIZE_F 5

int*recFind(int*a, int n) {
    int i = 0;
    while (i < n)
        a[i++] = a[i] - a[i+1];
    if (!n) return a;
        recFind(a, n - 1);
}
int main()
{
    int first[SIZE_F],*n;
    for (int i = 0; i < SIZE_F; i++)
        std::cin >> first[i];

    n = recFind(first, SIZE_F - 1);//size - 1
    for (int i = 0; i < SIZE_F; i++)
        std::cout << n[i];
}

Mukul Kumar
la source

1

Japt , 11 9 octets

Nc¡=äa
yÌ

Essayez-le

2 octets enregistrés grâce à Oliver.

12 11 octets

_äa}hUÊN yÌ

Essayez-le

1 octet économisé grâce à Oliver.

Hirsute
la source

2

9 octets et 10 octets

Oliver

@Oliver, ne pas penser à utiliser y(f)est déjà assez mauvais, mais oublier complètement la nouvelle ligne est impardonnable! Mettra à jour sous peu. Merci :)

Shaggy

1

Julia 0,6 , 44 octets

x->reverse([(j=x[end];x=-diff(x);j)for i=x])

Essayez-le en ligne!

Même principe itératif que ma réponse R.

Julia 0,6 , 55 octets

x->inv([binomial(i,j)for i=(l=length(x)-1:-1:0),j=l])*x

Essayez-le en ligne!

@ Algorithme de Lynn (inverse de la matrice Pascal multipliée par entrée).

Kirill L.
la source

Ajout d'une pyramide à l'envers… INVERSE!

TA TÂCHE

EXEMPLE

Réponses:

JavaScript (ES6), 62 58 49 46 octets

Commenté

Haskell , 22 octets

Haskell, 42 octets

TI-BASIC, 54 octets

Gelée , 6 octets

Comment?

MathGolf , 14 11 octets

Explication

Python 2 , 56 octets

Gelée , 5 octets

Pari / GP , 36 octets

R , 69 67 octets

Javascript (ES6), 127 octets

Wolfram Language (Mathematica) , 57 octets

05AB1E , 12 11 octets

R , 55 63 55 53 octets

Perl 6 , 37 octets

Explication:

Python 2 , 78 octets

C # (Visual C # Interactive Compiler) , 164 octets

Fusain , 19 octets

APL + WIN, 34 ou 28 octets

Attaché , 29 octets

C, 76 octets

Japt , 11 9 octets

12 11 octets

Julia 0,6 , 44 octets

Julia 0,6 , 55 octets