Sum to 100: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 139: Line 139:
=={{header|JavaScript}}==
=={{header|JavaScript}}==
{{Trans|Haskell}}
{{Trans|Haskell}}
===ES6===
===ES5===
{{Trans|Haskell}}
<lang JavaScript>(function () {
'use strict';


// GENERIC FUNCTIONS ----------------------------------------------------

// permutationsWithRepetition :: Int -> [a] -> [[a]]
var permutationsWithRepetition = function (n, as) {
return as.length > 0 ? (
foldl1(curry(cartesianProduct)(as), replicate(n, as))
) : [];
};

// cartesianProduct :: [a] -> [b] -> [[a, b]]
var cartesianProduct = function (xs, ys) {
return [].concat.apply([], xs.map(function (x) {
return [].concat.apply([], ys.map(function (y) {
return [
[x].concat(y)
];
}));
}));
};

// curry :: ((a, b) -> c) -> a -> b -> c
var curry = function (f) {
return function (a) {
return function (b) {
return f(a, b);
};
};
};

// foldl1 :: (a -> a -> a) -> [a] -> a
var foldl1 = function (f, xs) {
return xs.length > 0 ? xs.slice(1)
.reduce(f, xs[0]) : [];
};

// replicate :: Int -> a -> [a]
var replicate = function (n, a) {
var v = [a],
o = [];
if (n < 1) return o;
while (n > 1) {
if (n & 1) o = o.concat(v);
n >>= 1;
v = v.concat(v);
}
return o.concat(v);
};

// group :: Eq a => [a] -> [[a]]
var group = function (xs) {
return groupBy(function (a, b) {
return a === b;
}, xs);
};

// groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
var groupBy = function (f, xs) {
var dct = xs.slice(1)
.reduce(function (a, x) {
var h = a.active.length > 0 ? a.active[0] : undefined,
blnGroup = h !== undefined && f(h, x);

return {
active: blnGroup ? a.active.concat(x) : [x],
sofar: blnGroup ? a.sofar : a.sofar.concat([a.active])
};
}, {
active: xs.length > 0 ? [xs[0]] : [],
sofar: []
});
return dct.sofar.concat(dct.active.length > 0 ? [dct.active] : []);
};

// sort :: Ord a => [a] -> [a]
var sort = function (xs) {
return xs.sort();
};

// sortBy :: (a -> a -> Ordering) -> [a] -> [a]
var sortBy = function (f, xs) {
return xs.sort(f);
};

// nub :: [a] -> [a]
var nub = function (xs) {
return nubBy(function (a, b) {
return a === b;
}, xs);
};

// nubBy :: (a -> a -> Bool) -> [a] -> [a]
var nubBy = function (p, xs) {
var x = xs.length ? xs[0] : undefined;

return x !== undefined ? [x].concat(nubBy(p, xs.slice(1)
.filter(function (y) {
return !p(x, y);
}))) : [];
};

// find :: (a -> Bool) -> [a] -> Maybe a
var find = function (f, xs) {
for (var i = 0, lng = xs.length; i < lng; i++) {
if (f(xs[i], i)) return xs[i];
}
return undefined;
};

// SIGNED DIGIT SEQUENCES (mapped to sums and to strings)

// data Sign :: [ 0 | 1 | -1 ] = ( Unsigned | Plus | Minus )
// asSum :: [Sign] -> Int
var asSum = function (xs) {
var dct = xs.reduceRight(function (a, sign, i) {
var d = i + 1; // zero-based index to [1-9] positions
if (sign !== 0) {
// Sum increased, digits cleared
return {
digits: [],
n: a.n + sign * parseInt([d].concat(a.digits)
.join(''), 10)
};
} else return { // Digits extended, sum unchanged
digits: [d].concat(a.digits),
n: a.n
};
}, {
digits: [],
n: 0
});
return dct.n + (dct.digits.length > 0 ? (
parseInt(dct.digits.join(''), 10)
) : 0);
};

// data Sign :: [ 0 | 1 | -1 ] = ( Unsigned | Plus | Minus )
// asString :: [Sign] -> String
var asString = function (xs) {
var ns = xs.reduce(function (a, sign, i) {
var d = (i + 1)
.toString();
return sign === 0 ? a + d : a + (sign > 0 ? ' +' : ' -') + d;
}, '');

return ns[0] === '+' ? ns.slice(1) : ns;
};

// unlines :: [String] -> String
var unlines = function (xs) {
return xs.join('\n');
};

// show :: a -> String
var show = function (x) {
return JSON.stringify(x);
}; //, null, 2);

// head :: [a] -> a
var head = function (xs) {
return xs.length ? xs[0] : undefined;
};

// SUM T0 100 ------------------------------------------------------------

// universe :: [[Sign]]
var universe = permutationsWithRepetition(9, [0, 1, -1])
.filter(function (x) {
return x[0] !== 1;
});

// allNonNegativeSums :: [Int]
var allNonNegativeSums = sort(universe.map(asSum)
.filter(function (x) {
return x >= 0;
}));

var checkProblem = function (xs) {
var sum = function (ns) {
return ns.split(' ')
.reduce(function (a, x) {
var s = x.trim();
return a + (isNaN(s) || s.length < 1 ? 0 : parseInt(s, 10));
}, 0);
};
var s = asString(xs),
sn = sum(s),
n = asSum(xs);

return sn !== n;
};

// SUM TO 100 -----------------------------------------------------------

return [
"Sums to 100:\n", unlines(universe.filter(function (x) {
return asSum(x) === 100;
})
.map(asString)),

"\n\n10 commonest sums (sum, followed by number of routes to it):\n",
show(sortBy(function (a, b) {
var lngA = a.length,
lngB = b.length;

if (lngA > lngB) return -1;
return lngA < lngB ? 1 : 0;
}, group(allNonNegativeSums))
.slice(0, 10)
.map(function (xs) {
return [xs[0], xs.length];
})),

"\n\nFirst positive integer not expressible as a sum of this kind:\n",
show(find(function (x, i) {
return x !== i;
}, sortBy(function (a, b) {
if (a < b) return -1;
return a > b ? 1 : 0;
}, nub(allNonNegativeSums))) - 1) // i is the the zero-based Array index
].join('\n') + '\n';
})();</lang>

