Powinieneś napisać program lub funkcję, która otrzymuje listę różnych liczb całkowitych jako dane wejściowe i wyjściowe lub zwraca liczbę wystąpień liczb wejściowych w poniższej piramidzie liczb odwróconych.

Zaczynając od oryginalnej listy w każdym kroku, tworzymy nową z maksymalnymi wartościami każdej pary sąsiednich liczb (np. 5 1 2 6Staje się 5 2 6). Zatrzymujemy się, gdy na liście jest tylko jeden numer.

Pełna piramida dla 5 1 2 6jest

5 1 2 6
 5 2 6 
  5 6  
   6   

Wynikowa liczba wystąpień to 3 1 2 4( 5 1 2 6odpowiednio).

Wejście

• Lista jednej lub więcej liczb całkowitych bez powtórzeń. (np. 1 5 1 6jest nieprawidłowy.)

Wynik

• Lista liczb całkowitych dodatnich. Ten ielement listy to liczba wystąpień ith liczby wejściowej w piramidzie.

Przykłady

Dane wejściowe => Dane wyjściowe

-5 => 1

8 4 => 2 1

5 9 7 => 1 4 1

1 2 3 9 8 6 7 => 1 2 3 16 3 1 2

6 4 2 1 3 5 => 6 4 2 1 3 5

5 2 9 1 6 0 => 2 1 12 1 4 1

120 5 -60 9 12 1 3 0 1200 => 8 2 1 3 16 1 4 1 9

68 61 92 58 19 84 75 71 46 69 25 56 78 10 89 => 2 1 39 2 1 27 6 5 1 6 1 2 14 1 12

To jest golf golfowy, więc wygrywa najkrótszy wpis.

Bonusowa łamigłówka: czy potrafisz rozwiązać problem na O(n*log n)czas?

Pyth, 19 17 bajtów

m/smmeSb.:QhkUQdQ

Sprawdź demonstrację online lub pełny pakiet testowy (pierwsze 4 bajty iterują przykłady).

Ten jest nieco mądrzejszy niż naiwne podejście. Każda liczba trójkąta może być reprezentowana jako maksymalna wartość podłączonego podzbioru Q. W pierwszym wierszu używa podzbiorów o długości 1, druga linia trójkąta używa podzbiorów o długości 2, ...

Wyjaśnienie

m/smmeSb.:QhkUQdQ    implicit: Q = input()
   m         UQ         map each k in [0, 1, 2, ..., len(Q)-1] to:
        .:Qhk              all subsets of Q of length (k + 1)
    meSb                   mapped to their maximum
  s                     join these lists together
m               Q    map each d of Q to:
 /             d        its count in the computed list

Aby to trochę zobrazować. m.:QhdUQa dane wejściowe [5, 1, 2, 6]dają mi wszystkie możliwe podzbiory:

[[[5], [1], [2], [6]], [[5, 1], [1, 2], [2, 6]], [[5, 1, 2], [1, 2, 6]], [[5, 1, 2, 6]]]

I mmeSk.:QhdUQdaje mi każdą z ich maksimów (które dokładnie odpowiadają rzędom w piramidzie):

[[5, 1, 2, 6], [5, 2, 6], [5, 6], [6]]

Pyth, 23 22 bajtów

|u&aYGmeSd.:G2QQm/sYdQ

To tylko proste podejście „rób, co ci powiedziano”.

Sprawdź demonstrację online lub pełny pakiet testowy (pierwsze 4 bajty iterują przykłady).

Wyjaśnienie

meSd.:G2odwzorowuje każdą parę [(G[0], G[1]), (G[1], G[2]), ...]na maksymalny element.

Yjest pustą listą, dlatego aYGdołącza Gsię do Y.

u...QQwielokrotnie stosuje te dwie funkcje ( len(Q)czasy), rozpoczynając od G = Qi aktualizując Gpo każdym uruchomieniu.

m/sYdQmapuje każdy element listy danych wejściowych na ich liczbę na spłaszczonej Yliście.

Python, 81

def f(L):
 if L:i=L.index(max(L));L=f(L[:i])+[~i*(i-len(L))]+f(L[i+1:])
 return L

Rozwiązanie typu „dziel i rządź”. Maksymalny element Mprzesiewa całą piramidę, dzieląc ją na prostokąt Mi dwie podpiramidy.

* * * M * *
 * * M M *
  * M M M
   M M M
    M M
     M

Tak więc ogólny wynik to wynik dla lewej podlisty, następnie obszar prostokąta, a następnie wynik dla prawej podlisty.

