Moins d'opérations à 100

15

Aperçu

Étant donné une liste de chiffres, trouvez le moins d'opérations pour faire 100

Contribution

Une chaîne de chiffres, qui peut ou non être dans l'ordre numérique. L'ordre des chiffres ne peut pas être modifié, mais des opérateurs plus (+) ou moins (-) peuvent être ajoutés entre chacun afin que la somme totale soit égale à 100.

Production

Le nombre d'opérateurs ajoutés, suivi de la séquence complète des chiffres et des opérateurs. Les deux peuvent être séparés par un espace, une tabulation ou une nouvelle séquence de lignes.

Exemples

valide

Entrée: 123456789
Sortie:3 123–45–67+89


Entrée non valide : 123456789
Sortie:
6 1+2+34-5+67-8+9
(Il existe des moyens de résoudre ce problème avec moins d'opérations)

CyberJacob
la source
En relation
Adám
Doit-on utiliser tous les chiffres? Pouvons-nous utiliser uniquement +et -? Pouvons-nous supposer que nous serons toujours en mesure de faire à 100partir de l'entrée?
TheLethalCoder
6
D'autres cas de test seraient les bienvenus.
Arnauld
2
Pouvez-vous confirmer que les signes ne peuvent pas être ajoutés au premier chiffre? Autrement dit, étant donné l'entrée 299399, serait -299+399valide?
Luis Mendo
1
'0' est-il un chiffre? Par exemple, «10808» est-il une entrée valide? '1 108-08' est-il une réponse valide?
Chas Brown

Réponses:

10

JavaScript (ES6), 153 176 octets

EDIT: En mode non strict, JS interprète les expressions numériques à préfixe 0 comme octales (par exemple, 017est analysé comme 15 en décimal). Il s'agit d'une version fixe qui prend en charge les zéros non significatifs.

let f =

s=>[...Array(3**(l=s.length,l-1))].map((_,n)=>m=eval((x=s.replace(/./g,(c,i)=>c+['','+','-'][o=(n/3**i|0)%3,j-=!o,o],j=l)).replace(/\b0+/g,' '))-100|j>m?m:(S=x,j),m=l)&&m+' '+S

console.log(f("123456789"))
console.log(f("20172117"))

Arnauld
la source
Bien, qu'en est-il de 20172117 en entrée?
mdahmoune
@LuisMendo En fait, je pense que la réponse attendue est 2-017-2+117. Mais 017c'est une notation octale en JS, qui donne 15 en décimal. Donc, mon code actuel ne trouve que 2-0-17-2+117. Je vais essayer de résoudre ce problème plus tard dans la journée.
Arnauld
@Arnauld Ah, je n'avais pas vu cette autre solution. Suppression de mon commentaire
Luis Mendo
@mdahmoune Merci d'avoir soulevé cette question. Maintenant corrigé.
Arnauld
3**(l=s.length,l-1)=>3**~-(l=s.length)
l4m2
5

MATL , 37 36 octets

n'+-'OhZ^!t2\s&SZ)"G@!vXzU100=?@z3M.

Le cas de test prend environ 6 secondes dans TIO.

Essayez-le en ligne!

Comment ça fonctionne

n        % Implicitly input a string. Number of elements, say k
'+-'     % Push this string
Oh       % Append char 0. This is treated like ' ' (space)
Z^       % Cartesian power of the three-char string '+- ' raised to k.
         % Gives a matrix where each row is a Cartesian k-tuple
!        % Transpose
t        % Duplicate
2\       % Modulo 2. This turns '+' and '-' into 1, and ' ' into 0
s        % Sum of each column: number of '+' and '-' symbols
&S       % Sort and push the indices of the sorting
Z)       % Apply as column indices. This sorts the columns (k-tuples)
         % by the number of '+' and '-' they contain
"        % For each column, i.e. each k-tuple formed by '+', '-' and ' '
  G      %   Push input string again
  @!     %   Push k-tuple as row vector (string)
  v      %   Concatenate vertically into a 2×k char array
  Xz     %   Remove space (and char 0). Gives a string as result. In this
         %   process, the 2×k array is linearized in column major order 
         %   (down, then across). So the '+' and '-' signs are between 
         %   digits of the input, or at the end
  U      %   Convert to number. This performs the operation determined by
         %   by the '+' and '-' signs and returns the result. A trailing
         %   '+' or '-' sign makes the input invalid, which causes an
         %   empty result
  100=   %   Is it equal to 100?
  ?      %   If so
    @    %     Push current k-tuple
    z    %     Number of nonzeros, i.e. of '+' and '-' signs
    3M   %     Push linearized string without spaces again
    .    %     Break for loop
         %   Implicit end
         % Implicit end
         % Implicitly dispplay stack
