Faire zéro à partir des premiers chiffres

15

Défi

Le défi consiste à écrire un code qui prend un entier positif 'n' comme entrée et affiche toutes les façons possibles d'écrire les nombres de 1 à n, avec un signe positif ou négatif entre les deux, de sorte que leur somme soit égal à zéro. N'oubliez pas que vous ne pouvez utiliser que l'addition ou la soustraction.

Par exemple, si l'entrée est 3, il y a 2 façons de faire la somme 0:

 1+2-3=0
-1-2+3=0

Notez que les nombres sont en ordre, à partir de 1 jusqu'à n (ce qui est 3 dans ce cas). Comme il ressort de l'exemple, le signe du premier nombre peut également être négatif, alors soyez prudent.

Maintenant, 3 était à peu près simple. Énumérons toutes les façons lorsque nous considérons le nombre 7.

 1+2-3+4-5-6+7=0
 1+2-3-4+5+6-7=0
 1-2+3+4-5+6-7=0
 1-2-3-4-5+6+7=0
-1+2+3+4+5-6-7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
-1-2+3-4+5+6-7=0

Donc, ici, nous avons un total de 8 façons possibles.


Entrée et sortie

Comme indiqué précédemment, l' entrée serait un entier positif . Votre sortie doit contenir toutes les manières possibles dont les nombres donnent une somme de zéro. Dans le cas où il n'y a aucun moyen de faire la même chose, vous pouvez sortir tout ce que vous voulez.

En outre, vous pouvez imprimer la sortie dans un format que vous souhaitez . Mais cela devrait être compréhensible . Par exemple, vous pouvez l'imprimer comme dans l'exemple ci-dessus. Ou, vous pouvez simplement imprimer les signes des nombres dans l'ordre. Sinon, vous pouvez également imprimer les «0» et les «1» dans l'ordre, où «0» afficherait un signe négatif et «1» afficherait un signe positif (ou vice versa).

Par exemple, vous pouvez représenter 1 + 2-3 = 0 en utilisant:

1+2-3=0
1+2-3
[1,2,-3]
++-
110
001    

Cependant, je recommanderais d'utiliser l'un des trois premiers formats pour plus de simplicité. Vous pouvez supposer que toutes les entrées sont valides.


Exemples

7 ->

 1+2-3+4-5-6+7=0
 1+2-3-4+5+6-7=0
 1-2+3+4-5+6-7=0
 1-2-3-4-5+6+7=0
-1+2+3+4+5-6-7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
-1-2+3-4+5+6-7=0

4 ->

 1-2-3+4=0
-1+2+3-4=0

2 -> -

8 ->

 1+2+3+4-5-6-7+8=0
 1+2+3-4+5-6+7-8=0
 1+2-3+4+5+6-7-8=0
 1+2-3-4-5-6+7+8=0
 1-2+3-4-5+6-7+8=0
 1-2-3+4+5-6-7+8=0
 1-2-3+4-5+6+7-8=0
-1+2+3-4+5-6-7+8=0
-1+2+3-4-5+6+7-8=0
-1+2-3+4+5-6+7-8=0
-1-2+3+4+5+6-7-8=0
-1-2+3-4-5-6+7+8=0
-1-2-3+4-5+6-7+8=0
-1-2-3-4+5+6+7-8=0

Notation

C'est le , donc le code le plus court gagne!

Manish Kundu
la source
Veuillez noter que ce n'est pas une dupe de codegolf.stackexchange.com/questions/8655/… , car ce défi est destiné à ne prendre que n en entrée et à utiliser tous les nombres 1-n dans l'ordre.
Manish Kundu
Pouvons-nous représenter au +fur Net à -mesure -N, ou est-ce que cela va trop loin? (par exemple 3-> [[-3,-3,3], [3,3,-3]])
Jonathan Allan
@JonathanAllan N'est-ce pas mentionné dans la liste des formats de sortie? Ou ai-je mal interprété votre question?
Manish Kundu
Je veux dire comme l' option 0et 1mais en utilisant Net -N(voir ma modification ci-dessus)
Jonathan Allan
2
@JonathanAllan Oui, c'est certainement permis. Assurez-vous de le mentionner dans la réponse.
Manish Kundu

Réponses:

5

Gelée , 9 octets

1,-ṗ×RSÐḟ

Essayez-le en ligne!

Exp

1,-ṗ×RSÐḟ  Main link. Input = n. Assume n=2.
1,-        Literal list [1, -1].
   ṗ       Cartesian power n. Get [[1, 1], [1, -1], [-1, 1], [-1, -1]]
    ×R     Multiply (each list) by Range 1..n.
       Ðḟ  ilter out lists with truthy (nonzero)
      S      Sum.