Zmienna wejściowa L jest ponownie wykorzystywana do przechowywania wyniku, dzięki czemu pusta lista jest mapowana na pustą listę.

Konstrukty w rozwiązaniu są uciążliwe w Pythonie. Może jakiś język z dopasowaniem wzorca może implementować następujący pseudokod?

def f(L):
 [] -> []
 A+[max(L)]+B -> f(A)+[(len(A)+1)*(len(B)+1)]+f(B)

CJam, 23 22 bajtów

Wciąż szukam opcji golfowych.

{]_,{)W$ew::e>~}%fe=~}

To jest funkcja CJam (w pewnym sensie). Oczekuje to liczb wejściowych na stosie i zwraca odpowiednie liczby wyjściowe również na stosie. Przykład:

5 1 2 6 {]_,{)W$ew::e>~}%fe=~}~

pozostawia

3 1 2 4

na stosie.

Jestem całkiem pewien, że tego nie ma O(n log n) czas.

Rozszerzenie kodu :

]_                     e# Wrap the input numbers on stack in an array and take a copy
  ,{          }%       e# Take length of the copy and run the loop from 0 to length - 1
    )W$                e# Increment the iterating index and copy the parsed input array
       ew              e# Get overlapping slices of iterating index + 1 size
         ::e>          e# Get maximum from each slice
             ~         e# Unwrap so that there can be finally only 1 level array
                fe=    e# For each of the original array, get the occurrence in this
                       e# final array created by the { ... }%
                   ~   e# Unwrap the count array and leave it on stack

Przyjrzyjmy się, jak to działa, opracowując przykład 5 1 2 6

W drugim rzędzie 5 1 2 6staje się, 5 2 6ponieważ 5, 2 and 6są odpowiednio maksimum [5 1], [1 2] and [2 6]. W trzecim rzędzie staje się, 5 6ponieważ5 and 6 są [5 2] and [2 6]odpowiednio maksimum . Można to również zapisać odpowiednio jako maksimum [5 1 2] and [1 2 6]. Podobnie dla ostatniego wiersza 6jest maksymalnie [5 1 2 6].

Zasadniczo tworzymy wycinki o odpowiedniej długości, zaczynając od wycinka długości 1, który jest zasadniczo pierwotnymi liczbami, z których każda jest owinięta w tablicę, aż do wycinka długości Ndla ostatniego rzędu, gdzieN jest liczba liczb całkowitych wejściowych.

Wypróbuj online tutaj

Mathematica, 72 bajty

