Debería escribir un programa o función que reciba una lista de enteros distintos como entrada y salida o que devuelva el número de apariciones de los números de entrada en la siguiente pirámide numérica invertida.

A partir de la lista original en cada paso, creamos uno nuevo con los valores máximos de cada par de números adyacentes (por ejemplo, se 5 1 2 6convierte en 5 2 6). Nos detenemos cuando solo hay un número en la lista.

La pirámide completa para 5 1 2 6es

5 1 2 6
 5 2 6 
  5 6  
   6   

El número resultante de ocurrencias son 3 1 2 4(para 5 1 2 6respectivamente).

Entrada

• Una lista de uno o más enteros sin repetición. (por ejemplo, 1 5 1 6no es válido)

Salida

• Una lista de enteros positivos. El ielemento th de la lista es el número de ocurrencias del inúmero de entrada th en la pirámide.

Ejemplos

Entrada => Salida

-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

Este es el código de golf, por lo que gana la entrada más corta.

Bonus puzzle: ¿puedes resolver el problema a O(n*log n)tiempo?

Pyth, 19 17 bytes

m/smmeSb.:QhkUQdQ

Consulte la Demostración en línea o el conjunto de pruebas completo (los primeros 4 bytes iteran sobre los ejemplos).

Este es un poco más inteligente que el enfoque ingenuo. Cada número del triángulo se puede representar como el valor máximo de un subconjunto conectado de Q. En la primera línea usa los subconjuntos de longitud 1, la segunda línea del triángulo usa los subconjuntos de longitud 2, ...

Explicación

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

Para visualizar esto un poco. m.:QhdUQy la entrada [5, 1, 2, 6]me da todos los subconjuntos posibles:

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

Y mmeSk.:QhdUQme da cada uno de sus máximos (que corresponde exactamente a las filas de la pirámide):

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

Pyth, 23 22 bytes

|u&aYGmeSd.:G2QQm/sYdQ

Este es solo el enfoque simple de "haz lo que te dicen".

Consulte la demostración en línea o un conjunto de pruebas completo (los primeros 4 bytes iteran sobre los ejemplos).

Explicación

meSd.:G2asigna cada par de [(G[0], G[1]), (G[1], G[2]), ...]al elemento máximo.

Yes una lista vacía, por lo tanto, se aYGagrega Ga la Y.

u...QQaplica repetidamente estas dos funciones ( len(Q)veces) comenzando G = Qy actualizando Gdespués de cada ejecución.

m/sYdQasigna cada elemento de la lista de entrada a su recuento en la Ylista aplanada .

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

Una solución de divide y vencerás. El elemento máximo se Mfiltra por toda la pirámide, dividiéndolo en un rectángulo de M's y dos subpirámides.

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

Por lo tanto, el resultado general es la salida de la sublista izquierda, seguido del área del rectángulo, seguido de la salida de la sublista derecha.

La variable de entrada Lse reutiliza para almacenar el resultado para que la lista vacía se asigne a la lista vacía.

Las construcciones en solución son prolijas en Python. ¿Quizás algún lenguaje con coincidencia de patrones pueda implementar el siguiente pseudocódigo?

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

CJam, 23 22 bytes

Todavía estoy buscando opciones de golf.

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

Esta es una función CJam (más o menos). Esto espera los números de entrada en la pila y también devuelve los recuentos de salida correspondientes en la pila. Un ejemplo:

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

hojas

3 1 2 4

en la pila

Estoy bastante seguro de que esto no es a O(n log n)tiempo.

Expansión de código :

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

Veamos cómo funciona elaborando un ejemplo de 5 1 2 6

En la segunda fila, se 5 1 2 6convierte en 5 2 6porque 5, 2 and 6son los máximos de [5 1], [1 2] and [2 6]respectivamente. En la tercera fila, se convierte en 5 6porque 5 and 6son máximos de [5 2] and [2 6]respectivamente. Esto también se puede escribir como máximo de [5 1 2] and [1 2 6]respectivamente. Del mismo modo para la última fila, 6es máximo de [5 1 2 6].

Básicamente, creamos los segmentos de longitud adecuados a partir del segmento de longitud 1, que son básicamente los números originales, cada uno envuelto en una matriz, hasta finalmente un segmento de longitud Npara la última fila, donde Nes el número de enteros de entrada.

Pruébalo en línea aquí

Mathematica, 72 bytes

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]

Cada entrada de la pirámide es el máximo de la sublista sobre su cono ascendente. Entonces, generamos todas estas sublistas, indexadas por intervalos [i,j]con 0 < i < j <= len(L), y contamos cuántas veces aparece cada elemento como máximo.

Una forma más corta de enumerar los subintervalos probablemente ahorraría caracteres. Una parametrización de un solo índice de los pares [i,j]sería un enfoque plausible.

Pipa , 56 + 1 = 57 bytes

No compito mucho con el vudú de CJam, me temo. Parece que necesito un mejor algoritmo. Ejecutar con -sbandera para obtener una salida delimitada por espacios.

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

Sin golf, con comentarios:

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

La redefinición de rcada vez a través de obras de la siguiente manera:

{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⌈/⍵}⍵}

Esta es una función que toma una lista, así;

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

Explicación:

• {...}⍵ : aplica la siguiente función a ⍵:
  • ⍵≡⍬:⍵: si ⍵ está vacío, devuelve ⍵
  • 2⌈/⍵: genera la siguiente lista
  • ⍵,∇: return ⍵, seguido del resultado de aplicar esta función a la siguiente lista
• ⍵∘.=: compara cada elemento en ⍵ con cada elemento en el resultado de la función
• +/: suma las filas (que representan elementos en ⍵)

Haskell, 78 bytes

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

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

Cómo funciona

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 bytes

Creo que encontré una forma interesante de hacerlo, pero solo después de que me di cuenta, el código era demasiado largo para competir. Oh, bueno, publicar esto de todos modos en caso de que alguien vea más potencial de golf.

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}

Estoy haciendo uso de la siguiente fórmula aquí:

ocurrencias de i = (cantidad de números consecutivos más pequeños que i a su izquierda + 1) * (cantidad de números consecutivos más pequeños que i a su derecha + 1)

De esta manera, no es necesario generar la pirámide completa o subconjuntos de ella. (Es por eso que inicialmente pensé que funcionaría en O (n), pero mala suerte, todavía necesitamos bucles internos).

MATLAB: (266 b)

• la corrección del código cuesta más bytes, voy a tener dificultades para reducirlo más adelante.

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

ENTRADA

un vector debe tener la forma [abcd ...]

• ejemplo:

  [2 4 7 11 3]

SALIDA

Ocurrencias de patrones.

s =

 1


s =

 2


s =

 3


s =

 8


s =

 1

EXPLICACIÓN:

si [abcd] es una entrada, el programa calcula el resultado ghij como

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

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)

Supongo que hay margen de mejora ...

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