Gelée , 9 octets

La suggestion de Jonathan Allan a produit une liste de signes.

1,-ṗæ.ÐḟR

Essayez-le en ligne!

user202729
la source
1
Que diriez-vous (ab?) D'utiliser le format de sortie laxiste avec ,Nṗæ.ÐḟR?
Jonathan Allan
Ou bien, cette sortie multiplie les sorties par n.
user202729
La Net -Nsortie je l' ai suggéré a été autorisée, de sorte que enregistre un octet :) (juste besoin de mentionner le format dans la réponse)
Jonathan Allan
5

Python 2 , 62 octets

f=lambda n,*l:f(n-1,n,*l)+f(n-1,-n,*l)if n else[l]*(sum(l)==0)

Essayez-le en ligne!

M. Xcoder a économisé 4 octets avec une utilisation astucieuse des arguments étoilés.

xnor
la source
1
62 octets utilisant *lau lieu del=[]
M. Xcoder
3

Perl, 37 36 octets

perl -E 'map eval||say,glob join"{+,-}",0..<>' <<< 7
Ton Hospel
la source
Bien fait. Vous pouvez laisser tomber -net <<<si vous remplacez $_par pop. Cela n'améliore pas réellement votre score, mais cela raccourcit l'expression globale;)
Chris
2

05AB1E , 11 octets

®X‚¹ãʒ¹L*O_

Essayez-le en ligne!

Le format de sortie pour, par exemple, l'entrée 3est:

[[-1, -1, 1], [1, 1, -1]]

C'est -1-2+3, 1+2-3.

Erik le Outgolfer
la source
2

Husk , 10 octets

fo¬ΣΠmSe_ḣ

Essayez-le en ligne!

Explication

Pas trop compliqué.

fo¬ΣΠmSe_ḣ  Implicit input, say n=4
         ḣ  Range: [1,2,3,4]
     m      Map over the range:
      Se     pair element with
        _    its negation.
            Result: [[1,-1],[2,-2],[3,-3],[4,-4]]
    Π       Cartesian product: [[1,2,3,4],[1,2,3,-4],..,[-1,-2,-3,-4]]
f           Keep those
   Σ        whose sum
 o¬         is falsy (equals 0): [[-1,2,3,-4],[1,-2,-3,4]]
Zgarb
la source
2

Python 3 , 105 octets

lambda n:[k for k in product(*[(1,-1)]*n)if sum(-~n*s for n,s in enumerate(k))==0]
from itertools import*

Essayez-le en ligne!

ovs
la source
1

Swift , 116 octets

func f(n:Int){var r=[[Int]()]
for i in 1...n{r=r.flatMap{[$0+[i],$0+[-i]]}}
print(r.filter{$0.reduce(0){$0+$1}==0})}

Essayez-le en ligne!

Explication

func f(n:Int){
  var r=[[Int]()]                         // Initialize r with [[]]
                                          // (list with one empty list)
  for i in 1...n{                         // For i from 1 to n:
    r=r.flatMap{[$0+[i],$0+[-i]]}         //   Replace every list in r with the list
  }                                       //   prepended with i and prepended with -i
  print(r.filter{$0.reduce(0){$0+$1}==0}) // Print all lists in r that sums to 0
}
Herman L
la source
1

Python 2 , 91 octets

lambda x:[s for s in[[~j*[1,-1][i>>j&1]for j in range(x)]for i in range(2**x)]if sum(s)==0]

Essayez-le en ligne!

Renvoie une liste de listes satisfaisantes (par exemple, f (3) = [[- 1, -2,3], [1,2, -3]])

Chas Brown
la source
1

C (gcc) , 171 octets

k,s;f(S,n,j)int*S;{if(j--)S[j]=~0,f(S,n,j),S[j]=1,f(S,n,j);else{for(s=k=0;k<n;k++)s+=S[k]*-~k;if(!s&&puts(""))for(k=0;k<n;)printf("%d",S[k++]+1);}}F(n){int S[n];f(S,n,n);}

Essayez-le en ligne! Utilise 0pour les 2signes négatifs et positifs.

Jonathan Frech
la source
1

Nettoyer , 79 octets

import StdEnv
$n=[k\\k<-foldr(\i l=[[p:s]\\s<-l,p<-[~i,i]])[[]][1..n]|sum k==0]

Essayez-le en ligne!

Οurous
la source
1

