Dodanie piramidy do góry nogami… ODWRÓCONE!

22

Dodawanie do góry nogami piramidy polega na pobieraniu listy liczb i sukcesywnym dodawaniu ich razem, aż do osiągnięcia jednej liczby.

Po podaniu liczb 2, 1, 1następuje następujący proces:

 2   1   1
   3   2 
     5

To kończy się liczbą 5.


TWOJE ZADANIE

Biorąc pod uwagę prawą stronę Upside-Down Pyramid (Rosnąco), napisz program lub funkcję, która zwróci oryginalną listę.

Nowe dodatkowe wyzwanie : spróbuj to zrobić w mniej niż O (n ^ 2)

PRZYKŁAD

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

UWAGA: Piramida do góry nogami nigdy nie będzie pusta i zawsze będzie składać się WYŁĄCZNIE z dodatnich liczb całkowitych.

Wycie
źródło
6
Witamy w PP&CG! To wyzwanie jest przyzwoite, ale można je poprawić. Radzę najpierw opublikować swoje wyzwania w piaskownicy, aby poprawić post, zanim zostanie on włączony do głównego.
Tau
13
Swobodny wgląd, że nie mogę znaleźć języka, w którym jest on krótszy:
fa([za,b,do,re,mi])=[1-46-4101-3)3)-1001-2)10001-100001][zabdoremi]
Lynn
4
Tylko do waszej wiadomości, to jest to samo co kata CodeWars .
ggorlen
6
@ggorlen wiem. To ja zrobiłem kata :)
Whimpers
8
Try doing this in less than O(n)z pewnością nie można przydzielić tablicy o rozmiarze n ani zmienić w niej elementów O (n) szybciej niż złożoność O (n)?
mój zaimek to monicareinstate

Odpowiedzi:

17

JavaScript (ES6),  62 58 49  46 bajtów

Zaoszczędź 3 bajty dzięki @Oliver

Zwraca listę jako ciąg rozdzielany przecinkami.

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

Wypróbuj online!

Skomentował

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
źródło
@Oliver, tak
Kudłaty
6

TI-BASIC, 54 bajty

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

Dane wejściowe to lista prawej strony trójkąta w Ans, jak opisano w wyzwaniu.
Wyjście to górny rząd wspomnianego trójkąta.

Przykłady:

{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}

Objaśnienie:
To rozwiązanie narusza fakt, że trójkąt utworzony przy użyciu prawej strony trójkąta, gdy początkiem jest zmiana w każdym elemencie.

Innymi słowy,

2 1 1
 3 2
  5

staje się:

5 2 1
 3 1
  2

Tak więc powstała lista jest prawą stroną tego nowego trójkąta, którą można utworzyć, ustawiając ostatni element na indeks długości jego listy nadrzędnej na liście wynikowej.

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"

Uwaga: TI-BASIC jest językiem tokenizowanym. Liczba znaków nie jest równa liczbie bajtów.

Tau
źródło
4

Galaretka , 6 bajtów

ṚIƬZḢṚ

Monadyczny link akceptujący listę liczb całkowitych, która daje listę liczb całkowitych.

Wypróbuj online!

W jaki sposób?

Buduje cały trójkąt, a następnie wyodrębnia wymagane elementy.

Ṛ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
źródło
Miał prawie identyczne rozwiązanie, ale Uzamiast s !
Nick Kennedy
IƬUZḢAdziałałby również z danym pytaniem; Zastanawiam się, czy gdzieś jest bajt oprócz…
Jonathan Allan
ạƝƬZṪ€też działa, ale znów jest szóstką.
Nick Kennedy
Tak, zauważyłem ten wariant; Teraz mam mniej nadziei.
Jonathan Allan
Właśnie opublikowałem 5-bajtowy, ale to trochę inne niż twoje podejście do części po budowie piramidy.
Erik the Outgolfer
4

MathGolf , 14 11 bajtów

xÆ‼├│?;∟;]x

Wypróbuj online!

Wyjaśnienie

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
źródło
3

Python 2 , 56 bajtów

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

Funkcja rekurencyjna przyjmująca listę dodatnich liczb całkowitych, która zwraca listę liczb całkowitych nieujemnych.

Wypróbuj online!

Jonathan Allan
źródło
3

Galaretka , 5 bajtów

_ƝƬa/

Wypróbuj online!

Możemy założyć, że cała piramida jest dodatnia, więc możemy użyć operacji && zamiast operacji „właściwej”.

Erik the Outgolfer
źródło
3

Pari / GP , 36 bajtów

