Ecrivez un programme ou une fonction qui prend une liste non vide d’entiers positifs. Vous pouvez supposer qu'il s'agit d'un format pratique convenable, tel que "1 2 3 4"ou [1, 2, 3, 4].

Les nombres dans la liste d'entrée représentent les tranches d'un graphique à secteurs complet , chaque taille de tranche étant proportionnelle à son nombre correspondant et toutes les tranches étant disposées autour du graphique dans l'ordre indiqué.

Par exemple, la tarte pour 1 2 3 4est:

La question à laquelle votre code doit répondre est la suivante: le diagramme à secteurs est-il déjà divisé en deux ? En d’autres termes, existe-t-il une ligne parfaitement droite d’un côté à l’autre du cercle, qui le divise symétriquement en deux?

Vous devez générer une valeur de vérité s'il existe au moins une bissectrice et une valeur de fausseté s'il n'en existe aucune .

Dans l' 1 2 3 4exemple, il y a une bissection entre 4 1et 2 3le résultat serait donc véridique.

Mais pour l'entrée, 1 2 3 4 5il n'y a pas de bissectrice, donc le résultat serait faux:

Exemples supplémentaires

Arranger les nombres différemment peut enlever les bissectrices.
par exemple 2 1 3 4→ fausseté:

Si un seul numéro figure dans la liste de saisie, le graphique n'est pas divisé en deux.
par exemple 10→ fausseté:

Il peut y avoir plusieurs bissectrices. Tant qu'il y a plus que zéro, le résultat est la vérité.
par exemple 6 6 12 12 12 11 1 12→ vérité: (il y a 3 bissectrices ici)

Des bisections peuvent exister même si elles ne sont pas évidentes visuellement.
par exemple 1000000 1000001→ fausseté:

par exemple 1000000 1000001 1→ vérité:

(Merci à nces.ed.gov pour la génération des camemberts.)

Cas de test

Truthy
1 2 3 4
6 6 12 12 12 11 1 12
1000000 1000001 1
1 2 3
1 1
42 42
1 17 9 13 2 7 3
3 1 2
10 20 10

Falsy
1 2 3 4 5
2 1 3 4
10
1000000 1000001
1
1 2
3 1 1
1 2 1 2 1 2
10 20 10 1

Notation

Le code le plus court en octets gagne. Tiebreaker est une réponse plus tôt.

J, 18 octets

5 octets grâce à Dennis.

