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)

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? — TheLethalCoder, Jul 4 '17 at 12:50
Can you confirm that signs cannot be prepended to the first digit? That is, given input 299399, would -299+399 be valid? — Luis Mendo, Jul 4 '17 at 17:08
Is '0' a digit? E.g., is '10808' a valid input? Is '1 108-08' a valid response? — Chas Brown, Jul 4 '17 at 19:07

Community · Accepted Answer · 2020-06-17 09:04:33Z

10

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

edited Jun 17 '20 at 9:04

CommunityBot

1

answered Jul 4 '17 at 13:45

Arnauld

159k15 gold badges158 silver badges564 bronze badges

\$\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

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

@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). — Jonathan Allan, Jul 4 '17 at 17:06
@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 — Luis Mendo, Jul 4 '17 at 17:06
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. — Jonathan Allan, Jul 4 '17 at 17:17
@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 — Luis Mendo, Jul 4 '17 at 23:17

Chas Brown · Accepted Answer · 2017-07-04 20:13:47Z

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

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Jonathan Allan · Accepted Answer · 2017-07-05 12:07:57Z

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!

Keyu Gan · Accepted Answer · 2017-07-06 05:07:46Z

2

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.

edited Jul 6 '17 at 5:07

answered Jul 4 '17 at 16:50

Keyu Gan

2,0888 silver badges25 bronze badges

Add a comment |

mdahmoune · Accepted Answer · 2017-07-14 10:22:57Z

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

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)). — Chas Brown, Jul 4 '17 at 21:31

sundar - Remember Monica · Accepted Answer · 2018-08-10 23:14:32Z

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.

Laikoni · Accepted Answer · 2017-07-05 16:42:17Z

1

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.

edited Jul 5 '17 at 16:42

answered Jul 5 '17 at 6:59

Laikoni

24.6k4 gold badges48 silver badges108 bronze badges

Add a comment |

Erik the Outgolfer · Accepted Answer · 2018-08-10 18:46:14Z

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

Stack Exchange Network

current community

your communities

more stack exchange communities

Fewest operations to 100

Overview

Input

Output

Examples

10 Answers 10

JavaScript (ES6), 153 176 bytes

MATL, 37 36 bytes

How it works

[Python 2], 164 158 bytes

PHP, 166 171 bytes

Jelly, 32 bytes

How?

Mathematica, 136 146 149 156 165 166 bytes

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

Python 2, 167 bytes, recursive method

Brachylog, 36 bytes

15 bytes

Haskell, 180 178 bytes

Jelly, 27 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf integer integer-partitions expression-building or ask your own question.

Linked

Hot Network Questions

Fewest operations to 100

Overview

Input

Output

Examples

10 Answers 10

JavaScript (ES6), 153 176 bytes

MATL, 37 36 bytes

How it works

[Python 2], 164 158 bytes

PHP, 166 171 bytes

Jelly, 32 bytes

How?

Mathematica, 136 146 149 156 165 166 bytes

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

Python 2, 167 bytes, recursive method

Brachylog, 36 bytes

15 bytes

Haskell, 180 178 bytes

Jelly, 27 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf integer integer-partitions expression-building or ask your own question.

Linked

Related

Hot Network Questions