Fewest operations to 100 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)
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=&gt;[...Array(3**(l=s.length,l-1))].map((_,n)=&gt;m=eval((x=s.replace(/./g,(c,i)=&gt;c+['','+','-'][o=(n/3**i|0)%3,j-=!o,o],j=l)).replace(/\b0+/g,' '))-100|j&gt;m?m:(S=x,j),m=l)&amp;&amp;m+' '+S

console.log(f("123456789"))
console.log(f("20172117"))