17
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ For a function submission, do I have to print them to STDOUT or simply output them ? \$\endgroup\$ – Optimizer Apr 26 '15 at 8:01

11 Answers 11

4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ your 17 byte version uses the same algorithm as mine, I guess that is now naive too :P \$\endgroup\$ – Optimizer Apr 26 '15 at 16:23
13
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ I can do one byte shorter with Mathematica's pattern matching, but it doesn't even beat the existing Mathematica submission: f@{}=##&@@{};f@{a___,l_,b___}/;l>a~Max~b:={f@{a},Length@{a,0}Length@{b,0},f@{b}} \$\endgroup\$ – Martin Ender Apr 26 '15 at 11:03
6
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

Mathematica, 72 bytes

Last/@Tally[Join@@NestList[MapThread[Max,{Most@#,Rest@#}]&,#,Length@#]]&
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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 ⍵)
\$\endgroup\$
1
\$\begingroup\$

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    
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

J (49)

I suppose there is some room for improvement...

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.