Fewest operations to 100

Question

Overview

Given a list of digits, find the fewest operations to make 100

Input

A string of digits, which may or may not be in numerical order. The order of the digits cannot be changed, however plus (+) or minus (-) operators may be added between each so that the total sum is equal to 100.

Output

The number of operators added, followed by the full sequence of digits and operators. The two can be separated by a space, tab, or new line sequence.

Examples

valid

Input: 123456789
Output: 3 123–45–67+89

Invalid
Input: 123456789
Output:
6 1+2+34-5+67-8+9
(There are ways of solving this with fewer operations)

Answer 1

JavaScript (ES6), 153 176 bytes

EDIT: In non-strict mode, JS interprets 0-prefixed numerical expressions as octal (e.g. 017 is parsed as 15 in decimal). This is a fixed version that supports leading zeros.

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

Answer 2

MATL, 37 36 bytes

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

The test case takes about 6 seconds in TIO.

Try it online!

How it works

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

Answer 3

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

Try it online!

Take N as a string of digits; returns a tuple (numOps, expressionString).

Basically the same approach as others; uses itertools.product to construct the individual "cases" e.g. for N=='1322', a "case" would be ('-','','+'), and would evaluate '1-32+2'.

Throws an ValueError if the input is invalid (but I think OP gauranteed no invalid inputs).

Answer 4

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

Run as pipe with -nR or test it online.

uses formatted numbers to sort the results -->
may print leading blanks (and may fail for input with more than 99 digits; increase the number at %2d to fix).

no more than 10 digits, 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);

breakdown

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

Answer 5

Jelly, 32 bytes

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

A full program which displays using the Jelly operators (_ instead of -).

Note: To show - in the output instead of _ (not a requirement) add ⁾_-y between F and Ṅ (⁾_- is a character pair literal ['_','-'] and y is the dyadic "translate" atom).

How?

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

Try it online!

Answer 6

Brachylog, 36 bytes

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

Try it online!

More than half of this is to get the output format right though. The actual core logic is only:

15 bytes

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

Try it online!

This returns a list like [123,–45,–67,89]. The expression is the sum of the elements, and the number of operators is 1 less than the length of the list.

~cLhℕ∧100~+L almost works for 12 bytes (Try it online!) - but it's too slow to handle full 9 digit input on TIO, and more importantly, it fails for inputs like 10808 - Brachylog is too smart to split numbers to have leading zeros, so doesn't see the [108, -08] partition.

Answer 7

Mathematica, 136 146 149 156 165 166 bytes

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

Returns {3, 123-45-67+89} for example.

The test case takes about 0.09 seconds to complete.

Answer 8

Python 2, 256 230 208 205 172 171 170 165 bytes, iterative method

• 33 thanks to Chas Brown
• One saved byte when replacing len(a) by w
• One saved byte when replacing z-=1;d=z by d=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)

Try it online!

Little explanation Using the representation in base 3, the code interleaves the digits with the operators {'+','-',concatenation} according to all possible combinations.

Python 2, 167 bytes, recursive method

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)

Try it online!

Some outputs

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

Answer 9

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]

Try it online! Usage: g "123456789" yields (3,"123-45-67+89").

# builds a list of all possible terms, ? evaluates a term and g filters those terms which evaluate to 100 and returns the one with the minimal number of operands.

Answer 10

Jelly, 27 bytes

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

Try it online!

Can't say I didn't take a few hints from Jonathan Allan's older answer. ;-)

Compared to his answer, this one is just two bytes shorter (30), not five, if we make the comparison fair due to language updates:

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

If we compare the other way (newer version instead of older), the difference is the same (his becomes 29 bytes, seen below):

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