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)

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"))

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

[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).

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

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!

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.

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')

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].

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.

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