Suis-je un tableau de golfy?

18

Définition et règles

Un tableau golfy est un tableau d'entiers, où chaque élément est supérieur ou égal à la moyenne arithmétique de tous les éléments précédents. Votre tâche consiste à déterminer si un tableau d'entiers positifs donnés en entrée est golfique ou non.

Cas de test et exemple

Par exemple, le tableau suivant:

[1, 4, 3, 8, 6]

Est un tableau de golf, car chaque terme est supérieur à la moyenne arithmétique de ceux qui le précèdent. Étudions-le étape par étape:

Nombre -> Éléments précédents -> Moyenne -> Suit la règle?

1 -> [] -> 0,0 -> 1 ≥ 0,0 (vrai)
4 -> [1] -> 1.0 -> 4 ≥ 1.0 (Vrai)
3 -> [1, 4] -> 2,5 -> 3 ≥ 2,5 (Vrai)
8 -> [1, 4, 3] -> 2. (6) -> 8 ≥ 2. (6) (Vrai)
6 -> [1, 4, 3, 8] -> 4.0 -> 6 ≥ 4.0 (Vrai)

Tous les éléments respectent la condition, il s'agit donc d'un tableau de golf. Notez qu'aux fins de ce défi, nous supposerons que la moyenne d'une liste vide ( []) est 0.

Plus de cas de test:

Entrée -> Sortie

[3] -> Vrai
[2, 12] -> Vrai
[1, 4, 3, 8, 6] -> Vrai
[1, 2, 3, 4, 5] -> Vrai
[6, 6, 6, 6, 6] -> Vrai
[3, 2] -> Faux
[4, 5, 6, 4] -> Faux
[4, 2, 1, 5, 7] -> Faux
[45, 45, 46, 43] -> Faux
[32, 9, 15, 19, 10] -> Faux

Notez que ce Puzzle 1 de CodeGolf-Hackathon et est également affiché sur Anarchy Golf (que l' on est cassé) - Quote par histocrat , mais je suis l'auteur original sur les deux sites, et donc permis de les rediffuser ici.

M. Xcoder
la source
L'entrée est-elle toujours une liste d'entiers positifs?
Kelly Lowder
@KellyLowder Oui.
M. Xcoder
C'est un problème amusant, je pensais le republier sur Anarchy Golf avec plus de cas de test, mais je pensais que vous pourriez y travailler.
histocrate
@histocrat Allez-y et republiez-le sur Anarchy Golf, j'aurais dû penser aux choses qui pourraient être exploitées en premier. Je suis plutôt content que vous le trouviez intéressant (Btw s'il vous plaît envoyez-moi un ping ici et donnez un lien si vous le republiez).
M. Xcoder
3
@streetster Ce sont des équivalents. Sum / i> x est identique à Sum> xi est identique à Sum + x> x (i + 1) est identique à (Sum + x) / (i + 1)> x.
histocrate

Réponses:

13

Python 2 , 37 octets

def g(a):sum(a)>len(a)*a.pop()or g(a)

Essayez-le en ligne!

Sorties via le code de sortie: se bloque (code de sortie 1) pour les tableaux golfy, quitte simplement avec le code de sortie 0 pour les tableaux non golfy. ovs et Jonathan Frech ont économisé 3 octets.

Python 2 , 44 octets

f=lambda a:a and sum(a)<=len(a)*a.pop()*f(a)

Essayez-le en ligne!

Une variante plus traditionnelle, qui revient Truepour les tableaux de golf, sinon False. Jonathan Frech a enregistré 2 octets.

Lynn
la source
1
Je pense que c'est a==[]orpossible a and.
Jonathan Frech
2
C'est en fait intelligent - cela se révèle sum(a)<=len(a)*a.pop()*[]pour le cas de base, ce qui est toujours vrai int < list!
Lynn
3
39 octets en tant que fonction qui se bloque pour des entrées véridiques.
OVS
1
@ovs 37 octets utilisant une fonction impérative.
Jonathan Frech
11

