Überblick

Suchen Sie anhand einer Liste mit Ziffern die wenigsten Operationen, um 100 zu erhalten

Eingang

Eine Zeichenfolge, die in numerischer Reihenfolge vorliegen kann oder nicht. Die Reihenfolge der Ziffern kann nicht geändert werden. Es können jedoch jeweils Plus- (+) oder Minus-Operatoren (-) hinzugefügt werden, sodass die Gesamtsumme gleich 100 ist.

Ausgabe

Die Anzahl der hinzugefügten Operatoren, gefolgt von der vollständigen Folge von Ziffern und Operatoren. Die beiden können durch ein Leerzeichen, einen Tabulator oder eine neue Zeilenfolge getrennt werden.

Beispiele

gültig

Eingabe: 123456789
Ausgabe:3 123–45–67+89

Ungültige
Eingabe: 123456789
Ausgabe:
6 1+2+34-5+67-8+9
(Es gibt Möglichkeiten, dies mit weniger Operationen zu lösen.)

JavaScript (ES6), 153 bis 176 Byte

BEARBEITEN: Im nicht strengen Modus interpretiert JS numerische Ausdrücke mit dem Präfix 0 als Oktal (z. B. 017wird sie als 15 in Dezimalform analysiert). Dies ist eine feste Version, die führende Nullen unterstützt.

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 Bytes

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

Der Testfall dauert in TIO ca. 6 Sekunden.

Probieren Sie es online!

Wie es funktioniert

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 Bytes

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)

Probieren Sie es online!

Nehmen Sie N als eine Folge von Ziffern; gibt ein Tupel zurück (numOps, expressionString).

Grundsätzlich der gleiche Ansatz wie bei anderen; verwendet itertools.product, um die einzelnen "Fälle" zu konstruieren, z. B. für N == '1322', wäre ein "Fall" ('-','','+')und würde '1-32 + 2' auswerten.

Wirft einen ValueError, wenn die Eingabe ungültig ist (aber ich denke, OP hat keine ungültigen Eingaben garantiert).

PHP, 166 171 Bytes

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

Laufen Sie als Rohr mit -nRoder testen Sie es online .

sortiert die Ergebnisse mit formatierten Zahlen ->
druckt möglicherweise führende Leerzeichen (und schlägt möglicherweise bei Eingaben mit mehr als 99 Stellen fehl; erhöhen Sie die Zahl, um sie %2dzu korrigieren).

nicht mehr als 10 Stellen, 161 Bytes

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

Nervenzusammenbruch

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

Jelly , 32 Bytes

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

Ein vollständiges Programm, das mit den Jelly-Operatoren ( _anstelle von -) angezeigt wird .

Hinweis: Um -in der Ausgabe statt _(nicht erforderlich) anzuzeigen, fügen Sie ⁾_-yzwischen Fund Ṅ( ⁾_-ist ein Zeichenpaar-Literal ['_','-']und) einy ist das dyadische "translate" -Atom).

Wie?

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

Probieren Sie es online!

Mathematica, 136 146 149 156 165 166 Bytes

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

Gibt {3, 123-45-67+89}zum Beispiel zurück.

Der Testfall dauert ca. 0,09 Sekunden.

Python 2 , 256 230 208 205 172 171 170 165 Bytes, iterative Methode

• 33 danke an Chas Brown
• Ein gespeichertes Byte beim Ersetzen len(a)durchw
• Ein gespeichertes Byte beim Ersetzen z-=1;d=zdurchd=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)

Probieren Sie es online!

Kleine Erklärung Unter Verwendung der Darstellung in Basis 3 verschachtelt der Code die Ziffern mit den Operatoren {'+', '-', Verkettung} nach allen möglichen Kombinationen.

Python 2 , 167 Bytes, rekursive Methode

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)

Probieren Sie es online!

Einige Ausgänge

"399299"    --> (1, '399-299')
"987654321" --> (4, '98-76+54+3+21')
"1111111"   --> (3, '1+111-1-11')

Brachylog , 36 Bytes

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

Probieren Sie es online!

Mehr als die Hälfte davon ist das richtige Ausgabeformat. Die eigentliche Kernlogik ist nur:

15 Bytes

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

Probieren Sie es online!

Dies gibt eine Liste wie [123, –45, –67,89] zurück. Der Ausdruck ist die Summe der Elemente, und die Anzahl der Operatoren ist 1 weniger als die Länge der Liste.

~cLhℕ∧100~+LFunktioniert fast für 12 Bytes ( Online testen! ) - aber es ist zu langsam, um vollständige 9-stellige Eingaben auf TIO zu verarbeiten, und was noch wichtiger ist, es schlägt fehl für Eingaben wie 10808: Brachylog ist zu intelligent, um Zahlen zu teilen, um führende Nullen zu haben, oder? t Die Partition [108, -08] sehen.

Haskell , 180 178 Bytes

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]

Probieren Sie es online! Verbrauch: g "123456789"Erträge (3,"123-45-67+89").

#Erstellt eine Liste aller möglichen Begriffe, ?wertet einen Begriff aus und gfiltert die Begriffe, die mit 100 bewertet werden, und gibt denjenigen mit der minimalen Anzahl von Operanden zurück.

Gelee , 27 Bytes

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

Probieren Sie es online!

Ich kann nicht sagen, dass ich Jonathan Allans älterer Antwort nicht ein paar Hinweise entnommen habe. ;-)

Im Vergleich zu seiner Antwort ist diese nur zwei Bytes kürzer (30) und nicht fünf, wenn wir den Vergleich aufgrund von Sprachaktualisierungen fair halten:

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

Wenn wir die andere Art vergleichen (neuere Version statt ältere), ist der Unterschied der gleiche (seine wird 29 Bytes, siehe unten):

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