Luis Mendo
la source
Super, qu'en est-il du 299399 en entrée?
mdahmoune
1
@mdahmoune 299399n'a pas de solution et n'est donc pas une entrée valide (les opérateurs ont été spécifiés pour aller "entre" les chiffres, cette entrée nécessiterait -299+399où le -n'est pas entre les chiffres).
Jonathan Allan
@mdahmoune Si les signes ne peuvent être insérés qu'entre les chiffres (comme le dit le texte du défi), je pense qu'il n'y a pas de solution. S'ils peuvent également être ajoutés au premier chiffre, la solution est -299+399, et dans ce cas, j'ai besoin d' un petit changement dans mon code . J'ai demandé des éclaircissements au PO
Luis Mendo
Il convient également de noter que s'il devait être à la fois avant et entre les deux, l'exemple 123456789devrait avoir un nombre d'opérateurs 4non 3.
Jonathan Allan
@mdahmoune L'OP a confirmé que les signes ne peuvent être qu'entre chiffres. Donc, mon code est correct et 299399est une entrée non valide car, comme l'OP l'a également précisé, chaque entrée doit avoir au moins une solution
Luis Mendo
3

[Python 2], 164 158 octets

from itertools import*
f=lambda N:min((len(s)-len(N),s)for s in(''.join(sum(zip(N,p+('',)),()))for p in product(('+','-',''),repeat=len(N)-1))if eval(s)==100)

Essayez-le en ligne!

Prenez N comme une chaîne de chiffres; renvoie un tuple (numOps, expressionString).

Fondamentalement, la même approche que les autres; utilise itertools.product pour construire les "cas" individuels, par exemple pour N == '1322', un "cas" serait ('-','','+'), et évaluerait '1-32 + 2'.

Lance une ValueError si l'entrée n'est pas valide (mais je pense que OP n'a garanti aucune entrée invalide).

Chas Brown
la source
3

PHP, 166 171 octets

for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=sprintf("%2d $s",strlen($s)-$e))for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);

Exécuter en tant que pipe avec -nRou tester en ligne .

utilise des nombres formatés pour trier les résultats ->
peut imprimer des blancs en tête (et peut échouer pour la saisie avec plus de 99 chiffres; augmenter le nombre à %2dpour corriger).

pas plus de 10 chiffres, 161 octets

for(;$n<3**$e=strlen($x=$argn);eval("return $s;")-100?:$r[]=(strlen($s)-$e)." $s")for($i=0,$s="",$k=$n++;a&$c=$x[$i];$k/=3)$s.="+-"[$i++?$k%3:2].$c;echo min($r);

panne

for(;$n<3**$e=strlen($x=$argn); # loop $n up
    eval("return $s;")-100?:        # 2. evaluate term, if 100 then
                                    # prepend number of operations, add to results
        $r[]=sprintf("%2d $s",strlen($s)-$e)
)
                                # 1. create term
    for($i=0,$s="",$k=$n++;         # init variables, increment $n
        a&$c=$x[$i];$k/=3)          # loop through digits/operator index
        $s.="+-"[$i++?$k%3:2].$c;   # prepend operator for base-3 digit (nothing for 2)
echo min($r);                   # print lowest result
Titus
la source
3

Gelée , 32 octets

L’⁾+_ṗż@€
ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L

Un programme complet qui s'affiche à l'aide des opérateurs Jelly (_ au lieu de -).

