Liczenie w piramidy

17

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?

randomra
źródło
Czy przed przesłaniem funkcji muszę je wydrukować do STDOUT, czy po prostu je wydrukować?
Optymalizator

Odpowiedzi:

4

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.

Jakube
źródło
twoja 17-bajtowa wersja używa tego samego algorytmu co mój, myślę, że teraz jest też naiwna: P
Optimizer
13

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)
xnor
źródło
Mogę zrobić jeden bajt krótszy z dopasowaniem wzorców Mathematica, ale nawet nie pobije to istniejącego zgłoszenia Mathematica:f@{}=##&@@{};f@{a___,l_,b___}/;l>a~Max~b:={f@{a},Length@{a,0}Length@{b,0},f@{b}}
Martin Ender
6

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[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

Optymalizator
źródło
3

Mathematica, 72 bajty

Last/@Tally[Join@@NestList[MapThread[Max,{Most@#,Rest@#}]&,#,Length@#]]&
alephalpha
źródło
3

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.

xnor
źródło
1

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

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 ⍵)
marinus
źródło
1

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

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

vvye
źródło
1

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) = ...

Abr001am
źródło
0

J (49)

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

[:+/~.="1 0[:;([:i.#)<@:(4 :'(}:>.}.)^:x y')"0 1]
.ıʇǝɥʇuʎs
źródło