22

Lista różnic listy liczb całkowitych to różnice list kolejnych członków.

Na przykład lista różnic

1, 3, 2 ,4

jest

2, -1, 2

Twoim zadaniem jest pobranie jako listy różnicowej i wyświetlenie, jak wyglądałaby lista różnic, gdyby posortowana była lista oryginalna.

Na przykład lista różnic

2, 1, -2, -1

Może reprezentować listę

2 4 5 3 2

Które po posortowaniu jest

2 2 3 4 5

Która ma listę różnic

0 1 1 1

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

code-golf array-manipulation

— Kreator pszenicy
źródło

Czy gwarantowane są unikalne rozwiązania?

— H.PWiz

@ H.PWiz Tak, są.

— Wheat Wizard

Związane z.

— całkowicie ludzki,

1

@ H.PWiz Szybki dowód: listę można doskonale odtworzyć z listy różnic (DL) w połączeniu z wartością pierwszego elementu, więc istnieje konwersja jeden do jednego z L na (FV, DL). Zwiększenie FV o dowolną ilość jest równoznaczne z dodaniem tej kwoty do każdego elementu L, a zatem nie może zmienić sortowania L, jeśli to porównanie jest odpowiednio monotoniczne. (Innymi słowy, nie wpływa to na sortowanie, chyba że dodawana liczba powoduje przepełnienie liczb całkowitych).

— CR Drost,

1

Czy możesz dodać jeszcze kilka przypadków testowych? Zauważam, że niektóre rozwiązania dają [-2, 100, -2, -1]na przykład różne wyniki .

— Kudłaty

16

05AB1E , 4 bajty