Gelée , 6 5 octets

<ÆmƤE

Essayez-le en ligne!

Comment ça fonctionne

<ÆmƤE  Main link. Argument: A (integer array)

 ÆmƤ   Compute the arithmetic means (Æm) of all prefixes (Ƥ) of A.
<      Perform element-wise comparison. Note that the leftmost comparison always
       yields 0, as n is equal to the arithmetic mean of [n].
    E  Test if all elements of the resulting array are equal, which is true if and
       only if all comparisons yielded 0.
Dennis
la source
cairdcoinheringaahing sur 6 octets (alternative):ÆmƤµ⁼Ṣ
M. Xcoder
@ Mr.Xcoder Golfé!
Dennis
Wow c'est génial :-)
M. Xcoder
5

JavaScript (ES6), 33 32 octets

a=>a.some(e=>e*++i<(s+=e),s=i=0)

Le code fonctionne également sur les valeurs négatives telles que [-3, -2]. Renvoie falsepour un tableau golfy, truepour d'autres tableaux. Edit: enregistré 1 octet grâce à @JustinMariner.

Neil
la source
1
Vous pouvez supprimer le !puisque la spécification ne demande que deux valeurs différentes, donc retourner falsequand c'est un tableau golfy est très bien.
Justin Mariner
4

Wolfram Language (Mathematica) , 35 octets

Max[Accumulate@#-Range@Tr[1^#]#]>0&

Essayez-le en ligne!

Sorties Falsepour les tableaux de golf et Trueautres.

Martin Ender
la source
1
Je vois que la relation fausse / vraie est inversée mais c'est OK
Kelly Lowder
4

MATL , 9 8 octets

tYstf/<a

Sorties 0pour les tableaux de golf, 1sinon.

Essayez-le en ligne!

Explication

Tenez compte des commentaires [1, 4, 3, 8, 6].

t    % Implicit input. Duplicate
     % STACK: [1, 4, 3, 8, 6], [1, 4, 3, 8, 6]
Ys   % Cumulative sum
     % STACK: [1, 4, 3, 8, 6], [1, 5, 8, 16, 22]
t    % Duplicate
     % STACK: [1, 4, 3, 8, 6], [1, 5, 8, 16, 22], [1, 5, 8, 16, 22]
f    % Find: indices of nonzeros. Gives [1, 2, ..., n], where n is input size
     % STACK: [1, 4, 3, 8, 6], [1, 5, 8, 16, 22], [1, 2, 3, 4, 5]
/    % Divide, element-wise
     % STACK: [1, 4, 3, 8, 6], [1, 2.5, 2.6667, 4, 4.4]
<    % Less than?, element-wise
     % STACK: [0, 0, 0, 0, 0]
a    % Any: true if and only there is some nonzero. Implicit display
     % STACK: 0
Luis Mendo
la source
4

Haskell , 53 50 48 octets

and.(z(<=).scanl1(+)<*>z(*)[1..].tail)
z=zipWith

Essayez-le en ligne!

Edit: -3 octets grâce à Zgarb!

Explication

La version sans point ci-dessus est équivalente au programme suivant:

f s = and $ zipWith(<=) (scanl1(+)s) (zipWith(*)[1..](tail s))

Compte tenu d' une entrée s=[1,4,3,8,6], scanl1(+)scalcule les sommes préfixe [1,5,8,16,22]et zipWith(*)[1..](tail s)laisse tomber le premier élément et se multiplie tous les autres éléments avec leur indice: [4,6,24,24]. La liste est désormais golfique si par paire les sommes de préfixe sont plus petites ou égales à l'index des éléments, ce qui peut être vérifié en zippant les deux listes avec (<=)et en vérifiant que tous les résultats sont Trueavec and.

Laikoni
la source
1
Vous pouvez éviter l'erreur de type comme celle-ci .
Zgarb
@Zgarb Avec le recul, c'est la solution évidente. Merci d'avoir souligné!
Laikoni
3

C # (Visual C # Compiler) , 71 + 18 = 89 octets

x=>x.Select((n,i)=>new{n,i}).Skip(1).All(y=>x.Take(y.i).Average()<=y.n)

18 octets supplémentaires pour using System.Linq;

Essayez-le en ligne!

chryslovelace
la source
2
Bienvenue sur le site! :)
DJMcMayhem
De manière générale, les déclarations d'importation ne sont pas considérées comme gratuites dans le code golf. Parce que cela nécessite la déclaration, using System.Linq;ce serait en fait 89 octets, parfois exprimés en "71 + 18 = 89" pour montrer que 18 octets sont requis mais ne font pas partie de la solution tout en ayant toujours le décompte final comme dernier chiffre de la ligne de titre ( ce qui est utile pour certains analyseurs automatiques).
Kamil Drakari
3

