15
\$\begingroup\$

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)

|improve this question
\$\endgroup\$
  • \$\begingroup\$ Related \$\endgroup\$ – Adám Jul 4 '17 at 12:23
  • \$\begingroup\$ Do we have to use all of the digits? Can we only use + and -? Can we assume we will always be able to make 100 from the input? \$\endgroup\$ – TheLethalCoder Jul 4 '17 at 12:50
  • 6
    \$\begingroup\$ Some more test cases would be much welcome. \$\endgroup\$ – Arnauld Jul 4 '17 at 13:36
  • 2
    \$\begingroup\$ Can you confirm that signs cannot be prepended to the first digit? That is, given input 299399, would -299+399 be valid? \$\endgroup\$ – Luis Mendo Jul 4 '17 at 17:08
  • 1
    \$\begingroup\$ Is '0' a digit? E.g., is '10808' a valid input? Is '1 108-08' a valid response? \$\endgroup\$ – Chas Brown Jul 4 '17 at 19:07

10 Answers 10

10
\$\begingroup\$

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

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Nice, what about 20172117 as input? \$\endgroup\$ – mdahmoune Jul 4 '17 at 16:47
  • \$\begingroup\$ @LuisMendo Actually, I think the expected answer is 2-017-2+117. But 017 is an octal notation in JS, which gives 15 in decimal. So my current code only finds 2-0-17-2+117. I'll try to address that problem later today. \$\endgroup\$ – Arnauld Jul 5 '17 at 6:17
  • \$\begingroup\$ @Arnauld Ah, I hadn't seen that other solution. Removing my comment \$\endgroup\$ – Luis Mendo Jul 5 '17 at 7:10
  • \$\begingroup\$ @mdahmoune Thanks for bringing this up. Now fixed. \$\endgroup\$ – Arnauld Jul 5 '17 at 13:09
  • \$\begingroup\$ 3**(l=s.length,l-1) => 3**~-(l=s.length) \$\endgroup\$ – l4m2 May 23 '18 at 1:35
5
\$\begingroup\$

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
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Great, what about 299399 as input? \$\endgroup\$ – mdahmoune Jul 4 '17 at 16:44
  • 1
    \$\begingroup\$ @mdahmoune 299399 has no solution and is hence not a valid input (the operators were specified to go "between" the digits, that input would require -299+399 where the - is not between digits). \$\endgroup\$ – Jonathan Allan Jul 4 '17 at 17:06
  • \$\begingroup\$ @mdahmoune If the signs can only be inserted between the digits (as the challenge text says), I think there is no solution. If they can also be prepended to the first digit, the solution is -299+399, and in that case I need a small change in my code. I've asked the OP for clarification \$\endgroup\$ – Luis Mendo Jul 4 '17 at 17:06
  • \$\begingroup\$ Also noteworthy that if it were meant to be both before and between then the example 123456789 should have an operator count of 4 not 3. \$\endgroup\$ – Jonathan Allan Jul 4 '17 at 17:17
  • \$\begingroup\$ @mdahmoune The OP has confirmed that signs can only be between digits. So my code is correct and 299399 is an invalid input because, as the OP has also clarified, every input should have at least one solution \$\endgroup\$ – Luis Mendo Jul 4 '17 at 23:17
3
\$\begingroup\$

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

|improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
|improve this answer
\$\endgroup\$
3
\$\begingroup\$

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!

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
2
\$\begingroup\$

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')
|improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ I like the use of divmod! A few golfs I can see: replace list(input()) with just input(), since a string is already iterable to save 6 bytes; replace b.count('+')+b.count('-') with len(b)-len(a) to save 12 bytes; and replace chr(r+43) with chr(r+43)*(d>0!=r-1) and then you can delete the line b=b[:-1].replace(',','') to save net 15 bytes ((d>0!=r-1) is equivalent to (d>0 and 0!=r-1)). \$\endgroup\$ – Chas Brown Jul 4 '17 at 21:31
2
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
|improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.