+/e.[:,/2*+/\-/+/\

@ HelkaHomba : Nope.

Usage

>> f =: +/e.[:,/2*+/\-/+/\
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

Ungolfed

black_magic  =: +/\-/+/\
doubled_bm   =: 2 * black_magic
flatten      =: ,/
sum          =: +/
is_member_of =: e.
f =: sum is_member_of monadic flatten doubled_bm

Version précédente de 23 octets:

[:+/[:+/+/=+:@-/~@(+/\)

Usage

>> f =: [:+/[:+/+/=+:@-/~@(+/\)
>> f 6 6 12 12 12 11 1 12
<< 4
>> f 10 20 10 1
<< 0

Ungolfed

black_magic =: -/~@(+/\)
double      =: +:
equals      =: =
sum         =: +/
monadic     =: [:
of          =: @
f =: monadic sum monadic sum (sum equals double of black_magic)

Explication

La somme de toutes les sous-chaînes est calculée par black_magic. Le +/\calcul des sommes partielles.

Par exemple, a b c ddevient a a+b a+b+c a+b+c+d.

La -/~construction alors une table de soustraction basée sur l'entrée, x y zdevient ainsi :

x-x x-y x-z
y-x y-y y-z
z-x z-y z-z

Appliqué à a a+b a+b+c a+b+c+d, le résultat serait:

    0  -b -b-c -b-c-d
    b   0   -c   -c-d
  b+c   c    0     -d
b+c+d c+d    d      0

Ceci calcule les sommes de toutes les sous-chaînes qui ne contiennent pas a.

Cela garantit d'être suffisant, car si une bissection contient a, l'autre bissection ne contiendra pas aet ne sera pas enveloppante.

Gelée , 9 à 8 octets

Ḥ+\©_Sf®

Renvoie une liste non vide (vérité) ou une liste vide (fausseté). Essayez-le en ligne! ou vérifier tous les cas de test .

Comment ça marche

Ḥ+\©_Sf®  Main link. Argument: A (list)

Ḥ         Double all integers in A.
 +\       Take the cumulative sum of 2A.
   ©      Copy; store the result in the register.
    _S    Subtract the sum of A from each partial sum of 2A.
      f®  Filter; intersect this list with the list in the register.

Julia, 34 30 29 octets

!x=sum(x)∈cumsum!(x,2x).-x'

Merci à @GlenO pour avoir joué 1 octet!

Essayez-le en ligne!

Comment ça marche

Après avoir stocké la somme cumulée de 2x dans x , nous soustrayons le vecteur de rangée x ' du vecteur de colonne x , ce qui donne la matrice de toutes les différences possibles. Essentiellement, ceci calcule les sommes de tous les sous-tableaux adjacents de x qui ne contiennent pas la première valeur, leurs négatifs et les 0 de la diagonale.

Enfin, nous testons si la somme du tableau d'origine x appartient à la matrice générée. Si tel est le cas, la somme d'au moins une des sous-listes adjacentes est égale à exactement la moitié de la somme de la liste complète, ce qui signifie qu'il existe au moins une bissectrice.

Python 2, 64 octets

f=lambda l,s=0:l>[]and(sum(l)==s)|f(l[1:],s+l[0])|f(l,s+l.pop())

Essaie de manière récursive de supprimer des éléments du début ou de la fin jusqu'à ce que la somme de ce qui reste soit égale à la somme de ce qui a été supprimé et stocké s. Prend du temps exponentiel dans la longueur de la liste.

Dennis a sauvegardé 3 octets avec pop.

Haskell, 41 octets

f l=elem(sum l/2)$scanr(:)[]l>>=scanl(+)0

L'idée est de vérifier s'il existe une sous-liste ldont la somme est égale sum l/2. Nous générons les sommes de ces sous-listes en tant que scanr(:)[]l>>=scanl(+)0. Regardons comment cela fonctionne avecl=[1,2,3]

>> scanr(:)[]l
[[1,2,3],[2,3],[3],[]] 
-- the suffixes of l

>> scanl(+)0 [2,3,4]
[0,2,5,9]
-- the cumulative sums of the input

>> scanr(:)[]l>>=scanl(+)0
[0,1,3,6,0,2,5,0,3,0]
-- the cumulative sums of the suffixes of l, flattened to a single list

Vieux 43 octets:

f l|c<-scanl1(+)l=elem(sum l/2)$(-)<$>c<*>c

Génère la liste cdes sommes cumulées. Ensuite, vérifie si deux de ces sommes diffèrent en sum l/2vérifiant s’il s’agit d’un élément de la liste des différences (-)<$>c<*>c.

Pyth, 10 à 9 octets

}sQmysd.:

Testez-le dans le compilateur Pyth .

Comment ça marche

       .:  Generate the list of all adjacent sublists.
   m       Map over the result:
     sd       Add the integers of the sublist.
    y         Double the sum.
 sQ        Compute the sum of the input.
}          Check if it belongs to the list of doubled sublist sums.

En fait, 21 octets

;Σ@2*;lR@τ╗`╜V♂Σi`Míu

Essayez-le en ligne!

Ce programme affiche un 0pour les faux cas et un entier positif pour les vrais.

Explication:

;Σ@2*;lR@τ╗`╜V♂Σi`Míu
;Σ                     sum of copy of input
  @2*                  double values in other copy
     ;lR               copy, range(1, len(input)+1)
        @τ             append other copy to itself
          ╗            save in reg0
           `╜V♂Σi`M    map: generate cyclic cumulative sums
                   íu  1-based index of sum of input (0 if not found)

Version non concurrente, 10 octets

;Σ@2*σ;)-∩

Essayez-le en ligne!

Ce programme génère une liste vide pour les faux cas et une liste non vide sinon. C'est essentiellement une réponse de Dennis's Jelly . Il n’est pas en concurrence car les fonctionnalités de somme cumulative et de différence vectorisée post-datent le défi.

Explication:

;Σ@2*σ;)-∩
;Σ          sum of copy of input
  @2*       multiply values in other copy by 2
     σ;     two copies of cumulative sum
       )-   subtract sum of input from each element in one copy
         ∩  set intersection with other copy

Python 2, 76 74 70 66 octets

def f(x):n=sum(x);print n in[2*sum(x[k/n:k%n])for k in range(n*n)]

Merci à @xnor pour avoir joué au golf 4 8 octets!

Testez-le sur Ideone . (cas de test plus grands exclus)

MATL , 10 octets

EYst!-Gs=z

La sortie est le nombre de bissectrices.

Essayez-le en ligne!

Explication

Même approche que Julia répond à Dennis .

E       % Implicit input. Multiply by 2 element-wise 
Ys      % Cumulative sum 
t!-     % Compute all pairwise differences. Gives a 2D array 
Gs      % Sum of input 
=       % Test for equality, element-wise 
z       % Number of nonzero elements. Implicit display 

Rubis, 60 53 octets

->a{a.any?{r=eval a*?+;a.rotate!.any?{|i|0==r-=2*i}}}

Génère toutes les partitions possibles en effectuant chaque rotation du tableau d'entrée, puis toutes les tranches de longueur 1 .. n, où nest la taille du tableau d'entrée. Puis vérifie s'il existe une partition avec une somme égale à la moitié de la somme totale du tableau d'entrée.

JavaScript (ES6), 83 octets

a=>a.map(_=>a.slice(--n).map(m=>s.push(t+=m),t=0),s=[],n=a.length)&&s.includes(t/2)

Génère toutes les sommes possibles, puis vérifie si la moitié de la dernière somme (somme de la liste complète) apparaît dans la liste. (Générer les sommes dans l’ordre légèrement délicat pour organiser la somme dont je dois être le dernier sauve 4 octets.)

Dyalog APL, 12 octets

+/∊2×+\∘.-+\

Testez-le avec TryAPL .

Comment ça marche

+/∊2×+\∘.-+\  Monadic function train. Right argument: y (vector)

     +\   +\  Yield the cumulative sum of y.
       ∘.-    Compute all differences of all partial sums.
              This computes the sums of all adjacent subvectors of y that do not
              contain the first value, their negatives, and 0's in the diagonal.
   2×         Multiply all differences by 2.
+/            Yield the sum of y.
  ∊           Test for membership.

Python 2 , 47 octets

k=t=1
for x in input():t<<=x;k|=t*t
print k&k/t

Essayez-le en ligne!

Je suis de retour 2.75 ans plus tard pour battre mon ancienne solution de plus de 25% en utilisant une nouvelle méthode.

Cette version plus longue de 1 octet est un peu plus claire.

k=t=0
for x in input():t+=x;k|=4**t
print k&k>>t

Essayez-le en ligne!

L'idée est de stocker l'ensemble des sommes cumulées tsous forme de bits k, le bit de réglage 2*tindiquant qu'il ts'agit d'une somme cumulée. Ensuite, nous vérifions si deux sommes cumulées diffèrent par la moitié de la somme de liste (finale t) en décalant kautant ce décalage et en procédant au niveau du bit &avec l'original pour voir que le résultat est non nul (vérité).

APL, 25 caractères

En supposant que la liste est donnée dans X ← 1 2 3 4.

(+/X)∊∘.{2×+/⍺↑⍵↓X,X}⍨⍳⍴X←⎕

Explication:

Tout d'abord, notez que APL évalue le formulaire de droite à gauche. Ensuite:

• X←⎕ prend la saisie de l'utilisateur et la stocke dans X

• ⍴X donne la longueur de X

• ⍳⍴X les nombres de 1 à ⍴X

• Le ⍺et ⍵dans {2×+/⍺↑⍵↓X,X}sont les arguments gauche et droit d'une fonction dyadique que nous définissons à l'intérieur des accolades.

  • Maintenant pour la ⍺↑⍵↓X,Xpartie: il X,Xsuffit de concaténer X avec lui-même; ↑et ↓sont prendre et laisser tomber.
  • +/réduit / plie +la liste à sa droite

  So 2 {2×+/⍺↑⍵↓X,X} 1= 2×+/2↑1↓X,X= 2×+/2↑1↓1 2 3 4 1 2 3 4=

  = 2×+/2↑2 3 4 1 2 3 4= 2×+/2 3= 2×5= 10.

• ∘.brace⍨idxest juste idx ∘.brace idx. ( ⍨est la carte en diagonale; ∘.est le produit extérieur)

  Cela nous donne donc une matrice ⍴Xpar ⍴Xqui contient deux fois la somme de toutes les sous-listes connectées.

   4  6  8  2
  10 14 10  6
  18 16 14 12
  20 20 20 20
  

  La dernière chose à faire est de vérifier si la somme de se Xsitue quelque part dans cette matrice.

• Ce que nous faisons avec (+/X)∊matrix.

Brachylog , 6 octets

sj+~+?

Essayez-le en ligne!

Les sorties ont réussi ou échoué, étaient imprimées true.ou false.exécutées comme un programme.

s         A contiguous sublist of the input
 j        with all of its items duplicated
  +       sums to
   ~+     the sum of the elements of
     ?    the input.

C, 161 145 129 octets

• économisé quelques octets grâce à @LeakyNun
• sauvé quelques octets grâce à @ceilingcat

i;j;k;t;r;s;f(x,n)int*x;{for(t=i=k=r=0;i<n;)t+=x[i++];for(;++k<n;i=n)for(;i--;r|=2*s==t)for(s=0,j=i;j<i+k;)s+=x[j++%n];return r;}

Ungolfed essayer en ligne

int f(int*x,int n)
{
    int t=0;

    for(int i=0;i<n;i++)
    {
        t += x[i];
    }

    for(int k=1;k<n;k++) // subset-size
    {
        for(int i=0,s;i<n;i++) // where to start
        {
            s=0;

            for(int j=i;j<i+k;j++) // sum the subset
            {
                s+=x[j%n];
            }

            if(2*s==t) return 1; // TRUE
        }
    }

    return 0; // FALSE
}

Haskell, 68 octets

f l|x<-[0..length l]=any(sum l==)[2*(sum$take a$drop b l)|a<-x,b<-x]

La fonction fcrée d’abord une liste des sommes de toutes les tranches possibles de la liste donnée. Ensuite, il se compare à la somme totale des éléments de la liste. Si nous obtenons à un moment donné la moitié de la somme totale, alors nous savons que nous avons une bissection. J'utilise aussi le fait que si vous takeou dropplus d'éléments que la liste, Haskell ne génère pas d'erreur.

Mathematica, 48 octets

!FreeQ[Outer[Plus,#,-#],Last@#/2]&@Accumulate@#&

Fonction anonyme, semblable en action aux nombreuses autres réponses.

Outer[Plus, #, -#], lorsqu’on agit sur Accumulate@#(qui agit à son tour sur la liste d’entrée en donnant une liste de totaux successifs) génère essentiellement le même tableau, comme au bas de la réponse de Leaky Nun.

!FreeQ[..., Last@#/2]vérifie si (Last@#)/2n'est pas absent du tableau résultant et Last@#est le dernier des totaux successifs, c'est-à-dire la somme de tous les éléments de la liste d'entrée.

Si cette réponse est quelque peu intéressante, ce n’est pas à cause d’un nouvel algorithme, mais plutôt des astuces spécifiques à Mathematica; eg !FreeQest agréable, comparé à MemberQ, car il ne nécessite pas un aplatissement de la table qu’il vérifie et il enregistre un octet.

APL (NARS), caractères 95, octets 190

{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}

Considérez un tableau d’entrée de 4 éléments: 1 2 3 4. Comment choisir l’utile pour cette partition d’exercice de cet ensemble? D'autres pensent que la partition de ces 4 éléments que nous pouvons utiliser est décrite dans le nombre binaire à gauche:

0001,0010,0100,1000 2^(0..4) 1 2 4  8 
0011,0110,1100,                3 6 12
0111,1110,                       7 14
1111                               15

(1001 ou 1011 ecc pourrait être dans cet ensemble mais nous avons déjà 0110 et 0100 ecc) donc un chapeau pour écrire une fonction qui, à partir du nombre d'éléments du tableau en entrée, construit ces nombres binaires ... ce serait:

c←{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}

celui de l'entrée 1 2 4 8 [2 ^ 0..lenBytesArgument-1] trouve 3 6 12, 7 14, 15; donc trouvez les nombres binaires de ces nombres et utilisez-les pour trouver les bonnes partitions du tableau d’entrée ... j’ai testé la fonction c uniquement pour cette entrée 4 éléments, mais il semble que c’est acceptable pour un nombre d’éléments différent ...

tester:

  f←{1≥k←≢w←⍵:0⋄s←+/⍵⋄∨/{s=2×s-+/⍵}¨↑¨{⍵⊂w}¨{(k⍴2)⊤⍵}¨{1≥≢⍵:⍵⋄⍵,∇{(1+2×(↑⍵))×2*0..¯2+≢⍵}⍵}2*0..k-1}
  f¨(1 2 3 4)(6 6 12 12 12 11 1 12)(1000000 1000001 1)(1 2 3)(1 1)(42 42)
1 1 1 1 1 1 
  f¨(1 2 3 4 5)(2 1 3 4)(,10)(1000000 1000001)(,1)(1 2)(3 1 1)
0 0 0 0 0 0 0