Counting in pyramids

Question

You should write a program or function which receives a list of distinct integers as input and outputs or returns the number of occurrences of the input numbers in the following upside-down number pyramid.

Starting from the original list in every step we create a new one with the maximal values of every pair of adjacent numbers (e.g. 5 1 2 6 becomes 5 2 6). We stop when there is only one number in the list.

The full pyramid for 5 1 2 6 is

5 1 2 6
 5 2 6 
  5 6  
   6   

The resulting number of occurrences are 3 1 2 4 (for 5 1 2 6 respectively).

Input

• A list of one or more integers with no repetition. (e.g. 1 5 1 6 is invalid.)

Output

• A list of positive integers. The ith element of the list is the number of occurrences of the ith input number in the pyramid.

Examples

Input => Output

-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

This is code-golf so the shortest entry wins.

Bonus puzzle: can you solve the problem in O(n*log n) time?

Answer 1

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

A divide-and-conquer solution. The maximum element M seeps all the way down the pyramid, splitting it into a rectangle of M's and two subpyramids.

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

So, the overall result is the output for the left sublist, followed by the area of the rectangle, followed by the output for the right sublist.

The input variable L is reused to stored the result so that the empty list is mapped to the empty list.

The constructs in solution are wordy in Python. Maybe some language with pattern-matching can implement the following pseudocode?

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

Answer 2

CJam, 23 22 bytes

Still looking for golfing options.

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

This is a CJam function (sort of). This expects the input numbers on stack and returns the corresponding output counts on the stack too. An example:

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

leaves

3 1 2 4

on stack.

Pretty sure that this is not in O(n log n) time.

Code expansion:

]_                     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

Lets take a look at how it works by working up an example of 5 1 2 6

In the second row, 5 1 2 6 becomes 5 2 6 because 5, 2 and 6 are the maximum of [5 1], [1 2] and [2 6] respectively. In the third row, it becomes 5 6 because 5 and 6 are maximum of [5 2] and [2 6] respectively. This can also be written as maximum of [5 1 2] and [1 2 6] respectively. Similarly for last row, 6 is maximum of [5 1 2 6].

So we basically create the proper length slices starting from slice of length 1, which is basically the original numbers, each wrapped in an array, to finally a slice of length N for the last row, where N is the number of input integers.

Try it online here

Answer 3

Pyth, 19 17 bytes

m/smmeSb.:QhkUQdQ

Check out the Online Demonstration or the complete Test Suite (first 4 byte iterate over the examples).

This one is a little bit more clever than the naive approach. Each number of the triangle can be represented as the maximal value of a connected subset of Q. In the first line it uses the subsets of length 1, the second line of the triangle uses the subsets of length 2, ...

Explanation

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

To visualize this a little bit. m.:QhdUQ and the input [5, 1, 2, 6] gives me all possible subsets:

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

And mmeSk.:QhdUQ gives me each of their maxima (which corresponds exactly to the rows in the pyramid):

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

Pyth, 23 22 bytes

|u&aYGmeSd.:G2QQm/sYdQ

This is just the simple "do what you're told" approach.

Check out the Online Demonstration or a complete Test Suite (first 4 byte iterate over the examples).

Explanation

meSd.:G2 maps each pair of [(G[0], G[1]), (G[1], G[2]), ...] to the maximal element.

Y is an empty list, therefore aYG appends G to the Y.

u...QQ repeatedly applies these two functions (len(Q) times) starting with G = Q and updating G after each run.

m/sYdQ maps each element of the input list to their count in the flattened Y list.

Answer 4

Mathematica, 72 bytes

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

Answer 5

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]

Each entry of the pyramid is the maximum of the sublist atop its upward cone. So, we generate all these sublists, indexed by intervals [i,j] with 0 < i < j <= len(L), and count how many time each element appears as a maximum.

A shorter way to enumerate the subintervals would likely save characters. A single-index parametrization of the pairs [i,j] would be a plausible approach.

Answer 6

Pip, 56 + 1 = 57 bytes

Not competing much with the CJam voodoo, I'm afraid. Looks like I need a better algorithm. Run with -s flag to get space-delimited output.

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

Ungolfed, with comments:

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

The redefinition of r each time through works as follows:

{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

Answer 7

APL (24)

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

This is a function that takes a list, like so;

      {+/⍵∘.={⍵≡⍬:⍵⋄⍵,∇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

Explanation:

• {...}⍵: apply the following function to ⍵:
  • ⍵≡⍬:⍵: if ⍵ is empty, return ⍵
  • 2⌈/⍵: generate the next list
  • ⍵,∇: return ⍵, followed by the result of applying this function to the next list
• ⍵∘.=: compare each element in ⍵ to each element in the result of the function
• +/: sum the rows (representing elements in ⍵)

Answer 8

Haskell, 78 bytes

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

Usage: 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].

How it works

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    

Answer 9

JavaScript, 109 bytes

I think I found an interesting way to go about this, but only after I was done realized the code was too long to compete. Oh well, posting this anyway in case someone sees further golfing potential.

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}

I'm making use of the following formula here:

occurrences of i = (amount of consecutive numbers smaller than i to its left + 1) * (amount of consecutive numbers smaller than i to its right + 1)

This way one doesn't need to actually generate the entire pyramid or subsets of it. (Which is why I initially thought it would run in O(n), but tough luck, we still need inner loops.)

Answer 10

MATLAB : (266 b)

• the correction of the code costs more bytes, i will struggle how to reduce it later.

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

INPUT

a vector must be of the form [a b c d ...]

• example:

  [2 4 7 11 3]

OUTPUT

pattern occurences.

s =

 1


s =

 2


s =

 3


s =

 8


s =

 1

EXPLANATION:

if [a b c d] is an input the program calculates result g h i j as

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

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

Answer 11

J (49)

I suppose there is some room for improvement...

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