APL (Dyalog) , 10 octets

Il s'agit d'une fonction de préfixe tacite anonyme (appelée train monadique en termes APL).

∧/⊢≥+⍳∘≢

Essayez tous les cas de test sur TIO!

Est-ce

∧/ tout à fait vrai que

 les éléments

 sont supérieurs ou égaux à

+\ les sommes cumulées

÷ divisé par

   les nombres entiers de 1 à

   le

   nombre d'éléments

?

Adam
la source
APL a un symbole pour "le" ??
user2390246
1
@ user2390246 lie les choses de la même manière que "le" se lie entre "compter les chats". Cela s'appelle vraiment Compose .
Adám
3

C (gcc) , 62 60 62 octets

  • Suppression de deux parenthèses superflues.
  • Ajout de deux octets pour corriger la réutilisabilité de la fonction ( b=).
f(A,S,k,b)int*A;{for(S=k=b=0;*A;S+=*A++)b+=!(S<=*A*k++);b=!b;}

Essayez-le en ligne!

Jonathan Frech
la source
3

05AB1E , 5 octets

ηÅA÷W

Essayez-le en ligne!

Une aide considérable de Dennis et Adnan est parvenue à cette version réduite. Un bug a également été corrigé pour rendre cela possible, merci encore à vous tous. Je prends peu de crédit pour cette réponse.


05AB1E , 10 octets

ηεÅA}ü.S_P

Essayez-le en ligne!


Long car DgsO/est l'équivalent de "moyenne" dans 05AB1E.

Apparemment, ÅAc'est la moyenne arithmétique.

Urne de poulpe magique
la source
Pour calculer les moyennes, j'utiliserais +\÷J(diviser la somme cumulée par des indices) dans Jelly. N'est-ce pas si facile dans 05AB1E? Edit: Nevermind.
Dennis
@Dennis ah, la somme cumulée dans 05AB1E est ü+qu'il n'y a vraiment pas de divie par des indices autres que gpour obtenir la longueur du tableau, Lpour pousser 1,2,...,net diviser pour obtenir la moyenne, qui est toujours essentiellement de 5 octets.
Urne de poulpe magique
.S_est un LONG chemin à parcourir <=, si quelqu'un a des idées lmk.
Urne de poulpe magique
Fonctionnerait ÷Wau lieu de ü.S_P?
Dennis
1
Oh, @Adnan vient de corriger la vectorisation de ÅA, ηÅA÷Wfonctionne donc maintenant.
Dennis
2

APL (Dyalog) , 15 octets

∧/⊢≥((+/÷≢)¨,\)

Essayez-le en ligne!

Comment?

            ,\  all prefixes
           ¨    for each
      +/÷≢      calculate arithmetic mean
  ⊢≥            element wise comparison
∧/              logically and the result
Uriel
la source
2

PowerShell , 60 octets

param($a)$o=1;$a|%{$o*=$_-ge($a[0..$i++]-join'+'|iex)/$i};$o

Essayez-le en ligne!