Last/@Tally[Join@@NestList[MapThread[Max,{Most@#,Rest@#}]&,#,Length@#]]&

Python, 81

lambda L:[sum(x==max(L[i:j])for j in range(len(L)+1)for i in range(j))for x in L]

Każde wejście piramidy stanowi maksimum podlisty na jej stożku skierowanym w górę. Generujemy więc wszystkie te listy podrzędne, indeksowane według przedziałów [i,j]z0 < i < j <= len(L) , i policzyć ile pojawi każdy element jako maksymalny czas.

Krótszy sposób wyliczenia podprzedziałów prawdopodobnie uratowałby znaki. Parametryzacja par z jednym indeksem [i,j]byłaby prawdopodobnym podejściem.

Pip , 56 + 1 = 57 bajtów

Obawiam się, że nie konkuruję dużo z voodoo CJam. Wygląda na to, że potrzebuję lepszego algorytmu. Uruchom z -sflagą, aby uzyskać wynik rozdzielany spacjami.

l:gr:0*,#gg:0*g+1WrFir:{c:r@[a--a]c@($<l@c)}M1,#r++(gi)g

Niegolfowany, z komentarzami:

l:g                              l = input from cmdline args
r:0*,#g                          r = current row as a list of indices into l
g:0*g+1                          Repurpose g to store the frequencies
Wr                               Loop until r becomes empty
 Fir:{c:r@[a--a]c@($<l@c)}M1,#r  Redefine r (see below) and loop over each i in it
  ++(gi)                         Increment g[i]
g                                Output g

Ponowne zdefiniowanie za rkażdym razem poprzez działa w następujący sposób:

{c:r@[a--a]c@($<l@c)}M1,#r
{                   }M1,#r       Map this function to each a from 1 to len(r) - 1:
 c:r@[a--a]                      c is a two-item list containing r[a] and r[a-1]
                l@c              The values of l at the indices contained in c
              $<                 Fold/less-than: true iff l[c[0]] < l[c[1]]
           c@(     )             Return c[0] if the former is greater, c[1] otherwise

APL (24)

{+/⍵∘.={⍵≡⍬:⍵⋄⍵,∇2⌈/⍵}⍵}

Jest to funkcja, która pobiera taką listę;

      {+/⍵∘.={⍵≡⍬:⍵⋄⍵,∇2⌈/⍵}⍵}68 61 92 58 19 84 75 71 46 69 25 56 78 10 89
2 1 39 2 1 27 6 5 1 6 1 2 14 1 12

Wyjaśnienie:

• {...}⍵ : zastosuj następującą funkcję do ⍵:
  • ⍵≡⍬:⍵: jeśli ⍵ jest puste, zwróć ⍵
  • 2⌈/⍵: wygeneruj następną listę
  • ⍵,∇: return ⍵, a następnie wynik zastosowania tej funkcji do następnej listy
• ⍵∘.=: porównaj każdy element w ⍵ z każdym elementem w wyniku funkcji
• +/: zsumuj wiersze (reprezentujące elementy w ⍵)

Haskell, 78 bajtów

l=length
f x=[l[b|b<-concat$take(l x)$iterate(zipWith max=<<tail)x,a==b]|a<-x]

Zastosowanie: f [68,61,92,58,19,84,75,71,46,69,25,56,78,10,89]->[2,1,39,2,1,27,6,5,1,6,1,2,14,1,12] .

Jak to działa

zipWith max=<<tail   -- apply 'max' on neighbor elements of a list
iterate (...) x      -- repeatedly apply the above max-thing on the
                     -- input list and build a list of the intermediate
                     -- results
take (l x) ...       -- take the first n elements of the above list
                     -- where n is the length of the input list
concat               -- concatenate into a single list. Now we have
                     -- all elements of the pyramid in a single list.
[ [b|b<-...,a==b] | a<-x]
                     -- for all elements 'a' of the input list make a 
                     -- list of 'b's from the pyramid-list where a==b.
 l                   -- take the length of each of these lists    

JavaScript, 109 bajtów

Myślę, że znalazłem ciekawy sposób, aby to zrobić, ale dopiero po tym, jak skończyłem, zorientowałem się, że kod jest zbyt długi, aby konkurować. No cóż, i tak to opublikuję, na wypadek, gdyby ktoś zobaczył dalszy potencjał golfa.

f=s=>{t=[];for(i=-1;s.length>++i;){j=k=i;l=r=1;for(;s[--j]<s[i];l++);for(;s[++k]<s[i];r++);t[i]=l*r}return t}

Korzystam z następującej formuły tutaj:

wystąpienia i = (liczba kolejnych liczb mniejszych niż i po jej lewej stronie + 1) * (liczba kolejnych liczb mniejszych od i po prawej stronie + 1)

W ten sposób nie trzeba generować całej piramidy ani jej podzbiorów. (Dlatego początkowo myślałem, że będzie działać w O (n), ale przy odrobinie szczęścia nadal potrzebujemy wewnętrznych pętli.)

MATLAB: (266 b)

• korekta kodu kosztuje więcej bajtów, będę miał problem z jego późniejszym zmniejszeniem.

v=input('');h=numel(v);for i=1:h,f=(v(i)>v(1));l=(v(i)>v(h));for j=h-1:-1:i+1,l=(v(i)>v(j))*(1+l);end,if(i>1),l=l+(v(i)>v(i-1))*l;end;for j=2:i-1,f=(v(i)>v(j))*(1+f);end,if(i<h),f=f+(v(i)>v(i+1))*f;end;s=f+l+1;if(i<h&&i>1),s=s-((v(i)>v(i+1))*(v(i)>v(i-1)));end;s
end

WEJŚCIE

wektor musi mieć postać [abcd ...]

• przykład:

  [2 4 7 11 3]

WYNIK

występujące wzory.

s =

 1


s =

 2


s =

 3


s =

 8


s =

 1

WYJAŚNIENIE:

jeśli [abcd] jest wejściem, program oblicza wynik ghij jako

g = (a> b) + (a> b) (a> c) + (a> b) (a> c) * (a> d) = (a> b) (1+ (a> c) ( 1+ (a> c))))

h = (b> a) + (b> c) + (b> a) (b> c) + (b> c) (b> d) + (b> a) (b> c) (b> d ) = ... „uproszczony”

i = (c> b) + (c> d) + (c> b) (c> d) + (c> b) (c> a) + (c> d) (c> b) (c> a ) = ..

j = (d> c) + (d> c) (d> b) + (d> c) (d> b) * (d> a) = ...

J (49)

Przypuszczam, że jest miejsce na poprawę ...

[:+/~.="1 0[:;([:i.#)<@:(4 :'(}:>.}.)^:x y')"0 1]