.¥{¥

Wypróbuj online!

Wyjaśnienie

.¥{¥
.¥   # Undelta the input list
  {  # Sort it
   ¥ # And get the deltas

— Datboi
źródło

Undelta05AB1E ma najbardziej niszowe wbudowane funkcje. o0

— całkowicie ludzki,

2

O cholera, pobij mnie do tego. Zawsze chciałem używać undelta.

— Magic Octopus Urn

16

Undeltaಠ ___ ಠ

— Business Cat

1

„Undelta” to po prostu skumulowana suma, prawda?

— Zgarb,

2

@Zgarb Undelta dodaje 0 jako pierwszy element listy, a następnie dokładnie tak, jak powiedziałeś, sumę skumulowaną lub odwrotną deltę.

— Magic Octopus Urn

9

Python 3 z Numpy , 56 54 53 bajtów

2 bajty wyłączone dzięki @Artyer (Numpy sortzamiast standardowych sorted). 1 bajt off dzięki @notjagan (przejście 0do cumsum)

lambda x:diff(sort(cumsum([0]+x)))
from numpy import*

Kod definiuje anonimową funkcję, która wprowadza listę lub tablicę Numpy i wyprowadza tablicę Numpy.

Wypróbuj online!

— Luis Mendo
źródło

1

Woah, nauczyłeś mnie dzisiaj czegoś nowego. Moje podejście numpybyło znacznie dłuższe. Wrócę jutro, aby głosować za tym, ponieważ widzę, że już jesteś ograniczony. Bardzo dobrze!

— Pan Xcoder,

@ Mr.Xcoder Thanks! Nie jestem ekspertem w Numpy, po prostu śledziłem to, co zrobiłbym w Matlabie: diff(sort([0 cumsum(x)]))(w Matlabie [ ]jest konkatenacja)

— Luis Mendo,

Obowiązek spełniony!

— Pan Xcoder,

-1 bajt poprzez przeniesienie 0do cumsum.

— notjagan

5

Mathematica, 40 bajtów

Differences@Sort@Accumulate@Join[{1},#]&

— J42161217
źródło

Differences@Sort@FoldList[+##&,1,#]&

— alephalpha

4

Galaretka , 6 bajtów

0;+\ṢI

Wypróbuj online!

— Erik the Outgolfer
źródło

4

Łuska , 4 bajty

Ẋ-O∫

Wypróbuj online!

Wyjaśnienie

      -- implicit input, e.g                               [2,1,-2,-1]
   ∫  -- cumulative sum                                    [0,2,3,1,0]
  O   -- sort                                              [0,0,1,2,3]
Ẋ     -- apply function to all adjacent pairs in the list  [(0,0),(0,1),(1,2),(2,3)]
 -    --   subtract                                        [0,1,1,1]

— H.PWiz
źródło

Innym językiem, który ma undelta? A może coś bardziej wbudowanego?

— Pan Xcoder,

@Pan. Xcoder Zdarza się, że suma ta jest taka sama jak undelta

— H.PWiz

@ H.PWiz Właściwie to nie to, co nazywamy sumą ... chyba że weźmiesz pod uwagę pusty prefiks.

— Erik the Outgolfer,

@EriktheOutgolfer Tak, to właśnie robi łuska, tak jak scanl(+)0w Haskell.

— H.PWiz

4

Pyth , 9 bajtów

-1 bajt dzięki @EriktheOutgolfer .

.+S+0sM._

Pakiet testowy.

Pyth , 10 bajtów

.+S.u+YNQ0

Wypróbuj online! lub Wypróbuj więcej przypadków testowych .

— Pan Xcoder
źródło

Jak w mojej (usuniętej) odpowiedzi, możesz użyć +0sM._zamiast .u+YNQ0-1.

— Erik the Outgolfer,

@EriktheOutgolfer Dlaczego go usunąłeś?

— Pan Xcoder,

Myślałem, że główny pomysł był zbyt podobny do twojego.

— Erik the Outgolfer,

@EriktheOutgolfer Ok, dziękuję

— Pan Xcoder,

m=+Zjest wariantem o tej samej długości sM._, ale niestety nie wydaje się, że może być krótszy.

— FryAmTheEggman

4

JavaScript (ES6), 57 56 bajtów

Zaoszczędzono 1 bajt dzięki produktom @ETH

a=>a.map(n=>t-=n,p=t=0).sort((a,b)=>b-a).map(n=>p-(p=n))

Próbny

Pokaż fragment kodu

let f =

a=>a.map(n=>t-=n,p=t=0).sort((a,b)=>b-a).map(n=>p-(p=n))

console.log(JSON.stringify(f([2, 1, -2, -1])))

Rozwiń fragment kodu

— Arnauld
źródło

.sort((a,b)=>a-b)To jest sposób na uzyskanie delt? Sortując z odejmowaniem? : P

— totalnie ludzki,

@totallyhuman Pierwszy map()daje delty. Ten kod je sortuje. Druga mapa odbudowuje nowe delty. Metoda JS sort()domyślnie używa kolejności leksykograficznej. Potrzebujemy więc tego wyspecjalizowanego oddzwaniania dla numerów> 9 (niestety).

— Arnauld,

To -p+(p=n)szlifuje moje narzędzia, ale niestety nie ma lepszego sposobu ... chyba że ...

— ETHproductions

co do cholery, nie

— nacisnąłem przycisku wysyłania

@ETHproductions Dzięki :-)

— Arnauld

3

Java 8, 123 bajty

Standardowe rozwiązanie: suma wejściowa, sortowanie, a następnie różnicowanie. Nie ma też istotnych sztuczek związanych z wdrażaniem.

l->{int s=l.length,d[]=new int[s+1],i=0;while(i<s)d[i+1]=d[i]+l[i++];for(java.util.Arrays.sort(d);i-->0;)l[i]=d[i+1]-d[i];}

Przesyłaj do Consumer<int[]>. Wyjście jest zmutowanym wejściem.

Wypróbuj online

Niegolfowana lambda

l -> {
    int
        s = l.length,
        d[] = new int[s + 1],
        i = 0
    ;
    while (i < s)
        d[i + 1] = d[i] + l[i++];
    for (java.util.Arrays.sort(d); i-- > 0; )
        l[i] = d[i + 1] - d[i];
}

Podziękowanie

-3 bajty dzięki Olivierowi Grégoire'owi , mistrzowi bezbożnej autoinkrementacji
-1 bajt dzięki Nevay

— Jakob
źródło

1

Można golf 3 bajty poprzez zmianę położenia gdzie zrobić swoje przyrosty i ogólny obliczeń:

l->{int s=l.length,d[]=new int[s+1],i=0;for(;i<s;)d[i+1]=d[i]+l[i++];java.util.Arrays.sort(d);for(i=0;i<s;)l[i]=-d[i]+d[++i];}

(uwaga niewidoczne znaki, SE, gdy kopiowanie / wklejanie)

— Olivier Grégoire

1

Dziękuję za mój nowy tytuł;) Oto bardziej bezczelność z okazji świętowania for(;i>0;)l[i-1]=d[i]-d[--i];(ostatnia pętla)

— Olivier Grégoire

Właśnie przerobiłem tę pętlę, dochodząc for(;i-->0;)l[i]=d[i+1]-d[i];do tej samej długości. Zaktualizuj, aby nadejść.

— Jakob,

2

Możesz zapisać 1 bajt za pomocą

l->{int s=l.length,d[]=new int[s+1],i=0;while(i<s)d[i+1]=d[i]+l[i++];for(java.util.Arrays.sort(d);i-->0;l[i]=d[i+1]-d[i]);}

.

— Nevay

Ach tak, oczywiście. Dzięki!

— Jakob

2

Brachylog , 15 bajtów

a₀ᶠ+ᵐ,0o{s₂↔-}ᶠ

Wypróbuj online!

— Erik the Outgolfer
źródło

2

R , 31 32 bajtów

-4 bajty dzięki @ user2390246 dla diffinv

+5 bajtów od Jarko dla cat

cat(diff(sort(diffinv(scan()))))

Odczytuje ze standardowego, zapisuje na standardowe. diffinvjest odwrotnością diffdla danej wartości początkowej (domyślnie 0). Ponieważ jest diffponownie edytowany, nie ma znaczenia, co to za wartość.

Jak zauważył Jarko Dubbeldam, musiałem poprawnie wydrukować wynik, kosztem pięciu bajtów. Niestety.

Wypróbuj online!

— Giuseppe
źródło

To też miałem na myśli. Nie musi jednak obsługiwać drukowania, ponieważ uruchomienie go jako pełnego programu (poprzez source) nie powoduje wypisania niczego.

— JAD

1

Jeśli używasz diffinvraczej niż cumsumnie musisz dodawać zera.

— user2390246

@ user2390246 wow, bardzo miło! TIL o diffinv.

— Giuseppe,

Ja też! Właśnie szukałem, czy są jakieś wcześniejsze odpowiedzi, do których mógłbym je zastosować.

— user2390246

1

Python 2 , 83 bajty

l,r=input(),[1]
for i in l:r+=[r[-1]+i]
r.sort()
print[b-a for a,b in zip(r,r[1:])]

Wypróbuj online!

Straszne rozwiązanie.

— całkowicie ludzki
źródło

W rzeczywistości nie jest to takie straszne

— Xcoder,

+=Operator Pythona na listach działa z dowolnym iterowalnym, więc możesz użyć r+=r[-1]+i,zamiast r+=[r[-1]+i]jednego bajtu i zapisać go.

— Jonathan Frech,

1

Perl 6 , 46 bajtów

{[\+](0,|@_).sort.rotor(2=>-1).flat.map(*R-*)}

Spróbuj

Rozszerzony:

{  # bare block lambda with implicit signature :(*@_)

  [\+](         # triangle reduce using &infix:«+»
    0,          # start with 0
    |@_         # Slip in the arguments from the outer block
  )             #                  (0, 2, 3, 1, 0)

  .sort         # sort the results (0,0,1,2,3)
  .rotor(2=>-1) # group in twos    ((0,0),(0,1),(1,2),(2,3))
  .flat         # flatten          (0,0,0,1,1,2,2,3)
  .map(*R-*)    # grab 2 values at a time, and subtract first from second
                # (0, 1, 1, 1)
}

— Brad Gilbert b2gills
źródło

1

Haskell , 74 bajty

import Data.List
g=sort.scanl(+)0
h l|k<-g l=map(\(x,y)->x-y)$zip(tail$k)k

Wypróbuj online!

Bezpośredni.

— Jferard
źródło

3

=<<z funkcji przydaje się monada: (zipWith(-)=<<tail).sort.scanl(+)0

— nimi

@nimi Bardzo miło. Nie jestem ekspertem od monad, ale powinienem był pomyśleć zipWith.

— jferard

1

TI-Basic (TI-84 Plus CE), 23 bajty

Prompt X
augment({0},cumSum(_LX→X
SortA(_LX
ΔList(_LX

Monity o dane wejściowe użytkownika. Lista musi być wprowadzana z wiodącym {, z liczbami oddzielonymi przez ,i z opcjonalnym końcowym }.

TI-Basic to tokenizowany język ; ΔList(i cumSum(są żetonami dwubajtowymi, wszystkie pozostałe używane żetony są jednobajtowe.

Przykład uruchomienia (z NAMEnazwą programu i {4,-2,7,-4,0}jako dane wejściowe):

prgmNAME
X=?{4,-2,7,-4,0}
               {2 2 1 0 4}

Wyjaśnienie:

Prompt X                  # 3 bytes, get list input, store in _LX
augment({0},cumSum(_LX→X   # 12 bytes, 
          # store the list ({0} prepended to the cumulative sum of _LX) to _LX
SortA(_LX                  # 4 bytes, sort _LX ascending
ΔList(_LX                  # 4 bytes, implicitly print the difference list of _LX

— pizzapanty184
źródło

Potrzebujesz tych L?

— Zacharý

@ Zacharý można je pominąć podczas przechowywania listy, ale pominięcie ich podczas odwołania odnosi się do zmiennej numerycznej X zamiast listy

— pizzapants184

1

C ++ (gcc) , 136 bajtów

Jako nienazwana ogólna lambda, przy założeniu, że dane wejściowe są podobne std::listi zwracane przez parametr referencyjny.

[](auto&L){auto r=L.begin(),l=L.insert(r,0);while(r!=L.end())*r+++=*l++;for(L.sort(),l=r=--L.end();--l!=L.begin();*r---=*l);L.erase(l);}

Wypróbuj online!

Nie golfowany:

[](auto&L){
 auto r=L.begin(),
      l=L.insert(r,0); //adds a zero right in front
 while(r!=L.end())
   *r++ += *l++;       //sum left to right
 for(
  L.sort(),            //sorting invalidates the iterators
  l=r=--L.end();       //so, reinit
  --l!=L.begin();      //decrement l beforehand 
  *r-- -= *l           //diff right to left
 );
 L.erase(l);           //l==L.begin(), so this removes the temporary 0
}

— Karl Napf
źródło

1

Pyth, 8 bajtów

.+S+M.uP

Demonstracja

.+S+M.uP
.+S+M.uPNQ    Implicit variables
     .u  Q    Apply the following function to the input repeatedly until it
              stops changing, then output the list of values, including the
              starting value.
       PN     Remove the last element. No-op if the list is empty.
   +M         Sum each list. This gives the cumulative sums in reverse order,
              including a 0 at the end for the empty list.
  S           Sort
.+            Deltas

— isaacg
źródło

+1 To fajne obejście z kumulatywnym stałym punktem. Osobiście nawet o tym nie myślałem.

— Pan Xcoder,

1

TI-Basic, 20 bajtów

cumSum(augment({0},Ans->L1
SortA(L1
ΔList(L1

— Timtech
źródło

1

Perl 5 , 87 + 1 (-a) = 88 bajtów

$a[0]=1;push@a,$a[-1]+$_ for@F;@a=sort{$a<=>$b}@a;print$a[0]-$_,$"while($_=shift@a)&&@a

Wypróbuj online!

— Xcali
źródło

1

VB.NET (.NET 4.5), 109 bajtów

Sub A(n)
Dim c=n.count-1
For i=1To c
n(i)+=n(i-1)
Next
n.Sort()
For i=c To 1 Step-1
n(i)-=n(i-1)
Next
End Sub

Funkcja, która oczekuje listy jako danych wejściowych i modyfikuje ją bezpośrednio. Oryginalny parametr może być następnie użyty do wydruku

Odtwarza oryginalną listę, dodając ją do przodu (zakłada domyślnie 0 jako pierwszy element)
Sortuje oryginalną listę
Pobiera różnice, przechodząc wstecz (więc nie muszę śledzić innej listy) (domyślny pierwszy element 0 oznacza, że pierwsza różnica jest taka sama jak najmniejszy element)

Wypróbuj online!

— Brian J.
źródło

Czy mógłbyś zaktualizować link TIO?

— Taylor Scott,

@TaylorScott Update w jaki sposób?

— Brian J,

Twój link TIO pokazuje zupełnie inny kod niż w twojej odpowiedzi

— Taylor Scott,

1

@TaylorScott Ahh .... Rozumiem. Musiałem wprowadzić pewne poprawki, ponieważ TIO używa Mono, ale korzystałem z kompilatora .NET 4.5

— Brian J

1

APL (Dyalog) , 15 14 bajtów

-1 bajt dzięki ngn .

(¯2-/⍋⊃¨⊂)0,+\

+\ suma skumulowana

0, wstaw zero

(… ) Zastosuj następującą funkcję ukrytą:

⊂ załącz (abyśmy mogli wybrać wiele przedmiotów)

⍋⊃¨ niech każdy z indeksów, który sortowałby argument, wybrał z tego

¯2-/ odwrócona różnica par

Wypróbuj online!

Oryginalne rozwiązanie znalezione przez uczestników Code Golf Hackathon na spotkaniu użytkowników Dyalog '17 :

¯2-/l[⍋l←+\0,⎕]

Wypróbuj online!

⎕ monit o wprowadzenie

0, wstaw zero

+\ suma skumulowana

l← przechowywać jako l

⍋ znajdź indeksy, które posortują l

l[… ] Użyj tego do indeksowanial

¯2-/ odwrócona różnica par

— Adám
źródło

1

Nie wiem, czy było to dozwolone podczas hackathonu, ale jeśli przepisałeś go w stylu bez punktów, możesz zapisać znak: (¯2- / ⍋⊃¨⊂) 0, + \

— ngn

@ngn W tej części warsztatów starano się, aby uczestnicy rozpoczęli pracę z PPCG, więc zasady tutaj były zgodne z PPCG. Dzięki.

— Adám

1

MATL , 6 bajtów

0hYsSd

Wypróbuj online!

0       # push 0
 h      # horizontal concatenate with implicit input
  Ys    # cumulative sum
    S   # sort
     d  # diff (implicit output)

— Giuseppe
źródło

0

Gaia , 7 bajtów

1¤++⊣ȯọ

Wypróbuj online!

Wyjaśnienie

1¤+      Prepend 1
   +⊣    Cumulative sums
     ȯ   Sort
      ọ  Deltas

— Business Cat
źródło

0

k , 16 bajtów

1_-':{x@<x}@+\0,

Wypróbuj online!

              0, /prepend a 0
            +\   /cumulative sum
     {x@<x}@     /sort
1_-':            /differences list

— zgrep
źródło

0

Japt , 10 bajtów

iT å+ n än

Sprawdź to

— Kudłaty
źródło

0

Röda , 42 bajty

{i=0{[0];[i]if i+=_}|sort|slide 2|[_2-_1]}

Wypróbuj online!

Jest to podobne do odpowiedzi w Perlu 6 . .sortjest |sort, .rotor(2=>-1).flatjest |slide 2 i .map(*R-*)jest |[_2-_1].

Wyjaśnienie:

{
  i=0 /* initialize variable i */
  /* the following block recreates the original list from differences: */
  {
    [0];       /* push 0 to the stream */
    [i]if i+=_ /* add every number in the stream to i and push i back */
  }|
  sort|    /* sort the numbers */
  slide 2| /* for values i1, i2, i3, ... in the stream
              push pairs i1, i2, i2, i3, ... */
  [_2-_1]  /* calculate difference of numbers in each pair in the stream */
}

Instrukcja [i]if i+=_jest równoważna z

for sfv do
  if i += sfv do
    push(i)
  done
done

+=Operator nie naciskać wartości strumienia, więc jest truthy. Mógłbym również użyć pewnego rodzaju bloku (np. {|j|i+=j;[i]}_), Aby powiązać dodawanie i wypychanie instrukcji, ale ifjest krótszy.

— fergusq
źródło

0

Julia 0.6.0 (34 bajty)

Prawie kopia tego, co zostało zrobione w R i Python 3

x->diff(sort(cumsum(vcat([0],x))))

— Goysa
źródło

0

J, 10 bajtów

/:~&.(+/\)

wyjaśnienie

„sortuj według sumy skanowania”: W J koniunkcja &.stosuje transformację po prawej stronie do danych wejściowych, następnie stosuje czasownik po lewej stronie (w tym przypadku sortuj /:~), a następnie wykonuje odwrotną transformację. Oznacza to, że J rozumie, jak odwrócić sumę skanu, która jest dokładnie potrzebna tutaj: kolejne różnice są danymi wejściowymi, które po zsumowaniu skanu wygenerują tę sumę skanu.

Wypróbuj online!

— Jonasz
źródło

Sortuj listę różnic

05AB1E , 4 bajty

Wyjaśnienie

Python 3 z Numpy , 56 54 53 bajtów

Mathematica, 40 bajtów

Galaretka , 6 bajtów

Łuska , 4 bajty

Wyjaśnienie

Pyth , 9 bajtów

Pyth , 10 bajtów

JavaScript (ES6), 57 56 bajtów

Próbny

Java 8, 123 bajty

Niegolfowana lambda

Podziękowanie

Brachylog , 15 bajtów

R , 31 32 bajtów

Python 2 , 83 bajty

Perl 6 , 46 bajtów

Rozszerzony:

Haskell , 74 bajty

TI-Basic (TI-84 Plus CE), 23 bajty

C ++ (gcc) , 136 bajtów

Pyth, 8 bajtów

TI-Basic, 20 bajtów

Perl 5 , 87 + 1 (-a) = 88 bajtów

VB.NET (.NET 4.5), 109 bajtów

APL (Dyalog) , 15 14 bajtów

MATL , 6 bajtów

Gaia , 7 bajtów

Wyjaśnienie

k , 16 bajtów

Japt , 10 bajtów

Röda , 42 bajty

Julia 0.6.0 (34 bajty)

J, 10 bajtów

wyjaśnienie