Prend l'entrée comme un tableau littéral (par exemple, @(1, 4, 3, 8, 6)) dans $a. Définit notre $ovariable de sortie sur 1. Boucle ensuite à travers $a. À chaque itération, nous utilisons (ab) la conversion implicite de PowerShell pour *=le résultat d'une comparaison booléenne par rapport à notre $orésultat. Le booléen est de savoir si la valeur actuelle $_est plus -gélevée que equal ou les termes précédents $a[0..$i++]additionnés ensemble ( -join'+'|iex) divisé par le nombre de termes que nous avons déjà vus $i. Donc, si une étape sur le chemin est fausse, elle $osera multipliée par 0. Sinon, il restera1 tout au long.

Nous plaçons ensuite simplement $osur le pipeline et la sortie est implicite. 1pour véridique et 0pour falsey.

AdmBorkBork
la source
2

C # (.NET Core) , 74 octets

x=>{for(int i=1,s=0;i<x.Count;)if(x[i]<(s+=x[i-1])/i++)return 0;return 1;}

Essayez-le en ligne!

Renvoie 0 pour faux et 1 pour vrai.

Réponse de 3 octets de plus que le noyau des chryslovelaces . Mais au total plusieurs octets plus courts car ma variante n'a besoin d'aucune instruction.using

raznagul
la source
2

Cubix , 35 octets

/I?/\+psu0^.\)*sqs;-\;;U;O1.....?@^

Essayez-le en ligne!

Pas l'utilisation la plus efficace de l'espace (6 no-ops dans le code) Ne produit aucune sortie pour un tableau golfy, 1pour un tableau non golfy.

Se développe dans le cube suivant:

      / I ?
      / \ +
      p s u
0 ^ . \ ) * s q s ; - \
; ; U ; O 1 . . . . . ?
@ ^ . . . . . . . . . .
      . . .
      . . .
      . . .

Explication à venir, mais elle contient essentiellement quelque chose comme la réponse MATL de Luis Mendo ou la réponse Julia de Dennis .

Regardez-le courir!

Giuseppe
la source
2

Matlab et Octave, 41 36 octets

5 octets enregistrés thx à Luis Mendo

all([a inf]>=[0 cumsum(a)./find(a)])

Essayez-le en ligne!

Leander Moesinger
la source
@LuisMendo Cela le briserait si n'importe quel élément de aest nul. Mais c'est une astuce néanmoins utile dans des situations similaires, gardez cela à l'esprit.
Leander Moesinger
La lecture est difficile! THX!
Leander Moesinger
Ça m'arrive tout le temps :-)
Luis Mendo
2

SQL (MySQL), 68 octets

select min(n>=(select ifnull(avg(n),1)from t s where s.i<t.i))from t

Essayez-le en ligne!

Renvoie 1 pour les tableaux golfy et 0 sinon. Prend entrée d'une table nommée , t. Pour créer t, exécutez:

CREATE TABLE t(i SERIAL,n INT)

et pour charger les valeurs:

truncate table t;insert into t(n)values(3),(2);
Einacio
la source
1

Python 2 , 52 octets

lambda A:all(k*j>=sum(A[:j])for j,k in enumerate(A))

Essayez-le en ligne!

Python 2 , 50 48 44 42 octets

  • Enregistré deux octets en insérant et en utilisant and .
  • Enregistrement de deux octets grâce à M. Xcoder en enchaînant l'affectationS=k=0 .
  • Enregistré deux octets en utilisant oret la valeur booléenne de la comparaison commek incrémentation.
  • Enregistré deux octets grâce à ovs ; élever un NameErroren utilisant une variable non définie au lieu d'un ZeroDivisionError.
S=k=0
for j in input():k+=S<=j*k or J;S+=j

Essayez-le en ligne!

Jonathan Frech
la source
46 octets pour votre version alternative.
M. Xcoder
@ Mr.Xcoder Merci.
Jonathan Frech
42 octets
ovs
@ovs Merci; façon soignée d'un octet pour déclencher une exception.
Jonathan Frech
1

q / kdb + , 14 octets

Solution:

min x>=avgs x:

Exemples:

q)min x>=avgs x:1 4 3 8 6
1b                           / truthy
q)min x>=avgs x:4 2 1 5 7
0b                           / falsey

Explication:

Assez simple avec le avgsintégré:

min x>=avgs x: / solution
            x: / store input in variable x
       avgs    / calculate running averages
    x>=        / array comparison, x greater than running average
min            / take minimum of list of booleans
streetster
la source
1

R , 38 34 octets

function(x)any(cumsum(x)/seq(x)>x)

Essayez-le en ligne!

ngm
la source
très agréable. Je ne sais pas pourquoi il n'y avait pas de réponse R avant ...
Giuseppe
Vous en gardiez tous une facile pour moi.
ngm
au lieu de définir ydans les arguments de la fonction, utiliser cumsum(x)directement est de 4 octets plus court. C'est dommage cummeann'existe pas en base R.
Giuseppe
1

Ajouter ++ , 54 octets

D,g,@@#,BFB
D,k,@,¦+AbL/
D,f,@,dbLR$€g€k0b]$+ABcB]£>ª!

Essayez-le en ligne!

Version non originale, 30 octets

D,f,@,¬+AbLRBcB/@0@B]ABcB]£>ª!

Essayez-le en ligne!

Les deux sorties 1 pour les tableaux de golf et 0 sinon

Comment ils travaillent

La première version a été créée par mes soins, sans vérifier aucune autre solution. Le second a été inspiré par le commentaire de Dennis , donc je suis moins content.

La première version

Ici, nous définissons notre fonction principale Fqui calcule le golfe de notre tableau d'entrée,UNE. Tout d'abord, nous devons fournir les suffixes deUNE, ce qui se fait en générant d'abord la plage B: =[1,...|UNE|], où |UNE| dénote la longueur de UNE. Cela se fait avec le code dbLR$, qui laisse[B,UNE]comme la pile. On itère ensuite la fonction dyadiquegsur ces deux listes. Étant dyadique, la fonction lie son argument de gauche commeUNEpour chaque élément itéré. Il itère ensuite sur la plageB, dont chaque élément de B étant le bon argument fourni à g. g est défini comme

D,g,@@#,BFB

qui est une fonction dyadique (ie prend 2arguments), et pousse ses arguments dans la pile dans l'ordre inverse ( #) avant l'exécution. BFaplatit ensuite les deux arguments. Nous supposerons que les arguments sontUNE et eX. This leaves the stack as [...A,e], where ... represents an array splat. Finally, B takes the first e elements of A and returns a list containing those elements.

Note : The function names g and k aren't chosen randomly. If the commands given to an operator (such as ) doesn't currently have a function (which g and k don't), then the named functions are searched for a matching function. This saves 2 bytes, as normally the function would have to wrapped in {...} to be recognised as a user-defined function. At the time of writing, the currently unused single byte commands are I, K, U, Y, Z, g, k, l, u and w.

When g is applied over the elements of a range x, this returns a list of prefixes for A. We then map our second helper function k over each of these prefixes. k is defined as

D,k,@,¦+AbL/

which is the standard implementation of the arithmetic mean. ¦+ calculates the sum of the argument, AbL calculates its length, then / divides the sum by the length. This calculates the arithmetic mean of each prefix, yielding a new array, C.

Unfortunately, C contains the mean of A as its final element, and does not include the mean of the empty list, 0. Therefore, we would have to remove the final element, and prepend a 0, but popping can be skipped, saving two bytes, for reasons explained in a second. Instead, we push [0] underneath C with 0b]$, then concatenate the two arrays forming a new array, C+.

Now, we need to check each element as being less than its corresponding element in A. We push A once again and zip the two arrays together with ABcB]. This is the reason we don't need to pop the final element: Bc is implemented with Python's zip function, which truncates the longer arrays to fit the length of the shortest array. Here, this removes the final element of C+ when creating the pairs.

