Pour un autre défi que j'écris, je dois vérifier que les cas de test peuvent être résolus avec des entiers bornés. Plus précisément, je dois vérifier les éléments suivants, pour un tableau non vide d'entiers Aet une largeur de bit entière n:

Tous les entiers adans Asatisfont -2**(n-1) <= a < 2**(n-1)(représentables avec ndes entiers complémentaires à deux bits).
La longueur de Aest inférieure à 2**n.
La somme de Asatisfait -2**(n-1) <= sum(A) < 2**(n-1).
Toutes les combinaisons d'éléments Asatisfont à toutes les conditions ci-dessus.

Naturellement, j'ai décidé de vous sous-traiter ce problème!

Étant donné un tableau d'entiers Aet une largeur de bit entière positive n, vérifiez qu'il Asatisfait aux conditions ci-dessus.

Cas de test

[0, 0, 0], 2: True
[0, 0, 0, 0], 2: False (violates #2)
[1, 2, 3, 4, 5], 8: True
[1, 2, 3, 4, 5], 2: False (violates all conditions)
[1, 2, 3, 4, 5], 5: True
[-3, 4, 1], 4: True
[10, 0, -10], 4: False (violates #1 and #4)
[27, -59, 20, 6, 10, 53, -21, 16], 8: False (violates #4)
[-34, 56, 41, -4, -14, -54, 30, 38], 16: True
[-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22], 7: False (violates #4)
[-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12], 12: True

Implémentation de référence (Python 3)

#!/usr/bin/env python3
from itertools import combinations
from ast import literal_eval


def check_sum(L, n):
  return -2**(n-1) <= sum(L) < 2**(n-1)


def check_len(L, n):
  return len(L) < 2**n


def check_elems(L, n):
  return all(-2**(n-1) <= a < 2**(n-1) for a in L)


A = literal_eval(input())
n = int(input())
OUTPUT_STR = "{}, {}: {}".format(A, n, "{}")

if not (check_elems(A, n) and check_len(A, n) and check_sum(A, n)):
  print(OUTPUT_STR.format(False))
  exit()

for k in range(1, len(A)):
  for b in combinations(A, k):
    if not check_sum(b, n):
      print(OUTPUT_STR.format(False))
      exit()

print(OUTPUT_STR.format(True))

Essayez-le en ligne!

code-golf array-manipulation integer permutations Mego
la source

Sandbox

Mego

Faut-il gérer la liste vide?

M. Xcoder

@ Mr.Xcoder Non, je vais clarifier.

Mego

7

Wolfram Language (Mathematica) , 40 octets

Max[x=2Tr/@Subsets@#,-x-1,Tr[1^#]]<2^#2&

Essayez-le en ligne!

La condition 1 est implicite en vérifiant la condition 3 pour tous les sous-ensembles, y compris ceux à un élément. Nous prenons donc le maximum de

deux fois la somme de chaque sous-ensemble,
un moins de deux fois le négatif de la somme de chaque sous-ensemble, et
la longueur de l'ensemble

et vérifiez si c'est inférieur à 2^#2(où #2est l'entrée de largeur de bit).

Au prix de seulement 6 octets supplémentaires, nous pouvons le remplacer Subsets@#par GatherBy[#,Arg], ce qui est beaucoup plus efficace car il ne calcule que les deux sous-ensembles les plus défavorables: le sous-ensemble de toutes les valeurs non négatives et le sous-ensemble de toutes les valeurs négatives. (Cela fonctionne car Arga une valeur 0sur les premiers et πsur les seconds.)

Misha Lavrov
la source

3

Gelée , 19 octets

ŒPS€;⁸L¤ḟ⁹’2*$ŒRṖ¤Ṇ

Essayez-le en ligne!

Il suffit de vérifier qu'il se mapped sum of powerset + length of settrouve dans la plage requise.

Leaky Nun
la source

1

Je pense (même si je ne suis pas sûr) que vous pouvez utiliser à la ÆẸplace de 2*$(non testé)

M. Xcoder

@ Mr.Xcoder Cela fonctionne.

user202729

3

05AB1E , 13 12 11 octets

1 octet enregistré grâce à M. Xcoder

æO·D±¹gMIo‹

Essayez-le en ligne!

Explication

æ             # powerset of first input
 O            # sum each subset
  ·           # multiply each element by 2
   D          # duplicate
    ±         # bitwise negation of each element in the copy
     ¹g       # push length of first input
       M      # get the maximum value on the stack
        Io    # push 2**<second input>
          ‹   # compare

Emigna
la source

@ Mr.Xcoder: Oh oui, merci! (Je continue d'oublier ±)

Emigna

2

JavaScript (ES6), 75 63 58 octets

a=>n=>!a.some(e=>(a.length|2*(e<0?l-=e:u+=e))>>n,u=0,l=-1)

La somme de n'importe quel sous-ensemble de amensonges se situe entre les sommes des éléments négatifs et non négatifs, donc vérifier les deux sommes suffit pour tout sauf le cas 2. Edit: économisé 12 17 octets grâce à @Arnauld.

Neil
la source

Bien mieux que mon approche naïve. :-) Cela pourrait être réduit à 61 octets

Arnauld

En fait, nous pouvons simplement traiter le test dans la boucle pendant 56 octets .

Arnauld

Piraté le ([-2, -1, -2]) (3)

l4m2

@ l4m2 Bonne prise. Correctif suggéré (57 octets)

Arnauld

@Arnauld Le problème ici est que cela [-2, -2], 3devrait être vrai, non?

Neil

1

Gelée , 21 20 octets

»0,«0$S€~2¦Ḥ;LṀ<2*Ɠ¤

Essayez-le en ligne!

Solution de complexité temporelle linéaire. Il s'avère que j'ai surestimé la complexité du temps

dans Le dix-neuvième octet, 2017-12-11 13-15-03Z, par user202729

@NewSandboxedPosts Le "vrai" problème de somme de sous-ensemble est beaucoup plus difficile. Celui-ci peut se faire en temps linéithmique ...

parce que maintenant je réalise que trier le tableau est complètement inutile.

Explication:

»0,«0$S€~2¦Ḥ;LṀ<2*Ɠ¤    Main link. Example list: [-1, 0, 1]
»0                      Maximize with 0. Get [0, 0, 1]
  ,                     Pair with
   «0$                    minimize with 0. Get [-1, 0, 0]
      S€                Sum €ach. Get [1, -1]
        ~               Inverse
          ¦               at element
         2                2. (list[2] = ~list[2]) Get [-1, 2]
           Ḥ            Unhalve (double, ×2). Get [-2, 4]
            ;           Concatenate with
             L            Length (3). Get [-2, 4, 3]
              Ṁ         Maximum of the list (4).
               <   ¤    Still less than
                2         two
                 *        raise to the power of
                  Ɠ       eval(input())

user202729
la source

Cela semble ~2¦possible ;~. EDIT: Terminé.

user202729

@ user202729 Incorrect. Cela ;~$fonctionnera quand même.

user202729

1

JavaScript (ES6), 114 octets

Prend des entrées dans la syntaxe de curry (A)(n). Renvoie un booléen.

A=>n=>!(A.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).some(a=>(s=eval(a.join`+`),s<0?~s:s)>>n-1)|A.length>>n)

Cas de test

Afficher l'extrait de code

let f =

A=>n=>!(A.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).some(a=>(s=eval(a.join`+`),s<0?~s:s)>>n-1)|A.length>>n)

console.log('[Truthy]')
console.log(f([0, 0, 0])(2))
console.log(f([1, 2, 3, 4, 5])(8))
console.log(f([1, 2, 3, 4, 5])(5))
console.log(f([-3, 4, 1])(4))
console.log(f([-34, 56, 41, -4, -14, -54, 30, 38])(16))
console.log(f([-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12])(12))

console.log('[Falsy]')
console.log(f([0, 0, 0, 0])(2)) // violates #2
console.log(f([1, 2, 3, 4, 5])(2)) // violates all conditions
console.log(f([10, 0, -10])(4)) // violates #1 and #4
console.log(f([27, -59, 20, 6, 10, 53, -21, 16])(8)) // violates #4
console.log(f([-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22])(7)) // violates #4

Développer l'extrait

Arnauld
la source

1

Pyth , 20 octets

>EleS++KyMsMyQmt_dKl

Essayez-le ici!

M. Xcoder
la source

@ user202729 J'ai demandé à l'OP, et nous n'avons pas à gérer la liste vide

M. Xcoder

1

Clojure, 121 117 octets

#(let[l(int(Math/pow 2(dec %2)))](every?(set(range(- l)l))(cons(count %)(for[i(vals(group-by pos? %))](apply + i)))))

Eh bien, c'était un peu stupide, la division en valeurs positives et négatives est beaucoup mieux que le tri. Original, mais étonnamment pas beaucoup plus long:

#(let[l(int(Math/pow 2(dec %2)))S(sort %)R reductions](every?(set(range(- l)l))(concat[(count S)](R + S)(R +(into()S)))))

Cela fonctionne en vérifiant les sommes de préfixe de la séquence dans l'ordre croissant et décroissant, je pense qu'il n'est pas nécessaire de générer toutes les combinaisons d'éléments dans A.

(into () S)est en fait identique à (reverse S), car les listes s'élèvent de la tête. Je ne pouvais pas trouver un moyen d'utiliser consau lieu de concatquand il y a deux listes consà. : /

NikoNyrh
la source

1

Gelée , 15 octets

ŒPS€Ḥ;~$;LṀl2<Ɠ

Essayez-le en ligne!

Explication

ŒPS€Ḥ;~$;LṀl2<Ɠ ~ Monadic full program.

ŒP              ~ Powerset.
  S€            ~ The sum of each subset.
    Ḥ           ~ Double (element-wise).
     ;~$        ~ Append the list of their bitwise complements.
        ;L      ~ Append the length of the first input.
          Ṁ     ~ And get the maximum.
           l2   ~ Base-2 logarithm.
             <Ɠ ~ Is smaller than the second input (from stdin)?

1 octet sauvé grâce à caird coinheringaahing (lecture de la deuxième entrée de STDIN au lieu de CLA).

M. Xcoder
la source

@ user202729 J'ai demandé à l'OP, et nous n'avons pas à gérer la liste vide

M. Xcoder

0

Husk , 14 octets

≥Lḋ▲ṁ§eLöa→DΣṖ

Aller avec la force brute en bouclant sur toutes les sous-listes, car la division en parties positives et négatives prend plus d'octets. Essayez-le en ligne!

Explication

≥Lḋ▲ṁ§eLöa→DΣṖ  Implicit inputs, say A=[1,2,3,4,5] and n=5
             Ṗ  Powerset of A: [[],[1],[2],[1,2],..,[1,2,3,4,5]]
    ṁ           Map and concatenate:
                  Argument: a sublist, say S=[1,3,4]
            Σ     Sum: 8
           D      Double: 16
          →       Increment: 17
        öa        Absolute value: 17
     §eL          Pair with length of S: [3,17]
                Result is [0,1,1,3,1,5,2,7,..,5,31]
   ▲            Maximum: 31
  ḋ             Convert to binary: [1,1,1,1,1]
 L              Length: 5
≥               Is it at most n: 1

Zgarb
la source

0

Python 2 , 72 71 70 octets

def f(x,n):t=2*sum(k*(k<0)for k in x);max(2*sum(x)-t,~t,len(x))>>n>0>_

La sortie se fait par présence / absence d'erreur .

Essayez-le en ligne!

Dennis
la source

Variation de N bits sur le sous-ensemble-Sum

Cas de test

Implémentation de référence (Python 3)

Réponses:

Wolfram Language (Mathematica) , 40 octets

Gelée , 19 octets

05AB1E , 13 12 11 octets

JavaScript (ES6), 75 63 58 octets

Gelée , 21 20 octets

JavaScript (ES6), 114 octets

Cas de test

Pyth , 20 octets

Clojure, 121 117 octets

Gelée , 15 octets

Explication

Husk , 14 octets

Explication

Python 2 , 72 71 70 octets