Na podstawie komentarza @Lynn :

fa([za,b,do,re,mi])=[1-46-4101-3)3)-1001-2)10001-100001][zabdoremi]

Pari / GP ma wbudowaną matrycę Pascal, a jej odwrotność jest dokładnie taką, jakiej potrzebujemy:

[100001100012)10013)3)1014641]-1=[10000-110001-2)100-13)-3)101-46-41]

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

Wypróbuj online!

alephalpha
źródło
3

R , 69 67 bajtów

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

Wypróbuj online!

Zwraca wektor kolumny.

-2 bajty dzięki Kirill L.

Również na podstawie komentarza Lynn :

fa([za,b,do,re,mi])=[1-46-4101-3)3)-1001-2)10001-100001][zabdoremi]

Jest dłuższy niż druga odpowiedź R, ale było to interesujące podejście do gry w golfa.

Giuseppe
źródło
2

JavaScript (ES6), 127 bajtów

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}

Oryginalny kod

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;
}

Och, straciłem ... dużo ... do poprzedniej odpowiedzi ...

Naruyoko
źródło
2

05AB1E , 12 11 bajtów

R.¥.Γ¥}¨ζнR

Port odpowiedzi galaretki @JonathanAllan , chociaż jestem galaretką na temat wygodniejszych wbudowań Jelly w tym przypadku. ;)
-1 bajt dzięki @Emigna .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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
źródło
2
Możesz zapisać bajt R.¥.Γ¥}¨, zaczynając od listy, której delta jest wejściem.
Emigna
@Emigna Ah, undelta w pętli z deltami, aby zapisać bajt na prepend. :) Dzięki!
Kevin Cruijssen
2

R , 55 63 55 53 bajtów

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

Wypróbuj online!

-2 bajty dzięki Giuseppe.

Kirill L.
źródło
2

Perl 6 , 37 bajtów

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

Wypróbuj online!

Wielokrotnie zmniejsza się przez odejmowanie elementarne, a następnie zwraca ostatnią liczbę każdej listy w odwrotnej kolejności.

Wyjaśnienie:

{                                  }  # 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
źródło
1

Python 2 , 78 bajtów

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

Wypróbuj online!

TFeld
źródło
1

Węgiel drzewny , 19 bajtów

Fθ«PI§θ±¹↑UMθ⁻§θ⊖λκ

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

Fθ«

Zapętlaj raz dla każdego terminu na oryginalnej liście.

PI§θ±¹↑

Wydrukuj ostatni termin na liście, ale przesuń kursor na początek poprzedniego wiersza, aby wyprowadzić terminy w odwrotnej kolejności.

UMθ⁻§θ⊖λκ

Oblicz delty, wstawiając na początku wartość fikcyjną, abyśmy mogli użyć operacji, która nie zmienia długości listy.

Neil
źródło
1

Attache , 29 bajtów

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

Wypróbuj online!

Wystarczy iterować Deltafunkcję, aż będzie pusta. Znacznie krótszy niż bardzo pełne PeriodicStepsrozwiązanie ...

Conor O'Brien
źródło
1

C, 76 bajtów

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);}  

wejście : (*a = pointer to array, n = last element's index of that array)
wyjście :return int* = output

Wyjaśnienie
przechodzi od prawej do góry, ponieważ ostatnie elementy są takie same zarówno na wejściu, jak i na wyjściu, funkcja wewnątrz pętli po prostu znajduje kolejne wyższe liczby w trójkącie, stopniowo sięgając do góry, pozostawiając odpowiedź nienaruszoną na końcu.

bez golfa (z 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
źródło
1

Japt , 11 9 bajtów

Nc¡=äa
yÌ

Spróbuj

2 bajty zapisane dzięki Oliverowi.

12 11 bajtów

_äa}hUÊN yÌ

Spróbuj

1 bajt zapisany dzięki Oliverowi.

Kudłaty
źródło
2
9 bajtów i 10 bajtów
Oliver
@Oliver, nie myślenie o użyciu y(f)jest wystarczająco złe, ale całkowite zapomnienie o nowej linii jest niewybaczalne! Wkrótce się zaktualizuje. Dzięki :)
Kudłaty
1

Julia 0.6 , 44 bajty

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

Wypróbuj online!

Ta sama zasada iteracyjna jak moja odpowiedź R.

Julia 0.6 , 55 bajtów

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

Wypróbuj online!

@ Algorytm Lynna (odwrotność macierzy Pascala pomnożonej przez dane wejściowe).

Kirill L.
źródło