Vous devez écrire un programme ou une fonction qui reçoit une liste d'entiers distincts en entrée et en sortie ou renvoie le nombre d'occurrences des nombres en entrée dans la pyramide numérique inversée suivante.

En partant de la liste d'origine à chaque étape, nous en créons une nouvelle avec les valeurs maximales de chaque paire de nombres adjacents (par exemple, 5 1 2 6devient 5 2 6). Nous nous arrêtons lorsqu'il n'y a qu'un seul numéro dans la liste.

La pyramide complète pour 5 1 2 6est

5 1 2 6
 5 2 6 
  5 6  
   6   

Le nombre d'occurrences résultant est 3 1 2 4(pour 5 1 2 6respectivement).

Contribution

• Une liste d'un ou plusieurs entiers sans répétition. (par exemple, 1 5 1 6n'est pas valide.)

Production

• Une liste d'entiers positifs. Le ie élément de la liste est le nombre d'occurrences du ie numéro d'entrée dans la pyramide.

Exemples

Entrée => Sortie

-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

Il s'agit de code-golf, donc l'entrée la plus courte l'emporte.

Puzzle bonus: pouvez-vous résoudre le problème à O(n*log n)temps?

Pyth, 19 17 octets

m/smmeSb.:QhkUQdQ

Découvrez la démonstration en ligne ou l'intégralité suite de tests (itération des 4 premiers octets sur les exemples).

Celui-ci est un peu plus intelligent que l'approche naïve. Chaque numéro du triangle peut être représenté comme la valeur maximale d'un sous-ensemble connecté deQ . Dans la première ligne, il utilise les sous-ensembles de longueur 1, la deuxième ligne du triangle utilise les sous-ensembles de longueur 2, ...

Explication

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

Pour visualiser cela un peu. m.:QhdUQet l'entrée [5, 1, 2, 6]me donne tous les sous-ensembles possibles:

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

Et mmeSk.:QhdUQme donne chacun de leurs maxima (qui correspond exactement aux rangées de la pyramide):

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

Pyth, 23 22 octets

|u&aYGmeSd.:G2QQm/sYdQ

Il s'agit simplement de l'approche «faites ce qu'on vous dit».

Découvrez la démonstration en ligne ou une suite de tests complète (itération des 4 premiers octets sur les exemples).

Explication

meSd.:G2mappe chaque paire de [(G[0], G[1]), (G[1], G[2]), ...]l'élément maximal.

Yest une liste vide, donc aYGs'ajoute Gà la Y.

u...QQapplique à plusieurs reprises ces deux fonctions ( len(Q)heures) en commençant par G = Qet en mettant Gà jour après chaque exécution.

m/sYdQmappe chaque élément de la liste d'entrée à leur nombre dans la Yliste aplatie .

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

Une solution diviser pour mieux régner. L'élément maximal Ms'infiltre tout le long de la pyramide, le divisant en un rectangle de Met deux sous-pyramides.

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

Ainsi, le résultat global est la sortie de la sous-liste de gauche, suivie de la zone du rectangle, suivie de la sortie de la sous-liste de droite.

La variable d'entrée Lest réutilisée pour stocker le résultat afin que la liste vide soit mappée à la liste vide.

Les constructions en solution sont verbeuses en Python. Peut-être qu'un langage avec correspondance de modèle peut implémenter le pseudocode suivant?

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

CJam, 23 22 octets

Toujours à la recherche d'options de golf.

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

Il s'agit d'une fonction CJam (en quelque sorte). Cela attend les numéros d'entrée sur la pile et renvoie également le nombre de sorties correspondant sur la pile. Un exemple:

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

feuilles

3 1 2 4

sur pile.

Je suis presque sûr que ce n'est pas à O(n log n)temps.

Expansion du code :

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

Voyons comment cela fonctionne en élaborant un exemple de 5 1 2 6

Dans la deuxième ligne, 5 1 2 6devient 5 2 6parce que 5, 2 and 6sont le maximum de [5 1], [1 2] and [2 6]respectivement. Dans la troisième ligne, cela devient 5 6parce que 5 and 6sont au maximum [5 2] and [2 6]respectivement. Cela peut également être écrit comme maximum de [5 1 2] and [1 2 6]respectivement. De même pour la dernière ligne, 6est au maximum de [5 1 2 6].

Donc, nous créons essentiellement les tranches de longueur appropriées à partir de la tranche de longueur 1, qui est essentiellement les nombres originaux, chacun enveloppé dans un tableau, pour enfin une tranche de longueur Npour la dernière ligne, où Nest le nombre d'entiers en entrée.

Essayez-le en ligne ici

Mathematica, 72 octets

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]

Chaque entrée de la pyramide est le maximum de la sous-liste au sommet de son cône ascendant. Ainsi, nous générons toutes ces sous-listes, indexées par intervalles [i,j]avec 0 < i < j <= len(L), et comptons le nombre de fois que chaque élément apparaît au maximum.

Une manière plus courte d'énumérer les sous-intervalles sauverait probablement des caractères. Une paramétrisation à un seul indice des paires [i,j]serait une approche plausible.

Pip , 56 + 1 = 57 octets

Pas trop en concurrence avec le vaudou CJam, je le crains. On dirait que j'ai besoin d'un meilleur algorithme. Exécutez avec -sindicateur pour obtenir une sortie délimitée par des espaces.

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

Non golfé, avec commentaires:

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 redéfinition de rchaque fois à travers les œuvres comme suit:

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

C'est une fonction qui prend une liste, comme ça;

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

Explication:

• {...}⍵ : appliquez la fonction suivante à ⍵:
  • ⍵≡⍬:⍵: si ⍵ est vide, retournez ⍵
  • 2⌈/⍵: générer la liste suivante
  • ⍵,∇: retourne ⍵, suivi du résultat de l'application de cette fonction à la liste suivante
• ⍵∘.=: comparer chaque élément de ⍵ à chaque élément du résultat de la fonction
• +/: additionne les lignes (représentant les éléments dans ⍵)

Haskell, 78 octets

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

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

Comment ça fonctionne

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 octets

Je pense avoir trouvé une façon intéressante de procéder, mais ce n'est qu'après avoir réalisé que le code était trop long pour concourir. Eh bien, je le poste quand même si quelqu'un voit un potentiel de golf supplémentaire.

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}

J'utilise la formule suivante ici:

occurrences de i = (nombre de nombres consécutifs inférieur à i à sa gauche + 1) * (nombre de nombres consécutifs inférieur à i à sa droite + 1)

De cette façon, il n'est pas nécessaire de générer la pyramide entière ou ses sous-ensembles. (C'est pourquoi j'ai d'abord pensé qu'il fonctionnerait en O (n), mais pas de chance, nous avons encore besoin de boucles internes.)

MATLAB: (266 b)

• la correction du code coûte plus d'octets, je vais avoir du mal à le réduire plus tard.

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

CONTRIBUTION

un vecteur doit être de la forme [abcd ...]

• exemple:

  [2 4 7 11 3]

PRODUCTION

occurrences de modèle.

s =

 1


s =

 2


s =

 3


s =

 8


s =

 1

EXPLICATION:

si [abcd] est une entrée, le programme calcule le résultat ghij comme

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

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)

Je suppose qu'il y a matière à amélioration ...

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