{{Out}}
(Run in Atom editor, through Script package)
<pre>Sums to 100:

123 +45 -67 +8 -9
123 +4 -5 +67 -89
123 -45 -67 +89
123 -4 -5 -6 -7 +8 -9
12 +3 +4 +5 -6 -7 +89
12 +3 -4 +5 +67 +8 +9
12 -3 -4 +5 -6 +7 +89
1 +23 -4 +56 +7 +8 +9
1 +23 -4 +5 +6 +78 -9
1 +2 +34 -5 +67 -8 +9
1 +2 +3 -4 +5 +6 +78 +9
-1 +2 -3 +4 +5 +6 +78 +9


10 commonest sums (sum, followed by number of routes to it):

[[9,46],[27,44],[1,43],[15,43],[21,43],[45,42],[3,41],[5,40],[17,39],[7,39]]


First positive integer not expressible as a sum of this kind:

211

[Finished in 0.386s]</pre>

===ES6===
{{Trans|Haskell}}
<lang JavaScript>(() => {
<lang JavaScript>(() => {
'use strict';
'use strict';

Revision as of 21:08, 4 January 2017

Sum to 100 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

Find solutions to the   sum to one hundred   puzzle.


Add (insert) the mathematical operators     +   or   ─     (plus or minus)   before any of the digits in the
decimal numeric string   123456789   such that the resulting mathematical expression adds up to a
particular sum   (in this iconic case,   100).


Example: 

           123 + 4 - 5 + 67 - 89   =   100

Show all output here.


  •   Show all solutions that sum to   100
  •   Show the sum that has the maximum   number   of solutions   (from zero to infinity*)
  •   Show the lowest positive sum that   can't   be expressed   (has no solutions), using the rules for this task


An example of a sum that can't be expressed (within the rules of this task) is:   5074
which, of course, is not the lowest positive sum that can't be expressed.


*   (where   infinity   would be a relatively small   123,456,789)


Haskell

<lang Haskell>import Control.Monad (replicateM) import Control.Arrow ((&&&)) import Data.Char (intToDigit) import Data.List (nub, group, sort, sortBy, find, intercalate) import Data.Function (on)

data Sign 

 = Unsigned
 | Plus
 | Minus
 deriving (Eq, Show)

universe :: (Int, Sign) universe = 

 zip [1 .. 9] <$>
 filter ((/= Plus) . head) (replicateM 9 [Unsigned, Plus, Minus])

allNonNegativeSums :: [Int] allNonNegativeSums = sort $ filter (>= 0) (asSum <$> universe)

asSum :: [(Int, Sign)] -> Int asSum xs = 

 n +
 (if null s
    then 0
    else read s :: Int)
 where
   (n, s) = foldr readSign (0, []) xs
   readSign :: (Int, Sign) -> (Int, String) -> (Int, String)
   readSign (i, x) (n, s)
     | x == Unsigned = (n, intToDigit i : s)
     | otherwise =
       ( (if x == Plus
            then (+)
            else (-))
           n
           (read (show i ++ s) :: Int)
       , [])

asString :: [(Int, Sign)] -> String asString = foldr signedDigit [] 

 where
   signedDigit (i, x) s
     | x == Unsigned = intToDigit i : s
     | otherwise =
       (if x == Plus
          then " +"
          else " -") ++
       [intToDigit i] ++ s

main :: IO () main = 

 mapM_
   putStrLn
   [ "Sums to 100:\n"
   , unlines $ asString <$> filter ((== 100) . asSum) universe
   
   , "\n10 commonest sums (sum, followed by number of routes to it):\n"
   , show
       ((head &&& length) <$>
        take 10 (sortBy (on (flip compare) length) (group allNonNegativeSums)))
        
   , "\n\nFirst positive integer not expressible as a sum of this kind:\n"
   , maybeReport (find (uncurry (/=)) (zip [0 ..] (nub allNonNegativeSums)))
   ]
 where
   maybeReport
     :: Show a
     => Maybe (a, b) -> String
   maybeReport (Just (x, _)) = show x
   maybeReport _ = "No gaps found"</lang>
Output:

(Run in Atom editor, through Script package) 

Sums to 100:

123 +45 -67 +8 -9
123 +4 -5 +67 -89
123 -45 -67 +89
123 -4 -5 -6 -7 +8 -9
12 +3 +4 +5 -6 -7 +89
12 +3 -4 +5 +67 +8 +9
12 -3 -4 +5 -6 +7 +89
1 +23 -4 +56 +7 +8 +9
1 +23 -4 +5 +6 +78 -9
1 +2 +34 -5 +67 -8 +9
1 +2 +3 -4 +5 +6 +78 +9
 -1 +2 -3 +4 +5 +6 +78 +9


10 commonest sums (sum, followed by number of routes to it):

[(9,46),(27,44),(1,43),(15,43),(21,43),(45,42),(3,41),(5,40),(7,39),(17,39)]


First positive integer not expressible as a sum of this kind:

211

[Finished in 1.181s]


JavaScript

Translation of: Haskell

ES5

Translation of: Haskell

<lang JavaScript>(function () { 

   'use strict';

   // GENERIC FUNCTIONS ----------------------------------------------------

   // permutationsWithRepetition :: Int -> [a] -> a
   var permutationsWithRepetition = function (n, as) {
       return as.length > 0 ? (
           foldl1(curry(cartesianProduct)(as), replicate(n, as))
       ) : [];
   };

   // cartesianProduct :: [a] -> [b] -> a, b
   var cartesianProduct = function (xs, ys) {
       return [].concat.apply([], xs.map(function (x) {
           return [].concat.apply([], ys.map(function (y) {
               return [
                   [x].concat(y)
               ];
           }));
       }));
   };

   // curry :: ((a, b) -> c) -> a -> b -> c
   var curry = function (f) {
       return function (a) {
           return function (b) {
               return f(a, b);
           };
       };
   };

   // foldl1 :: (a -> a -> a) -> [a] -> a
   var foldl1 = function (f, xs) {
       return xs.length > 0 ? xs.slice(1)
           .reduce(f, xs[0]) : [];
   };

   // replicate :: Int -> a -> [a]
   var replicate = function (n, a) {
       var v = [a],
           o = [];
       if (n < 1) return o;
       while (n > 1) {
           if (n & 1) o = o.concat(v);
           n >>= 1;
           v = v.concat(v);
       }
       return o.concat(v);
   };

   // group :: Eq a => [a] -> a
   var group = function (xs) {
       return groupBy(function (a, b) {
           return a === b;
       }, xs);
   };

   // groupBy :: (a -> a -> Bool) -> [a] -> a
   var groupBy = function (f, xs) {
       var dct = xs.slice(1)
           .reduce(function (a, x) {
               var h = a.active.length > 0 ? a.active[0] : undefined,
                   blnGroup = h !== undefined && f(h, x);

               return {
                   active: blnGroup ? a.active.concat(x) : [x],
                   sofar: blnGroup ? a.sofar : a.sofar.concat([a.active])
               };
           }, {
               active: xs.length > 0 ? [xs[0]] : [],
               sofar: []
           });
       return dct.sofar.concat(dct.active.length > 0 ? [dct.active] : []);
   };

   // sort :: Ord a => [a] -> [a]
   var sort = function (xs) {
       return xs.sort();
   };

   // sortBy :: (a -> a -> Ordering) -> [a] -> [a]
   var sortBy = function (f, xs) {
       return xs.sort(f);
   };

   // nub :: [a] -> [a]
   var nub = function (xs) {
       return nubBy(function (a, b) {
           return a === b;
       }, xs);
   };

   // nubBy :: (a -> a -> Bool) -> [a] -> [a]
   var nubBy = function (p, xs) {
       var x = xs.length ? xs[0] : undefined;

       return x !== undefined ? [x].concat(nubBy(p, xs.slice(1)
           .filter(function (y) {
               return !p(x, y);
           }))) : [];
   };

   // find :: (a -> Bool) -> [a] -> Maybe a
   var find = function (f, xs) {
       for (var i = 0, lng = xs.length; i < lng; i++) {
           if (f(xs[i], i)) return xs[i];
       }
       return undefined;
   };

   // SIGNED DIGIT SEQUENCES  (mapped to sums and to strings)

   // data Sign :: [ 0 | 1 | -1 ] = ( Unsigned | Plus | Minus )
   // asSum :: [Sign] -> Int
   var asSum = function (xs) {
       var dct = xs.reduceRight(function (a, sign, i) {
           var d = i + 1; //  zero-based index to [1-9] positions
           if (sign !== 0) {
               // Sum increased, digits cleared
               return {
                   digits: [],
                   n: a.n + sign * parseInt([d].concat(a.digits)
                       .join(), 10)
               };
           } else return { // Digits extended, sum unchanged
               digits: [d].concat(a.digits),
               n: a.n
           };
       }, {
           digits: [],
           n: 0
       });
       return dct.n + (dct.digits.length > 0 ? (
           parseInt(dct.digits.join(), 10)
       ) : 0);
   };

   // data Sign :: [ 0 | 1 | -1 ] = ( Unsigned | Plus | Minus )
   // asString :: [Sign] -> String
   var asString = function (xs) {
       var ns = xs.reduce(function (a, sign, i) {
           var d = (i + 1)
               .toString();
           return sign === 0 ? a + d : a + (sign > 0 ? ' +' : ' -') + d;
       }, );

       return ns[0] === '+' ? ns.slice(1) : ns;
   };

   // unlines :: [String] -> String
   var unlines = function (xs) {
       return xs.join('\n');
   };

   // show :: a -> String
   var show = function (x) {
       return JSON.stringify(x);
   }; //, null, 2);

   // head :: [a] -> a
   var head = function (xs) {
       return xs.length ? xs[0] : undefined;
   };

   // SUM T0 100 ------------------------------------------------------------

   // universe :: Sign
   var universe = permutationsWithRepetition(9, [0, 1, -1])
       .filter(function (x) {
           return x[0] !== 1;
       });

   // allNonNegativeSums :: [Int]
   var allNonNegativeSums = sort(universe.map(asSum)
       .filter(function (x) {
           return x >= 0;
       }));

   var checkProblem = function (xs) {
       var sum = function (ns) {
           return ns.split(' ')
               .reduce(function (a, x) {
                   var s = x.trim();
                   return a + (isNaN(s) || s.length < 1 ? 0 : parseInt(s, 10));
               }, 0);
       };
       var s = asString(xs),
           sn = sum(s),
           n = asSum(xs);

       return sn !== n;
   };

   // SUM TO 100 -----------------------------------------------------------

   return [
       "Sums to 100:\n", unlines(universe.filter(function (x) {
               return asSum(x) === 100;
           })
           .map(asString)),

       "\n\n10 commonest sums (sum, followed by number of routes to it):\n",
       show(sortBy(function (a, b) {
               var lngA = a.length,
                   lngB = b.length;

               if (lngA > lngB) return -1;
               return lngA < lngB ? 1 : 0;
           }, group(allNonNegativeSums))
           .slice(0, 10)
           .map(function (xs) {
               return [xs[0], xs.length];
           })),

       "\n\nFirst positive integer not expressible as a sum of this kind:\n",
       show(find(function (x, i) {
           return x !== i;
       }, sortBy(function (a, b) {
           if (a < b) return -1;
           return a > b ? 1 : 0;
       }, nub(allNonNegativeSums))) - 1) // i is the the zero-based Array index
   ].join('\n') + '\n';

})();</lang>

Output:

(Run in Atom editor, through Script package) 

Sums to 100:

123 +45 -67 +8 -9
123 +4 -5 +67 -89
123 -45 -67 +89
123 -4 -5 -6 -7 +8 -9
12 +3 +4 +5 -6 -7 +89
12 +3 -4 +5 +67 +8 +9
12 -3 -4 +5 -6 +7 +89
1 +23 -4 +56 +7 +8 +9
1 +23 -4 +5 +6 +78 -9
1 +2 +34 -5 +67 -8 +9
1 +2 +3 -4 +5 +6 +78 +9
 -1 +2 -3 +4 +5 +6 +78 +9


10 commonest sums (sum, followed by number of routes to it):

[[9,46],[27,44],[1,43],[15,43],[21,43],[45,42],[3,41],[5,40],[17,39],[7,39]]


First positive integer not expressible as a sum of this kind:

211

[Finished in 0.386s]

ES6

Translation of: Haskell

<lang JavaScript>(() => { 

   'use strict';

   // GENERIC FUNCTIONS ----------------------------------------------------

   // permutationsWithRepetition :: Int -> [a] -> a
   const permutationsWithRepetition = (n, as) =>
       as.length > 0 ? (
           foldl1(curry(cartesianProduct)(as), replicate(n, as))
       ) : [];

   // cartesianProduct :: [a] -> [b] -> a, b
   const cartesianProduct = (xs, ys) =>
       [].concat.apply([], xs.map(x =>
       [].concat.apply([], ys.map(y => [[x].concat(y)]))));

   // curry :: ((a, b) -> c) -> a -> b -> c
   const curry = f => a => b => f(a, b);

   // foldl1 :: (a -> a -> a) -> [a] -> a
   const foldl1 = (f, xs) =>
       xs.length > 0 ? xs.slice(1)
       .reduce(f, xs[0]) : [];

   // replicate :: Int -> a -> [a]
   const replicate = (n, a) => {
       let v = [a],
           o = [];
       if (n < 1) return o;
       while (n > 1) {
           if (n & 1) o = o.concat(v);
           n >>= 1;
           v = v.concat(v);
       }
       return o.concat(v);
   };

   // group :: Eq a => [a] -> a
   const group = xs => groupBy((a, b) => a === b, xs);

   // groupBy :: (a -> a -> Bool) -> [a] -> a
   const groupBy = (f, xs) => {
       const dct = xs.slice(1)
           .reduce((a, x) => {
               const
                   h = a.active.length > 0 ? a.active[0] : undefined,
                   blnGroup = h !== undefined && f(h, x);

               return {
                   active: blnGroup ? a.active.concat(x) : [x],
                   sofar: blnGroup ? a.sofar : a.sofar.concat([a.active])
               };
           }, {
               active: xs.length > 0 ? [xs[0]] : [],
               sofar: []
           });
       return dct.sofar.concat(dct.active.length > 0 ? [dct.active] : []);
   };

   // sort :: Ord a => [a] -> [a]
   const sort = xs => xs.sort();

   // sortBy :: (a -> a -> Ordering) -> [a] -> [a]
   const sortBy = (f, xs) => xs.sort(f);

   // nub :: [a] -> [a]
   const nub = xs => nubBy((a, b) => a === b, xs);

   // nubBy :: (a -> a -> Bool) -> [a] -> [a]
   const nubBy = (p, xs) => {
       const x = xs.length ? xs[0] : undefined;

       return x !== undefined ? [x].concat(
           nubBy(p, xs.slice(1)
               .filter(y => !p(x, y)))
       ) : [];
   };

   // find :: (a -> Bool) -> [a] -> Maybe a
   const find = (f, xs) => {
       for (var i = 0, lng = xs.length; i < lng; i++) {
           if (f(xs[i], i)) return xs[i];
       }
       return undefined;
   }



   // SIGNED DIGIT SEQUENCES  (mapped to sums and to strings)

   // data Sign :: [ 0 | 1 | -1 ] = ( Unsigned | Plus | Minus )
   // asSum :: [Sign] -> Int
   const asSum = xs => {
       const dct = xs.reduceRight((a, sign, i) => {
           const d = i + 1; //  zero-based index to [1-9] positions
           if (sign !== 0) { // Sum increased, digits cleared
               return {
                   digits: [],
                   n: a.n + (sign * parseInt([d].concat(a.digits)
                       .join(), 10))
               };
           } else return { // Digits extended, sum unchanged
               digits: [d].concat(a.digits),
               n: a.n
           };
       }, {
           digits: [],
           n: 0
       });
       return dct.n + (dct.digits.length > 0 ? (
           parseInt(dct.digits.join(), 10)
       ) : 0);
   };

   // data Sign :: [ 0 | 1 | -1 ] = ( Unsigned | Plus | Minus )
   // asString :: [Sign] -> String
   const asString = xs => {
       const ns = xs.reduce((a, sign, i) => {
           const d = (i + 1)
               .toString();
           return (sign === 0 ? (
               a + d
           ) : (a + (sign > 0 ? ' +' : ' -') + d));
       }, );

       return ns[0] === '+' ? ns.slice(1) : ns;
   };

   // unlines :: [String] -> String
   const unlines = xs => xs.join('\n');

   // show :: a -> String
   const show = x => JSON.stringify(x); //, null, 2);

   // head :: [a] -> a
   const head = xs => xs.length ? xs[0] : undefined;

   // SUM T0 100 ------------------------------------------------------------

   // universe :: Sign
   const universe = permutationsWithRepetition(9, [0, 1, -1])
       .filter(x => x[0] !== 1);

   // allNonNegativeSums :: [Int]
   const allNonNegativeSums = sort(universe.map(asSum)
       .filter(x => x >= 0));

   const checkProblem = (xs) => {
       const sum = ns => ns.split(' ')
           .reduce((a, x) => {
               const s = x.trim();
               return a + (isNaN(s) || s.length < 1 ? 0 : parseInt(s, 10))
           }, 0);
       const
           s = asString(xs),
           sn = sum(s),
           n = asSum(xs);

       return sn !== n;
   }



   // SUM TO 100 -----------------------------------------------------------

   return [
       "Sums to 100:\n",
       unlines(universe.filter(x => asSum(x) === 100)
           .map(asString)),

       "\n\n10 commonest sums (sum, followed by number of routes to it):\n",
       show(sortBy((a, b) => {
               const
                   lngA = a.length,
                   lngB = b.length;

               if (lngA > lngB) return -1;
               return lngA < lngB ? 1 : 0;
           }, group(allNonNegativeSums))
           .slice(0, 10)
           .map(xs => [xs[0], xs.length])),

       "\n\nFirst positive integer not expressible as a sum of this kind:\n",
       show(find(
           (x, i) => x !== i,
           sortBy((a, b) => {
               if (a < b) return -1;
               return a > b ? 1 : 0;
           }, nub(allNonNegativeSums))
       ) - 1) // i is the the zero-based Array index.
   ].join('\n') + '\n';

})();</lang>

Output:

(Run in Atom editor, through Script package) 

Sums to 100:

123 +45 -67 +8 -9
123 +4 -5 +67 -89
123 -45 -67 +89
123 -4 -5 -6 -7 +8 -9
12 +3 +4 +5 -6 -7 +89
12 +3 -4 +5 +67 +8 +9
12 -3 -4 +5 -6 +7 +89
1 +23 -4 +56 +7 +8 +9
1 +23 -4 +5 +6 +78 -9
1 +2 +34 -5 +67 -8 +9
1 +2 +3 -4 +5 +6 +78 +9
 -1 +2 -3 +4 +5 +6 +78 +9


10 commonest sums (sum, followed by number of routes to it):

[[9,46],[27,44],[1,43],[15,43],[21,43],[45,42],[3,41],[5,40],[17,39],[7,39]]


First positive integer not expressible as a sum of this kind:

211

[Finished in 0.361s]

Perl 6

Works with: Rakudo version 2016.12

<lang perl6>my @ops = ['-', ], |( [' + ', ' - ', ] xx 8 ); my @str = [X~] map { .Slip }, ( @ops Z 1..9 ); my %sol = @str.classify: *.subst( ' - ', ' -', :g )\ 

                         .subst( ' + ',  ' ', :g ).words.sum;

my %count.push: %sol.map({ .value.elems => .key });

my $max_solutions = %count.max( + *.key ); my $first_unsolvable = first { %sol{$_} :!exists }, 1..*; my @two_largest_sums = %sol.keys.sort(-*)[^2];

given %sol{100}:p { 

   say "{.value.elems} solutions for sum {.key}:";
   say "    $_" for .value.list;

}

say .perl for :$max_solutions, :$first_unsolvable, :@two_largest_sums;</lang>

Output:
12 solutions for sum 100:
    -1 + 2 - 3 + 4 + 5 + 6 + 78 + 9
    1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
    1 + 2 + 34 - 5 + 67 - 8 + 9
    1 + 23 - 4 + 5 + 6 + 78 - 9
    1 + 23 - 4 + 56 + 7 + 8 + 9
    12 + 3 + 4 + 5 - 6 - 7 + 89
    12 + 3 - 4 + 5 + 67 + 8 + 9
    12 - 3 - 4 + 5 - 6 + 7 + 89
    123 + 4 - 5 + 67 - 89
    123 + 45 - 67 + 8 - 9
    123 - 4 - 5 - 6 - 7 + 8 - 9
    123 - 45 - 67 + 89
:max_solutions("46" => $["9", "-9"])
:first_unsolvable(211)
:two_largest_sums(["123456789", "23456790"])

REXX

<lang rexx>/*REXX pgm solves a puzzle: using the string 123456789, insert - or + to sum to 100*/ parse arg LO HI . /*obtain optional arguments from the CL*/ if LO== | LO=="," then LO=100 /*Not specified? Then use the default.*/ if HI== | HI=="," then HI=LO /* " " " " " " */ if LO=00 then HI=123456789 /*LOW specified as zero with leading 0s*/ ops= '+-'; sol="solution"; L=length(ops) + 1 /*define operators (and their length). */ @.=; do i=1 to L-1; @.i=substr(ops,i,1) /* " some handy-dandy REXX literals*/ 

           end   /*i*/                          /*   "   individual operators for speed*/

mx=0; mn=999999; mxL=; mnL= /*initialize some minimums and maximums*/ tell= (LO==HI); do j=LO to HI until LO==00 & mn==0 /*solve with a range of sums*/ 

                  z=solve(j);  y=z;  if y==0  then y='no'  /*find # solutionson for  J.*/
                  if tell   then say y sol ||s(y) 'found.' /*Not a range?  Show number.*/
                  if z> mx  then mxL=                      /*see if this is a new max. */
                  if z>=mx  then do; mxL=mxL j; mx=z; end  /*remember this new maximum.*/
                  if z< mn  then mnL=                      /*see if this is a new min. */
                  if z<=mn  then do; mnL=mnL j; mn=z; end  /*remember this new minimum.*/
                  end   /*j*/

if tell then exit /*should we show max and min*/ @@= 'number of solutions: ' _=words(mxL); say 'sum's(_) "of" mxL ' 's(_,"have",'has') 'the maximum' @@ mx _=words(mnL); say 'sum's(_) "of" mnL ' 's(_,"have",'has') 'the minimum' @@ mn exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ s: if arg(1)==1 then return arg(3); return word(arg(2) "s",1) /*simple pluralizer*/ /*──────────────────────────────────────────────────────────────────────────────────────*/ solve: parse arg answer; #=0 /*obtain the answer (sum) to the puzzle*/ 

         do a=L-1  to L;        aa=      @.a'1' /*choose one  of  ─       or  nothing. */
          do b=1  for L;        bb=aa || @.b'2' /*   "    "    "  ─   +,  or  abutment.*/
           do c=1  for L;       cc=bb || @.c'3' /*   "    "    "  "   "    "      "    */
            do d=1  for L;      dd=cc || @.d'4' /*   "    "    "  "   "    "      "    */
             do e=1  for L;     ee=dd || @.e'5' /*   "    "    "  "   "    "      "    */
              do f=1  for L;    ff=ee || @.f'6' /*   "    "    "  "   "    "      "    */
               do g=1  for L;   gg=ff || @.g'7' /*   "    "    "  "   "    "      "    */
                do h=1  for L;  hh=gg || @.h'8' /*   "    "    "  "   "    "      "    */
                 do i=1  for L; ii=hh || @.i'9' /*   "    "    "  "   "    "      "    */
                 interpret '$=' ii              /*calculate the sum of modified string.*/
                 if $\==answer  then iterate    /*Is sum not equal to answer? Then skip*/
                 #=#+1;         if tell  then say  'solution: '     $     " ◄───► "    ii
                 end   /*i*/
                end    /*h*/
               end     /*g*/
              end      /*f*/
             end       /*e*/
            end        /*d*/
           end         /*c*/
          end          /*b*/
         end           /*a*/    ;   return #    /*return the number of solutions found.*/</lang>

output   when the default input is used: 

solution:  100  ◄───►  -1+2-3+4+5+6+78+9
solution:  100  ◄───►  1+2+3-4+5+6+78+9
solution:  100  ◄───►  1+2+34-5+67-8+9
solution:  100  ◄───►  1+23-4+5+6+78-9
solution:  100  ◄───►  1+23-4+56+7+8+9
solution:  100  ◄───►  12+3+4+5-6-7+89
solution:  100  ◄───►  12+3-4+5+67+8+9
solution:  100  ◄───►  12-3-4+5-6+7+89
solution:  100  ◄───►  123+4-5+67-89
solution:  100  ◄───►  123+45-67+8-9
solution:  100  ◄───►  123-4-5-6-7+8-9
solution:  100  ◄───►  123-45-67+89
12 solutions found.

output   when the following input is used:   00 

sum of  9  has the maximum number of solutions:  46
sum of  211  has the minimum number of solutions:  0

For those that are interested, the 46 solutions (for the sum of 9) are: 

solution:  9  ◄───►  -1+2+3+4+5+6+7-8-9
solution:  9  ◄───►  -1+2+3-4+5-6-7+8+9
solution:  9  ◄───►  -1+2+3-4-5+6+7-8+9
solution:  9  ◄───►  -1+2+3-45+67-8-9
solution:  9  ◄───►  -1+2+34+56+7-89
solution:  9  ◄───►  -1+2-3+4+5-6+7-8+9
solution:  9  ◄───►  -1+2-3+4-5+6+7+8-9
solution:  9  ◄───►  -1+23+4+5+67-89
solution:  9  ◄───►  -1+23+4-5-6-7-8+9
solution:  9  ◄───►  -1+23-4+5-6-7+8-9
solution:  9  ◄───►  -1+23-4-5+6+7-8-9
solution:  9  ◄───►  -1-2+3+4+5+6-7-8+9
solution:  9  ◄───►  -1-2+3+4+5-6+7+8-9
solution:  9  ◄───►  -1-2+3-4-5-6+7+8+9
solution:  9  ◄───►  -1-2+3-4-56+78-9
solution:  9  ◄───►  -1-2-3+4-5+6-7+8+9
solution:  9  ◄───►  -1-2-3+45-6-7-8-9
solution:  9  ◄───►  -1-2-3-4+5+6+7-8+9
solution:  9  ◄───►  -1-2-34+56+7-8-9
solution:  9  ◄───►  -1-23+45-6-7-8+9
solution:  9  ◄───►  -12+3-45-6+78-9
solution:  9  ◄───►  -12+34+5+6-7-8-9
solution:  9  ◄───►  -12+34+56-78+9
solution:  9  ◄───►  -12-34+5+67-8-9
solution:  9  ◄───►  1+2+3+4-5-6-7+8+9
solution:  9  ◄───►  1+2+3-4+5-6+7-8+9
solution:  9  ◄───►  1+2+3-4-5+6+7+8-9
solution:  9  ◄───►  1+2-3+4+5+6-7-8+9
solution:  9  ◄───►  1+2-3+4+5-6+7+8-9
solution:  9  ◄───►  1+2-3-4-5-6+7+8+9
solution:  9  ◄───►  1+2-3-4-56+78-9
solution:  9  ◄───►  1+2-34-56+7+89
solution:  9  ◄───►  1+23+4-5-6-7+8-9
solution:  9  ◄───►  1+23-4+5-6+7-8-9
solution:  9  ◄───►  1+23-45+6+7+8+9
solution:  9  ◄───►  1-2+3+4+5+6-7+8-9
solution:  9  ◄───►  1-2+3-4-5+6-7+8+9
solution:  9  ◄───►  1-2-3+4+5-6-7+8+9
solution:  9  ◄───►  1-2-3+4-5+6+7-8+9
solution:  9  ◄───►  1-2-3-4+5+6+7+8-9
solution:  9  ◄───►  1-2-3-4-5-67+89
solution:  9  ◄───►  1-23+4+5-67+89
solution:  9  ◄───►  1-23+45-6-7+8-9
solution:  9  ◄───►  1-23-4+5+6+7+8+9
solution:  9  ◄───►  1-23-45-6-7+89
solution:  9  ◄───►  12-34-56+78+9
46 solutions found.

zkl

Taking a big clue from Haskell and just calculate the world. <lang zkl>var all = // ( (1,12,123...-1,-12,...), (2,23,...) ...) 

  (9).pump(List,fcn(n){ split("123456789"[n,*]) })       // 45
  .apply(fcn(ns){ ns.extend(ns.copy().apply('*(-1))) }); // 90

fcn calcAllSums{ // calculate all 6572 sums (1715 unique) 

  fcn(n,sum,soFar,r){
     if(n==9) return();
     foreach b in (all[n]){

if(sum+b>=0 and b.abs()%10==9) r.appendV(sum+b,"%s%+d".fmt(soFar,b)); self.fcn(b.abs()%10,sum + b,"%s%+d".fmt(soFar,b),r); 

     }
  }(0,0,"",r:=Dictionary());
  r

} 

   // "123" --> (1,12,123)

fcn split(nstr){ (1).pump(nstr.len(),List,nstr.get.fp(0),"toInt") }</lang> <lang zkl>fcn showSums(allSums,N=100,printSolutions=2){ 

  slns:=allSums.find(N,T);
  if(printSolutions)    println("%d solutions for N=%d".fmt(slns.len(),N));
  if(printSolutions==2) println(slns.concat("\n"));
  println();

}

allSums:=calcAllSums(); showSums(allSums); showSums(allSums,0,1);

println("Smallest postive integer with no solution: ", 

  [1..].filter1('wrap(n){ Void==allSums.find(n) }));

println("5 commonest sums (sum, number of ways to calculate to it):"); ms:=allSums.values.apply("len").sort()[-5,*]; // 5 mostest sums allSums.pump(List, // get those pairs 

  'wrap([(k,v)]){ v=v.len(); ms.holds(v) and T(k.toInt(),v) or Void.Skip })

.sort(fcn(kv1,kv2){ kv1[1]>kv2[1] }) // and sort .println();</lang>

Output:
12 solutions for N=100
+1+2+3-4+5+6+78+9
+1+2+34-5+67-8+9
+1+23-4+5+6+78-9
+1+23-4+56+7+8+9
+12+3+4+5-6-7+89
+12+3-4+5+67+8+9
+12-3-4+5-6+7+89
+123+4-5+67-89
+123+45-67+8-9
+123-4-5-6-7+8-9
+123-45-67+89
-1+2-3+4+5+6+78+9

22 solutions for N=0

Smallest postive integer with no solution: 211

5 commonest sums (sum, number of ways to calculate to it):
L(L(9,46),L(27,44),L(15,43),L(1,43),L(21,43))
Retrieved from "https://rosettacode.org/wiki/Sum_to_100?oldid=273492"