Remarque: pour afficher -dans la sortie au lieu de _(pas obligatoire), ajoutez ⁾_-yentre Fet (⁾_- est un littéral de paire de caractères ['_','-']et yest l'atome dyadique "translate").

Comment?

L’⁾+_ṗż@€ - Link 1, form all sums from a partition: list of lists of characters
                                     e.g. ["12","345","67"]
L         - length                        3
 ’        - decremented                   2
  ⁾+_     - literal ['+','_']
     ṗ    - Cartesian power               ["++","+_","_+","__"]
      ż@€ - zip for €ach (swap @rguments) ["12+345+67","12+345_67","12_345+67","12_345_67"]

ŒṖÇ€ẎµFV=ȷ2µÐfLÞḢFṄḟ³L - Main link: list of characters
ŒṖ                     - all partitions
  Ç€                   - call the last link (1) as a monad for €ach
    Ẏ                  - tighten (flatten by 1 level)
     µ     µÐf         - filter keep if:
      F                -   flatten
       V               -   evaluate as Jelly code (perform the sum)
         ȷ2            -   literal 100
        =              -   equal?
               Þ       - sort by:
              L        -  length
                Ḣ      - head
                 F     - flatten
                  Ṅ    - print that and a newline
                   ḟ³  - filter out the characters from the input
                     L - length (number of operators)
                       - implicit print

Essayez-le en ligne!

Jonathan Allan
la source
2

Mathematica, 136 146 149 156 165 166 octets

#&@@Sort[{StringLength@#-e+9!(ToExpression@#-100)^2,#}&/@StringJoin/@(Riffle[b,#]&)/@Tuples[{"","+","-"},(e=Length[b=Characters@#])-1]]&

Renvoie {3, 123-45-67+89}par exemple.

Le test élémentaire prend environ 0,09 seconde.

Keyu Gan
la source
2

Python 2 , 256 230 208 205 172 171 170 165 octets, méthode itérative

  • 33 merci à Chas Brown
  • Un octet enregistré lors du remplacement len(a)parw
  • Un octet enregistré lors du remplacement z-=1;d=zpard=z=z-1
q=[];a=input()
w=len(a);z=n=3**w
while z-n/3:
 d=z=z-1;j=0;b=''
 while d:r=d%3;d/=3;b+=a[j]+chr(r+43)*(d>0!=r-1);j+=1
 if eval(b)==100:q+=[(len(b)-w,b)]
print min(q)

Essayez-le en ligne!

Petite explication En utilisant la représentation en base 3, le code entrelace les chiffres avec les opérateurs {'+', '-', concaténation} selon toutes les combinaisons possibles.

Python 2 , 167 octets, méthode récursive

def f(s):
 if len(s)==1:return[s]
 b=s[0];q=[]
 for z in f(s[1:]):q+=[b+'+'+z,b+'-'+z,b+z]
 return q
a=input()
print min((len(x)-len(a),x)for x in f(a)if eval(x)==100)

Essayez-le en ligne!

Quelques sorties

"399299"    --> (1, '399-299')
"987654321" --> (4, '98-76+54+3+21')
"1111111"   --> (3, '1+111-1-11')
mdahmoune
la source
1
J'aime l'utilisation de divmod! Quelques golfs que je peux voir: remplacer list(input())par juste input(), car une chaîne est déjà itérable pour économiser 6 octets; remplacer b.count('+')+b.count('-')par len(b)-len(a)pour économiser 12 octets; et remplacez chr(r+43)par chr(r+43)*(d>0!=r-1)puis vous pouvez supprimer la ligne b=b[:-1].replace(',','')pour économiser net 15 octets ( (d>0!=r-1)équivaut à (d>0 and 0!=r-1)).
Chas Brown
2

Brachylog , 36 octets

~cịᵐ{|ṅ}ᵐ{+100&{ℕṫ,"+"↻|ṫ}ᵐcbE&kl;E}

Essayez-le en ligne!

Cependant, plus de la moitié de cela consiste à obtenir le bon format de sortie. La logique de base réelle est seulement:

15 octets

~cịᵐ{|ṅ}ᵐ.+100∧

Essayez-le en ligne!

Cela renvoie une liste comme [123, –45, –67,89]. L'expression est la somme des éléments et le nombre d'opérateurs est inférieur de 1 à la longueur de la liste.

~cLhℕ∧100~+Lfonctionne presque pendant 12 octets ( essayez-le en ligne! ) - mais il est trop lent pour gérer la pleine entrée à 9 chiffres sur TIO, et plus important encore, il échoue pour des entrées comme 10808- Brachylog est trop intelligent pour diviser les nombres pour avoir des zéros en tête, donc ne fait pas '' t voir la partition [108, -08].

Sundar - Rétablir Monica
la source
1

Haskell , 180 178 octets

m#[a]=[[a]]
m#(b:r)|s<-m#r=m(b:)=<<[s,m('+':)s,m('-':)s]
o '-'=(-)
o _=(+)
(p:r)?a|[(b,s)]<-lex r=s?o p a(read b)
_?a=a
g s=minimum[(sum[1|c<-t,c<'0'],t)|t<-map#s,('+':t)?0==100]

Essayez-le en ligne! Utilisation: g "123456789"rendements (3,"123-45-67+89").

#construit une liste de tous les termes possibles, ?évalue un terme et gfiltre les termes qui évaluent à 100 et renvoie celui avec le nombre minimal d'opérandes.

Laikoni
la source
0

Gelée , 27 octets

L’““+“_”ṗ⁸żF¥ⱮV⁼ȷ2ƊƇLÞḢṄḟ⁸L

Essayez-le en ligne!

Je ne peux pas dire que je n'ai pas pris quelques indices de l'ancienne réponse de Jonathan Allan. ;-)

Comparé à sa réponse, celui-ci n'est que de deux octets plus court (30), pas cinq, si nous rendons la comparaison équitable en raison des mises à jour linguistiques:

L’““+“_”ṗ⁸żF¥Ð€V⁼ȷ2$$ÐfLÞḢṄḟ⁸L

Si nous comparons dans l'autre sens (une version plus récente au lieu d'une ancienne), la différence est la même (la sienne devient 29 octets, vue ci-dessous):

ŒṖżⱮL’⁾+_ṗƲ$€ẎFV=ȷ2ƲƇLÞḢFṄḟ³L
Erik le Outgolfer
la source