Penambahan Piramida Terbalik ... Terbalik!

22

Penambahan Piramida Terbalik adalah proses mengambil daftar angka dan menambahkannya secara berurutan hingga Anda mencapai satu angka.

Ketika diberi nomor 2, 1, 1proses berikut terjadi:

 2   1   1
   3   2 
     5

Ini berakhir dengan angka 5.


TUGAS ANDA

Diberikan sisi kanan Piramida Terbalik (Naik), tulis program atau fungsi yang akan mengembalikan daftar asli.

Tantangan Ekstra Baru : Coba lakukan ini kurang dari O (n ^ 2)

CONTOH

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

CATATAN: Piramida Terbalik tidak akan pernah kosong dan akan selalu terdiri dari bilangan bulat positif SAJA.

Rengekan
sumber
6
Selamat datang di PP&CG! Tantangan ini layak, meskipun bisa diperbaiki. Saya akan merekomendasikan memposting tantangan Anda di Sandbox terlebih dahulu untuk meningkatkan postingan sebelum diprioritaskan.
Tau
13
Wawasan gratis yang tidak dapat saya temukan dalam bahasa yang lebih pendek:
f([a,b,c,d,e])=[1464101331001210001100001][abcde]
Lynn
4
Hanya FYI, ini sama dengan kata CodeWars .
ggorlen
6
@ggorlen saya tahu. Saya orang yang membuat kata :)
Whimpers
8
Try doing this in less than O(n)tentunya tidak mungkin untuk mengalokasikan array berukuran n atau mengubah O (n) item di dalamnya lebih cepat daripada O (n) kompleksitas?
kata ganti saya adalah monicareinstate

Jawaban:

17

JavaScript (ES6),  62 58 49  46 byte

Disimpan 3 byte berkat @Oliver

Mengembalikan daftar sebagai string yang dipisahkan koma.

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

Cobalah online!

Berkomentar

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
sumber
@Liver, ya
Shaggy
6

TI-BASIC, 54 byte

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

Input adalah daftar sisi kanan segitiga Ans, seperti yang dijelaskan dalam tantangan.
Output adalah baris atas dari segitiga tersebut.

Contoh:

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

Penjelasan:
Solusi ini menyalahgunakan fakta bahwa segitiga terbentuk menggunakan sisi kanan segitiga saat awal berakhir dengan perubahan pada setiap elemen.

Dengan kata lain,

2 1 1
 3 2
  5

menjadi:

5 2 1
 3 1
  2

Dengan demikian, daftar yang dihasilkan adalah sisi kanan dari segitiga baru ini, yang dapat dibentuk dengan mengatur elemen terakhir ke indeks panjang daftar induknya dalam daftar yang dihasilkan.

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"

Catatan: TI-BASIC adalah bahasa tokenized. Jumlah karakter tidak sama dengan jumlah byte.

Tau
sumber
4

Jelly , 6 byte

ṚIƬZḢṚ

Tautan monadik yang menerima daftar bilangan bulat yang menghasilkan daftar bilangan bulat.

Cobalah online!

Bagaimana?

Bangun seluruh segitiga lalu ekstrak elemen yang diperlukan.

Ṛ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
sumber
Punya solusi yang hampir sama tetapi dengan Us bukannya !
Nick Kennedy
IƬUZḢAakan bekerja dengan pertanyaan yang diberikan juga; Saya ingin tahu apakah ada byte yang disimpan di suatu tempat ...
Jonathan Allan
ạƝƬZṪ€bekerja juga tetapi sekali lagi enam.
Nick Kennedy
Yap, saya perhatikan varian itu; Saya kurang berharap sekarang.
Jonathan Allan
Saya baru saja memposting 5-byter, tapi ini sedikit berbeda dari pendekatan Anda mengenai bagian setelah pembangunan piramida.
Erik the Outgolfer
4

MathGolf , 14 11 byte

xÆ‼├│?;∟;]x

Cobalah online!

Penjelasan

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
maks
sumber
3

Python 2 , 56 byte

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

Fungsi rekursif menerima daftar bilangan bulat positif yang mengembalikan daftar bilangan bulat non-negatif.

Cobalah online!

Jonathan Allan
sumber
3

Jelly , 5 byte

_ƝƬa/

Cobalah online!

Kita dapat mengasumsikan seluruh piramida itu positif, jadi kita bisa menggunakan operasi && alih-alih operasi "benar".

Erik the Outgolfer
sumber
3

Pari/GP, 36 bytes

Based on @Lynn's comment:

Free insight that I can't find a language it's shorter in:

f([a,b,c,d,e])=[1464101331001210001100001][abcde]

Pari/GP has a built-in for the Pascal matrix, and its inverse is exactly the matrix we need:

[1000011000121001331014641]1=[1000011000121001331014641]

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

Try it online!

alephalpha
sumber
3

R, 69 67 bytes

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

Try it online!

Returns a column vector.

-2 bytes thanks to Kirill L.

Also based on Lynn's comment:

Free insight that I can't find a language it's shorter in:

f([a,b,c,d,e])=[1464101331001210001100001][abcde]

It's longer than the other R answer, but it was an interesting approach to take and try to golf.

Giuseppe
sumber
2

Javascript (ES6), 127 bytes

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}

Original code

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, I lost like... a lot... to the previous answer...

Naruyoko
sumber
2

05AB1E, 12 11 bytes

R.¥.Γ¥}¨ζнR

Port 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:

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
sumber
2
You can save a byte with R.¥.Γ¥}¨ by starting from the list whose delta is the input.
Emigna
@Emigna Ah, undelta into a loop with deltas to save a byte on the prepend. :) Thanks!
Kevin Cruijssen
2

R, 55 63 55 53 bytes

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

Try it online!

-2 bytes thanks to Giuseppe.

Kirill L.
sumber
2

Perl 6, 37 bytes

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

Try it online!

Repeatedly reduces by elementwise subtraction, and then returns the last number of each list in reverse.

Explanation:

{                                  }  # 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
sumber
1

Python 2, 78 bytes

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

Try it online!

TFeld
sumber
1

Charcoal, 19 bytes

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

Try it online! Link is to verbose version of code. Explanation:

Fθ«

Loop once for each term in the original list.

PI§θ±¹↑

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.

UMθ⁻§θ⊖λκ

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.

Neil
sumber
1

Attache, 29 bytes

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

Try it online!

Simply iterates the Delta function until its empty. Much shorter than the very verbose PeriodicSteps solution...

Conor O'Brien
sumber
1

C, 76 bytes

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

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++)

#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
sumber
1

Japt, 11 9 bytes

Nc¡=äa
yÌ

Try it

2 bytes saved thanks to Oliver.

12 11 bytes

_äa}hUÊN yÌ

Try it

1 byte saved thanks to Oliver.

Shaggy
sumber
2
9 bytes and 10 bytes
Oliver
@Oliver, not thinking to use y(f) is bad enough, but completely forgetting the newline is unforgivable! Will update shortly. Thanks :)
Shaggy
1

Julia 0.6, 44 bytes

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

Try it online!

Same iterative principle as my R answer.

Julia 0.6, 55 bytes

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

Try it online!

@Lynn's algorithm (inverse of Pascal matrix multiplied by input).

Kirill L.
sumber