Python 3 + numpy, 104 103 octets

import itertools as I,numpy as P
lambda N:[r for r in I.product(*[[-1,1]]*N)if sum(P.arange(N)*r+r)==0]

La sortie est [-1, 1] correspondant au signe.

user2699
la source
Vous pouvez supprimer l'espace avant ifpour -1 octet
ovs
0

JavaScript (ES6), 69 61 octets

8 octets enregistrés en se débarrassant de k , comme suggéré par @Neil

Imprime toutes les solutions avec alert () .

f=(n,o='')=>n?f(n-1,o+'+'+n)&f(n-1,o+'-'+n):eval(o)||alert(o)

Cas de test

Utilisation de console.log () au lieu de alert () pour plus de convivialité.

Arnauld
la source
Avez-vous besoin k? Quelque chose comme ça:f=(n,o='')=>n?['+','-'].map(c=>f(n-1,c+n+o)):eval(o)||alert(o)
Neil
@Neil, vraiment pas ... Merci.
Arnauld
0

Rétine , 73 octets

.+
*
_
=_$`
+0`=
-$%"+
(-(_)+|\+(_)+)+
$&=$#2=$#3=
G`(=.+)\1=
=.*

_+
$.&

Essayez-le en ligne! Explication:

.+
*

Convertissez l'entrée en unaire.

_
=_$`

Convertissez le nombre en une liste de =nombres préfixés.

+0`=
-$%"+

Remplacez chacun =à son tour par les deux -et +, en dupliquant le nombre de lignes à chaque fois.

(-(_)+|\+(_)+)+
$&=$#2=$#3=

Comptez séparément le nombre de _s après -s et +s. Cela résume les nombres négatifs et positifs.

G`(=.+)\1=

Conservez uniquement les lignes où les -s et +s s'annulent.

=.*

Supprimez les comptes.

_+
$.&

Convertissez en décimal.

Neil
la source
0

Perl 6 , 43 octets

{grep *.sum==0,[X] (1..$_ X*1,-1).rotor(2)}

Try it
Renvoie une séquence de listes

Étendu:

{  # bare block lambda with implicit parameter 「$_」

  grep              # only return the ones
    *.sum == 0,     # that sum to zero

    [X]             # reduce with cross meta operator

      (
          1 .. $_   # Range from 1 to the input

        X*          # cross multiplied by

          1, -1

      ).rotor(2)    # take 2 at a time (positive and negative)
}

1..$_ X* 1,-1(1, -1, 2, -2)
(…).rotor(2)((1, -1), (2, -2))
[X] …((1, 2), (1, -2), (-1, 2), (-1, -2))

Brad Gilbert b2gills
la source
0

J , 35 30 octets

-5 octets grâce à FrownyFrog!

>:@i.(]#~0=1#.*"1)_1^2#:@i.@^]

Essayez-le en ligne!

Original:

J , 35 octets

[:(#~0=+/"1)>:@i.*"1(_1^[:#:@i.2^])

Comment ça fonctionne

Je multiplie la liste 1..n avec toutes les listes possibles de coefficients 1 / -1 et je trouve celles qui s'additionnent à zéro.

                    (             ) - the list of coefficients
                             i.     - list 0 to 
                               2^]  - 2 to the power of the input
                     _1^[:          - -1 to the power of 
                          #:@       - each binary digit of each number in 0..n-1 to 
                 *"1                - each row multiplied by
            >:@i.                   - list 1..n
  (#~      )                        - copy those rows
     0=+/"1                         - that add up to 0
[:                                  - compose   

Essayez-le en ligne!

Comme alternative, j'ai essayé un verbe explicite, en utilisant l'approche du produit cartésien de +/-:

J , 37 octets

3 :'(#~0=+/"1)(-y)]\;{(<"1@,.-)1+i.y'

{(<"1@,.-) trouve les produits cartésiens par exemple:

{(<"1@,.-) 1 2 3
┌───────┬────────┐
│1 2 3  │1 2 _3  │
├───────┼────────┤
│1 _2 3 │1 _2 _3 │
└───────┴────────┘

┌───────┬────────┐
│_1 2 3 │_1 2 _3 │
├───────┼────────┤
│_1 _2 3│_1 _2 _3│
└───────┴────────┘

Dommage qu'il contienne le résultat, j'ai donc dépensé quelques octets pour déballer les valeurs

Essayez-le en ligne!

Galen Ivanov
la source
@FrownyFrog Merci, je n'étais pas satisfait du côté droit de mon code.
Galen Ivanov