Finally, we starmap pA,qC+;p<q¬(pq) over each pair p,q to obtain an array of all 0s if the array is golfy, and array containing at least a single 1 if otherwise. We then check that all elements are falsey i.e. are equal to 0 with ª! and return that value.

The second version

This takes advantage of Dennis' approach to remove 24 bytes, by eliminating the helper functions. Given our input array of A, we first compute the cumulative sums with ¬+, i.e the array created from [A0,A0+A1,A0+A1+A2,...,A0+...+Ai]. We then generate Jelly's equivalent of J (indicies), by calculating the range B:=[1...|A|] where |A| once again means the length of the array.

Next, we divide each element in A by the corresponding index in B with BcB/ and prepend 0 with @0@B]. This results in a new array, C+, defined as

C+:=[0,A0,A0+A12,A0+A1+A23,...,A0+...+Aii+1]

The final part is identical to the first version: we push and zip A with C+, then starmap inequality over each pair before asserting that all elements in the resulting array were falsy.

caird coinheringaahing
la source
0

Pyth, 11 10 bytes

-1 byte thanks to Mr. Xcoder

.A.egb.O<Q

Try it online!

Dave
la source
7 bytes: SI.OM._ (port of cairdcoinheringaahing's solution from Jelly, by Erik the Outgolfer), or 10 bytes using your approach: .A.egb.O<Q
Mr. Xcoder
Post the port as yourself, it's a totally different approach!
Dave
0

Java (OpenJDK 8), 96 bytes

I know it's not a good golfing language, but I still gave it a go!

Input array as first argument of comma separated ints to test.

Returns 1 for true, 0 for false.

a->{int i=1,j,r=1,s=0;for(;i<a.length;i++,s=0){for(j=0;j<i;s+=a[j++]);r=s/i>a[i]?0:r;}return r;}

Try it online!

Luke Stevens
la source
0

Java 7, 100 bytes

Golfed:

int g(int[]a){int i=1,m=0,s=m,r=1;for(;i<a.length;){s+=a[i-1];m=s/i;r-=a[i++]<m&&r>0?1:0;}return r;}

Ungolfed:

int golfy(int[]a)
{
    int i = 1, m = 0, s = m, r = 1;
    for (; i < a.length;)
    {
        s += a[i-1];
        m = s / i;
        r -= a[i++] < m && r>0? 1 : 0;
    }
    return r;
}

Try it online

Returns 0 for ungolfy and 1 for golfy arrays. Slightly longer than java 8 answer.

peech
la source
0

PHP, 44 bytes

while($n=$argv[++$i])$n<($s+=$n)/$i&&die(1);

takes input from command line arguments, exits with 0 (ok) for a golfy array, with 1 else.

Run with -nr or try it online.

Titus
la source
0

J, 19 bytes

[:*/[>:[:}:0,+/\%#\

+/\ % #\ averages of the prefixes: #\ produces 1..n

}:0, add 0 to the beginning and remove the last

[>: is the original list element by element >= to the shifted list of averages?

*/ are all the elements greater, ie, the previous list is all 1s?

Try it online!

Jonah
la source
0

AWK, 39 bytes

{for(;i++*$i>=s&&i<=NF;s+=$i);$0=i>NF}1

Try it online!

Note that the TIO link has 5 extra bytes i=s=0 to allow for multi-line input.

Robert Benson
la source
0

Japt, 10 bytes

Came up with two 10 byte solutions, can't seem to improve on that.

eȨU¯Y x÷Y

Try it


Explanation

               :Implicit input of array U
eÈ             :Is every element, at 0-based index Y
  ¨            :Greater than or equal to
   U¯Y         :U sliced from index 0 to index Y
        ÷Y     :Divide each element by Y
       x       :Reduce by addition

Alternative

eÈ*°Y¨(T±X

Try it

               :Implicit input of array U
eÈ             :Is every element X (at 0-based index Y)
  *°Y          :Multiplied by Y incremented by 1
     ¨         :Greater than or equal to
      (T±X     :T (initially 0) incremented by X
Shaggy
la source